Submission #59670261

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
typedef modint1000000007 mi;

int a[105],b[105];

int main(){
    int n,s;cin>>n>>s;
    rep(i,n)cin>>a[i]>>b[i];
    vector<bitset<100008>>B(n+1);
    B[0].flip(0);
    rep(i,n){
        B[i+1]|=(B[i]<<a[i]);
        B[i+1]|=(B[i]<<b[i]);
    }
    if(B[n][s]){
        string res;
        int cnt=s;
        for(int i=n-1;i>=0;i--){
            if(cnt-a[i]>=0&&B[i][cnt-a[i]]){
                res.push_back('A');
                cnt-=a[i];
            }
            else{
                res.push_back('B');
                cnt-=b[i];
            }
        }
        reverse(all(res));
        cout<<res<<endl;
    }
    else{
        cout<<"Impossible"<<endl;
    }
}

Submission Info

Submission Time
Task 056 - Lucky Bag（★5）
User Rho17
Language C++ 20 (gcc 12.2)
Score 5
Code Size 951 Byte
Status AC
Exec Time 13 ms
Memory 4504 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 5 / 5
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All max_01.txt, max_02.txt, max_03.txt, max_04.txt, max_05.txt, max_06.txt, max_07.txt, max_08.txt, max_09.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
max_01.txt AC 13 ms 4348 KiB
max_02.txt AC 2 ms 4140 KiB
max_03.txt AC 2 ms 4392 KiB
max_04.txt AC 2 ms 4504 KiB
max_05.txt AC 2 ms 4128 KiB
max_06.txt AC 1 ms 3480 KiB
max_07.txt AC 1 ms 3452 KiB
max_08.txt AC 2 ms 3540 KiB
max_09.txt AC 2 ms 4208 KiB
random_01.txt AC 2 ms 3976 KiB
random_02.txt AC 2 ms 3948 KiB
random_03.txt AC 1 ms 3944 KiB
random_04.txt AC 1 ms 3660 KiB
random_05.txt AC 2 ms 4024 KiB
random_06.txt AC 1 ms 3476 KiB
random_07.txt AC 2 ms 4128 KiB
random_08.txt AC 2 ms 4108 KiB
random_09.txt AC 2 ms 3864 KiB
random_10.txt AC 2 ms 3700 KiB
random_11.txt AC 2 ms 3716 KiB
random_12.txt AC 2 ms 3864 KiB
random_13.txt AC 1 ms 3680 KiB
random_14.txt AC 2 ms 4236 KiB
random_15.txt AC 1 ms 3508 KiB
random_16.txt AC 2 ms 4472 KiB
random_17.txt AC 2 ms 4152 KiB
random_18.txt AC 2 ms 3868 KiB
random_19.txt AC 1 ms 3676 KiB
random_20.txt AC 2 ms 4128 KiB
random_21.txt AC 2 ms 4456 KiB
random_22.txt AC 2 ms 4452 KiB
random_23.txt AC 2 ms 4496 KiB
random_24.txt AC 2 ms 4240 KiB
sample_01.txt AC 1 ms 3584 KiB
sample_02.txt AC 1 ms 3444 KiB
sample_03.txt AC 1 ms 3488 KiB