Submission #1221658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221658		Tenis0206	Tortoise (CEOI21_tortoise)	C++20	0 / 100	0 ms	328 KiB

tortoise

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e5;

struct candy
{
    int poz, to, val;
};

int n;
int v[nmax + 5];

int st[nmax + 5], dr[nmax + 5];

vector<candy> l;

void debug(vector<candy> a)
{
    for(auto it : a)
    {
        cerr<<it.poz<<' '<<it.to<<' '<<it.val<<'\n';
    }
    cerr<<'\n';
}

bool can_add(int poz, int to)
{
    //debug(l);
    if(!v[poz])
    {
        return false;
    }
    if(poz >= l.back().poz)
    {
        if(to < l.back().to)
        {
            return false;
        }
        int Min = l.back().val + abs(l.back().poz - l.back().to) + abs(l.back().to - poz);
        if(dr[l.back().poz] != 0)
        {
            Min = min(Min, l.back().val + abs(l.back().poz - dr[l.back().poz]) + abs(dr[l.back().poz] - poz));
        }
        if(st[l.back().poz] != 0)
        {
            Min = min(Min, l.back().val + abs(l.back().poz - st[l.back().poz]) + abs(st[l.back().poz] - poz));
        }
        if(Min <= 2 * (poz - 1))
        {
            return true;
        }
        return false;
    }
    int poz_l = 0;
    for(int i=1; i<l.size(); i++)
    {
        if(l[i].poz <= poz)
        {
            poz_l = i;
        }
        else
        {
            break;
        }
    }
    if(l[poz_l].to > to)
    {
        return false;
    }
    if(l[poz_l + 1].to < to)
    {
        return false;
    }
    int Min = l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz);
    if(dr[l[poz_l].poz] != 0)
    {
        Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz));
    }
    if(st[l[poz_l].poz] != 0)
    {
        Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - st[l[poz_l].poz]) + abs(st[l[poz_l].poz] - poz));
    }
    if(Min > 2 * (poz - 1))
    {
        return false;
    }
    int dif = 0;
    if(Min == l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz))
    {
        dif += abs(poz - l[poz_l].to);
        dif += abs(l[poz_l + 1].poz - to);
        dif += abs(poz - to);
        dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
    }
    else if(dr[l[poz_l].poz] != 0 && Min == l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz))
    {
        dif += abs(dr[l[poz_l].poz] - poz);
        dif += abs(l[poz_l + 1].poz - to);
        dif += abs(poz - to);
        dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
        dif -= abs(l[poz_l].poz - l[poz_l].to);
        dif += abs(l[poz_l].poz - dr[l[poz_l].poz]);
    }
    else
    {
        dif += abs(st[l[poz_l].poz] - poz);
        dif += abs(l[poz_l + 1].poz - to);
        dif += abs(poz - to);
        dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
        dif -= abs(l[poz_l].poz - l[poz_l].to);
        dif += abs(l[poz_l].poz - st[l[poz_l].poz]);
    }
    for(int i=poz_l+1; i<l.size(); i++)
    {
        if(l[i].val + dif > 2 * (l[i].poz - 1))
        {
            return false;
        }
    }
    return true;
}

void add(int poz, int to)
{
    if(poz >= l.back().poz)
    {
        int Min = l.back().val + abs(l.back().poz - l.back().to) + abs(l.back().to - poz);
        if(l.size() != 1 && dr[l.back().poz] != 0)
        {
            Min = min(Min, l.back().val + abs(l.back().poz - dr[l.back().poz]) + abs(dr[l.back().poz] - poz));
        }
        if(l.size() != 1 && st[l.back().poz] != 0)
        {
            Min = min(Min, l.back().val + abs(l.back().poz - st[l.back().poz]) + abs(st[l.back().poz] - poz));
        }
        if(l.size() != 1 && dr[l.back().poz] != 0 && Min == l.back().val + abs(l.back().poz - dr[l.back().poz]) + abs(dr[l.back().poz] - poz))
        {
            l[l.size() - 1].to = dr[l.back().poz];
        }
        else if(l.size() != 1 && st[l.back().poz] != 0 && Min == l.back().val + abs(l.back().poz - st[l.back().poz]) + abs(st[l.back().poz] - poz))
        {
            l[l.size() - 1].to = st[l.back().poz];
        }
        l.push_back({poz, to, Min});
        return;
    }
    int poz_l = 0;
    for(int i=1; i<l.size(); i++)
    {
        if(l[i].poz <= poz)
        {
            poz_l = i;
        }
        else
        {
            break;
        }
    }
    int Min = l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz);
    if(poz_l != 0 && dr[l[poz_l].poz] != 0)
    {
        Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz));
    }
    if(poz_l != 0 && st[l[poz_l].poz] != 0)
    {
        Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - st[l[poz_l].poz]) + abs(st[l[poz_l].poz] - poz));
    }
    int dif = 0;
    if(Min == l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz))
    {
        dif += abs(poz - l[poz_l].to);
        dif += abs(l[poz_l + 1].poz - to);
        dif += abs(poz - to);
        dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
    }
    else if(poz_l != 0 && dr[l[poz_l].poz] != 0 && Min == l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz))
    {
        dif += abs(dr[l[poz_l].poz] - poz);
        dif += abs(l[poz_l + 1].poz - to);
        dif += abs(poz - to);
        dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
        dif -= abs(l[poz_l].poz - l[poz_l].to);
        dif += abs(l[poz_l].poz - dr[l[poz_l].poz]);
        l[poz_l].to = dr[l[poz_l].poz];
    }
    else
    {
        dif += abs(st[l[poz_l].poz] - poz);
        dif += abs(l[poz_l + 1].poz - to);
        dif += abs(poz - to);
        dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
        dif -= abs(l[poz_l].poz - l[poz_l].to);
        dif += abs(l[poz_l].poz - st[l[poz_l].poz]);
        l[poz_l].to = st[l[poz_l].poz];
    }
    vector<candy> aux;
    for(int i=0; i<=poz_l; i++)
    {
        aux.push_back(l[i]);
    }
    aux.push_back({poz, to, Min});
    for(int i=poz_l+1; i<l.size(); i++)
    {
        aux.push_back({l[i].poz, l[i].to, l[i].val + dif});
    }
    l = aux;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    for(int i=1; i<=n; i++)
    {
        if(v[i] == -1)
        {
            st[i] = i;
            continue;
        }
        st[i] = st[i - 1];
    }
    for(int i=n; i>=1; i--)
    {
        if(v[i] == -1)
        {
            dr[i] = i;
            continue;
        }
        dr[i] = dr[i + 1];
    }
    vector<pair<int,pair<int,int>>> c;
    for(int i=1; i<=n; i++)
    {
        if(v[i] < 1)
        {
            continue;
        }
        if(st[i] != 0)
        {
            c.push_back({i - st[i], {i, st[i]}});
        }
        if(dr[i] != 0)
        {
            c.push_back({dr[i] - i, {i, dr[i]}});
        }
    }
    sort(c.begin(), c.end());
    l.push_back({1, 1, 0});
    for(auto it : c)
    {
        int poz = it.second.first;
        int to = it.second.second;
        while(can_add(poz, to))
        {
            --v[poz];
            add(poz, to);
        }
    }
    int rez = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i] == -1)
        {
            continue;
        }
        rez += v[i];
    }
    cout<<rez<<'\n';
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27