제출 #1327004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1327004		yeuler	Exam (eJOI20_exam)	C++20	0 / 100	285 ms	589824 KiB

exam

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb push_back
#define fi first
#define se second
#define vector2d(x) vector<vector<x>>
#define pii pair<int, int>
#define pl pair<ll, ll>
#define kagamine_len ios_base::sync_with_stdio(0); cin.tie(0);
#define file_in freopen("input.txt", "r", stdin);
#define file_out freopen("output.txt", "w", stdout);
#define all(x) x.begin()+1, x.end()

using namespace std;

/*

g++ -std=c++20 NOI23_Topical.cpp -o output/NOI23_Topical.exe
./output/NOI23_Topical.exe


Input
n -> modules, k -> topics
r1,1, ... r1,k
v       -> untuk modul _ perlu knowledge brp di topic _
rn,1, rn,k
u1,1, ... u1,k
v       -> knowledge yg didapatkan stlh selesai modul _ untuk topic _
un,1, un,k


*/

ll n, k;

void sub_1(){
    vector r(n+1, vector<ll>(k+1));
    vector u(n+1, vector<ll>(k+1));
    vector<bool> udh(n+1, 0);

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

    bool can = 1;
    vector<ll> cur(k+1);
    while (can){
        can = 0;
        for (ll i = 1; i <= n; i++){
            if (udh[i]) continue;

            bool req = 1;
            for (ll j = 1; j <= k; j++){
                if (r[i][j] > cur[j]){
                    req = 0;
                    break;
                }
            }

            if (req){
                can = 1;
                udh[i] = 1;
                for (ll j = 1; j <= k; j++){
                    cur[j] += u[i][j];
                }
            }
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= n; i++){
        if (udh[i]) ans++;
    }

    cout << ans << "\n";
}

void solve(){
    vector<ll> r(n+1);
    vector<ll> u(n+1);
    vector<ll> ord(n+1);
    iota(all(ord), 1);

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

    sort(all(ord), [&](ll a, ll b){
        return r[a] < r[b];
    });

    ll cur = 0, ans = 0;
    for (ll i : ord){
        if (r[i] <= cur){
            cur += u[i];
            ans++;
        }
    }

    cout << ans << "\n";
}


int main(){
    kagamine_len

    cin >> n >> k;

    if (k == 1 && n > 100){
        solve();
    }
    else {
        sub_1();
    }

    
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22