oj.uz

답안 #890538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890538 2023-12-21T12:25:47 Z htphong0909 휴가 (IOI14_holiday) C++17
100 / 100
 1151 ms 6108 KB 
#include <bits/stdc++.h>
using namespace std;
 
set<pair<int, int>> chosen;
set<pair<int, int>, greater<>> have;
long long curSum = 0;
int lt = 1;
int rt = 0;
int n, d, start;
int du;
int arr[100001];
long long ans = -1e18;
 
void giveToHave()
{
    du++;
    have.insert(*chosen.begin());
    curSum -= chosen.begin()->first;
    chosen.erase(chosen.begin());
}
 
void giveToChosen()
{
    du--;
    chosen.insert(*have.begin());
    curSum += have.begin()->first;
    have.erase(have.begin());
}
 
void Add(int x)
{
    have.insert(make_pair(arr[x], x));
}
 
void Del(int x)
{
    if (chosen.find(make_pair(arr[x], x)) != chosen.end())
    {
        chosen.erase(make_pair(arr[x], x));
        curSum -= arr[x];
        du++;
    }
    else have.erase(make_pair(arr[x], x));
}
 
int calcDis(int l, int r)
{
    if (l > r) return 0;
    if (start <= l) return(l - start + (r - l));
    if (start >= r) return(start - r + (r - l));
    return (min(start - l, r - start) + (r - l));
}
 
void stable()
{
    while (du < 0 && !chosen.empty()) giveToHave();
    while ((du > 0 && !have.empty())) giveToChosen();
    while (!have.empty() && !chosen.empty() && have.begin()->first > chosen.begin()->first) giveToHave(), giveToChosen();
}
 
long long cost(int l, int r)
{
    while (lt != l || rt != r)
    {
        while (rt < r)
        {
            du += calcDis(lt, rt) - calcDis(lt, rt + 1);
            rt++;
            Add(rt);
            stable();
        }
        while (rt > lt && rt > r)
        {
            du += calcDis(lt, rt) - calcDis(lt, rt - 1);
            Del(rt);
            rt--;
            stable();
        }
        while (lt < rt && lt < l)
        {
            du += calcDis(lt, rt) - calcDis(lt + 1, rt);
            Del(lt);
            lt++;
            stable();
        }
        while (lt > l)
        {
            du += calcDis(lt, rt) - calcDis(lt - 1, rt);
            lt--;
            Add(lt);
            stable();
        }
    }
    return curSum;
}
 
void divide(int l, int r, int gL, int gR)
{
    if (l > r) return;
    int mid = (l + r) / 2;
    long long bestCost = -1e18;
    int bestPos = gL;
    for (int i = gL; i <= min(mid, gR); i++)
    {
        if (cost(i, mid) > bestCost)
        {
            bestCost = cost(i, mid);
            bestPos = i;
        }
    }
    ans = max(ans, bestCost);
    divide(l, mid - 1, gL, bestPos);
    divide(mid + 1, r, bestPos, gR);
}
 
long long findMaxAttraction(int _n, int _start, int _d, int *attraction)
{
    n = _n;
    d = _d;
    start = _start + 1;
    for (int i = 1; i <= n; i++) arr[i] = attraction[i - 1];
    du = d;
    divide(1, n, 1, n);
    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 406 ms 6108 KB Output is correct
2 Correct 406 ms 5848 KB Output is correct
3 Correct 429 ms 5848 KB Output is correct
4 Correct 408 ms 5712 KB Output is correct
5 Correct 887 ms 5452 KB Output is correct
6 Correct 162 ms 2128 KB Output is correct
7 Correct 403 ms 3480 KB Output is correct
8 Correct 695 ms 4120 KB Output is correct
9 Correct 111 ms 1872 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 860 KB Output is correct
2 Correct 8 ms 860 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 17 ms 856 KB Output is correct
5 Correct 14 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 5 ms 604 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 409 ms 6100 KB Output is correct
2 Correct 363 ms 5876 KB Output is correct
3 Correct 294 ms 2136 KB Output is correct
4 Correct 14 ms 856 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 5 ms 868 KB Output is correct
8 Correct 1140 ms 4836 KB Output is correct
9 Correct 1151 ms 4840 KB Output is correct