제출 #1221606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221606		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;
        }
        if(l.back().val + abs(l.back().poz - l.back().to) + abs(l.back().to - poz) <= 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(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
    {
        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]);
    }
    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)
{
    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(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));
    }
    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
    {
        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];
    }
    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