提出 #67002472
ソースコード 拡げる
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using P=pair<int,ll>;
using vi=vc<int>;
void solve(){
int n;
ll W;
cin>>n>>W;
int B=62;
vc<vc<ll>> vec(B+2);
for(int i=0;i<n;i++){
int x;
ll y;
cin>>x>>y;
vec[x].pb(y);
}
ll ret=0;
for(int i=0;i<B;i++){
sort(vec[i].begin(),vec[i].end(),greater<ll>());
if(!vec[i].empty()){
int p=0;
if(W>>i&1){
ret+=vec[i][p];
p++;
}
while(p<vec[i].size()){
if(p+1<vec[i].size()){
vec[i+1].pb(vec[i][p]+vec[i][p+1]);
p+=2;
} else{
vec[i+1].pb(vec[i][p]);
break;
}
}
}
}
cout<<ret<<endl;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
int T;
cin>>T;
while(T--) solve();
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | B - Binary Knapsack |
| ユーザ | yutaka1999 |
| 言語 | C++ 23 (Clang 16.0.6) |
| 得点 | 500 |
| コード長 | 1751 Byte |
| 結果 | AC |
| 実行時間 | 238 ms |
| メモリ | 7244 KiB |
コンパイルエラー
./Main.cpp:54:20: warning: comparison of integers of different signs: 'int' and 'size_type' (aka 'unsigned long') [-Wsign-compare]
while(p<vec[i].size()){
~^~~~~~~~~~~~~~
./Main.cpp:55:23: warning: comparison of integers of different signs: 'int' and 'size_type' (aka 'unsigned long') [-Wsign-compare]
if(p+1<vec[i].size()){
~~~^~~~~~~~~~~~~~
2 warnings generated.
ジャッジ結果
| セット名 | Sample | All | ||||
|---|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 0 | 500 / 500 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| Sample | sample-01.txt |
| All | 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, 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, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, hand-01.txt, sample-01.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| 01-01.txt | AC | 238 ms | 3456 KiB |
| 01-02.txt | AC | 56 ms | 3632 KiB |
| 01-03.txt | AC | 33 ms | 3572 KiB |
| 01-04.txt | AC | 28 ms | 3552 KiB |
| 01-05.txt | AC | 31 ms | 3788 KiB |
| 01-06.txt | AC | 35 ms | 7244 KiB |
| 01-07.txt | AC | 35 ms | 7040 KiB |
| 01-08.txt | AC | 142 ms | 3504 KiB |
| 01-09.txt | AC | 43 ms | 3440 KiB |
| 01-10.txt | AC | 30 ms | 3532 KiB |
| 01-11.txt | AC | 29 ms | 3748 KiB |
| 01-12.txt | AC | 32 ms | 7032 KiB |
| 01-13.txt | AC | 32 ms | 7208 KiB |
| 01-14.txt | AC | 30 ms | 3772 KiB |
| 01-15.txt | AC | 33 ms | 7004 KiB |
| 01-16.txt | AC | 33 ms | 6984 KiB |
| 02-01.txt | AC | 32 ms | 3448 KiB |
| 02-02.txt | AC | 31 ms | 3664 KiB |
| 02-03.txt | AC | 36 ms | 7020 KiB |
| 02-04.txt | AC | 34 ms | 7008 KiB |
| 02-05.txt | AC | 23 ms | 3660 KiB |
| 02-06.txt | AC | 32 ms | 7024 KiB |
| 02-07.txt | AC | 21 ms | 7044 KiB |
| 02-08.txt | AC | 30 ms | 3768 KiB |
| 02-09.txt | AC | 35 ms | 6904 KiB |
| 02-10.txt | AC | 32 ms | 7060 KiB |
| 03-01.txt | AC | 23 ms | 6348 KiB |
| 03-02.txt | AC | 23 ms | 6540 KiB |
| 03-03.txt | AC | 22 ms | 6584 KiB |
| 03-04.txt | AC | 25 ms | 7056 KiB |
| 03-05.txt | AC | 34 ms | 7092 KiB |
| 03-06.txt | AC | 22 ms | 7000 KiB |
| 03-07.txt | AC | 34 ms | 6704 KiB |
| hand-01.txt | AC | 1 ms | 3440 KiB |
| sample-01.txt | AC | 1 ms | 3460 KiB |