제출 #881988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881988		alexdd	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	2049 ms	62176 KiB

route

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
mt19937 rnd(1823764);
int n,k;
int a[1000005];
int inita[1000005];
int root[1000005];
int tole[1000005];
int tori[1000005];
priority_queue<pair<int,int>> pq;
void afis()
{
    /*for(int i=1;i<=n;i++)
        cout<<a[root[i]]<<" ";
    cout<<"\n";*/
    /*for(int i=1;i<=n;i++)
    {
        if(i==1 || root[i]!=root[i-1])
        {
            cout<<root[i]<<"  "<<tole[root[i]]<<" "<<tori[root[i]]<<"  "<<a[root[i]]<<"\n";
        }
    }*/
}
void initializeaza_secvente()
{
    if(a[1]==a[n])
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=a[1])
                break;
            root[i]=1;
            tori[1]=i;
        }
        for(int i=n;i>0;i--)
        {
            if(a[i]!=a[n])
                break;
            root[i]=1;
            tole[1]=i;
        }
        int aux = tori[1]+1;
        root[aux] = aux;
        tole[aux] = aux;
        for(int i=tori[1]+2;i<tole[1];i++)
        {
            if(a[i]!=a[i-1])
            {
                tori[aux]=i-1;
                aux=i;
                tole[i]=i;
            }
            root[i]=aux;
        }
        tori[aux]=tole[1]-1;
    }
    else
    {
        int aux=1;
        root[1]=1;
        tole[1]=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]!=a[i-1])
            {
                tori[aux]=i-1;
                aux=i;
                tole[i]=i;
            }
            root[i]=aux;
        }
        tori[aux]=n;
    }
    for(int i=1;i<=n;i++)
    {
        if(root[i]==i)
        {
            int tol = tole[i]-1;
            if(tol==0)
                tol=n;
            int tor = tori[i]+1;
            if(tor==n+1)
                tor=1;
            if(a[tol]>a[i] && a[tor]>a[i])
            {
                pq.push({-(tori[i]-tole[i]),i});
            }
        }
    }
    //for(int i=1;i<=n;i++)
      //  cout<<root[i]<<" ";
}
void unite(int x, int y)
{
    if(tori[x]-tole[x] <= tori[y]-tole[y])
    {
        tole[y] = tole[x];
        int j = tole[x];
        while(j!=tori[x])
        {
            root[j] = y;
            j++;
            if(j==n+1)
                j=0;
        }
        root[tori[x]] = y;
    }
    else
    {
        tori[x] = tori[y];
        int j = tole[y];
        while(j!=tori[y])
        {
            root[j] = x;
            j++;
            if(j==n+1)
                j=0;
        }
        root[tori[y]] = x;
    }
}
void verif_debug()
{

}
int dp[105][1005][1005];///dp[i][cnt][ult]
int solve_dp()
{
    int mnm=INF;
    for(int primu=0;primu<=k;primu++)
    {
        for(int i=0;i<=k;i++)
            for(int j=0;j<=k;j++)
                dp[1][i][j]=INF;
        dp[1][primu][primu] = 0;
        for(int i=2;i<=n;i++)
        {
            for(int cnt=0;cnt<=k;cnt++)
            {
                for(int u=0;u<=cnt;u++)
                {
                    dp[i][cnt][u] = INF;
                    for(int p=0;p+u<=cnt;p++)
                    {
                        dp[i][cnt][u] = min(dp[i][cnt][u], dp[i-1][cnt-u][p] + abs((a[i]+u) - (a[i-1]+p)));
                    }
                    //if(dp[i][cnt][u]<INF) cout<<i<<" "<<cnt<<" "<<u<<"   "<<dp[i][cnt][u]<<"\n";
                }
            }
        }
        for(int cnt=0;cnt<=k;cnt++)
        {
            for(int u=0;u<=cnt;u++)
            {
                mnm = min(mnm, dp[n][cnt][u] + abs((a[n]+u) - (a[1]+primu)));
            }
        }
    }
    mnm = -mnm;
    for(int i=1;i<n;i++)
        mnm += abs(a[i]-a[i+1]);
    mnm += abs(a[1]-a[n]);
    return mnm;
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cout<<solve_dp();
    return 0;
    while(1)
    {
        for(int i=1;i<=n;i++)
        {
            inita[i] = rnd()%1000000000;
            a[i] = inita[i];
        }
        bool bl=1;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=a[1])
                bl=0;
            if(i>1) sum += abs(a[i]-a[i-1]);
        }
        int rezdp = solve_dp();
        sum += abs(a[1]-a[n]);
        if(bl)
        {
            cout<<0;
            return 0;
        }
        initializeaza_secvente();

        while(!pq.empty())
        {
            verif_debug();
            int x = pq.top().second;
            pq.pop();
            cout<<x<<" zzz\n";
            if(tori[x]-tole[x]+1 > k)
                break;
            int tol = tole[x]-1;
            if(tol==0)
                tol=n;
            int tor = tori[x]+1;
            if(tor==n+1)
                tor=1;

            if((tori[x]-tole[x]+1) * (min(a[root[tol]],a[root[tor]]) - a[x]) < k)
            {
                if(a[root[tol]]<a[root[tor]])
                {
                    k -= (tori[x]-tole[x]+1) * (a[root[tol]] - a[x]);
                    a[x] = a[root[tol]];
                    unite(root[tol], x);
                }
                else if(a[root[tol]]>a[root[tor]])
                {
                    k -= (tori[x]-tole[x]+1) * (a[root[tor]] - a[x]);
                    a[x] = a[root[tor]];
                    unite(x, root[tor]);
                }
                else
                {
                    k -= (tori[x]-tole[x]+1) * (a[root[tor]] - a[x]);
                    a[x] = a[root[tor]];
                    unite(root[tol], x);
                    unite(root[x], root[tor]);
                }
            }
            else
            {
                a[x] += k / (tori[x]-tole[x]+1);
                afis();
                break;
            }
            afis();
            bool eq=1;
            for(int i=1;i<=n;i++)
            {
                if(root[i]!=root[1])
                {
                    eq=0;
                    break;
                }
            }
            if(eq)
            {
                //cout<<"oh no equal\n";
                break;
            }
            ///trebuie sa verificam daca tot sirul ii egal, atunci dam break
            x = root[x];
            tol = tole[x]-1;
            if(tol==0)
                tol=n;
            tor = tori[x]+1;
            if(tor==n+1)
                tor=1;
            if(a[tol] > a[x] && a[tor] > a[x])
            {
                pq.push({-(tori[x]-tole[x]),x});
            }
        }
        for(int i=1;i<n;i++)
        {
            sum -= abs(a[root[i+1]] - a[root[i]]);
        }
        sum -= abs(a[root[n]] - a[root[1]]);
        //cout<<sum;
        if(sum!=rezdp)
        {
            ///do something
            for(int i=1;i<=n;i++)
            {
                cout<<inita[i]<<" ";
            }
            return 0;
        }
    }
    return 0;
}
/**
9 1000
1 1 1 2 2 3 3 1 1

9 1000
1 1 1 3 3 3 3 1 1

10 1000
5 4 3 2 1 1 2 3 4 5

8 3
7 9 1 1 9 9 9 9

n = 2 ?????

*/

• Subtask 1: 0 / 100