Submission #996867

#	Time	Username	Problem	Language	Result	Execution time	Memory
996867		errorgorn	Ski 2 (JOI24_ski2)	C++17	100 / 100	252 ms	222808 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
ii arr[305];
int pre[305];

int dp[305][305][305];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	
	sort(arr,arr+n);
	
	rep(x,0,n) pre[x+1]=pre[x]+arr[x].fi;
	arr[n].fi=1e18;
	
	memset(dp,31,sizeof(dp));
	
	dp[0][1][0]=0;
	
	rep(x,0,n){
		if (x){
			rep(y,1,n+1){
				int curr=0;
				int mn=arr[0].se;
				rep(z,0,n+1){
					while (curr+1<n && arr[curr+1].fi<arr[x].fi+z){
						curr++;
						mn=min(mn,arr[curr].se);
					}
					
					dp[x][y+1][z]=min(dp[x][y+1][z],dp[x][y][z]+mn);
				}
			}
		}
		
		rep(y,1,n+1){
			int curr=x;
			rep(z,0,n+1){
				while (curr+1<n && curr<x+y-1 && arr[curr+1].fi<=arr[x].fi+z) curr++;
				
				int Z=max((arr[x].fi+z+1)-arr[curr+1].fi,0LL);
				dp[curr+1][y][Z]=min(dp[curr+1][y][Z],dp[x][y][z]+((arr[x].fi+z)*(curr-x+1)-(pre[curr+1]-pre[x]))*k);
			}
		}
	}
	
	int ans=1e18;
	rep(y,1,n+1) rep(z,0,n+1) ans=min(ans,dp[n][y][z]);
	
	cout<<ans<<endl;
}

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