oj.uz

Submission #575862

# Submission time Handle Problem Language Result Execution time Memory
575862 2022-06-11T11:41:08 Z 2fat2code Holiday (IOI14_holiday) C++17
100 / 100
 1860 ms 15128 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 100005;
const int dmax = 300005;

long long n, nn, start, d, curr, dp[4][dmax];
vector<long long>compress;
pair<long long, long long>tree[4 * nmax];

void update(int l, int r, int pos, pair<long long, long long>val, int nod){
    if(l == r){
        if(val.sc == 1LL) tree[nod].fr += val.fr;
        else tree[nod].fr -= val.fr;
        tree[nod].sc += val.sc;
    }
    else{
        int mid = l + (r - l) / 2;
        if(pos <= mid) update(l, mid, pos, val, 2*nod);
        else update(mid+1, r, pos, val, 2*nod + 1);
        tree[nod].fr = (tree[2 * nod].fr + tree[2 * nod + 1].fr);
        tree[nod].sc = (tree[2 * nod].sc + tree[2 * nod + 1].sc);
    }
}


long long query(int l, int r, long long nrelemente, int nod){
    if(l == r){
        return compress[l - 1] * min(nrelemente, tree[nod].sc);
    }
    else{
        int mid = l + (r - l) / 2;
        if(tree[2*nod + 1].sc >= nrelemente){
            return query(mid + 1, r, nrelemente, 2*nod + 1);
        }
        else{
            return tree[2*nod + 1].fr + query(l, mid, nrelemente - tree[2*nod+1].sc, 2*nod);
        }
    }
}

void O_o(int l_time, int r_time, int l_interval, int r_interval, long long penalty, vector<long long>&arr, int indx){
    if(r_time < l_time) return;
    else{
        int mid = l_time + (r_time - l_time) / 2;
        long long maxi = -1, position = l_interval;
        for(int i=l_interval;i<=r_interval;i++){
            auto it = lower_bound(all(compress), arr[i]) - compress.begin();
            update(1, nn, it + 1, {compress[it], 1}, 1);
            long long curr = mid - i * penalty;
            if(curr >= 0){
                long long lmao = query(1, nn, curr, 1);
                if(maxi < lmao){
                    maxi = lmao;
                    position = i;
                }
            }
        }
        dp[indx][mid] = maxi;
        for(int i=r_interval;i>=position;i--){
            auto it = lower_bound(all(compress), arr[i]) - compress.begin();
            update(1, nn, it + 1, {compress[it], -1}, 1);
        }
        O_o(mid + 1, r_time, position, r_interval, penalty, arr, indx);
        for(int i=position-1;i>=l_interval;i--){
            auto it = lower_bound(all(compress), arr[i]) - compress.begin();
            update(1, nn, it + 1, {compress[it], -1}, 1);
        }
        O_o(l_time, mid - 1, l_interval, position, penalty, arr, indx);
    }
}

long long findMaxAttraction(int n, int start, int d, int a[]) {
    vector<long long>attraction;
    for(int i=0;i<n;i++) attraction.push_back(a[i]);
    for(auto it : attraction){
        compress.push_back(it);
    }
    compress.push_back(0);
    sort(all(compress));
    compress.resize(unique(all(compress)) - compress.begin());
    nn = (int)compress.size();
    vector<long long>lmao;
    for(int i=start;i<n;i++) lmao.push_back(attraction[i]);
    O_o(0, d, 0, lmao.size() - 1, 1, lmao, 0);
    lmao[0] = 0;
    O_o(0, d, 0, lmao.size() - 1, 2, lmao, 1);
    lmao.clear();
    for(int i=start;i>=0;i--) lmao.push_back(attraction[i]);
    O_o(0, d, 0, lmao.size() - 1, 1, lmao, 2);
    lmao[0] = 0;
    O_o(0, d, 0, lmao.size() - 1, 2, lmao, 3);
    long long ans = 0;
    for(int i=0;i<=d;i++){
        ans = max(ans, dp[0][i] + dp[3][d - i]);
        ans = max(ans, dp[2][i] + dp[1][d - i]);
    }
    return ans; 
}

// 1. Solve the problem
// 2. ???
// 3. Profit!

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 9396 KB Output is correct
2 Correct 51 ms 9404 KB Output is correct
3 Correct 129 ms 9392 KB Output is correct
4 Correct 87 ms 9388 KB Output is correct
5 Correct 584 ms 6980 KB Output is correct
6 Correct 278 ms 7184 KB Output is correct
7 Correct 325 ms 4800 KB Output is correct
8 Correct 395 ms 4876 KB Output is correct
9 Correct 201 ms 8704 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1108 KB Output is correct
2 Correct 5 ms 980 KB Output is correct
3 Correct 29 ms 1116 KB Output is correct
4 Correct 28 ms 1044 KB Output is correct
5 Correct 26 ms 1028 KB Output is correct
6 Correct 7 ms 788 KB Output is correct
7 Correct 6 ms 724 KB Output is correct
8 Correct 6 ms 784 KB Output is correct
9 Correct 4 ms 768 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 10992 KB Output is correct
2 Correct 1452 ms 15128 KB Output is correct
3 Correct 675 ms 4244 KB Output is correct
4 Correct 23 ms 980 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 6 ms 800 KB Output is correct
7 Correct 4 ms 708 KB Output is correct
8 Correct 1860 ms 9908 KB Output is correct
9 Correct 1857 ms 9772 KB Output is correct