Submission #1008535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008535		GrindMachine	Ski 2 (JOI24_ski2)	C++17	86 / 100	1645 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

knew beforehand that it was dp

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<pll> a(n+5);
    rep1(i,n) cin >> a[i].ff >> a[i].ss;
    sort(a.begin()+1,a.begin()+n+1);
    ll m = n+a[n].ff;

    auto b = a;
    ll add_cost = 0;

    rep1(i,n){
        if(i == 1) conts;
        if(b[i].ff <= b[1].ff){
            ll add = b[1].ff-b[i].ff+1;
            b[i].ff += add;
            add_cost += add*k;
        }
    }

    sort(b.begin()+1,b.begin()+n+1);

    vector<pll> c,d;
    c.pb({0,0}), d.pb({0,0});
    ll mn = inf2;

    rep1(i,n){
        if(b[i].ss < mn){
            d.pb(b[i]);
            mn = b[i].ss;
        }
        else{
            c.pb(b[i]);
        }
    }

    ll siz1 = sz(c)-1, siz2 = sz(d)-1;
    ll dp[siz1+5][m+5][n+5];
    memset(dp,0x3f,sizeof dp);
    dp[1][d[1].ff][1] = 0;

    rep1(i,siz1){
        rep(h,m+1){
            ll mn_cost = inf2;
            ll nxth = inf2;
            rep1(j,siz2){
                auto [height,cost] = d[j];
                if(height > h){
                    amin(nxth,height);
                }
                else{
                    amin(mn_cost,cost);
                }
            }

            // place from c[i]
            rep(f,n+1){
                if(dp[i][h][f] > inf2) conts;

                ll sumh = 0;

                for(int j = i; j <= siz1; ++j){
                    sumh += c[j].ff;
                    ll h2 = max((ll)h+1,c[j].ff);
                    if(h2 > nxth) break;

                    ll curr_sum = sumh, curr_cnt = j-i+1;
                    if(h2 == nxth){
                        curr_sum += nxth;
                        curr_cnt++;
                    }

                    ll sub = min((ll)f,curr_cnt);
                    ll f2 = f-sub+curr_cnt;
                    ll curr_cost = (curr_cnt-sub)*mn_cost;
                    curr_cost += (curr_cnt*h2-curr_sum)*k;

                    amin(dp[j+1][h2][f2],dp[i][h][f]+curr_cost);
                }
            }

            // place from d[i] (nxth)
            if(nxth <= m){
                rep(f,n+1){
                    ll f2 = f;
                    ll curr_cost = 0;
                    if(f2 == 0){
                        curr_cost += mn_cost;
                    }
                    else{
                        f2--;
                    }

                    f2++;
                    amin(dp[i][nxth][f2],dp[i][h][f]+curr_cost);
                }
            }
        }
    }

    ll ans = inf2;
    rep(h,m+5){
        rep(f,n+5){
            ll val = dp[siz1+1][h][f];
            amin(ans,dp[siz1+1][h][f]);
        }
    }

    ans += add_cost;
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(int)':
Main.cpp:163:16: warning: unused variable 'val' [-Wunused-variable]
  163 |             ll val = dp[siz1+1][h][f];
      |                ^~~

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