Submission #788642

#	Time	Username	Problem	Language	Result	Execution time	Memory
788642		stefanneagu	Self Study (JOI22_ho_t2)	C++17	35 / 100	1071 ms	25204 KiB

Main

#include <iostream>
#include <set>
#define int long long

using namespace std;

const int nmax = 3e5 + 7;

int v[nmax], b[nmax];

struct pairing {
    int first, second;
    const bool operator < (pairing a) const {
        if(first != a.first) {
            return first < a.first;
        } else {
            return second > a.second;
        }
    }
};

int32_t main() {
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        cin >> v[i];
    } 
    for(int i = 1; i <= n; i ++){
        cin >> b[i];
    }
    set<pairing> pq;
    for(int i = 1; i <= n; i ++) {
        pq.insert({max(v[i], b[i]), i});
    }
    for(int i = 2; i <= k; i ++) {
        for(int j = 1; j <= n; j ++) {
            pairing curr = *(pq.begin());
            int sum = curr.first, ind = curr.second;
            if(pq.find({sum, j}) != pq.end()) {
                ind = j;
            }
            pq.erase({sum, ind});
            if(j == ind) {
                sum += max(v[j], b[j]);
            } else {
                sum +=  b[ind];
            }
            pq.insert({sum, ind});
        }
    } 
    int minn = 1e18;
    for(auto it : pq) {
        // cout << it.first << " " << it.second << endl;
        minn = min(minn, it.first);
    }
    cout << minn;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 9