oj.uz

Submission #991927

# Submission time Handle Problem Language Result Execution time Memory
991927 2024-06-03T12:15:45 Z KK_1729 Gym Badges (NOI22_gymbadges) C++17
15 / 100
 463 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

bool comp(pair<int, int> x, pair<int, int> y){
    return x.first+x.second < y.first+y.second;
}
void solve(){
    
    int n; cin >> n;
    vector<int> x(n), l(n);
    FOR(i,0,n) cin >> x[i];
    FOR(i,0,n) cin >> l[i];
    
    vector<pair<int, int>> o = {{}};
    FOR(i,0,n) o.pb({x[i], l[i]});
    sort(all(o), comp);
    
    vector<vector<int>> dp(n+1, vector<int>(n+1, 1e17));
    dp[0][0] = 0;
    FOR(i,1,n+1){
        FOR(j,1,i+1){
            dp[i][j] = dp[i-1][j];
            if (dp[i-1][j-1] <= o[i].second) dp[i][j] = min(dp[i][j], dp[i-1][j-1]+o[i].first);
        }
    }
    int ans = 0;
    FOR(i,1,n+1){
        if (dp[n][i] < 1e17) ans = max(ans, i);
    }
    // printVector(dp[n]);
    cout << ans << endl;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int t = 1; // cin >> t;
    while (t--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 412 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 463 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 412 KB Output is correct
21 Correct 100 ms 190292 KB Output is correct
22 Correct 104 ms 193364 KB Output is correct
23 Correct 93 ms 191852 KB Output is correct
24 Correct 93 ms 192476 KB Output is correct
25 Correct 92 ms 192336 KB Output is correct
26 Correct 92 ms 190292 KB Output is correct
27 Correct 99 ms 194644 KB Output is correct
28 Correct 90 ms 188756 KB Output is correct
29 Correct 97 ms 192596 KB Output is correct
30 Correct 99 ms 195924 KB Output is correct
31 Correct 95 ms 195412 KB Output is correct
32 Incorrect 120 ms 189920 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 412 KB Output is correct
21 Runtime error 463 ms 1048580 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -