Submission #1279341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279341		Hisu	Topical (NOI23_topical)	C++20	100 / 100	380 ms	136468 KiB

Main

// Chaiyo...
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ed "\n"
#define int long long

const int N = 2e5 + 5;

void solve(int iTest){
    int n, k; cin >> n >> k;
    vector<vector<int>> r(n + 2, vector<int> (k + 2, 0));
    vector<vector<int>> u(n + 2, vector<int> (k + 2, 0));
    vector<int> p(k + 2, 0), cnt(n + 2, 0), ptr(k + 2, 0);
    vector<vector<pair<int, int>>> s(k + 2);

    queue<int> q;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            cin >> r[i][j];
        }

        for(int j = 1; j <= k; j++) {
            s[j].push_back({r[i][j], i});
            if(r[i][j] <= p[j]) cnt[i]++;
        }

        if(cnt[i] == k) q.push(i);
    }

    for(int i = 1; i <= k; i++) {
        sort(s[i].begin(), s[i].end());
        while(ptr[i] < n && s[i][ptr[i]].first <= p[i]) ptr[i]++;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            cin >> u[i][j];
        }
    }

    int ans = 0;
    while(q.size()) {
        int id = q.front(); q.pop();
        ans++;
//        cout << id << ed;

        for(int i = 1; i <= k; i++)
            p[i] += u[id][i];

//        for(int i = 1; i <= k; i++) cout << p[i] << ' ';
//        cout << ed;

        for(int i = 1; i <= k; i++) {
            while(ptr[i] < n && s[i][ptr[i]].first <= p[i]) {
                cnt[s[i][ptr[i]].second]++;

                if(cnt[s[i][ptr[i]].second] == k)
                    q.push(s[i][ptr[i]].second);

                ptr[i]++;
            }
        }
    }

    cout << ans;
}

#define TASK "main"

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if(fopen(TASK ".inp","r")){
        freopen(TASK ".inp","r",stdin);
        freopen(TASK ".out","w",stdout);
    }
    else if(fopen("main.inp","r")){
        freopen("main.inp","r",stdin);
        freopen("main.out","w",stdout);
    }

    int T = 1;
//    cin >> T;
    for(int iTest = 1; iTest <= T; iTest++){
        solve(iTest);
    }
}

/**
**/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(TASK ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(TASK ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen("main.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("main.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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