Submission #1021110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021110		ReLice	Ski 2 (JOI24_ski2)	C++17	100 / 100	476 ms	223060 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=1e5+7;
const ll M=1e5+7;
const ld eps=1e-9;
ll val[N];
ll dis(ll i,ll j){
    return 1;
    if(i==0)return 1;
    return val[j]-val[i];
}
void solve(){
    ll i,j;
    ll n,k;
    cin>>n>>k;
    pll v(n);
    set<ll> st;
    map<ll,ll> ccnt,mp;
    for(i=0;i<n;i++){
        cin>>v[i].fr>>v[i].sc;
        ccnt[v[i].fr]++;
    }
    sort(all(v));
    ll x=0,c=0;
    while(true){
        c+=ccnt[x];
        if(c==0){
            ll low=ub(all(v),make_pair(x,-inf))-v.begin();
            if(low==v.sz) break;
            x=v[low].fr;
            continue;
        }
        st.ins(x);
        c--;
        x++;
    }
    c=0;
    for(auto i : st){
        mp[i]=++c;
        val[c]=i;
    }
    vll cnt(n+5,0);
    ll dp[n+5][n+5][n+5];
    for(i=0;i<=n+1;i++){
        for(j=0;j<=n+1;j++){
            for(ll q=0;q<=n+1;q++)dp[i][j][q]=inf;
        }
    }
    vll mn(n+5,inf);
    st.clear();
    for(i=0;i<n;i++){
        v[i].fr=mp[v[i].fr];
        cnt[v[i].fr]++;
        st.ins(v[i].sc);
        mn[v[i].fr]=*st.begin();
    }
    for(i=2;i<=n;i++){
        mn[i]=min(mn[i],mn[i-1]);
    }

    dp[0][0][1]=0;
    for(i=0;i<=c;i++){
        for(j=0;j<=n;j++){
            for(ll q=1;q<=n;q++){
                if(dp[i][j][q]>=inf) continue;
                for(ll l=0;l<=j;l++){
                    if(mn[i-1]==inf && l>0)break;
                    ll x=j-l;
                    chmin(dp[i+1][max(0ll,cnt[i+1]+x-(q+l))][q+l],dp[i][j][q]+x*k*dis(i,i+1)+(i>0 ? l*mn[i-1] : 0));
                }
            }
        }
    }
    ll ans=inf;
    for(i=0;i<=n;i++){
        chmin(ans,dp[n+1][0][i]);
    }
    cout<<ans<<endl;
}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
7 10
1 2
1 3
4 2
100 1
100 2
100 3
300 2


*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:69:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if(low==v.sz) break;
      |                   ^

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