Submission #1283269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283269		third	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	445 ms	4412 KiB

Main

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 505
#define LOG 17
using namespace std;

// y tuong: for tung X, dp[i][j][cnt] => tu nghi duoc

// da doc sol

// toi uu: vi khi cnt < X, ta se ko bo qua con nao
// -> so trang thai thuc te rat nho

bool ghuy4g;

const ll inf = 1e18;

double ans = 1e18;

ll n, k, cur;
pii a[N];

bool cmp(pii a, pii b) {
	if (a.se == b.se) {
		return a.fi < b.fi;
	}
	return a.se < b.se;
}

void pre() {
	
}

double dp[505][505][2];

void mn(double &u, double v) {
	u = min(u, v);
}

void solve1(ll X) {
	for (int i = 0; i <= n; i ++) {
		for (int j = 0; j <= i; j ++) {
			dp[i][j][0] = dp[i][j][1] = inf;
		}
	}
	
	dp[0][0][0] = 0;
	
	if (X == 0) {
		dp[0][0][1] = 0;
	}
	
	for (int cnt = 0; cnt < X; cnt ++) {
		for (int i = 1; i <= n; i ++) {
			// ko bo
			mn(dp[i][cnt][0], dp[i - 1][cnt][0] + double(a[i].fi) / (X + 1));
			if (cnt > 0 && a[i].se != inf) {
				mn(dp[i][cnt][0], dp[i - 1][cnt - 1][0] + double(a[i].se) / cnt);
			}
			if (i >= k && cnt == X){
				ans = min(ans, dp[i][cnt][0]);
				if (dp[i][cnt][0] == 2.25) {
					cout << "HEre " << i << " " << cnt << endl;
					exit(0);
				}
			}
		}
	}
	for (int i = X; i <= n; i ++) {
		for (int j = 1; j <= i; j ++) {
			if (i - 1 >= j) {
				mn(dp[i][j][1], dp[i - 1][j][1]); // bo
			}
			mn(dp[i][j][1], dp[i - 1][j - 1][1] + double(a[i].fi) / (X + 1) );
			// chon con bi nua
			if (X && a[i].se != inf) {
				mn(dp[i][j][1], dp[i - 1][X - 1][0] + double(a[i].se) / X);
			}
			if (j >= k) {
				ans = min(ans, dp[i][j][1]);
				/*if (dp[i][j][1] >= 9 && dp[i][j][1] <= 9.4) {
					cout << dp[i][j][1] << endl;
					cout << "here " << X << " " << i << " " << j << endl;
					//cout << dp[i - 1][j - 1][0] + double(a[i].se) / X << endl;
					exit(0);
				}*/
			}
		}
	}
}

void solve() {
	for (int i = 0; i <= n; i ++) {
		for (int j = 0; j <= n; j ++) {
			dp[i][j][0] = inf;
			dp[i][j][1] = inf;
		}
	}
	for (int X = 1; X <= n; X ++) {
		solve1(X);
	}
	cout << fixed << setprecision(6) << ans;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n >> k;
   	priority_queue<ll, vector<ll>, greater<ll>> pq;
   	for (int i = 1; i <= n; i ++) {
   		cin >> a[i].fi >> a[i].se;
   		if (a[i].se == -1) a[i].se = inf;
   		pq.push(a[i].fi);
   	}
   	
   	ll kk = k, res = 0;
   	while (kk) {
   		res += pq.top();
   		pq.pop();
   		kk --;
   	}
   	ans = min(ans, (double)res);
   	
   	sort(a + 1, a + 1 + n, cmp);
   	
   	solve();
   	
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

Compilation message (stderr)

Main.cpp:21:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const ll inf = 1e18;
      |                ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23