oj.uz

Submission #1093915

# Submission time Handle Problem Language Result Execution time Memory
1093915 2024-09-28T05:01:55 Z Roumak77 Topical (NOI23_topical) C++17
33 / 100
 216 ms 16104 KB 
#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]++;

                if(temp[i] == n){
                    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] == n){
                        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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 30 ms 460 KB Output is correct
5 Correct 31 ms 348 KB Output is correct
6 Correct 35 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 18 ms 1884 KB Output is correct
5 Correct 17 ms 2036 KB Output is correct
6 Correct 216 ms 16104 KB Output is correct
7 Correct 185 ms 15960 KB Output is correct
8 Correct 193 ms 15960 KB Output is correct
9 Correct 181 ms 15960 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 30 ms 460 KB Output is correct
5 Correct 31 ms 348 KB Output is correct
6 Correct 35 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -