Submission #1004985

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

template<typename T>T gcd(T x, T y) { if(y == 0)return x; else return gcd(y, x%y); }
int nCr_saturated(int n, int k, int infinity) {
	const int MaxK = 30;
	if(k > n) return 0;
	if(k > n / 2) k = n - k;
	if(k == 0) return 1;
	assert(0 <= k && k <= MaxK);
	int factors[MaxK];
	rep(i, k)
		factors[i] = n - i;
	rep(i, k) {
		int x = i + 1;
		rep(j, k) {
			int g = gcd(factors[j], x);
			factors[j] /= g;
			x /= g;
		}
		assert(x == 1);
	}
	int product = 1;
	rep(i, k) {
		long long P = (long long)product * factors[i];
		if(P >= infinity)
			return infinity;
		else
			product = (int)P;
	}
	return product;
}

vector<int> trans(const vector<int> &a, int t, bool naive = false) {
	assert(t >= 0);
	const int logT = 30;
	int M = (int)a.size();
	vector<int> res = a;
	if(t <= logT || naive) {
		rep(k, t) {
			rep(i, M - 1)
				amin((res[i + 1] += res[i]), INF);
		}
	} else {
		int X = min(logT, M);
		rep(i, X) {
			int sum = 0;
			for(int j = i; j >= 0; -- j) {
				int coeff = nCr_saturated((i - j) + t - 1, i - j, INF);
				long long S = sum + (long long)coeff * a[j];
				if(S > INF) {
					sum = INF;
					break;
				} else {
					sum = (int)S;
				}
			}
			res[i] = sum;
		}
		reu(i, X, M)
			res[i] = INF;
	}
	return res;
}

int solve(const vector<int> &a, const vector<int> &b) {
	int M = (int)a.size();
	if(b < a)
		return 0;
	if(b[0] > a[0])
		return INF;
	int t = (b[1] - a[1] + a[0] - 1) / a[0];
	vector<int> c = trans(a, t);
	return b < c ? t : t + 1;
}

int main() {
	int N; int M;
	while(~scanf("%d%d", &N, &M)) {
		vector<vector<int> > A(N, vector<int>(M));
		for(int i = 0; i < N; ++ i) for(int j = 0; j < M; ++ j)
			scanf("%d", &A[i][j]);
		if(M == 1) {
			bool ok = true;
			rep(i, N - 1)
				ok &= A[i][0] < A[i + 1][0];
			puts(ok ? "-1" : "0");
			continue;
		}
		vector<int> g(N - 1);
		bool ok = true;
		rep(i, N - 1) {
			int x = solve(A[i + 1], A[i]);
			if(x == INF) {
				ok = false;
				break;
			} else if(x > 0) {
				g[i] = x;
			} else {
				int y = solve(A[i], A[i + 1]);
				if(y > 0 && y < INF && trans(A[i], y - 1) == A[i + 1])
					-- y;
				g[i] = -y + 1;
			}
		}
		if(!ok) {
			puts("-1");
			continue;
		}
		ll ans = 0;
		ll curt = 0;
		rep(i, N - 1) {
			curt = max(curt + g[i], 0LL);
			ans += curt;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:89:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &A[i][j]);
                         ^

Judge Result