oj.uz

Submission #1005523

# Submission time Handle Problem Language Result Execution time Memory
1005523 2024-06-22T14:48:46 Z vjudge1 Topical (NOI23_topical) C++17
100 / 100
 555 ms 146456 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<ll>> r(n, vector<ll>(k)), u(n, vector<ll>(k));
    vector<vector<pair<ll, int>>> P(k);
    int ans = 0;
    queue<int> q;
    vector<ll> sum(k);
    vector<int> cnt(n), pt(k);
    vector<bool> vis(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            cin >> r[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            cin >> u[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            P[j].push_back(make_pair(r[i][j], i));
        }
    }

    for (int i = 0; i < k; ++i) {
        sort(P[i].begin(), P[i].end());
    }
    int rt = -1;
    for (int i = 0; i < n; ++i) {
        bool al = true;
        for (int j = 0; j < k; ++j) {
            if (r[i][j] > 0) {
                al = false;
                break;
            }
        }
        if (al) {
            rt = i;
            break;
        }
    }

    if (rt == -1) {
        cout << "0" << "\n";
        return 0;
    }
    q.push(rt);
    while (!q.empty()) {
        int nw = q.front();
        q.pop();
        if (vis[nw]) continue;
        vis[nw] = true;
        ans++;
        for (int j = 0; j < k; ++j) {
            sum[j] += u[nw][j];
            while (pt[j] < n && P[j][pt[j]].first <= sum[j]) {
                if (++cnt[P[j][pt[j]].second] == k) {
                    q.push(P[j][pt[j]].second);
                }
                pt[j]++;
            }
        }
    }
    cout << ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 1532 KB Output is correct
4 Correct 369 ms 94004 KB Output is correct
5 Correct 377 ms 94068 KB Output is correct
6 Correct 358 ms 94152 KB Output is correct
7 Correct 264 ms 88352 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 436 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 344 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 860 KB Output is correct
12 Correct 9 ms 860 KB Output is correct

Subtask #3
21.0 / 21.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 7 ms 2004 KB Output is correct
4 Correct 59 ms 15420 KB Output is correct
5 Correct 63 ms 15044 KB Output is correct
6 Correct 555 ms 146456 KB Output is correct
7 Correct 509 ms 145888 KB Output is correct
8 Correct 536 ms 146232 KB Output is correct
9 Correct 507 ms 144092 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 1532 KB Output is correct
4 Correct 369 ms 94004 KB Output is correct
5 Correct 377 ms 94068 KB Output is correct
6 Correct 358 ms 94152 KB Output is correct
7 Correct 264 ms 88352 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 5 ms 860 KB Output is correct
15 Correct 5 ms 860 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 5 ms 860 KB Output is correct
18 Correct 5 ms 860 KB Output is correct
19 Correct 9 ms 860 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 7 ms 2004 KB Output is correct
23 Correct 59 ms 15420 KB Output is correct
24 Correct 63 ms 15044 KB Output is correct
25 Correct 555 ms 146456 KB Output is correct
26 Correct 509 ms 145888 KB Output is correct
27 Correct 536 ms 146232 KB Output is correct
28 Correct 507 ms 144092 KB Output is correct
29 Correct 444 ms 54600 KB Output is correct
30 Correct 437 ms 49448 KB Output is correct
31 Correct 474 ms 55384 KB Output is correct
32 Correct 271 ms 45532 KB Output is correct
33 Correct 337 ms 42280 KB Output is correct
34 Correct 322 ms 45532 KB Output is correct
35 Correct 409 ms 51908 KB Output is correct
36 Correct 367 ms 48396 KB Output is correct
37 Correct 421 ms 51364 KB Output is correct
38 Correct 233 ms 44232 KB Output is correct