제출 #1155233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155233		jiahng	Ski 2 (JOI24_ski2)	C++20	100 / 100	495 ms	444012 KiB

Main

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

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef pair<ll,ll> pill;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF (ll)1e10
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
typedef pair <pi,pi> pipi;
#define maxn 310

int N,K;
pi A[maxn];
int dp[2*maxn][maxn][maxn];
int num[2*maxn], smin[2*maxn], delt[2*maxn];

int32_t main(){
	fast;
	cin >> N >> K;
	FOR(i,1,N){
		cin >> A[i].f >> A[i].s;
	}
	sort(A+1,A+N+1);
	vi v;
	FOR(i,1,N){
		v.pb(A[i].f);
		v.pb(A[i].f+1);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	int M = v.size();
	FOR(i,1,M) smin[i] = INF;
	FOR(i,1,M) num[i] = 0;
	FOR(i,1,N){
		int h = lbd(v, A[i].f) - v.begin() + 1;
		num[h]++; smin[h] = min(smin[h], A[i].s);
	}
	//~ FOR(i,1,M) cout << num[i] << ' ';
	//~ cout << '\n';
	FOR(i,2,M) smin[i] = min(smin[i], smin[i-1]);
	FOR(i,1,M-1){
		delt[i] = v[i] - v[i-1];
	}
	delt[M] = INF;
	FOR(i,0,M+1) FOR(j,0,N+1) FOR(k,0,N+1) dp[i][j][k] = INF;
	FOR(k,1,N) dp[M+1][0][k] = 0;

	DEC(i,M,1) FOR(j,0,N) DEC(k,N,0){
		if (k==0){
			dp[i][j][k] = dp[i+1][j+num[i]][0] + K*(j+num[i]);
			if (j + num[i] > 0) dp[i][j][k] = min(dp[i][j][k], dp[i+1][j+num[i]-1][1] + K*(j+num[i]-1));
		}else{
			if (k < N) dp[i][j][k] = dp[i][j][k+1] + smin[i-1];
			
			int x = min(j+num[i], k*delt[i]), y = j+num[i] - x;
			assert(y >= 0);
			int n = x/k;
			int num_moves = k * n * (n-1) / 2 + (x % k) * n + y * delt[i];
			dp[i][j][k] = min(dp[i][j][k], dp[i+1][y][k] + K*num_moves);
		}
	}
	//~ cout << num[2] << ' ' << smin[1] << ' ' << dp[2][1][1];
	cout << dp[1][0][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