Submission #1635634
Source Code Expand
#include <algorithm> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const ll mod = 1e9 + 7; const int W = 1234567; int dp[W]; // dp[i + 1][j] = max(dp[i][j], dp[i][j - a[i]] + 1 if j <= b[i]) int main(void) { int n; cin >> n; vector<PI> pt; REP(i, 0, n) { int a, b; cin >> a >> b; pt.push_back(PI(b, a)); // b first!! This vector should be sorted by b!! } sort(pt.begin(), pt.end()); REP(i, 0, n) { int b = pt[i].first; int a = pt[i].second; if (a > b) { continue; } // ONEGAI O(nW) solution for (int j = b; j >= a; --j) { dp[j] = max(dp[j], dp[j - a] + 1); } } int ma = 0; REP(i, 0, W) { ma = max(ma, dp[i]); } cout << ma << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - ファーストアクセプタンス |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1250 Byte |
Status | AC |
Exec Time | 676 ms |
Memory | 4480 KB |
Judge Result
Set Name | Set 01 | Set 02 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 20 / 20 | 80 / 80 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Set 01 | 000_sample1.in, 000_sample2.in, 020_001_0014_random.in, 020_002_0005_random.in, 020_003_0001_random.in, 020_004_0006_random.in, 020_005_0009_random.in, 020_006_0016_random.in, 020_007_0016_random.in, 020_008_0016_random.in, 020_009_0016_random.in, 020_010_0016_random.in, 020_011_0012_just.in, 020_012_0013_just.in, 020_013_0014_just.in, 020_014_0015_just.in, 020_015_0016_just.in, 020_016_0010_almost.in, 020_017_0003_almost.in, 020_018_0004_almost.in, 020_019_0016_almost.in, 020_020_0013_almost.in, 020_021_0016_almost.in, 020_022_0016_almost.in, 020_023_0016_almost.in, 020_024_0016_almost.in, 020_025_0016_almost.in, 020_026_0016_mixed.in, 020_027_0016_mixed.in, 020_028_0016_mixed.in, 020_029_0016_mixed.in, 020_030_0016_mixed.in, 020_031_0016_mixed.in, 020_032_0016_mixed.in, 020_033_0016_mixed.in, 020_034_0016_mixed.in, 020_035_0016_mixed.in |
Set 02 | 000_sample1.in, 000_sample2.in, 020_001_0014_random.in, 020_002_0005_random.in, 020_003_0001_random.in, 020_004_0006_random.in, 020_005_0009_random.in, 020_006_0016_random.in, 020_007_0016_random.in, 020_008_0016_random.in, 020_009_0016_random.in, 020_010_0016_random.in, 020_011_0012_just.in, 020_012_0013_just.in, 020_013_0014_just.in, 020_014_0015_just.in, 020_015_0016_just.in, 020_016_0010_almost.in, 020_017_0003_almost.in, 020_018_0004_almost.in, 020_019_0016_almost.in, 020_020_0013_almost.in, 020_021_0016_almost.in, 020_022_0016_almost.in, 020_023_0016_almost.in, 020_024_0016_almost.in, 020_025_0016_almost.in, 020_026_0016_mixed.in, 020_027_0016_mixed.in, 020_028_0016_mixed.in, 020_029_0016_mixed.in, 020_030_0016_mixed.in, 020_031_0016_mixed.in, 020_032_0016_mixed.in, 020_033_0016_mixed.in, 020_034_0016_mixed.in, 020_035_0016_mixed.in, 100_001_0863_random.in, 100_002_0233_random.in, 100_003_0787_random.in, 100_004_0237_random.in, 100_005_0003_random.in, 100_006_1000_random.in, 100_007_1000_random.in, 100_008_1000_random.in, 100_009_1000_random.in, 100_010_1000_random.in, 100_011_0996_just.in, 100_012_0997_just.in, 100_013_0998_just.in, 100_014_0999_just.in, 100_015_1000_just.in, 100_016_0728_almost.in, 100_017_0811_almost.in, 100_018_0354_almost.in, 100_019_0467_almost.in, 100_020_0053_almost.in, 100_021_1000_almost.in, 100_022_1000_almost.in, 100_023_1000_almost.in, 100_024_1000_almost.in, 100_025_1000_almost.in, 100_026_1000_mixed.in, 100_027_1000_mixed.in, 100_028_1000_mixed.in, 100_029_1000_mixed.in, 100_030_1000_mixed.in, 100_031_1000_mixed.in, 100_032_1000_mixed.in, 100_033_1000_mixed.in, 100_034_1000_mixed.in, 100_035_1000_mixed.in |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000_sample1.in | AC | 3 ms | 256 KB |
000_sample2.in | AC | 3 ms | 256 KB |
020_001_0014_random.in | AC | 7 ms | 3968 KB |
020_002_0005_random.in | AC | 5 ms | 3072 KB |
020_003_0001_random.in | AC | 3 ms | 256 KB |
020_004_0006_random.in | AC | 4 ms | 1280 KB |
020_005_0009_random.in | AC | 6 ms | 4224 KB |
020_006_0016_random.in | AC | 7 ms | 4224 KB |
020_007_0016_random.in | AC | 10 ms | 4352 KB |
020_008_0016_random.in | AC | 8 ms | 4352 KB |
020_009_0016_random.in | AC | 10 ms | 4352 KB |
020_010_0016_random.in | AC | 7 ms | 4096 KB |
020_011_0012_just.in | AC | 12 ms | 4352 KB |
020_012_0013_just.in | AC | 9 ms | 4352 KB |
020_013_0014_just.in | AC | 13 ms | 4352 KB |
020_014_0015_just.in | AC | 12 ms | 4224 KB |
020_015_0016_just.in | AC | 12 ms | 4352 KB |
020_016_0010_almost.in | AC | 9 ms | 4352 KB |
020_017_0003_almost.in | AC | 4 ms | 1792 KB |
020_018_0004_almost.in | AC | 6 ms | 4096 KB |
020_019_0016_almost.in | AC | 17 ms | 4352 KB |
020_020_0013_almost.in | AC | 13 ms | 4224 KB |
020_021_0016_almost.in | AC | 14 ms | 4352 KB |
020_022_0016_almost.in | AC | 13 ms | 4352 KB |
020_023_0016_almost.in | AC | 14 ms | 4352 KB |
020_024_0016_almost.in | AC | 13 ms | 4352 KB |
020_025_0016_almost.in | AC | 11 ms | 4352 KB |
020_026_0016_mixed.in | AC | 8 ms | 4096 KB |
020_027_0016_mixed.in | AC | 12 ms | 4352 KB |
020_028_0016_mixed.in | AC | 12 ms | 4352 KB |
020_029_0016_mixed.in | AC | 9 ms | 4224 KB |
020_030_0016_mixed.in | AC | 10 ms | 4224 KB |
020_031_0016_mixed.in | AC | 10 ms | 4224 KB |
020_032_0016_mixed.in | AC | 11 ms | 4352 KB |
020_033_0016_mixed.in | AC | 14 ms | 4352 KB |
020_034_0016_mixed.in | AC | 9 ms | 4096 KB |
020_035_0016_mixed.in | AC | 9 ms | 4352 KB |
100_001_0863_random.in | AC | 174 ms | 4352 KB |
100_002_0233_random.in | AC | 59 ms | 4352 KB |
100_003_0787_random.in | AC | 188 ms | 4352 KB |
100_004_0237_random.in | AC | 57 ms | 4352 KB |
100_005_0003_random.in | AC | 4 ms | 3456 KB |
100_006_1000_random.in | AC | 215 ms | 4352 KB |
100_007_1000_random.in | AC | 218 ms | 4352 KB |
100_008_1000_random.in | AC | 229 ms | 4352 KB |
100_009_1000_random.in | AC | 223 ms | 4352 KB |
100_010_1000_random.in | AC | 230 ms | 4352 KB |
100_011_0996_just.in | AC | 676 ms | 4352 KB |
100_012_0997_just.in | AC | 660 ms | 4352 KB |
100_013_0998_just.in | AC | 673 ms | 4352 KB |
100_014_0999_just.in | AC | 665 ms | 4352 KB |
100_015_1000_just.in | AC | 651 ms | 4352 KB |
100_016_0728_almost.in | AC | 498 ms | 4352 KB |
100_017_0811_almost.in | AC | 543 ms | 4352 KB |
100_018_0354_almost.in | AC | 238 ms | 4352 KB |
100_019_0467_almost.in | AC | 311 ms | 4352 KB |
100_020_0053_almost.in | AC | 32 ms | 4352 KB |
100_021_1000_almost.in | AC | 672 ms | 4352 KB |
100_022_1000_almost.in | AC | 650 ms | 4480 KB |
100_023_1000_almost.in | AC | 667 ms | 4352 KB |
100_024_1000_almost.in | AC | 655 ms | 4352 KB |
100_025_1000_almost.in | AC | 650 ms | 4352 KB |
100_026_1000_mixed.in | AC | 522 ms | 4352 KB |
100_027_1000_mixed.in | AC | 349 ms | 4352 KB |
100_028_1000_mixed.in | AC | 289 ms | 4352 KB |
100_029_1000_mixed.in | AC | 371 ms | 4352 KB |
100_030_1000_mixed.in | AC | 266 ms | 4352 KB |
100_031_1000_mixed.in | AC | 408 ms | 4352 KB |
100_032_1000_mixed.in | AC | 399 ms | 4352 KB |
100_033_1000_mixed.in | AC | 589 ms | 4352 KB |
100_034_1000_mixed.in | AC | 342 ms | 4352 KB |
100_035_1000_mixed.in | AC | 422 ms | 4352 KB |