# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
969108 | 2024-04-24T13:53:37 Z | TrendBattles | Gym Badges (NOI22_gymbadges) | C++14 | 124 ms | 12172 KB |
//https://oj.uz/problem/view/NOI22_gymbadges #include <bits/stdc++.h> using namespace std; using lli = int64_t; #define INFILE "NOI22_gymbadges.inp" #define OUTFILE "NOI22_gymbadges.ans" int main() { ios::sync_with_stdio(0); cin.tie(0); if (fopen(INFILE, "r")) { freopen(INFILE, "r", stdin); freopen(OUTFILE, "w", stdout); } int N; cin >> N; vector <int> X(N), L(N); for (int& v : X) cin >> v; for (int& v : L) cin >> v; if (*max_element(L.begin(), L.end()) == *min_element(L.begin(), L.end())) { sort(X.begin(), X.end()); int ans = N; lli sum = 0; for (int i = 0; i < N; ++i) { if (sum > L[0]) { ans = i; break; } sum += X[i]; } cout << ans; return 0; } vector <int> order(N); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&] (int u, int v) { return L[u] < L[v]; }); const lli inf = 0x3f3f3f3f3f3f3f3f; vector <lli> dp(N + 1, inf); dp[0] = 0; for (int i = 0; i < N; ++i) { for (int j = N; j; --j) { if (dp[j - 1] <= L[order[i]]) { dp[j] = min(dp[j], dp[j - 1] + X[order[i]]); } } } for (int i = N; i >= 0; --i) { if (dp[i] < inf) { cout << i; return 0; } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 456 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Incorrect | 0 ms | 348 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 111 ms | 4356 KB | Output is correct |
2 | Correct | 106 ms | 4188 KB | Output is correct |
3 | Correct | 106 ms | 4188 KB | Output is correct |
4 | Correct | 106 ms | 4348 KB | Output is correct |
5 | Correct | 111 ms | 4364 KB | Output is correct |
6 | Correct | 124 ms | 4360 KB | Output is correct |
7 | Correct | 99 ms | 4440 KB | Output is correct |
8 | Correct | 102 ms | 4356 KB | Output is correct |
9 | Correct | 101 ms | 4356 KB | Output is correct |
10 | Correct | 107 ms | 4352 KB | Output is correct |
11 | Correct | 91 ms | 4188 KB | Output is correct |
12 | Correct | 96 ms | 4184 KB | Output is correct |
13 | Correct | 94 ms | 11392 KB | Output is correct |
14 | Correct | 92 ms | 11664 KB | Output is correct |
15 | Correct | 98 ms | 11604 KB | Output is correct |
16 | Correct | 112 ms | 12040 KB | Output is correct |
17 | Correct | 100 ms | 12112 KB | Output is correct |
18 | Correct | 107 ms | 12172 KB | Output is correct |
19 | Correct | 100 ms | 12116 KB | Output is correct |
20 | Correct | 104 ms | 12164 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 456 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Incorrect | 0 ms | 348 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 456 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Incorrect | 0 ms | 348 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |