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
Submission Time | |
---|---|
Task | B - Takahashi the Magician |
User | btk15049 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2766 Byte |
Status | RE |
Exec Time | 240 ms |
Memory | 35712 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 | 9 ms | 19968 KB |
hack_2.txt | AC | 9 ms | 19968 KB |
hack_3.txt | WA | 9 ms | 19968 KB |
hack_4.txt | AC | 9 ms | 19968 KB |
hack_5.txt | WA | 9 ms | 19968 KB |
sample_1.txt | AC | 9 ms | 19968 KB |
sample_2.txt | AC | 9 ms | 19968 KB |
sample_3.txt | AC | 9 ms | 19968 KB |
subtask_1_1.txt | WA | 9 ms | 19968 KB |
subtask_1_10.txt | WA | 9 ms | 19968 KB |
subtask_1_11.txt | AC | 111 ms | 35712 KB |
subtask_1_12.txt | WA | 9 ms | 19968 KB |
subtask_1_13.txt | WA | 9 ms | 20096 KB |
subtask_1_14.txt | WA | 9 ms | 19968 KB |
subtask_1_15.txt | AC | 114 ms | 35712 KB |
subtask_1_16.txt | WA | 129 ms | 35712 KB |
subtask_1_17.txt | WA | 129 ms | 35712 KB |
subtask_1_18.txt | AC | 115 ms | 35712 KB |
subtask_1_19.txt | WA | 9 ms | 19968 KB |
subtask_1_2.txt | AC | 9 ms | 19968 KB |
subtask_1_20.txt | AC | 9 ms | 19968 KB |
subtask_1_3.txt | AC | 9 ms | 19968 KB |
subtask_1_4.txt | RE | 104 ms | 19968 KB |
subtask_1_5.txt | WA | 9 ms | 19968 KB |
subtask_1_6.txt | WA | 9 ms | 20096 KB |
subtask_1_7.txt | WA | 9 ms | 20096 KB |
subtask_1_8.txt | AC | 112 ms | 35712 KB |
subtask_1_9.txt | AC | 45 ms | 27776 KB |
subtask_2_1.txt | WA | 16 ms | 21504 KB |
subtask_2_10.txt | WA | 21 ms | 22784 KB |
subtask_2_11.txt | WA | 79 ms | 35584 KB |
subtask_2_12.txt | AC | 85 ms | 35712 KB |
subtask_2_13.txt | AC | 80 ms | 35712 KB |
subtask_2_14.txt | AC | 85 ms | 35712 KB |
subtask_2_15.txt | AC | 9 ms | 19968 KB |
subtask_2_16.txt | AC | 77 ms | 35712 KB |
subtask_2_17.txt | AC | 77 ms | 35712 KB |
subtask_2_18.txt | AC | 240 ms | 35712 KB |
subtask_2_19.txt | WA | 9 ms | 19968 KB |
subtask_2_2.txt | RE | 167 ms | 35712 KB |
subtask_2_20.txt | WA | 9 ms | 19968 KB |
subtask_2_21.txt | WA | 9 ms | 19968 KB |
subtask_2_22.txt | WA | 9 ms | 19968 KB |
subtask_2_23.txt | WA | 9 ms | 19968 KB |
subtask_2_24.txt | WA | 9 ms | 19968 KB |
subtask_2_25.txt | WA | 9 ms | 19968 KB |
subtask_2_26.txt | WA | 9 ms | 19968 KB |
subtask_2_27.txt | WA | 9 ms | 19968 KB |
subtask_2_3.txt | WA | 77 ms | 35712 KB |
subtask_2_4.txt | WA | 43 ms | 27776 KB |
subtask_2_5.txt | WA | 86 ms | 35712 KB |
subtask_2_6.txt | WA | 81 ms | 35712 KB |
subtask_2_7.txt | WA | 36 ms | 26240 KB |
subtask_2_8.txt | WA | 13 ms | 20864 KB |
subtask_2_9.txt | WA | 25 ms | 23552 KB |
subtask_3_1.txt | WA | 9 ms | 19968 KB |
subtask_3_10.txt | WA | 118 ms | 35712 KB |
subtask_3_11.txt | AC | 118 ms | 35712 KB |
subtask_3_12.txt | AC | 121 ms | 35712 KB |
subtask_3_13.txt | WA | 9 ms | 19968 KB |
subtask_3_14.txt | WA | 9 ms | 19968 KB |
subtask_3_2.txt | AC | 10 ms | 20096 KB |
subtask_3_3.txt | AC | 122 ms | 35712 KB |
subtask_3_4.txt | WA | 114 ms | 35712 KB |
subtask_3_5.txt | AC | 131 ms | 35712 KB |
subtask_3_6.txt | WA | 115 ms | 35584 KB |
subtask_3_7.txt | AC | 151 ms | 35712 KB |
subtask_3_8.txt | WA | 125 ms | 35712 KB |
subtask_3_9.txt | AC | 133 ms | 35712 KB |