oj.uz

Submission #893320

# Submission time Handle Problem Language Result Execution time Memory
893320 2023-12-27T01:49:14 Z vjudge1 Topical (NOI23_topical) C++17
100 / 100
 544 ms 154672 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=1e6;
vector<vector<int>> a,b;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq[N+1];
int cnt[N+1];
int val[N+1];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    a.resize(n+1);
    b.resize(n+1);
    for(int i=1;i<=n;++i)
    {
        a[i].resize(k+1);
        for(int j=1;j<=k;++j)
        {
            cin >> a[i][j];
            pq[j].push({a[i][j], i});
        }
    }
    for(int i=1;i<=n;++i)
    {
        b[i].resize(k+1);
        for(int j=1;j<=k;++j)
        {
            cin >> b[i][j];
            //pq[j].push({a[i][j], i});
        }
    }
    queue<int> q;
    for(int j=1;j<=k;++j)
    {
        while(!pq[j].empty() && pq[j].top().first<=val[j])
        {
            auto p = pq[j].top();
            pq[j].pop();
            cnt[p.second]++;
            if(cnt[p.second]==k) q.push(p.second);
        }
    }
    int kq=0;
    while(!q.empty())
    {
        while(!q.empty())
        {
            kq++;
            int i = q.front();
            q.pop();
            for(int j=1;j<=k;++j) val[j]+=b[i][j];
        }
        for(int j=1;j<=k;++j)
        {
            while(!pq[j].empty() && pq[j].top().first<=val[j])
            {
                auto p = pq[j].top();
                pq[j].pop();
                cnt[p.second]++;
                if(cnt[p.second]==k) q.push(p.second);
            }
        }
    }
    cout << kq;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33112 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 9 ms 33628 KB Output is correct
4 Correct 171 ms 76284 KB Output is correct
5 Correct 170 ms 76112 KB Output is correct
6 Correct 172 ms 76244 KB Output is correct
7 Correct 134 ms 72276 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33116 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 6 ms 33112 KB Output is correct
4 Correct 7 ms 33116 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 7 ms 33116 KB Output is correct
7 Correct 9 ms 33372 KB Output is correct
8 Correct 9 ms 33372 KB Output is correct
9 Correct 9 ms 33372 KB Output is correct
10 Correct 9 ms 33488 KB Output is correct
11 Correct 9 ms 33372 KB Output is correct
12 Correct 10 ms 33372 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33116 KB Output is correct
2 Correct 7 ms 33220 KB Output is correct
3 Correct 11 ms 34504 KB Output is correct
4 Correct 51 ms 45368 KB Output is correct
5 Correct 40 ms 45296 KB Output is correct
6 Correct 461 ms 154672 KB Output is correct
7 Correct 544 ms 152936 KB Output is correct
8 Correct 457 ms 154544 KB Output is correct
9 Correct 536 ms 153012 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33112 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 9 ms 33628 KB Output is correct
4 Correct 171 ms 76284 KB Output is correct
5 Correct 170 ms 76112 KB Output is correct
6 Correct 172 ms 76244 KB Output is correct
7 Correct 134 ms 72276 KB Output is correct
8 Correct 7 ms 33116 KB Output is correct
9 Correct 7 ms 33116 KB Output is correct
10 Correct 6 ms 33112 KB Output is correct
11 Correct 7 ms 33116 KB Output is correct
12 Correct 7 ms 33116 KB Output is correct
13 Correct 7 ms 33116 KB Output is correct
14 Correct 9 ms 33372 KB Output is correct
15 Correct 9 ms 33372 KB Output is correct
16 Correct 9 ms 33372 KB Output is correct
17 Correct 9 ms 33488 KB Output is correct
18 Correct 9 ms 33372 KB Output is correct
19 Correct 10 ms 33372 KB Output is correct
20 Correct 7 ms 33116 KB Output is correct
21 Correct 7 ms 33220 KB Output is correct
22 Correct 11 ms 34504 KB Output is correct
23 Correct 51 ms 45368 KB Output is correct
24 Correct 40 ms 45296 KB Output is correct
25 Correct 461 ms 154672 KB Output is correct
26 Correct 544 ms 152936 KB Output is correct
27 Correct 457 ms 154544 KB Output is correct
28 Correct 536 ms 153012 KB Output is correct
29 Correct 218 ms 51408 KB Output is correct
30 Correct 220 ms 49232 KB Output is correct
31 Correct 300 ms 58760 KB Output is correct
32 Correct 157 ms 51344 KB Output is correct
33 Correct 169 ms 49236 KB Output is correct
34 Correct 215 ms 52044 KB Output is correct
35 Correct 276 ms 58752 KB Output is correct
36 Correct 229 ms 52052 KB Output is correct
37 Correct 260 ms 52048 KB Output is correct
38 Correct 199 ms 58608 KB Output is correct