Submission #1227659

---

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++
//	puts("-------------ned");
	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[0];
//		show(nd);
//		show(nb2);
		if(nb2>a[2]) return nd;

		//assert(nd<=10000)
		rep(t,10000000){
			if(a<b) return t;
			b = getnext(b);
		}
	}else{
		a.back()++;
		return 1-need(b,a);
	}
}
ll brute(){
	vector<ll> a(M),b(M);
	rep(i,M) a[i]=o[0][i];
	ll ans=0;
	rep(i,N-1){
		rep(j,M) b[j]=o[i+1][j];
		ll nd=-1;
		rep(t,100000){
			if(a<b){
				nd=t;
				break;
			}
			b=getnext(b);
		}
//		show(nd);
		if(nd==-1) return -1;
		ans+=nd;
		a=b;
	}
	return ans;
}
ll ns[1000];
ll br;
ll solve(){
	cin>>N>>M;
	rep(i,N) rep(j,M) cin>>o[i][j];
	// N=rand()%5+1,M=rand()%5+1;
	// int r0 = rand()%10+1;
	// rep(i,N){
	// 	o[i][0] = r0;
	// 	rep1(j,M-1) o[i][j] = rand()%10+1;
	// }
//	br = brute();
	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;
//		show(nd);
		ans+=nd;
		prev=nd;
	}
	return ans;
}
int main(){
	// srand((unsigned)time(NULL));
	// while(true){
	// 	ll slv = solve();
	// 	// show(slv);
	// 	// show(br);
	// 	if(br != slv){
	// 		puts("0-----");
	// 		cout<<N<<" "<<M<<endl;
	// 		rep(i,N){
	// 			rep(j,M) cout<<o[i][j]<<" ";
	// 			puts("");
	// 		}
	// 		assert(0);
	// 	}
	// 	puts("ok");
//		cout<<solve()<<endl;
//	}
	cout<<solve()<<endl;
}

Submission Info

Judge Result