oj.uz

Submission #888461

# Submission time Handle Problem Language Result Execution time Memory
888461 2023-12-17T13:31:58 Z vjudge1 Topical (NOI23_topical) C++17
100 / 100
 350 ms 164792 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> a, b;
vector<pair<int, int>> g[1000005];
long long int c[1000005], d[1000005], f[1000005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    a = vector<vector<int>> (n + 1, vector<int>(k + 1, 0));
    b = vector<vector<int>> (n + 1, vector<int>(k + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> a[i][j];
            g[j].push_back({a[i][j], i});
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> b[i][j];
        }
    }
    for (int i = 1; i <= k; i++) {
        sort(g[i].begin(), g[i].end());
    }
    int res = 0;
    while (1) {
        int flag = 0;
        for (int i = 1; i <= k; i++) {
            while (c[i] < n && f[i] >= g[i][c[i]].first) {
                int h = g[i][c[i]].second;
                d[h]++;
                if (d[h] == k) {
                    for (int j = 1; j <= k; j++) {
                        f[j] += b[h][j];
                    }
                    flag = 1;
                    res++;
                }
                c[i]++;
            }
        }
        if (flag == 0) break;
    }
    cout << res;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24664 KB Output is correct
2 Correct 6 ms 24668 KB Output is correct
3 Correct 7 ms 25180 KB Output is correct
4 Correct 191 ms 98172 KB Output is correct
5 Correct 207 ms 98020 KB Output is correct
6 Correct 196 ms 98020 KB Output is correct
7 Correct 163 ms 77436 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24668 KB Output is correct
2 Correct 6 ms 24668 KB Output is correct
3 Correct 6 ms 24540 KB Output is correct
4 Correct 6 ms 24664 KB Output is correct
5 Correct 6 ms 24668 KB Output is correct
6 Correct 6 ms 24668 KB Output is correct
7 Correct 9 ms 24924 KB Output is correct
8 Correct 10 ms 24924 KB Output is correct
9 Correct 8 ms 24980 KB Output is correct
10 Correct 8 ms 24948 KB Output is correct
11 Correct 8 ms 24924 KB Output is correct
12 Correct 9 ms 24916 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24664 KB Output is correct
2 Correct 6 ms 24664 KB Output is correct
3 Correct 9 ms 26204 KB Output is correct
4 Correct 40 ms 38588 KB Output is correct
5 Correct 37 ms 38600 KB Output is correct
6 Correct 350 ms 164792 KB Output is correct
7 Correct 348 ms 163636 KB Output is correct
8 Correct 337 ms 164792 KB Output is correct
9 Correct 324 ms 163252 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24664 KB Output is correct
2 Correct 6 ms 24668 KB Output is correct
3 Correct 7 ms 25180 KB Output is correct
4 Correct 191 ms 98172 KB Output is correct
5 Correct 207 ms 98020 KB Output is correct
6 Correct 196 ms 98020 KB Output is correct
7 Correct 163 ms 77436 KB Output is correct
8 Correct 5 ms 24668 KB Output is correct
9 Correct 6 ms 24668 KB Output is correct
10 Correct 6 ms 24540 KB Output is correct
11 Correct 6 ms 24664 KB Output is correct
12 Correct 6 ms 24668 KB Output is correct
13 Correct 6 ms 24668 KB Output is correct
14 Correct 9 ms 24924 KB Output is correct
15 Correct 10 ms 24924 KB Output is correct
16 Correct 8 ms 24980 KB Output is correct
17 Correct 8 ms 24948 KB Output is correct
18 Correct 8 ms 24924 KB Output is correct
19 Correct 9 ms 24916 KB Output is correct
20 Correct 6 ms 24664 KB Output is correct
21 Correct 6 ms 24664 KB Output is correct
22 Correct 9 ms 26204 KB Output is correct
23 Correct 40 ms 38588 KB Output is correct
24 Correct 37 ms 38600 KB Output is correct
25 Correct 350 ms 164792 KB Output is correct
26 Correct 348 ms 163636 KB Output is correct
27 Correct 337 ms 164792 KB Output is correct
28 Correct 324 ms 163252 KB Output is correct
29 Correct 208 ms 60888 KB Output is correct
30 Correct 209 ms 57972 KB Output is correct
31 Correct 255 ms 66168 KB Output is correct
32 Correct 156 ms 51796 KB Output is correct
33 Correct 169 ms 50516 KB Output is correct
34 Correct 195 ms 53844 KB Output is correct
35 Correct 232 ms 62368 KB Output is correct
36 Correct 196 ms 56860 KB Output is correct
37 Correct 220 ms 60180 KB Output is correct
38 Correct 152 ms 54768 KB Output is correct