Submission #3750195
Source Code Expand
#include <algorithm> #include <cassert> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> /* #include <regex> */ using namespace std; /* g++ -g -std=c++11 */ /* freopen("input.txt", "rt", stdin); */ /* freopen("output.txt", "wt", stdout); */ #define ALL(c) (c).begin(), (c).end() #define ALLR(c) (c).rbegin(), (c).rend() #define FOR(i,a,b) for (int i=(a); i < (b); ++i) #define FORR(i,a,b) for (int i=(a); i > (b); --i) #define FOR_ALL(i,c) for (__typeof((c).begin()) i=(c).begin(); \ i != (c).end(); ++i) #define FOR_ALLR(i,c) for (__typeof((c).rbegin()) i=(c).rbegin(); \ i != (c).rend(); ++i) #define SZ(array) (sizeof(array)/sizeof(array[0])) #define lc(x) (x<<1) /* 2*x */ #define rc(x) (x<<1 | 1) /* 2*x+1 */ #define lowbit(x) (x & (-x)) /* 0b10100 -> 0b100 */ typedef long long LL; typedef map<int,int> MII; typedef pair<int,int> PII; typedef set<int> SI; typedef vector<bool> VB; typedef vector<double> VD; typedef vector<int> VI; typedef vector<string> VS; /* check if a key is in container C */ template <class C> inline bool in_(const typename C::key_type& k, const C& A) { return A.find(k) != A.end(); } inline bool in_(const string& s, const string& S) { return S.find(s) != string::npos; } const LL inf = 1e16; VI H,P, sorted; bool cmp(const int i, const int j) { return H[i]+P[i] < H[j]+P[j]; } int main() { #ifdef foo_ freopen("foo", "rt", stdin); #endif ios::sync_with_stdio(false); int n; while (cin >> n) { H = P = sorted = VI(n); FOR(i,0,n) { cin >> H[i] >> P[i]; sorted[i] = i; } sort(ALL(sorted),cmp); vector<LL> dp = vector<LL>(n+1,inf); dp[0] = 0; int ans = 0; FOR(i,0,n) { const int j = sorted[i]; FORR(x,n-1,-1) if (dp[x] != inf && dp[x] <= H[j]) { dp[x+1] = min(dp[x+1], dp[x]+P[j]); ans = max(ans, x+1); } } cout << ans << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Zabuton |
User | chef29 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2548 Byte |
Status | AC |
Exec Time | 34 ms |
Memory | 384 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
All | sample-01.txt, sample-02.txt, sample-03.txt, 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, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 3 ms | 256 KB |
01-04.txt | AC | 6 ms | 256 KB |
01-05.txt | AC | 20 ms | 384 KB |
01-06.txt | AC | 20 ms | 384 KB |
01-07.txt | AC | 20 ms | 384 KB |
01-08.txt | AC | 20 ms | 384 KB |
01-09.txt | AC | 20 ms | 384 KB |
01-10.txt | AC | 1 ms | 256 KB |
01-11.txt | AC | 2 ms | 256 KB |
01-12.txt | AC | 9 ms | 384 KB |
01-13.txt | AC | 21 ms | 384 KB |
01-14.txt | AC | 22 ms | 384 KB |
01-15.txt | AC | 22 ms | 384 KB |
01-16.txt | AC | 22 ms | 384 KB |
01-17.txt | AC | 22 ms | 384 KB |
01-18.txt | AC | 22 ms | 384 KB |
01-19.txt | AC | 1 ms | 256 KB |
01-20.txt | AC | 2 ms | 256 KB |
01-21.txt | AC | 15 ms | 384 KB |
01-22.txt | AC | 28 ms | 384 KB |
01-23.txt | AC | 28 ms | 384 KB |
01-24.txt | AC | 28 ms | 384 KB |
01-25.txt | AC | 28 ms | 384 KB |
01-26.txt | AC | 28 ms | 384 KB |
01-27.txt | AC | 29 ms | 384 KB |
01-28.txt | AC | 19 ms | 384 KB |
01-29.txt | AC | 19 ms | 384 KB |
01-30.txt | AC | 19 ms | 384 KB |
01-31.txt | AC | 20 ms | 384 KB |
01-32.txt | AC | 19 ms | 384 KB |
01-33.txt | AC | 19 ms | 384 KB |
01-34.txt | AC | 19 ms | 384 KB |
01-35.txt | AC | 34 ms | 384 KB |
01-36.txt | AC | 34 ms | 384 KB |
01-37.txt | AC | 33 ms | 384 KB |
01-38.txt | AC | 33 ms | 384 KB |
01-39.txt | AC | 33 ms | 384 KB |
01-40.txt | AC | 19 ms | 384 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 1 ms | 256 KB |