oj.uz

Submission #789027

# Submission time Handle Problem Language Result Execution time Memory
789027 2023-07-20T21:36:38 Z stefanneagu Self Study (JOI22_ho_t2) C++17
0 / 100
 368 ms 26188 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 = 0;
    for(int i = 1; i <= n; i ++) {
        int 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 = 0;
    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 = 1;
        }
    }
    if(!test) {
        sort(v + 1, v + n + 1);
        int l = 0, r = 1e18;
        while(l < r) {
            int mid = (l + r) / 2;
            if(check(mid) == 1) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        while(check(r) == 0 && 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 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 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 596 KB Output is correct
11 Correct 294 ms 25988 KB Output is correct
12 Correct 328 ms 26188 KB Output is correct
13 Correct 180 ms 26108 KB Output is correct
14 Correct 181 ms 26016 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 368 ms 26076 KB Output is correct
17 Correct 335 ms 26040 KB Output is correct
18 Incorrect 364 ms 26024 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 368 ms 26076 KB Output is correct
3 Correct 335 ms 26040 KB Output is correct
4 Incorrect 364 ms 26024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 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 596 KB Output is correct
11 Correct 294 ms 25988 KB Output is correct
12 Correct 328 ms 26188 KB Output is correct
13 Correct 180 ms 26108 KB Output is correct
14 Correct 181 ms 26016 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 368 ms 26076 KB Output is correct
17 Correct 335 ms 26040 KB Output is correct
18 Incorrect 364 ms 26024 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 368 ms 26076 KB Output is correct
3 Correct 335 ms 26040 KB Output is correct
4 Incorrect 364 ms 26024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 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 596 KB Output is correct
11 Correct 294 ms 25988 KB Output is correct
12 Correct 328 ms 26188 KB Output is correct
13 Correct 180 ms 26108 KB Output is correct
14 Correct 181 ms 26016 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 368 ms 26076 KB Output is correct
17 Correct 335 ms 26040 KB Output is correct
18 Incorrect 364 ms 26024 KB Output isn't correct
19 Halted 0 ms 0 KB -