Submission #1129031

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 INT;
struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
typedef vector<INT> V;
typedef vector<V> VV;

INT comb[114514][11];
const INT INF=1e12;
struct latte{
    latte(){
        for(int i=0;i<114514;i++)comb[i][0]=1;
        for(int i=1;i<114514;i++)
            for(int j=1;j<=min(i,10);j++)
                comb[i][j]=min(INF,comb[i-1][j]+comb[i-1][j-1]);
    }
}malta;

LL f(V a,V b){
    int m=b.size();
    LL cnt=0;
    while(a>b&&b.size()>10){
        cnt++;
        FOR(i,1,m)
            b[i]+=b[i-1];
        while(b.back()>INF)b.pop_back();
    }
    if(a<=b){
        return cnt;
    }
    LL k=(a[1]-b[1]+b[0]-1)/b[0];
    if(b[0]*k+b[1]>a[1])return cnt+k;
    if(k==0)return cnt+k+1;
    if(k>=114500)return cnt+k;
    for(int id=2;id<b.size();id++){
        LL sum=b[id];
        REP(i,id){
            sum+=min(INF,b[i]*comb[k+id-1][id-i]);
        }
        if(sum>a[id])return cnt+k;
        if(sum<a[id])return cnt+k+1;
    }
    return cnt+k;
}
LL g(V a,V b){
    int m=b.size();
    LL cnt=0;
    while(a>b&&b.size()>10){
        cnt++;
        FOR(i,1,m)
            b[i]+=b[i-1];
        while(b.back()>INF)b.pop_back();
    }
    if(a==b){
        return cnt;
    }
    if(a<b) return cnt-1;
    LL k=(a[1]-b[1]+b[0]-1)/b[0];
    if(b[0]*k+b[1]>a[1])return cnt+k-1;
    if(k==0)return cnt+k;
    if(k>=114514)return cnt+k-1;
    for(int id=2;id<b.size();id++){
        LL sum=b[id];
        REP(i,id){
            sum+=min(INF,b[i]*comb[k+id-1][id-i]);
        }
        if(sum>a[id])return cnt+k-1;
        if(sum<a[id])return cnt+k;
    }
    return cnt+k;
}

int main(){
    int N,M;
    cin>>N>>M;
    VV A(N,V(M));
    REP(i,N)REP(j,M){
        int a;
        cin>>a;
        A[i][j]=a;
    }
    vector<LL> B(N-1,0);
    REP(i,N-1){
        if(A[i][0]>A[i+1][0]){
            cout<<-1<<endl;
            return 0;
        }
        if(A[i]==A[i+1])B[i]=0;
        else if(A[i]>A[i+1])B[i]=f(A[i],A[i+1]);
        else B[i]=-g(A[i+1],A[i]);
        //       cout<<B[i]<<endl;
    }
    LL res=0,now=0;
    REP(i,N-1){
        now=max(0ll,now+B[i]);
        res+=now;
    }
    cout<<res<<endl;
    return 0;
}

Submission Info

Judge Result