Submission #1313509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313509		prunjuice	Topical (NOI23_topical)	C++20	100 / 100	408 ms	136580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pf push_front
const int mod = 1e9 + 7;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int ans = 0;
    int idx = 0;
    vector <vector <int>> v (n, vector <int> (m)); // knowledge required
    vector <vector <int>> v2 (n, vector <int> (m)); // knowledge gained
    vector <int> v3 (n); // topics
    vector <int> v4 (m, 0); // sliding window
    vector <int> v5 (m, 0); // current knowledge
    vector <bool> v6 (n, false); // used
    deque <vector <pair <int, int>>> dq (m);
    deque <int> dq2;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> v[i][j];
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> v2[i][j];
        }
    }
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            dq[i].pb({v[j][i], j});
        }
    }
    for (int i = 0; i < m; i++){
        sort (dq[i].begin(), dq[i].end());
    }
    for (int i = 0; i < m; i++){
        while (v4[i] < n && dq[i][v4[i]].fi <= v5[i]){
            v3[dq[i][v4[i]].se] += 1;
            if (v3[dq[i][v4[i]].se] == m){
                dq2.pb(dq[i][v4[i]].se);
            }
            v4[i] += 1;
        }
    }
    while (!dq2.empty()){
        idx = dq2.front();
        dq2.pop_front(); 
        if (v6[idx]){
            continue;
        }
        v6[idx] = true;
        ans += 1;
        for (int i = 0; i < m; i++){
            v5[i] += v2[idx][i];
            while (v4[i] < n && dq[i][v4[i]].fi <= v5[i]){
                v3[dq[i][v4[i]].se] += 1;
                if (v3[dq[i][v4[i]].se] == m){
                    dq2.pb(dq[i][v4[i]].se);
                }
                v4[i] += 1;
            }
        }
    }
    cout << ans << endl;
}

• Subtask 1: 12 / 12
• Subtask 2: 28 / 28
• Subtask 3: 21 / 21
• Subtask 4: 39 / 39