Submission #1104115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104115	2024-10-22T20:11:12 Z	Kirill22	City (BOI06_city)	C++17	100 / 100	73 ms	19392 KB

city

#include "bits/stdc++.h"
 
using namespace std;
 
void solve() {
    long long n, t;
    int k;
    cin >> n >> t >> k;
    vector<long long> c(k), pref(k + 1);
    for (int i = 0; i < k; i++) {
        cin >> c[i];
        pref[i + 1] = pref[i] + c[i];
    }
    vector<pair<long long, long long>> tmp;
    for (long long x = 4, s = 0, d = 0; ; x += 4, d += 1) {
        tmp.push_back({x, d});
        s += x;
        if (s >= n) {
            break;
        }
    }
    const int m = (int) tmp.size();
//    vector<int> have(m, 0);
//    using T = pair<long long, int>;
//    priority_queue<T, vector<T>, greater<T>> pq;
//    for (int i = 0; i < m; i++) {
//        pq.push({t * tmp[i].second + c[0], i});
////        cout << t << " " << tmp[i].second << endl;
//    }
    long long L = 0, R = (long long) 1e18;
    while (L + 1 < R) {
        long long M = (L + R) / 2;
        long long cnt = 0;
        for (int i = 0, uk = k - 1; i < m; i++) {
            // t * tmp[i].second + c[j] <= M
            while (uk >= 0 && t * tmp[i].second + c[uk] > M) {
                uk--;
            }
            cnt = min(n, cnt + (uk + 1) * tmp[i].first);
        }
        if (cnt >= n) {
            R = M;
        } else {
            L = M;
        }
    }
    long long ans = 0;
    for (int i = 0, uk = k - 1; i < m; i++) {
        // t * tmp[i].second + c[j] <= M
        while (uk >= 0 && t * tmp[i].second + c[uk] > L) {
            uk--;
        }
        n -= (uk + 1) * tmp[i].first;
        ans += tmp[i].first * (pref[uk + 1] + t * tmp[i].second * (uk + 1));
//        cnt = min(n, cnt + uk + 1);
    }
    cout << ans + n * R << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	73 ms	18880 KB	Output is correct
3	Correct	4 ms	980 KB	Output is correct
4	Correct	5 ms	972 KB	Output is correct
5	Correct	6 ms	1488 KB	Output is correct
6	Correct	3 ms	980 KB	Output is correct
7	Correct	70 ms	19392 KB	Output is correct
8	Correct	9 ms	3524 KB	Output is correct
9	Correct	8 ms	1484 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct