Submission #1129633


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[1145140][11];
const INT INF=1e15;
struct latte{
    latte(){
        for(int i=0;i<1145140;i++)comb[i][0]=1;
        for(int i=1;i<1145140;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,bool eq){
    int m=b.size();
    LL cnt=0;
    int ub=m;
    while(a>b){
        cnt++;
        FOR(i,1,m){
            b[i]+=b[i-1];
            chmin(b[i],INF);
            if(b[i]==INF)chmin(ub,i);
        }
        if(ub<10)break;
    }
    if(eq){
        if(a==b)return cnt+1;
        if(a<b)return cnt;
    }
    else{
        if(a==b)return -cnt+1;
        if(a<b)return -cnt+1;
    }
    LL k=(a[1]-b[1]+b[0]-1)/b[0];
    //if(k<0)return 0;
    if(b[0]*k+b[1]>a[1]){
        if(eq)
            return cnt+k;
        else{
            return -cnt-k+1;
        }
    }
    if(k==0){
        if(eq){
            return cnt+k+1;
        }
        else{
            return -cnt-k; 
        }
    }
   
    
    if(k>=1000000){
        if(eq)
            return cnt+k;
        else return -cnt-k+1;
    }
    for(int id=2;id<b.size();id++){
        INT sum=b[id];
        REP(i,id){
            sum+=min(INF,b[i]*comb[k+id-1][id-i]);
        }
        if(sum>a[id]){
            if(eq)
                return cnt+k;
            else
                return -cnt-k+1;
        }
        if(sum<a[id]){
            if(eq)return cnt+k+1;
            else return -cnt-k;
        }
    }
    if(eq){
        return cnt+k+1;
    }
    else{
        return -cnt-k+1;
    }
}


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;
    }
    if(M==1){
        int ans=0;
        REP(i,N-1)if(A[i]>=A[i+1])ans=-1;
        cout<<ans<<endl;
        return 0;
    }
    vector<LL> B(N-1,0);
    REP(i,N-1){
        if(A[i]==A[i+1])B[i]=1;
        else if(A[i]>A[i+1]){
            if(A[i][0]>A[i+1][0]){
                cout<<-1<<endl;
                return 0;
            }
            B[i]=f(A[i],A[i+1],true);
        }
        else {
            if(A[i][0]<A[i+1][0])B[i]=-INF;
            else 
                B[i]=f(A[i+1],A[i],false);
        }
        //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

Submission Time
Task B - Takahashi the Magician
User btk15049
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3126 Byte
Status WA
Exec Time 315 ms
Memory 212736 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 800 0 / 200
Status
AC × 3
AC × 23
WA × 4
AC × 34
WA × 1
AC × 68
WA × 4
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
Case Name Status Exec Time Memory
hack_1.txt AC 71 ms 197120 KB
hack_2.txt AC 71 ms 197120 KB
hack_3.txt AC 71 ms 197120 KB
hack_4.txt AC 71 ms 197120 KB
hack_5.txt WA 71 ms 197120 KB
sample_1.txt AC 71 ms 197120 KB
sample_2.txt AC 71 ms 197120 KB
sample_3.txt AC 71 ms 197120 KB
subtask_1_1.txt AC 72 ms 197120 KB
subtask_1_10.txt AC 71 ms 197120 KB
subtask_1_11.txt AC 174 ms 212736 KB
subtask_1_12.txt AC 71 ms 197120 KB
subtask_1_13.txt WA 72 ms 197120 KB
subtask_1_14.txt WA 72 ms 197120 KB
subtask_1_15.txt AC 178 ms 212736 KB
subtask_1_16.txt AC 176 ms 212736 KB
subtask_1_17.txt AC 177 ms 212736 KB
subtask_1_18.txt AC 179 ms 212736 KB
subtask_1_19.txt WA 72 ms 197120 KB
subtask_1_2.txt AC 72 ms 197120 KB
subtask_1_20.txt AC 72 ms 197120 KB
subtask_1_3.txt AC 72 ms 197120 KB
subtask_1_4.txt AC 71 ms 197120 KB
subtask_1_5.txt AC 72 ms 197120 KB
subtask_1_6.txt AC 72 ms 197248 KB
subtask_1_7.txt AC 72 ms 197248 KB
subtask_1_8.txt AC 175 ms 212736 KB
subtask_1_9.txt AC 108 ms 204928 KB
subtask_2_1.txt AC 78 ms 198656 KB
subtask_2_10.txt AC 84 ms 199936 KB
subtask_2_11.txt AC 140 ms 212736 KB
subtask_2_12.txt AC 149 ms 212736 KB
subtask_2_13.txt AC 142 ms 212736 KB
subtask_2_14.txt AC 149 ms 212736 KB
subtask_2_15.txt AC 72 ms 197120 KB
subtask_2_16.txt AC 139 ms 212736 KB
subtask_2_17.txt AC 139 ms 212736 KB
subtask_2_18.txt AC 315 ms 212736 KB
subtask_2_19.txt AC 72 ms 197120 KB
subtask_2_2.txt AC 139 ms 212736 KB
subtask_2_20.txt AC 71 ms 197120 KB
subtask_2_21.txt AC 71 ms 197120 KB
subtask_2_22.txt AC 71 ms 197120 KB
subtask_2_23.txt AC 72 ms 197120 KB
subtask_2_24.txt AC 71 ms 197120 KB
subtask_2_25.txt AC 71 ms 197120 KB
subtask_2_26.txt AC 72 ms 197120 KB
subtask_2_27.txt AC 71 ms 197120 KB
subtask_2_3.txt AC 140 ms 212736 KB
subtask_2_4.txt AC 105 ms 204928 KB
subtask_2_5.txt AC 148 ms 212736 KB
subtask_2_6.txt AC 140 ms 212736 KB
subtask_2_7.txt AC 100 ms 203392 KB
subtask_2_8.txt AC 77 ms 198016 KB
subtask_2_9.txt AC 87 ms 200704 KB
subtask_3_1.txt AC 72 ms 197120 KB
subtask_3_10.txt AC 181 ms 212736 KB
subtask_3_11.txt AC 181 ms 212736 KB
subtask_3_12.txt AC 176 ms 212736 KB
subtask_3_13.txt AC 72 ms 197248 KB
subtask_3_14.txt AC 72 ms 197120 KB
subtask_3_2.txt AC 72 ms 197248 KB
subtask_3_3.txt AC 186 ms 212736 KB
subtask_3_4.txt AC 177 ms 212736 KB
subtask_3_5.txt AC 222 ms 212736 KB
subtask_3_6.txt AC 177 ms 212736 KB
subtask_3_7.txt AC 208 ms 212736 KB
subtask_3_8.txt AC 187 ms 212736 KB
subtask_3_9.txt AC 225 ms 212736 KB