oj.uz

Submission #875346

# Submission time Handle Problem Language Result Execution time Memory
875346 2023-11-19T07:47:44 Z deadeye0 Topical (NOI23_topical) C++17
100 / 100
 684 ms 136724 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
int n, k;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n >> k;
    vector<vector<int>> r(n, vector<int>(k));
    vector<vector<int>> u(n, vector<int>(k));
    vector<int> cnt(n, k);
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        ll sum = 0;
        for (int j = 0; j < k; ++j) cin >> r[i][j], sum += r[i][j];
        if (!sum) q.push(i), cnt[i] = 0;
    }   
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) cin >> u[i][j];
    }   
    vector<vector<int>> order(k, vector<int>(n));
    for (int i = 0; i < k; ++i) {
        iota(order[i].begin(), order[i].end(), 0);
        sort(order[i].begin(), order[i].end(), [&](int x, int y) {
            return r[x][i] < r[y][i];
        });
    }
    vector<ll> cur(k);
    vector<int> id(k);
    int ans = 0;
    while (q.size()) {
        int x = q.front(); q.pop();
        ++ans;
        for (int j = 0; j < k; ++j) {
            cur[j] += u[x][j];
            while (id[j] < n && cur[j] >= r[order[j][id[j]]][j]) {
                if (!--cnt[order[j][id[j]]]) q.push(order[j][id[j]]);
                ++id[j];
            }
        }
    }
    cout << ans;
    return 0;
}

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 2 ms 1192 KB Output is correct
4 Correct 172 ms 86432 KB Output is correct
5 Correct 187 ms 86212 KB Output is correct
6 Correct 183 ms 86280 KB Output is correct
7 Correct 141 ms 80616 KB Output is correct

Subtask #2
28.0 / 28.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 388 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 2 ms 728 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 604 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 4 ms 1724 KB Output is correct
4 Correct 41 ms 13908 KB Output is correct
5 Correct 39 ms 13656 KB Output is correct
6 Correct 677 ms 136492 KB Output is correct
7 Correct 675 ms 135080 KB Output is correct
8 Correct 684 ms 136724 KB Output is correct
9 Correct 678 ms 134996 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 2 ms 1192 KB Output is correct
4 Correct 172 ms 86432 KB Output is correct
5 Correct 187 ms 86212 KB Output is correct
6 Correct 183 ms 86280 KB Output is correct
7 Correct 141 ms 80616 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 388 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 348 KB Output is correct
14 Correct 2 ms 728 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 728 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 4 ms 1724 KB Output is correct
23 Correct 41 ms 13908 KB Output is correct
24 Correct 39 ms 13656 KB Output is correct
25 Correct 677 ms 136492 KB Output is correct
26 Correct 675 ms 135080 KB Output is correct
27 Correct 684 ms 136724 KB Output is correct
28 Correct 678 ms 134996 KB Output is correct
29 Correct 207 ms 30708 KB Output is correct
30 Correct 212 ms 29768 KB Output is correct
31 Correct 327 ms 34248 KB Output is correct
32 Correct 142 ms 21416 KB Output is correct
33 Correct 163 ms 22288 KB Output is correct
34 Correct 200 ms 22916 KB Output is correct
35 Correct 306 ms 30796 KB Output is correct
36 Correct 231 ms 25992 KB Output is correct
37 Correct 255 ms 28764 KB Output is correct
38 Correct 139 ms 23204 KB Output is correct