oj.uz

Submission #789014

# Submission time Handle Problem Language Result Execution time Memory
789014 2023-07-20T21:07:10 Z stefanneagu Self Study (JOI22_ho_t2) C++17
0 / 100
 284 ms 26496 KB 
#include <iostream>
#include <set>
#include <algorithm>
#define int long long

using namespace std;

const int nmax = 3e5 + 7;

int v[nmax], b[nmax], cnt[nmax], n, k;

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

bool check(int x) {
    int sum = x;
    for(int i = 2; i <= n; i ++) {
        int curr = (v[1] * x) / v[i];
        if(v[i] * curr < v[1] * 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(b[i] != v[i]) {
            test = 0;
        }
    }
    if(test == 1) {
        sort(v + 1, v + n + 1);
        int l = 0, r = n * k;
        while(l < r) {
            int mid = (l + r) / 2;
            if(check(mid) == 1) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        while(check(r) == 0) {
            r --;
        }
        while(check(r + 1) == 1) {
            r ++;
        }
        cout << 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());
            int sum = curr.first, 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});
        }
    } 
    int minn = 1e18;
    for(auto it : pq) {
        // cout << it.first << " " << it.second << endl;
        minn = min(minn, it.first);
    }
    cout << minn;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 5 ms 700 KB Output is correct
11 Correct 275 ms 26492 KB Output is correct
12 Correct 284 ms 26496 KB Output is correct
13 Correct 186 ms 26480 KB Output is correct
14 Correct 185 ms 26424 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 5 ms 700 KB Output is correct
11 Correct 275 ms 26492 KB Output is correct
12 Correct 284 ms 26496 KB Output is correct
13 Correct 186 ms 26480 KB Output is correct
14 Correct 185 ms 26424 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 5 ms 700 KB Output is correct
11 Correct 275 ms 26492 KB Output is correct
12 Correct 284 ms 26496 KB Output is correct
13 Correct 186 ms 26480 KB Output is correct
14 Correct 185 ms 26424 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -