제출 #1131107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131107		12345678	Ski 2 (JOI24_ski2)	C++20	0 / 100	2120 ms	444640 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=305;

ll n, mv, h[nx], c[nx], dp[2*nx][nx][nx], cnt[2*nx], res;

ll solve(int i, int j, int k)
{
    if (dp[i][j][k]!=-1) return dp[i][j][k];
    if (i==2*nx-1) return max(j-k, 0)*c[1];
    dp[i][j][k]=1e18;
    for (int l=0; l<=j; l++)
    {
        if (j-l<=k) dp[i][j][k]=min(dp[i][j][k], solve(i+1, cnt[i+1]+l, k)+l*mv);
        else dp[i][j][k]=min(dp[i][j][k], solve(i+1, cnt[i+1]+l, j-l)+c[1]*((j-l)-k)+l*mv);
    }
    //cout<<"dp "<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
    return dp[i][j][k];
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>mv;
    for (int i=1; i<=n; i++) cin>>h[i]>>c[i];
    for (int i=2; i<=n; i++) if (h[i]==h[1]) h[i]++, res+=mv;
    for (int i=2; i<=n; i++) cnt[h[i]]++;
    for (int i=0; i<2*nx; i++) for (int j=0; j<nx; j++) for (int k=0; k<nx; k++) dp[i][j][k]=-1;
    solve(h[1]+1, cnt[h[1]+1], 1);
    //cout<<"res "<<res<<'\n';
    cout<<res+dp[h[1]+1][cnt[h[1]+1]][1];
}

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