Submission #1189483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189483		alexander707070	Ski 2 (JOI24_ski2)	C++20	0 / 100	1 ms	320 KiB

Main

#include<bits/stdc++.h>
#define MAXN 107
using namespace std;

const long long inf=1e15;

struct tower{
    int h,c;

    inline friend bool operator < (tower fr,tower sc){
        if(fr.h==sc.h)return fr.c<sc.c;
        return fr.h<sc.h;
    }
}a[MAXN];

int n,K;
long long dp[MAXN][MAXN][MAXN];

long long cost(int x,int y){
    return (abs(a[x].h-a[y].h)+1)*K;
}

int main(){


    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>a[i].h>>a[i].c;
    }

    sort(a+1,a+n+1);
    a[0].h=-1;

    for(int pos=n+1;pos>=1;pos--){
        for(int last=0;last<pos;last++){
            for(int taken=0;taken<=last;taken++){

                if(pos==n+1 and last==0){
                    dp[pos][last][taken]=inf;
                    continue;
                }

                if(pos==n+1){
                    for(int i=last+1;i<=n;i++){
                        if(a[i].h==a[last].h)dp[pos][last][taken]+=K;
                        else break;
                    }

                    dp[pos][last][taken]+=max(n-last-1,0) * a[last].c;
                    if(taken>0 and last==n)dp[pos][last][taken]-=a[last].c;

                    continue;
                }

                dp[pos][last][taken]=dp[pos+1][last][taken];
                if(a[pos].h==a[last].h)continue;

                long long sum=0,take=0;

                for(int i=last+1;i<pos;i++){
                    if(last!=0 and a[last].c+(a[i].h==a[last].h)*K<=a[pos].c+cost(i,pos)){
                        sum+=a[last].c+(a[i].h==a[last].h)*K;
                    }else{
                        take++;
                        sum+=cost(i,pos) + a[pos].c;
                    }
                }

                if(last==0 or a[last].c>a[pos].c + cost(last,pos)){
                    take+=taken;
                    sum+=-(taken)*a[last].c + taken*(a[pos].c + cost(last,pos));
                }

                dp[pos][last][taken]=min(dp[pos][last][taken] , dp[pos+1][pos][take] + sum);
            }
        }
    }

    cout<<dp[1][0][0]<<"\n";

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 33
• Subtask 5: 0 / 27
• Subtask 6: 0 / 14