Submission #1227643

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
int MX=100000;
int N,M;
ll o[1000][1000];
ll inf = 1e13;
vector<ll> getnext(vector<ll> a){
	int N = a.size();
	vector<ll> b(N);
	rep(i,N) b[i]=a[i];
	rep(i,N-1) b[i+1]+=b[i];
	return b;
}
ll need(vector<ll> a,vector<ll> b){	//need b++
	if(a[0]<b[0]) return -inf;
	assert(a[0]==b[0]);
	int N = a.size();

	if(a>=b){
		ll nd = (a[1]-b[1]+b[0]-1)/b[0];
		if(a[1]<nd*b[0]+b[1]) return nd;
		assert(a[1]==nd*b[0]+b[1]);
		if(N==2) return nd+1;

		ll nb2 = b[2] + nd*b[1] + nd*(nd+1)/2*b[2];
		if(nb2>a[2]) return nd;

		//assert(nd<=10000)
		rep(t,10000000){
			if(a<b) return t;
			b = getnext(b);
		}
	}else{
		return -need(b,a);
	}
}
ll ns[1000];
ll solve(){
	cin>>N>>M;
	rep(i,N) rep(j,M) cin>>o[i][j];
	if(N==1){
		return 0;
	}
	rep(i,N-1) if(o[i][0]>o[i+1][0]){
		return -1;
	}
	if(M==1){
		rep(i,N-1) if(o[i][0]==o[i+1][0]){
			return -1;
		}
		return 0;
	}

	rep(i,N-1){
		vector<ll> a(M),b(M);
		rep(j,M) a[j]=o[i][j],b[j]=o[i+1][j];
		ns[i] = need(a,b);
//		show(ns[i]);
		assert(ns[i]!=inf);
	}

	ll ans = 0;
	ll prev = 0;
	rep(i,N-1){
		ll nd = ns[i] + prev;
		if(nd<0) nd=0;
		ans+=nd;
		prev=nd;
	}
	return ans;
}
int main(){
	cout<<solve()<<endl;
}

Submission Info

Judge Result