結果
問題 | No.2161 Black Market |
ユーザー |
![]() |
提出日時 | 2022-12-13 22:04:26 |
言語 | cLay (20241019-1) |
結果 |
AC
|
実行時間 | 187 ms / 7,000 ms |
コード長 | 1,044 bytes |
コンパイル時間 | 6,945 ms |
コンパイル使用メモリ | 228,756 KB |
実行使用メモリ | 38,588 KB |
最終ジャッジ日時 | 2024-11-07 15:58:45 |
合計ジャッジ時間 | 9,807 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
ll@n,@k,@l,@p; ll n1=n>>1,n2=n-n1; vector<pair<ll,ll>>g1[18],g2[18]; // hanbun zen rekkyo g1[0].push_back({0,0}); rep(i,n1){ ll@a,@b; rrep(j,i+1){ for(auto x:g1[j]){ g1[j+1].push_back({x.first+b,x.second+a}); } } } g2[0].push_back({0,0}); rep(i,n2){ ll@a,@b; rrep(j,i+1){ for(auto x:g2[j]){ g2[j+1].push_back({x.first+b,x.second+a}); } } } // zaatsu cost ll za[1<<18],zn=0; rep(i,n1+1){ for(auto x:g1[i]){ za[zn++]=l-x.second; } } rep(i,n2+1){ for(auto x:g2[i]){ za[zn++]=x.second; } } coordcomp(zn,za); zn=0; rep(i,n1+1){ for(auto&x:g1[i]){ x.second=za[zn++]; } } rep(i,n2+1){ for(auto&x:g2[i]){ x.second=za[zn++]; } } // kazoeru ll z=0; ll j=0; vector<pair<ll,ll>>g; rrep(i,n1+1){ while(j<=n2&&i+j<=k){ g.insert(g.end(),g2[j].begin(),g2[j].end()); ++j; } sort(g.begin(),g.end()); sort(g1[i].begin(),g1[i].end()); ll l=g.size()-1; fenwick<ll>f; f.malloc(1<<18,1); for(auto x:g1[i]){ while(l>=0&&x.first+g[l].first>=p){ f.add(g[l].second,1); --l; } z+=f.get(x.second); } } wt(z);