Submission #691968
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N; int W[201010]; int T[201010]; /* int S[101010]; ll dp[3030][3030]; int sp[3030][3030]; */ int lef[201010],rig[201010]; int depth[201010]; set<pair<int,int>> SS; set<pair<int,int>> R[201010]; /* void slow(){ int i,j,k,l,r,x,y; string s; FOR(i,N) dp[i][i]=0,sp[i][i]=i; FOR(i,N-1) dp[i][i+1]=(W[i]+W[i+1]),sp[i][i+1]=i; for(i=2;i<=N-1;i++) { for(x=0;x+i<N;x++) { dp[x][x+i]=1LL<<60; for(y=sp[x][x+i-1];y<=sp[x+1][x+i];y++) { if(dp[x][y]+dp[y+1][x+i]<dp[x][x+i]) { dp[x][x+i]=dp[x][y]+dp[y+1][x+i]; sp[x][x+i]=y; } } dp[x][x+i]+=S[x+i+1]-S[x]; } } cout<<dp[0][N-1]<<endl; } */ void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>W[i]; //if(N<=3000) return slow(); FOR(i,N) lef[i]=max(i-1,0), rig[i]=min(N-1,i+1); FOR(i,N-1) { R[i].insert({W[i],i}); R[i].insert({W[i+1],i+1}); T[i]=W[i]+W[i+1]; SS.insert({T[i],i}); } int nex=N; while(SS.size()) { /* FORR(r,SS) _P("%d:%d ",r.first,r.second); _P("\n"); FOR(i,N-1) if(rig[i]>=0) _P("%d:%d:%d(%d) ",lef[i],i,rig[i],R[i].size()); _P("\n"); */ auto r=*SS.begin(); SS.erase(SS.begin()); x=r.second; /* FORR(rr,R[x]) _P("<%d:%d>",rr.first,rr.second); _P("x=%d %d\n",x,R[x].size()); */ if(R[x].size()==1) { break; } auto rx=R[x].begin()->second; R[x].erase(R[x].begin()); auto ry=R[x].begin()->second; R[x].erase(R[x].begin()); /* FORR(rr,R[x]) _P("<%d:%d>",rr.first,rr.second); _P("x=%d %d\n",x,R[x].size()); _P("%d-%d %d %d -> %d\n",x,rig[x],rx.second,ry.second,nex); */ lef[nex]=rx; rig[nex]=ry; W[nex]=W[rx]+W[ry]; R[x].insert({W[nex],nex}); if((rx==x || ry==x) && x){ // merge lef //_P("lef\n"); y=lef[x]; rig[y]=rig[x]; lef[rig[x]]=y; SS.erase({T[y],y}); R[y].erase({W[x],x}); if(R[y].size()<R[x].size()) swap(R[x],R[y]); FORR(r,R[x]) R[y].insert(r); R[x].clear(); rig[x]=-1; x=y; } if((rx==rig[x] || ry==rig[x]) && rig[x]<N-1){ //_P("ri\n"); y=rig[x]; lef[rig[y]]=x; rig[x]=rig[y]; SS.erase({T[y],y}); R[y].erase({W[y],y}); if(R[y].size()>R[x].size()) swap(R[x],R[y]); FORR(r,R[y]) R[x].insert(r); R[y].clear(); rig[y]=-1; } auto it=R[x].begin(); T[x]=it->first; it++; T[x]+=it->first; SS.insert({T[x],x}); nex++; } for(i=nex-1;i>=N;i--) depth[lef[i]]=depth[rig[i]]=depth[i]+1; ll ret=0; //FOR(i,N) _P("%d:%d:%d ",i,depth[i],W[i]); FOR(i,N) ret+=depth[i]*W[i]; cout<<ret<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 101 |
Code Size | 3286 Byte |
Status | AC |
Exec Time | 318 ms |
Memory | 27264 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 18 ms | 9728 KB |
01_00.txt | AC | 18 ms | 9728 KB |
01_01.txt | AC | 21 ms | 9728 KB |
01_02.txt | AC | 20 ms | 9728 KB |
01_03.txt | AC | 18 ms | 9728 KB |
01_04.txt | AC | 20 ms | 9728 KB |
01_05.txt | AC | 18 ms | 9728 KB |
01_06.txt | AC | 18 ms | 9728 KB |
01_07.txt | AC | 20 ms | 9728 KB |
01_08.txt | AC | 20 ms | 9728 KB |
01_09.txt | AC | 20 ms | 9728 KB |
01_10.txt | AC | 21 ms | 9728 KB |
01_11.txt | AC | 18 ms | 9728 KB |
01_12.txt | AC | 18 ms | 9728 KB |
01_13.txt | AC | 20 ms | 9728 KB |
01_14.txt | AC | 18 ms | 9728 KB |
01_15.txt | AC | 20 ms | 9728 KB |
01_16.txt | AC | 18 ms | 9728 KB |
01_17.txt | AC | 22 ms | 9728 KB |
01_18.txt | AC | 21 ms | 9728 KB |
01_19.txt | AC | 18 ms | 9728 KB |
01_20.txt | AC | 20 ms | 9728 KB |
01_21.txt | AC | 18 ms | 9728 KB |
01_22.txt | AC | 18 ms | 9728 KB |
01_23.txt | AC | 20 ms | 9728 KB |
01_24.txt | AC | 20 ms | 9728 KB |
01_25.txt | AC | 18 ms | 9728 KB |
01_26.txt | AC | 18 ms | 9728 KB |
01_27.txt | AC | 21 ms | 9728 KB |
01_28.txt | AC | 18 ms | 9728 KB |
01_29.txt | AC | 18 ms | 9728 KB |
02_00.txt | AC | 24 ms | 10240 KB |
02_01.txt | AC | 26 ms | 10240 KB |
02_02.txt | AC | 24 ms | 10240 KB |
02_03.txt | AC | 26 ms | 10240 KB |
02_04.txt | AC | 23 ms | 10240 KB |
02_05.txt | AC | 23 ms | 10240 KB |
02_06.txt | AC | 24 ms | 10240 KB |
02_07.txt | AC | 26 ms | 10240 KB |
02_08.txt | AC | 24 ms | 10240 KB |
02_09.txt | AC | 23 ms | 10240 KB |
02_10.txt | AC | 26 ms | 10240 KB |
02_11.txt | AC | 24 ms | 10240 KB |
02_12.txt | AC | 26 ms | 10240 KB |
02_13.txt | AC | 26 ms | 10240 KB |
02_14.txt | AC | 24 ms | 10240 KB |
02_15.txt | AC | 26 ms | 10240 KB |
02_16.txt | AC | 24 ms | 10240 KB |
02_17.txt | AC | 23 ms | 10240 KB |
02_18.txt | AC | 23 ms | 10240 KB |
02_19.txt | AC | 23 ms | 10240 KB |
02_20.txt | AC | 23 ms | 10240 KB |
02_21.txt | AC | 23 ms | 10240 KB |
02_22.txt | AC | 24 ms | 10240 KB |
02_23.txt | AC | 26 ms | 10240 KB |
02_24.txt | AC | 26 ms | 10240 KB |
02_25.txt | AC | 24 ms | 10240 KB |
02_26.txt | AC | 25 ms | 10240 KB |
02_27.txt | AC | 26 ms | 10240 KB |
02_28.txt | AC | 26 ms | 10240 KB |
02_29.txt | AC | 26 ms | 10240 KB |
03_00.txt | AC | 290 ms | 27264 KB |
03_01.txt | AC | 285 ms | 27264 KB |
03_02.txt | AC | 298 ms | 27264 KB |
03_03.txt | AC | 291 ms | 27264 KB |
03_04.txt | AC | 315 ms | 27264 KB |
03_05.txt | AC | 212 ms | 27264 KB |
03_06.txt | AC | 236 ms | 27264 KB |
03_07.txt | AC | 249 ms | 27264 KB |
03_08.txt | AC | 262 ms | 27264 KB |
03_09.txt | AC | 264 ms | 27264 KB |
03_10.txt | AC | 254 ms | 27264 KB |
03_11.txt | AC | 248 ms | 27264 KB |
03_12.txt | AC | 264 ms | 27264 KB |
03_13.txt | AC | 266 ms | 27264 KB |
03_14.txt | AC | 269 ms | 27264 KB |
03_15.txt | AC | 268 ms | 27264 KB |
03_16.txt | AC | 268 ms | 27264 KB |
03_17.txt | AC | 300 ms | 27264 KB |
03_18.txt | AC | 254 ms | 27264 KB |
03_19.txt | AC | 270 ms | 27264 KB |
03_20.txt | AC | 278 ms | 27264 KB |
03_21.txt | AC | 288 ms | 27264 KB |
03_22.txt | AC | 276 ms | 27264 KB |
03_23.txt | AC | 310 ms | 27264 KB |
03_24.txt | AC | 276 ms | 27264 KB |
03_25.txt | AC | 302 ms | 27264 KB |
03_26.txt | AC | 295 ms | 27264 KB |
03_27.txt | AC | 295 ms | 27264 KB |
03_28.txt | AC | 288 ms | 27264 KB |
03_29.txt | AC | 318 ms | 27264 KB |
03_30.txt | AC | 298 ms | 27264 KB |
03_31.txt | AC | 287 ms | 27264 KB |
03_32.txt | AC | 297 ms | 27264 KB |
03_33.txt | AC | 295 ms | 27264 KB |
03_34.txt | AC | 286 ms | 27264 KB |