Submission #789041

#	Time	Username	Problem	Language	Result	Execution time	Memory
789041		stefanneagu	Self Study (JOI22_ho_t2)	C++17	62 / 100	1062 ms	22596 KiB

Main

#include <iostream>
#include <set>
#include <algorithm>
 
using namespace std;
 
const int nmax = 3e5 + 7;
 
int v[nmax], b[nmax], cnt[nmax], n, k;
long long unu = 1;

struct pairing {
    long long first;
    int second;
    const bool operator < (pairing a) const {
        if(first != a.first) {
            return first < a.first;
        } else {
            return second > a.second;
        }
    }
};
 
bool check(long long x) {
    long long sum = 0;
    for(int i = 1; i <= n; i ++) {
        long long curr = x / v[i];
        if(v[i] * curr < x) {
            curr ++;
        }
        sum += curr;
    }
    if(sum <= n * k) {
        return 1;
    }
    return 0;
}
 
int32_t main() {
    int test = 1;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        cin >> v[i];
    } 
    for(int i = 1; i <= n; i ++){
        cin >> b[i];
        if(v[i] != b[i]) {
            test = 1;
        }
    }
    if(!test) {
        long long l = 0, r = 1e18;
        while(l < r) {
            long long mid = (l + r) / 2;
            if(check(mid) == 1) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << max(unu, r);
        return 0;
    }
    set<pairing> pq;
    for(int i = 1; i <= n; i ++) {
        pq.insert({max(v[i], b[i]), i});
        cnt[i] = 1;
    }
    for(int i = 2; i <= k; i ++) {
        for(int j = 1; j <= n; j ++) {
            pairing curr = *(pq.begin());
            long long sum = curr.first;
            int ind = curr.second;
            pq.erase({sum, ind});
            if(cnt[ind] < k) {
                sum += max(v[ind], b[ind]);
                cnt[ind] ++;
            } else {
                sum +=  b[ind];
            }
            pq.insert({sum, ind});
        }
    } 
    long long 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: 27 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 9