oj.uz

Submission #933138

# Submission time Handle Problem Language Result Execution time Memory
933138 2024-02-25T06:57:28 Z browntoad Topical (NOI23_topical) C++14
100 / 100
 432 ms 132888 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

const ll maxn = 1e6+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;

int n, k;
vector<pii> nw[maxn];
vector<int> nwptr(maxn);

vector<int> val(maxn);
vector<int> sat(maxn); // how many topics satisfies for each module
vector<vector<int>> bonus;

signed main(){
    IOS();
    cin>>n>>k;

    REP(i, n){
        REP(j, k){
            int x; cin>>x;
            nw[j].pb({x, i});
        }
    }
    REP(j, k) sort(ALL(nw[j]));

    bonus.resize(n);
    REP(i, n){
        bonus[i].resize(k);
        REP(j, k){
            cin>>bonus[i][j];
        }
    }

    // initial
    queue<int> qu;
    REP(j, k){
        for (int &i = nwptr[j]; i < n && nw[j][i].f <= val[j]; i++){
            sat[nw[j][i].s]++;
            if (sat[nw[j][i].s] == k) {
                qu.push(nw[j][i].s);
            }
        }
    }
    int ans = 0;
    while(SZ(qu)){
        ans++;
        int x = qu.front(); qu.pop();
        REP(l, k){
            val[l] += bonus[x][l];
        }

        REP(j, k){
            for (int &i = nwptr[j]; i < n && nw[j][i].f <= val[j]; i++){
                sat[nw[j][i].s]++;
                if (sat[nw[j][i].s] == k) {
                    qu.push(nw[j][i].s);
                }
            }
        }
    }
    cout<<ans<<endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47448 KB Output is correct
2 Correct 12 ms 47448 KB Output is correct
3 Correct 14 ms 47872 KB Output is correct
4 Correct 195 ms 95824 KB Output is correct
5 Correct 188 ms 95784 KB Output is correct
6 Correct 198 ms 95620 KB Output is correct
7 Correct 158 ms 91176 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47452 KB Output is correct
2 Correct 11 ms 47304 KB Output is correct
3 Correct 11 ms 47196 KB Output is correct
4 Correct 11 ms 47196 KB Output is correct
5 Correct 11 ms 47452 KB Output is correct
6 Correct 11 ms 47452 KB Output is correct
7 Correct 12 ms 47708 KB Output is correct
8 Correct 14 ms 47708 KB Output is correct
9 Correct 13 ms 47708 KB Output is correct
10 Correct 14 ms 47708 KB Output is correct
11 Correct 12 ms 47708 KB Output is correct
12 Correct 13 ms 47708 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 47452 KB Output is correct
2 Correct 11 ms 47452 KB Output is correct
3 Correct 14 ms 48096 KB Output is correct
4 Correct 41 ms 56020 KB Output is correct
5 Correct 39 ms 55752 KB Output is correct
6 Correct 421 ms 132312 KB Output is correct
7 Correct 432 ms 128344 KB Output is correct
8 Correct 417 ms 132888 KB Output is correct
9 Correct 415 ms 128172 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47448 KB Output is correct
2 Correct 12 ms 47448 KB Output is correct
3 Correct 14 ms 47872 KB Output is correct
4 Correct 195 ms 95824 KB Output is correct
5 Correct 188 ms 95784 KB Output is correct
6 Correct 198 ms 95620 KB Output is correct
7 Correct 158 ms 91176 KB Output is correct
8 Correct 10 ms 47452 KB Output is correct
9 Correct 11 ms 47304 KB Output is correct
10 Correct 11 ms 47196 KB Output is correct
11 Correct 11 ms 47196 KB Output is correct
12 Correct 11 ms 47452 KB Output is correct
13 Correct 11 ms 47452 KB Output is correct
14 Correct 12 ms 47708 KB Output is correct
15 Correct 14 ms 47708 KB Output is correct
16 Correct 13 ms 47708 KB Output is correct
17 Correct 14 ms 47708 KB Output is correct
18 Correct 12 ms 47708 KB Output is correct
19 Correct 13 ms 47708 KB Output is correct
20 Correct 11 ms 47452 KB Output is correct
21 Correct 11 ms 47452 KB Output is correct
22 Correct 14 ms 48096 KB Output is correct
23 Correct 41 ms 56020 KB Output is correct
24 Correct 39 ms 55752 KB Output is correct
25 Correct 421 ms 132312 KB Output is correct
26 Correct 432 ms 128344 KB Output is correct
27 Correct 417 ms 132888 KB Output is correct
28 Correct 415 ms 128172 KB Output is correct
29 Correct 238 ms 89348 KB Output is correct
30 Correct 219 ms 84560 KB Output is correct
31 Correct 278 ms 86388 KB Output is correct
32 Correct 213 ms 82452 KB Output is correct
33 Correct 215 ms 79212 KB Output is correct
34 Correct 224 ms 81404 KB Output is correct
35 Correct 286 ms 83640 KB Output is correct
36 Correct 252 ms 84924 KB Output is correct
37 Correct 319 ms 88160 KB Output is correct
38 Correct 174 ms 78796 KB Output is correct