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 |
|
|
|
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 |