Submission #995155

#	Time	Username	Problem	Language	Result	Execution time	Memory
995155		prvocislo	Ski 2 (JOI24_ski2)	C++17	100 / 100	710 ms	2644 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, hs;
    for (int i = 0; i < n; i++) cin >> hi[i] >> ci[i], cs.push_back(ci[i]), hs.push_back(hi[i]), hs.push_back(hi[i] + 1);
    cs.push_back(inf);
    sort(cs.begin(), cs.end());
    hs.push_back(1e9 + 500);
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());
    for (int i = 0; i < n; i++) ci[i] = lower_bound(cs.begin(), cs.end(), ci[i]) - cs.begin(), hi[i] = lower_bound(hs.begin(), hs.end(), hi[i]) - hs.begin();
    int h = hs.size();
    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]);
    vector<vector<ll> > cnt(n + 1, vector<ll>(n + 1, 0));
    for (ll z = 1; z <= n; z++) for (ll up = 1; up <= n; up++)
    {
        if (up % z == 0) cnt[z][up] = cnt[z][up - z] + z * k * (up / z);
        else             cnt[z][up] = cnt[z][up - (up % z)] + (up % z) * k * (up / z + 1);
    }
    ll ans = inf;
    clear(0);
    int c = minc[0];
    dp[0][1][cnth[0] - 1] = 0;
    for (int h2 = 0; 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)
            {
                upd(dp[nw][z][total], dp[pv][z][up]);
                continue;
            }
            ll val = dp[pv][z][up];
            ll rmv = min((ll)up, (hs[h2 + 1] - hs[h2] - 1) * z);
            val += cnt[z][rmv];
            val += ((ll)(up - rmv)) * k * (hs[h2 + 1] - hs[h2]);
            for (int stay = 0; stay <= total - rmv; stay++) // pocet tych co tu ostanu
            {
                int z2 = max(stay, z);
                int up2 = total - stay - rmv;
                ll cena = val + max(0ll, (ll)(stay - z)) * 1ll * cs[c];
                upd(dp[nw][z2][up2], cena);
            }
        }
        c = min(c, minc[h2 + 1]);
    }
    for (int z = 0; z <= n; z++) upd(ans, dp[(h - 1) & 1][z][0]);
    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: 14 / 14