oj.uz

Submission #992216

# Submission time Handle Problem Language Result Execution time Memory
992216 2024-06-04T06:04:35 Z inventiontime Gym Badges (NOI22_gymbadges) C++17
42 / 100
 1189 ms 421820 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;
const int maxn = 5005;

int dp[maxn][maxn];

void solve() {

    int n; cin >> n;
    vti g(n+1);
    loop1(i, n) cin >> g[i][1]; // x
    loop1(i, n) cin >> g[i][2]; // l
    loop1(i, n) g[i][0] = g[i][1] + g[i][2];
    sort(all1(g));
    loop(i, n+1) loop(j, n+1) dp[i][j] = inf;
    loop(i, n+1) dp[i][0] = 0;
    loop1(i, n) {
        loop1(j, n) {
            if(dp[i-1][j-1] <= g[i][2])
                ckmin(dp[i][j], dp[i-1][j-1] + g[i][1]);
            ckmin(dp[i][j], dp[i-1][j]);
        }
    }
    int res = 0;
    loop1(i, n) if(dp[n][i] < inf) res = i;
    cout << res << endl;

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

Subtask #1
15.0 / 15.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1189 ms 421820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 89 ms 193200 KB Output is correct
22 Correct 79 ms 194668 KB Output is correct
23 Correct 122 ms 194340 KB Output is correct
24 Correct 83 ms 194388 KB Output is correct
25 Correct 81 ms 194168 KB Output is correct
26 Correct 78 ms 193308 KB Output is correct
27 Correct 111 ms 195412 KB Output is correct
28 Correct 101 ms 192592 KB Output is correct
29 Correct 77 ms 194384 KB Output is correct
30 Correct 102 ms 196180 KB Output is correct
31 Correct 84 ms 195752 KB Output is correct
32 Correct 97 ms 193216 KB Output is correct
33 Correct 89 ms 194640 KB Output is correct
34 Correct 110 ms 195496 KB Output is correct
35 Correct 92 ms 195256 KB Output is correct
36 Correct 111 ms 195668 KB Output is correct
37 Correct 89 ms 193792 KB Output is correct
38 Correct 89 ms 192984 KB Output is correct
39 Correct 105 ms 194832 KB Output is correct
40 Correct 84 ms 193676 KB Output is correct
41 Correct 118 ms 195668 KB Output is correct
42 Correct 86 ms 193620 KB Output is correct
43 Correct 83 ms 193624 KB Output is correct
44 Correct 95 ms 194896 KB Output is correct
45 Correct 87 ms 194132 KB Output is correct
46 Correct 86 ms 195920 KB Output is correct
47 Correct 84 ms 194388 KB Output is correct
48 Correct 86 ms 194280 KB Output is correct
49 Correct 113 ms 193364 KB Output is correct
50 Correct 90 ms 194388 KB Output is correct

Subtask #4
0 / 49.0

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