Submission #3368709


Source Code Expand

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N, P; cin >> N >> P;
    vector<Pii> ab(N);
    REP(i, N) cin >> ab[i].first >> ab[i].second;
    SORT(ab); REVERSE(ab);

    mat dp(N + 1, vec(P + 100 + 1, 0));
    int minp = 100;
    int ans = 0;
    REP(n, N){
        minp = min(minp, ab[n].first);
        REP(p, P + 100 + 1){
            if(p + ab[n].first <= P + 100)
            dp[n + 1][p + ab[n].first] = max(dp[n][p] + ab[n].second, dp[n][p + ab[n].first]);
        }
        ans = max(ans, dp[n + 1][P + minp]);
    }
    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Submission Info

Submission Time
Task C - おやつ
User sumitacchan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1497 Byte
Status AC
Exec Time 133 ms
Memory 199808 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 3
AC × 17
AC × 38
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_00.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_00.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask2_00.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_00.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 384 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 384 KB
subtask1_10.txt AC 1 ms 384 KB
subtask1_11.txt AC 1 ms 384 KB
subtask1_12.txt AC 1 ms 384 KB
subtask1_13.txt AC 1 ms 384 KB
subtask1_14.txt AC 1 ms 384 KB
subtask2_00.txt AC 13 ms 17024 KB
subtask2_01.txt AC 24 ms 34048 KB
subtask2_02.txt AC 95 ms 141056 KB
subtask2_03.txt AC 14 ms 18688 KB
subtask2_04.txt AC 30 ms 41728 KB
subtask2_05.txt AC 73 ms 108160 KB
subtask2_06.txt AC 4 ms 3584 KB
subtask2_07.txt AC 12 ms 16896 KB
subtask2_08.txt AC 4 ms 4864 KB
subtask2_09.txt AC 24 ms 35072 KB
subtask2_10.txt AC 132 ms 199808 KB
subtask2_11.txt AC 133 ms 199808 KB
subtask2_12.txt AC 133 ms 199808 KB
subtask2_13.txt AC 133 ms 199808 KB
subtask2_14.txt AC 133 ms 199808 KB
subtask2_15.txt AC 133 ms 199808 KB
subtask2_16.txt AC 133 ms 199808 KB
subtask2_17.txt AC 133 ms 199808 KB
subtask2_18.txt AC 133 ms 199808 KB
subtask2_19.txt AC 133 ms 199808 KB