oj.uz

Submission #789030

# Submission time Handle Problem Language Result Execution time Memory
789030 2023-07-20T21:47:10 Z stefanneagu Self Study (JOI22_ho_t2) C++17
0 / 100
 318 ms 30732 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) {
      int vxx[1000000000000001];
        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;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:51:11: warning: unused variable 'vxx' [-Wunused-variable]
   51 |       int vxx[1000000000000001];
      |           ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 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 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 314 ms 30732 KB Output is correct
12 Correct 313 ms 30632 KB Output is correct
13 Correct 187 ms 29920 KB Output is correct
14 Correct 207 ms 29880 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 318 ms 6152 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 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 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 314 ms 30732 KB Output is correct
12 Correct 313 ms 30632 KB Output is correct
13 Correct 187 ms 29920 KB Output is correct
14 Correct 207 ms 29880 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 318 ms 6152 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 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 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 314 ms 30732 KB Output is correct
12 Correct 313 ms 30632 KB Output is correct
13 Correct 187 ms 29920 KB Output is correct
14 Correct 207 ms 29880 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 318 ms 6152 KB Output isn't correct
17 Halted 0 ms 0 KB -