oj.uz

Submission #464349

# Submission time Handle Problem Language Result Execution time Memory
464349 2021-08-13T04:28:19 Z blue Holiday (IOI14_holiday) C++17
100 / 100
 3446 ms 6384 KB 
#include "holiday.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

const int maxN = 100'000;

int N;
int S;
int D;
vector<long long> A;

long long res = 0;

long long high_sum = 0;
multiset<long long> high_values;
multiset<long long> low_values;
int L;
int R;
int can_visit;

void insert_value(long long V)
{
    high_values.insert(V);
    high_sum += V;

    while((int)(high_values.size()) > max(can_visit, 0))
    {
        low_values.insert(*high_values.begin());
        high_sum -= *high_values.begin();
        high_values.erase(high_values.begin());
    }
}

void erase_value(long long V)
{
    if(low_values.find(V) != low_values.end())
    {
        low_values.erase(low_values.find(V));
    }
    else
    {
        high_values.erase(high_values.find(V));
        high_sum -= V;
    }

    while((int)(high_values.size()) + 1 <= can_visit && (int)((int)(low_values.size())) >= 1)
    {
        high_values.insert(*low_values.rbegin());
        high_sum += *low_values.rbegin();
        low_values.erase(low_values.find(*low_values.rbegin()));
    }
}

void expand_right()
{
    can_visit--;

    R++;
    insert_value(A[R]);
}

void contract_right()
{
    can_visit++;

    erase_value(A[R]);
    R--;
}

void expand_left()
{
    can_visit -= 2;

    L--;
    insert_value(A[L]);
}

void contract_left()
{
    can_visit += 2;

    erase_value(A[L]);
    L++;
}

void solve(int l1, int l2, int r1, int r2)
{
    // cerr << "solve " << l1 << ' ' << l2 << ' ' << r1 << ' ' << r2 << '\n';
    int l = (l1+l2)/2;

    while(L-1 >= l)
        expand_left();

    while(R+1 <= max(r1, l))
        expand_right();

    while(L+1 <= l)
        contract_left();

    while(R-1 >= max(r1, l))
        contract_right();

    long long score = high_sum;
    int best_r = R;

    while(R+1 <= r2)
    {
        expand_right();

        if(high_sum > score)
        {
            score = high_sum;
            best_r = R;
        }

        // cerr << L << ' ' << R << ' ' << score << '\n';
        // cerr << can_visit << '\n';
        // for(int a: high_values) cerr << a << ' ';
        // cerr << '\n';
        // cerr << high_sum << '\n';
        // cerr << "\n\n";
    }

    res = max(res, score);

    // cerr << "best_r = " << best_r << '\n';

    if(l1 <= l-1)
        solve(l1, l-1, r1, best_r);
    if(l+1 <= l2)
        solve(l+1, l2, best_r, r2);
}


long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    N = n;
    S = start;
    D = d;
    A = vector<long long>(N);
    for(int i = 0; i < N; i++) A[i] = attraction[i];

    // cerr << "D = " << D << '\n';

    if(D == 0) return 0;

    //part 1: first left, then right

    high_values.insert(A[S]);
    high_sum = A[S];
    L = R = S;
    can_visit = d;

    // cerr << "left, then right\n";
    // cerr << "S = " << S << '\n';

    solve(0, S, 0, N-1);


    reverse(A.begin(), A.end());

    S = N-1 - S;
    high_values.clear();
    low_values.clear();

    // cerr << "new S = " << S << '\n';
    high_values.insert(A[S]);
    high_sum = A[S];
    L = R = S;
    can_visit = d;
    // cerr << "right, then left\n";
    solve(0, S, 0, N-1);

    return res;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 6112 KB Output is correct
2 Correct 260 ms 6100 KB Output is correct
3 Correct 761 ms 6084 KB Output is correct
4 Correct 1078 ms 6080 KB Output is correct
5 Correct 2049 ms 5572 KB Output is correct
6 Correct 210 ms 2124 KB Output is correct
7 Correct 907 ms 3408 KB Output is correct
8 Correct 1320 ms 4044 KB Output is correct
9 Correct 160 ms 1740 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 832 KB Output is correct
2 Correct 9 ms 844 KB Output is correct
3 Correct 11 ms 848 KB Output is correct
4 Correct 34 ms 716 KB Output is correct
5 Correct 28 ms 800 KB Output is correct
6 Correct 8 ms 716 KB Output is correct
7 Correct 9 ms 716 KB Output is correct
8 Correct 13 ms 728 KB Output is correct
9 Correct 11 ms 720 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 6116 KB Output is correct
2 Correct 592 ms 6212 KB Output is correct
3 Correct 750 ms 2892 KB Output is correct
4 Correct 33 ms 796 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 11 ms 716 KB Output is correct
7 Correct 11 ms 720 KB Output is correct
8 Correct 3364 ms 5564 KB Output is correct
9 Correct 3446 ms 6384 KB Output is correct