Submission #691973
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 lef[201010],rig[201010]; int depth[201010]; set<pair<int,int>> SS; set<pair<int,int>> R[201010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>W[i]; 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()) { auto r=*SS.begin(); SS.erase(SS.begin()); x=r.second; 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()); 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 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){ // merge right 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)->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 | 2289 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 | 18 ms | 9728 KB |
01_02.txt | AC | 18 ms | 9728 KB |
01_03.txt | AC | 18 ms | 9728 KB |
01_04.txt | AC | 18 ms | 9728 KB |
01_05.txt | AC | 18 ms | 9728 KB |
01_06.txt | AC | 18 ms | 9728 KB |
01_07.txt | AC | 18 ms | 9728 KB |
01_08.txt | AC | 18 ms | 9728 KB |
01_09.txt | AC | 18 ms | 9728 KB |
01_10.txt | AC | 18 ms | 9728 KB |
01_11.txt | AC | 18 ms | 9728 KB |
01_12.txt | AC | 18 ms | 9728 KB |
01_13.txt | AC | 18 ms | 9728 KB |
01_14.txt | AC | 18 ms | 9728 KB |
01_15.txt | AC | 18 ms | 9728 KB |
01_16.txt | AC | 18 ms | 9728 KB |
01_17.txt | AC | 19 ms | 9728 KB |
01_18.txt | AC | 18 ms | 9728 KB |
01_19.txt | AC | 19 ms | 9728 KB |
01_20.txt | AC | 18 ms | 9728 KB |
01_21.txt | AC | 18 ms | 9728 KB |
01_22.txt | AC | 18 ms | 9728 KB |
01_23.txt | AC | 18 ms | 9728 KB |
01_24.txt | AC | 18 ms | 9728 KB |
01_25.txt | AC | 18 ms | 9728 KB |
01_26.txt | AC | 18 ms | 9728 KB |
01_27.txt | AC | 20 ms | 9728 KB |
01_28.txt | AC | 18 ms | 9728 KB |
01_29.txt | AC | 18 ms | 9728 KB |
02_00.txt | AC | 23 ms | 10240 KB |
02_01.txt | AC | 23 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 | 23 ms | 10240 KB |
02_07.txt | AC | 23 ms | 10240 KB |
02_08.txt | AC | 23 ms | 10240 KB |
02_09.txt | AC | 23 ms | 10240 KB |
02_10.txt | AC | 24 ms | 10240 KB |
02_11.txt | AC | 24 ms | 10240 KB |
02_12.txt | AC | 23 ms | 10240 KB |
02_13.txt | AC | 23 ms | 10240 KB |
02_14.txt | AC | 23 ms | 10240 KB |
02_15.txt | AC | 23 ms | 10240 KB |
02_16.txt | AC | 23 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 | 23 ms | 10240 KB |
02_23.txt | AC | 23 ms | 10240 KB |
02_24.txt | AC | 23 ms | 10240 KB |
02_25.txt | AC | 23 ms | 10240 KB |
02_26.txt | AC | 24 ms | 10240 KB |
02_27.txt | AC | 24 ms | 10240 KB |
02_28.txt | AC | 24 ms | 10240 KB |
02_29.txt | AC | 23 ms | 10240 KB |
03_00.txt | AC | 299 ms | 27264 KB |
03_01.txt | AC | 299 ms | 27264 KB |
03_02.txt | AC | 304 ms | 27264 KB |
03_03.txt | AC | 290 ms | 27264 KB |
03_04.txt | AC | 299 ms | 27264 KB |
03_05.txt | AC | 209 ms | 27264 KB |
03_06.txt | AC | 234 ms | 27264 KB |
03_07.txt | AC | 244 ms | 27264 KB |
03_08.txt | AC | 249 ms | 27264 KB |
03_09.txt | AC | 250 ms | 27264 KB |
03_10.txt | AC | 257 ms | 27264 KB |
03_11.txt | AC | 247 ms | 27264 KB |
03_12.txt | AC | 254 ms | 27264 KB |
03_13.txt | AC | 257 ms | 27264 KB |
03_14.txt | AC | 265 ms | 27264 KB |
03_15.txt | AC | 263 ms | 27264 KB |
03_16.txt | AC | 256 ms | 27264 KB |
03_17.txt | AC | 273 ms | 27264 KB |
03_18.txt | AC | 248 ms | 27264 KB |
03_19.txt | AC | 270 ms | 27264 KB |
03_20.txt | AC | 271 ms | 27264 KB |
03_21.txt | AC | 278 ms | 27264 KB |
03_22.txt | AC | 267 ms | 27264 KB |
03_23.txt | AC | 298 ms | 27264 KB |
03_24.txt | AC | 263 ms | 27264 KB |
03_25.txt | AC | 279 ms | 27264 KB |
03_26.txt | AC | 285 ms | 27264 KB |
03_27.txt | AC | 279 ms | 27264 KB |
03_28.txt | AC | 289 ms | 27264 KB |
03_29.txt | AC | 318 ms | 27264 KB |
03_30.txt | AC | 311 ms | 27264 KB |
03_31.txt | AC | 311 ms | 27264 KB |
03_32.txt | AC | 306 ms | 27264 KB |
03_33.txt | AC | 308 ms | 27264 KB |
03_34.txt | AC | 311 ms | 27264 KB |