提出 #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
結果
AC × 1
AC × 35
セット名 テストケース
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