oj.uz

Submission #669143

# Submission time Handle Problem Language Result Execution time Memory
669143 2022-12-05T20:11:04 Z emuyumi Holiday (IOI14_holiday) C++17
100 / 100
 1629 ms 14940 KB 
#include <bits/stdc++.h>
#include "holiday.h"
 
using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MN = 1e5;
 
vector<ll> calc(int n, int src, int ld, const vector<ll> &a){
    vector<ll> ret(4 * MN + 1);
    if (src == n - 1) return ret;
    struct Seg{ int dl, dr, r; };
    vector<Seg> q, nxt = {{1, 3 * (n - 1 - src), n - 1}};
// nxt[0] = {7, 7, n - 1};
    priority_queue<ll> off;
    priority_queue<ll, vector<ll>, greater<ll>> on;
    while (!nxt.empty()){
        swap(nxt, q);
// for (auto [dl, dr, r] : q) cout << dl << " " << dr << " " << r << '\n';
// cout << '\n';
        nxt.clear();
        while (!off.empty()) off.pop();
        while (!on.empty()) on.pop();
        int i = src;
        ll cur = 0;
        for (auto [dl, dr, r] : q){
            int d = (dl + dr) >> 1;
            int k = r;
            while (true){
                while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
                while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
                if (cur > ret[d]) k = i, ret[d] = cur;
// cout << cur << " ";
                if (i == r) break;
                cur += a[++i], on.push(a[i]);
            }
// cout << d << " -> " << ret[d] << '\n';
            if (d != dl) nxt.push_back({dl, d - 1, k});
            if (d != dr) nxt.push_back({d + 1, dr, r});
        }
    }
// cout << "done" << '\n';
    return ret;
}
 
ll solve(int n, int start, int d, vector<ll> a){
    vector<ll> r = calc(n, start, 1, a);
    reverse(a.begin(), a.end()); start = n - start - 1;
    vector<ll> l = calc(n, start, 2, a);
    ll ans = 0;
    for (int i = 0; i <= d; ++i){
        ans = max(ans, l[i] + r[d - i]);
    }
    for (int i = 0; i <= d - 1; ++i){
        ans = max(ans, l[i] + r[(d - 1) - i] + a[start]);
    }
// for (int i = 0; i <= 10; ++i) cout << i << ": " << r[i] << '\n';
    return ans;
}
 
ll findMaxAttraction(int n, int start, int d, int attraction[]){
    vector<ll> vec;
    for (int i = 0; i < n; ++i) vec.push_back(attraction[i]);
    ll ans = solve(n, start, d, vec);
// cout << ans << " ";
    start = n - start - 1;
    reverse(vec.begin(), vec.end());
    ans = max(ans, solve(n, start, d, vec));
// cout << solve(n, start, d, vec) << '\n';
    return ans;
}

Compilation message

holiday.cpp: In function 'std::vector<long long int> calc(int, int, int, const std::vector<long long int>&)':
holiday.cpp:31:67: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |                 while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:32:66: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |                 while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6884 KB Output is correct
2 Correct 5 ms 6884 KB Output is correct
3 Correct 5 ms 6884 KB Output is correct
4 Correct 5 ms 6868 KB Output is correct
5 Correct 5 ms 6880 KB Output is correct
6 Correct 5 ms 7028 KB Output is correct
7 Correct 5 ms 6884 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 14744 KB Output is correct
2 Correct 224 ms 14904 KB Output is correct
3 Correct 302 ms 14888 KB Output is correct
4 Correct 231 ms 14888 KB Output is correct
5 Correct 1486 ms 14816 KB Output is correct
6 Correct 422 ms 9176 KB Output is correct
7 Correct 806 ms 11012 KB Output is correct
8 Correct 963 ms 12092 KB Output is correct
9 Correct 273 ms 8644 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7160 KB Output is correct
2 Correct 10 ms 7124 KB Output is correct
3 Correct 19 ms 7124 KB Output is correct
4 Correct 30 ms 7156 KB Output is correct
5 Correct 26 ms 7124 KB Output is correct
6 Correct 12 ms 7012 KB Output is correct
7 Correct 13 ms 7016 KB Output is correct
8 Correct 12 ms 7012 KB Output is correct
9 Correct 12 ms 6964 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 12788 KB Output is correct
2 Correct 1602 ms 14940 KB Output is correct
3 Correct 621 ms 9920 KB Output is correct
4 Correct 27 ms 7036 KB Output is correct
5 Correct 12 ms 6968 KB Output is correct
6 Correct 12 ms 7024 KB Output is correct
7 Correct 14 ms 6996 KB Output is correct
8 Correct 1627 ms 11980 KB Output is correct
9 Correct 1629 ms 11840 KB Output is correct