Submission #1257518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257518		Icelast	Ski 2 (JOI24_ski2)	C++20	100 / 100	257 ms	1912 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e15+9;
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        if(poi.size() > 0) pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
void solve(){
    ll n, K;
    cin >> n >> K;
    vector<ll> h(n+1), c(n+1);
    for(int i = 1; i <= n; i++){
        cin >> h[i] >> c[i];
    }
    normalize norm;
    for(int i = 1; i <= n; i++){
        norm.add(h[i]);
        norm.add(h[i]+1);
    }
    norm.start();
    int N = norm.pot.size();
    vector<ll> decode(N+2);
    for(int i = 1; i <= N; i++){
        decode[i] = norm.pot[i-1];
    }
    decode[N+1] = 1e10;
    for(int i = 1; i <= n; i++){
        h[i] = norm.encode(h[i]);
    }
    vector<ll> d(N+2, 0), mn(N+2, INF);
    for(int i = 1; i <= n; i++){
        d[h[i]]++;
        mn[h[i]] = min(mn[h[i]], c[i]);
    }
    for(int i = 1; i <= N; i++){
        mn[i] = min(mn[i], mn[i-1]);
    }
    auto pfmn = [&](int i) -> ll{
        if(i == -1) return INF;
        return mn[i];
    };
    auto chmin = [&](ll &a, ll b) -> void{
        a = min(a, b);
    };
    vector<vector<ll>> f(n+1, vector<ll>(n+1, INF)), prv = f;
    f[1][d[1]] = 0;
    for(int i = 1; i < N+1; i++){
        prv = f;
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= n; k++){
                f[j][k] = INF;
            }
        }
        for(int j = 1; j <= n; j++){
            for(int k = 0; k <= n; k++){
                //prv[j][k] -> f[j][d[i+1] + k-j] + (k-j) * K (subtask 5)
                ll c = max(0, k - j); // amount that will get push
                ll w = decode[i+1] - decode[i];
                //if the rectangle w*j is enough to store all pushy balls
                if(c <= (w-1) * j){
                    ll p = c/j, q = c%j;
                    ll whole_part = p*(p+1)/2 * j * K;
                    ll incomplete_part = q*(p+1)*K;
                    chmin(f[j][d[i+1]], prv[j][k] + whole_part + incomplete_part);
                }else{
                    ll new_balls = c - (w-1)*j; // minus the balls to fill in the rectangle
                    ll rectangle_cost = w*(w-1)/2 * j * K; // (w-1 length)
                    ll extra_cost = new_balls * w * K;
                    if(d[i+1] + new_balls <= n) // just for overflow checking
                        chmin(f[j][d[i+1] + new_balls], prv[j][k] + rectangle_cost + extra_cost);
                }

            }
        }
        for(int j = 0; j < n; j++){
            for(int k = 0; k <= n; k++){
                //f[j][k] -> f[j+1][k] + pfmn(i)
                chmin(f[j+1][k], f[j][k] + pfmn(i));
            }
        }
    }
    ll ans = INF;
    for(int j = 0; j <= n; j++){
        ans = min(ans, f[j][0]);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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