Submission #2277460

---

Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int lim = 1000000001;
int calc(vector<int> v1, vector<int> v2, bool flag_eq = false) {
	if(v1 < v2) return -calc(v2, v1, true) + 1;
	if((v1[1] - v2[1]) % v1[0] != 0) return (v1[1] - v2[1]) / v1[0] + 1;
	int ex = (v1[1] - v2[1]) / v1[0];
	int lp = v1.size();
	for(int i = 0; i < ex; i++) {
		int clp = lp;
		for(int j = 1; j < lp; j++) {
			v2[j] += v2[j - 1];
			if(v2[j] >= lim) {
				v2[j] = lim;
				if(clp == lp) clp = j;
			}
		}
		lp = clp;
		if(lp == 2) {
			v2[1] += ex - i - 1;
			break;
		}
	}
	if((!flag_eq && v1 < v2) || (flag_eq && v1 <= v2)) return ex;
	return ex + 1;
}
int N, M;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	vector<vector<int> > v(N, vector<int>(M));
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> v[i][j];
		}
	}
	if(M == 1) {
		bool f = true;
		for(int i = 1; i < N; i++) {
			if(v[i - 1][0] >= v[i][0]) f = false;
		}
		cout << (f ? 0 : -1) << endl;
	}
	else {
		bool f = true;
		for(int i = 1; i < N; i++) {
			if(v[i - 1][0] > v[i][0]) f = false;
		}
		if(!f) cout << -1 << endl;
		else {
			long long cur = 0, ret = 0;
			for(int i = 1; i < N; i++) {
				long long res = calc(v[i - 1], v[i]);
				cur = max(cur + res, 0LL);
				ret += cur;
			}
			cout << ret << endl;
		}
	}
	return 0;
}

Submission Info

Judge Result