제출 #1036431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036431		parsadox2	Ski 2 (JOI24_ski2)	C++17	100 / 100	165 ms	421712 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second
#define int long long
using namespace std;

const int N = 3e2 + 2 , inf = 1e18;
int n , h , a[N] , c[N] , prfmn[N] , dp[N][N][N][2] , nex[N];

int f(int k , int j)
{
    int tmp = k / j;
    int res = tmp * k - tmp * (tmp + 1) * j / 2;
    res *= h;
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);  cout.tie(0);
    cin >> n >> h;
    vector <pair<int ,int>> vec;
    for(int i = 1 ; i <= n ; i++)
    {
        int x , y;  cin >> x >> y;
        vec.push_back(make_pair(x , y));
    }
    sort(vec.begin() , vec.end());
    for(int i = 0 ; i < n ; i++)
    {
        a[i] = vec[i].F;
        c[i] = vec[i].S;
        prfmn[i] = c[i];
    }
    nex[n - 1] = n;
    a[n] = inf;
    for(int i = n - 2 ; i >= 0 ; i--)
        nex[i] = (a[i] == a[i + 1] ? nex[i + 1] : i + 1);
    /*for(int i = 0 ; i < n ; i++)
        cout << i << " : " << nex[i] << endl;
    for(int i = 0 ; i < n ; i++)
        cout << a[i] << " ";
    cout << '\n';
    for(int i = 0 ; i < n ; i++)
        cout << c[i] << " ";
    cout << '\n';*/
    for(int i = 1 ; i < n ; i++)
        prfmn[i] = min(prfmn[i] , prfmn[i - 1]);
    for(int i = n ; i >= 1 ; i--)  for(int j = 0 ; j <= n ; j++)
    {
        if(i >= j)
            continue;
        dp[n][i][j][0] = dp[n][i + 1][j][0] + prfmn[n - 1];
        dp[n][i][j][0] = min(dp[n][i][j][0] , f(j , i));
        dp[n][i][j][1] = dp[n][i][j][0];
    } 
    for(int i = n - 1 ; i >= 1 ; i--)  for(int j = n ; j >= 1 ; j--)  for(int k = 0 ; k <= i ; k++)
    {
        int tmp = nex[i] - i + k;
        if(tmp <= j)
        {
            dp[i][j][k][0] = dp[nex[i]][j][0][0];
        }
        else
        {
            if(a[i] + 1 == a[nex[i]])
                dp[i][j][k][0] = dp[nex[i]][j][tmp - j][0] + (tmp - j) * h;
            else
                dp[i][j][k][0] = dp[nex[i]][j][tmp - j][1] + (tmp - j) * h;
            dp[i][j][k][0] = min(dp[i][j][k][0] , dp[i][j + 1][k][0] + prfmn[i - 1]);
        }
        if(k <= j)
        {
            dp[i][j][k][1] = dp[i][j][0][0];
        }
        else
        {
            tmp = (a[i] - a[i - 1] - 1) * j;
            if(tmp >= k)
                dp[i][j][k][1] = dp[i][j][0][0] + f(k , j);
            else
            {
                dp[i][j][k][1] = dp[i][j][k - tmp][0] + f(tmp , j) + (k - tmp) * (a[i] - a[i - 1] - 1) * h;
            }
            dp[i][j][k][1] = min(dp[i][j][k][1] , dp[i][j + 1][k][1] + prfmn[i - 1]);
        }
        //cout << i << " " << j << " " << k << " " << dp[i][j][k][0] << " " << dp[i][j][k][1] << endl;
    }
    if(a[0] + 1 == a[nex[0]])
        cout << dp[nex[0]][1][nex[0] - 1][0] + (nex[0] - 1) * h << '\n';
    else
        cout << dp[nex[0]][1][nex[0] - 1][1] + (nex[0] - 1) * h << '\n';
    return 0;
}

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