Submission #986502

#	Time	Username	Problem	Language	Result	Execution time	Memory
986502		boris_mihov	Ski 2 (JOI24_ski2)	C++17	42 / 100	570 ms	54624 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 40 + 10;
const int MAXH = 40 + 10;
const int MAXB = 1024;
const llong INF = 1e18;

int n;
llong k;
llong h[MAXN];
llong c[MAXN];
llong dp[2 * MAXH][MAXN][MAXN][MAXN];
bool bl[2 * MAXH][MAXN][MAXN][MAXN];
int cntWith[2 * MAXH];
int minC[2 * MAXH];
llong maxH;

llong f(int height, int waiting, int free, int min)
{
    if (height == 2 * MAXH)
    {
        if (waiting > 0) return INF;
        return 0;
    }

    if (bl[height][waiting][free][min])
    {
        return dp[height][waiting][free][min];
    }

    bl[height][waiting][free][min] = true;
    dp[height][waiting][free][min] = f(height + 1, waiting + cntWith[height], free, min);
    
    int newMin = min;
    if (c[minC[height]] < c[min])
    {
        newMin = minC[height];
    }

    for (int choose = 1 ; choose <= waiting + cntWith[height] ; ++choose)
    {
        if (min == 0 && choose == 2) break;
        dp[height][waiting][free][min] = std::min(dp[height][waiting][free][min], f(height + 1, waiting + cntWith[height] - choose, std::max(free, choose), newMin) + std::max(0, choose - free) * c[min] + k * choose * height - k * cntWith[height] * height);
    }

    return dp[height][waiting][free][min];
}

void solve()
{
    c[0] = INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        cntWith[h[i]]++;
        if (c[minC[h[i]]] > c[i])
        {
            minC[h[i]] = i; 
        }
    }

    std::cout << f(0, 0, 1, 0) << '\n';
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> h[i] >> c[i];
        maxH = std::max(maxH, h[i]);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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