Submission #1093918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093918		Roumak77	Topical (NOI23_topical)	C++17	100 / 100	511 ms	43576 KiB

Main

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;


void subtask1(ll n, ll k){

    for(ll i = 0; i < k; i++){
        ll temp;
        cin >> temp;
        if(temp > 0){
            cout << 0 << endl;
            return;
        }
    }

    cout << 1 << endl;

}


void subtask3(ll n, ll k){
    vector<pair<ll, ll>> list_n(n, {0, 0});

    for(ll i = 0; i < n; i++){
        cin >> list_n[i].first;
    }

    for(ll i = 0; i < n; i++){
        cin >> list_n[i].second;
    }

    sort(list_n.begin(), list_n.end());

    ll curr = 0;

    for(ll i = 0; i < n; i++){
        if(list_n[i].first <= curr){
            curr += list_n[i].second;
        }else{
            cout << i << endl;
            return;
        }
    }
    cout << n << endl;
}

void subtask2(ll n, ll k){
    vector<bool> vis(n, false);
    vector<vector<pair<ll, ll>>> list_n(n, vector<pair<ll, ll>>(k, {0, 0}));
    ll cnt = 0;
    vector<ll> curr(k, 0);
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < k; j++){
            cin >> list_n[i][j].first;
        }
    }
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < k; j++){
            cin >> list_n[i][j].second;
        }
    }

    while(cnt != n){
        bool add = false;
        for(ll i = 0; i < n; i++){
            if(vis[i]){
                continue;
            }

            bool pos = true;
            for(ll j = 0; j < k; j++){
                if(curr[j] < list_n[i][j].first){
                    pos = false;
                    break;
                }
            }

            if(!pos){
                continue;
            }
            for(ll j = 0; j < k; j++){
                curr[j] += list_n[i][j].second;
            }
            vis[i] = true;
            add=true;
            cnt++;
        }
        if(!add){
            break;
        }
    }

    cout << cnt << endl;

}

void subtask4(ll n, ll k){


    queue<ll> q;
    vector<vector<pair<ll, ll>>> sort_list(k, vector<pair<ll, ll>>(n, {0, 0})); // The value of cost, idx
    vector<vector<ll>> list_n(n, vector<ll>(k, 0)); // The value of up_cost
    vector<ll> curr(k, 0);
    vector<ll> curr_taken(k, 0);
    vector<ll> temp(n, 0);
    ll cnt = 0;
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < k; j++){
            cin >> sort_list[j][i].first;
            sort_list[j][i].second = i;

            if(sort_list[j][i].first <= curr[j]){
                temp[i]++;

                curr_taken[j]++;
                //cout << "temp " << i << " : " << temp[i] << " " << n <<  " " << (temp[i] == n) << endl;
                if(temp[i] == k){
                    //cout << "temp " << i << " : " << temp[i] << endl;
                    q.push(i);
                }
            }
        }
    }
    for(ll i = 0; i < k; i++){
        sort(sort_list[i].begin(), sort_list[i].end());
    }
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < k; j++){
            cin >> list_n[i][j];
        }
    }

    while(!q.empty()){
        ll idx = q.front();
        q.pop();
        cnt++;
        for(ll i = 0; i < k; i++){
            curr[i] += list_n[idx][i];

            while(curr_taken[i] != n){
                if(sort_list[i][curr_taken[i]].first <= curr[i]){
                    temp[sort_list[i][curr_taken[i]].second]++;
                    if(temp[sort_list[i][curr_taken[i]].second] == k){
                        q.push(sort_list[i][curr_taken[i]].second);
                    }
                    curr_taken[i]++;
                }else{
                    break;
                }
            }
        }
    }

    cout << cnt << endl;



}

void solve(){

    ll n, k;
    cin >> n >> k;

    if(n == 1){
        subtask1(n, k);
        return;
    }else if(k == 1){
        subtask3(n, k);
    }else if(n <= 100 && k <= 100){
        subtask4(n, k);
    }else{
        subtask4(n, k);
    }

}

bool single = true;

int main(){

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

    ll t = 1;
    if(!single) cin >> t;

    while(t--){
        solve();
    }
}

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