oj.uz

Submission #789012

# Submission time Handle Problem Language Result Execution time Memory
789012 2023-07-20T21:02:44 Z stefanneagu Self Study (JOI22_ho_t2) C++17
0 / 100
 284 ms 31912 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;
            }
        }
        cout << r - 1;
        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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 279 ms 31912 KB Output is correct
12 Correct 284 ms 31912 KB Output is correct
13 Correct 197 ms 29916 KB Output is correct
14 Correct 186 ms 29924 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 279 ms 31912 KB Output is correct
12 Correct 284 ms 31912 KB Output is correct
13 Correct 197 ms 29916 KB Output is correct
14 Correct 186 ms 29924 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 279 ms 31912 KB Output is correct
12 Correct 284 ms 31912 KB Output is correct
13 Correct 197 ms 29916 KB Output is correct
14 Correct 186 ms 29924 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -