Submission #1104443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104443		andrei_iorgulescu	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1948 ms	238120 KiB

prison

#include <bits/stdc++.h>
 
using namespace std;
 
using ld = long double;
 
ld eps = 0.000001d;
 
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);
    if (f[nod].empty())
        dp[nod].val = c, dp[nod].cate = 1;
    else
    {
        copacel var2;
        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];
            }
        }
        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();
    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: 25 / 25
• Subtask 6: 20 / 20