Submission #1096929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096929		andrei_iorgulescu	The short shank; Redemption (BOI21_prison)	C++14	55 / 100	367 ms	110020 KiB

prison

#include <bits/stdc++.h>

using namespace std;

using ld = long double;

ld eps = 0.001d;

int n, d, t, v[2000005], k[2000005];
int bad;

struct copacel
{
    ld val = 0;
    int cate = 0;
};

copacel dp[2000005];
int sz[2000005];
vector<int> f[2000005];
ld c;

void dfs(int nod)
{
    for (auto fiu : f[nod])
        dfs(fiu);
    copacel var1, var2;
    var1.cate = 1;
    var1.val = c;
    for (auto fiu : f[nod])
    {
        if (dp[fiu].val < sz[fiu])
        {
            var1.cate += dp[fiu].cate;
            var1.val += dp[fiu].val;
        }
        else
            var1.val += sz[fiu];
    }
    if (f[nod].empty())
    {
        dp[nod] = var1;
        return;
    }
    var2.val = var2.cate = 0;
    ld mindif = 1e9;
    for (auto fiu : f[nod])
        mindif = min(mindif, dp[fiu].val - min(dp[fiu].val, (ld)sz[fiu]));
    bool tkn = false;
    for (auto fiu : f[nod])
    {
        if (!tkn and dp[fiu].val - min(dp[fiu].val, (ld)sz[fiu]) == mindif)
        {
            tkn = true;
            var2.cate += dp[fiu].cate;
            var2.val += dp[fiu].val;
        }
        else
        {
            if (dp[fiu].val < sz[fiu])
            {
                var2.cate += dp[fiu].cate;
                var2.val += dp[fiu].val;
            }
            else
                var2.val += sz[fiu];
        }
    }
    if (var1.val < var2.val)
        assert(false);
    if (var1.val <= var2.val)
        dp[nod] = var1;
    else
        dp[nod] = var2;
}

void solve(ld cost)
{
    c = cost;
    for (int i = 1; i <= n; i++)
        dp[i].val = dp[i].cate = 0;
    dfs(1);
}

void ufuf(int nod)
{
    sz[nod] = 1;
    for (auto fiu : f[nod])
    {
        ufuf(fiu);
        sz[nod] += sz[fiu];
    }
}

void build_tree()
{
    vector<pair<int,int>> ranges;
    vector<int> wow;
    for (int i = 1; i <= n; i++)
    {
        wow.push_back(i);
        int j = 0;
        while (!wow.empty())
        {
            int jcur = wow.back();
            if (v[jcur] + i - jcur > t)
                wow.pop_back();
            else
            {
                j = jcur;
                break;
            }
        }
        if (j == i)
            bad++;
        else if (j != 0)
            ranges.push_back({j, i - 1});
    }
    if (ranges.empty())
    {
        n = 0;
        return;
    }
    ranges.push_back({1, n});
    sort(ranges.begin(), ranges.end(), [](pair<int,int> A, pair<int,int> B){
         if (A.first != B.first)
            return A.first < B.first;
         return A.second > B.second;
         });
    n = ranges.size();
    stack<int> stk;
    stk.push(1);
    for (int i = 1; i < n; i++)
    {
        while (ranges[stk.top() - 1].second < ranges[i].first)
            stk.pop();
        f[stk.top()].push_back(i + 1);
        stk.push(i + 1);
    }
    ufuf(1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> d >> t;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    for (int i = 1; i <= n; i++)
        k[i] = v[i] - i;
    build_tree();
    if (n - 1 <= d)
    {
        cout << bad;
        return 0;
    }
    ld st = n, pas = (ld)(1 << 20);
    while (pas >= eps)
    {
        if (st - pas >= 1)
        {
            solve(st - pas);
            if (dp[1].cate <= d)
                st -= pas;
        }
        pas /= 2.0d;
    }
    solve(st);
    ld ans = dp[1].val - (ld)d * st;
    int aa = ans;
    if (ans - (ld)aa >= 0.5d)
        aa++;
    cout << aa + bad;
    return 0;
}

/**
yeah so aliens pe fata
pentru i, imi fac un interval de tipul: "daca pun aici un gate nu o sa se mai revolte i"
in fine, astea au structura de arbore din fericire, deci dupa ce imi fac arborele si aliens, e doar un dp[nod][0/1]
**/

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20