Submission #995008

#	Time	Username	Problem	Language	Result	Execution time	Memory
995008		prvocislo	Ski 2 (JOI24_ski2)	C++17	86 / 100	818 ms	1048576 KiB

Main

// He was a moth to the flame
// She was holding the matches
// Soon, she's gonna find stealing other people's toys
// On the playground won't make you many friends

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const ll inf = 1e18;
const int maxn = 301;
// dp[vyska v ktorej som][pocet zadarmo hran][pocet tych, co prisli na tuto vysku zdola] = minimalna cena
ll dp[2][maxn][maxn];
void clear(int i)
{
    for (int a = 0; a < maxn; a++) for (int b = 0; b < maxn; b++) for (int c = 0; c < maxn; c++)
            dp[i][a][b] = inf;
}
void upd(ll& a, ll b)
{
    a = min(a, b);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll k;
    cin >> n >> k;
    vector<int> hi(n), ci(n);
    vector<ll> cs;
    for (int i = 0; i < n; i++) cin >> hi[i] >> ci[i], cs.push_back(ci[i]);
    cs.push_back(inf);
    sort(cs.begin(), cs.end());
    for (int i = 0; i < n; i++) ci[i] = lower_bound(cs.begin(), cs.end(), ci[i]) - cs.begin();
    int h = *max_element(hi.begin(), hi.end()) + n + 2;
    vector<int> cnth(h);
    vector<int> minc(h, n);
    for (int i = 0; i < n; i++) cnth[hi[i]]++, minc[hi[i]] = min(minc[hi[i]], ci[i]);
    ll ans = inf;
    int mini = *min_element(hi.begin(), hi.end());
    int maxi = *max_element(hi.begin(), hi.end());
    clear(mini & 1);
    int c = minc[mini];
    dp[mini & 1][1][cnth[mini] - 1] = ((ll)(cnth[mini] - 1)) * k;
    for (int h2 = mini; h2 + 1 < h; h2++) // robime prechody na ten o jeden viac
    {
        int pv = h2 & 1, nw = (h2 + 1) & 1;
        clear(nw);
        for (int z = 0; z <= n; z++) for (int up = 0; up <= n; up++) if (dp[pv][z][up] != inf)
        {
            int total = up + cnth[h2 + 1];
            if (!total)
            {
                if (h2 >= maxi) upd(ans, dp[pv][z][up]);
                upd(dp[nw][z][total], dp[pv][z][up]);
                continue;
            }
            for (int stay = 1; stay <= total; stay++) // pocet tych co tu ostanu
            {
                int z2 = max(stay, z);
                int up2 = total - stay;
                ll cena = dp[pv][z][up] + max(0ll, (ll)(stay - z)) * 1ll * cs[c] + ((ll)up2) * k;
                upd(dp[nw][z2][up2], cena);
            }
        }
        c = min(c, minc[h2 + 1]);
    }
    cout << ans << "\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: 0 / 14