Submission #1129536
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=1e12; 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; } else{ 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]){ 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)return cnt+k; 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; } else{ 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; } 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][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],true); 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 | 2874 Byte |
Status | RE |
Exec Time | 317 ms |
Memory | 212864 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 800 | 0 / 200 | ||||||||||||||||||||
Status |
|
|
|
|
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 | WA | 73 ms | 197120 KB |
hack_2.txt | WA | 73 ms | 197120 KB |
hack_3.txt | WA | 73 ms | 197120 KB |
hack_4.txt | AC | 72 ms | 197120 KB |
hack_5.txt | WA | 72 ms | 197120 KB |
sample_1.txt | AC | 72 ms | 197120 KB |
sample_2.txt | AC | 72 ms | 197120 KB |
sample_3.txt | AC | 72 ms | 197120 KB |
subtask_1_1.txt | WA | 72 ms | 197120 KB |
subtask_1_10.txt | WA | 72 ms | 197120 KB |
subtask_1_11.txt | AC | 175 ms | 212736 KB |
subtask_1_12.txt | WA | 72 ms | 197120 KB |
subtask_1_13.txt | WA | 72 ms | 197120 KB |
subtask_1_14.txt | WA | 73 ms | 197120 KB |
subtask_1_15.txt | AC | 187 ms | 212736 KB |
subtask_1_16.txt | WA | 191 ms | 212736 KB |
subtask_1_17.txt | WA | 191 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 | 73 ms | 197120 KB |
subtask_1_20.txt | AC | 73 ms | 197120 KB |
subtask_1_3.txt | AC | 73 ms | 197120 KB |
subtask_1_4.txt | RE | 168 ms | 197120 KB |
subtask_1_5.txt | RE | 168 ms | 197120 KB |
subtask_1_6.txt | RE | 169 ms | 197248 KB |
subtask_1_7.txt | RE | 167 ms | 197248 KB |
subtask_1_8.txt | AC | 176 ms | 212736 KB |
subtask_1_9.txt | AC | 108 ms | 204928 KB |
subtask_2_1.txt | WA | 79 ms | 198656 KB |
subtask_2_10.txt | WA | 84 ms | 199936 KB |
subtask_2_11.txt | WA | 141 ms | 212736 KB |
subtask_2_12.txt | AC | 149 ms | 212736 KB |
subtask_2_13.txt | AC | 143 ms | 212736 KB |
subtask_2_14.txt | AC | 151 ms | 212736 KB |
subtask_2_15.txt | AC | 73 ms | 197120 KB |
subtask_2_16.txt | AC | 140 ms | 212736 KB |
subtask_2_17.txt | AC | 140 ms | 212736 KB |
subtask_2_18.txt | AC | 317 ms | 212736 KB |
subtask_2_19.txt | WA | 72 ms | 197120 KB |
subtask_2_2.txt | RE | 230 ms | 212736 KB |
subtask_2_20.txt | WA | 72 ms | 197120 KB |
subtask_2_21.txt | WA | 72 ms | 197120 KB |
subtask_2_22.txt | WA | 73 ms | 197120 KB |
subtask_2_23.txt | WA | 72 ms | 197120 KB |
subtask_2_24.txt | WA | 72 ms | 197120 KB |
subtask_2_25.txt | WA | 73 ms | 197120 KB |
subtask_2_26.txt | WA | 73 ms | 197120 KB |
subtask_2_27.txt | WA | 73 ms | 197248 KB |
subtask_2_3.txt | WA | 141 ms | 212736 KB |
subtask_2_4.txt | WA | 106 ms | 204928 KB |
subtask_2_5.txt | WA | 149 ms | 212736 KB |
subtask_2_6.txt | WA | 141 ms | 212736 KB |
subtask_2_7.txt | WA | 100 ms | 203392 KB |
subtask_2_8.txt | WA | 76 ms | 198016 KB |
subtask_2_9.txt | WA | 88 ms | 200704 KB |
subtask_3_1.txt | AC | 72 ms | 197120 KB |
subtask_3_10.txt | WA | 183 ms | 212736 KB |
subtask_3_11.txt | AC | 193 ms | 212736 KB |
subtask_3_12.txt | AC | 176 ms | 212736 KB |
subtask_3_13.txt | WA | 72 ms | 197120 KB |
subtask_3_14.txt | WA | 73 ms | 197120 KB |
subtask_3_2.txt | AC | 73 ms | 197248 KB |
subtask_3_3.txt | AC | 191 ms | 212736 KB |
subtask_3_4.txt | WA | 178 ms | 212736 KB |
subtask_3_5.txt | WA | 192 ms | 212864 KB |
subtask_3_6.txt | WA | 179 ms | 212736 KB |
subtask_3_7.txt | AC | 209 ms | 212736 KB |
subtask_3_8.txt | WA | 187 ms | 212736 KB |
subtask_3_9.txt | WA | 195 ms | 212736 KB |