oj.uz

Submission #923380

# Submission time Handle Problem Language Result Execution time Memory
923380 2024-02-07T07:09:47 Z goodspeed0208 Let's Win the Election (JOI22_ho_t3) C++14
5 / 100
 455 ms 1018780 KB 
#include<bits/stdc++.h>
#define pii pair<int, int>
#define INF 5000000
using namespace std;

bool cmp(pii a, pii b) {
	if (a.second == -1 || b.second == -1) return a.second != -1;
	return a.second < b.second;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, K;
	cin >> n >> K;
	vector<pii>v(n+1);
	vector<double>a(n+1), b(n+1);
	for (int i = 1 ; i <=  n ;i++) cin >> v[i].first >> v[i].second;
	//sort(v.begin()+1, v.end(), cmp);
	for (int i = 1 ; i <= n ;i++) a[i] = (double)v[i].first, b[i] = (double)v[i].second;
	
	vector<vector<vector<double> > >dp(505, vector<vector<double> >(505, vector<double>(505, INF)) );
	//double dp[505][505][505];
	dp[0][0][1] = 0.0;
	double ans = INF;
	for (int i = 1 ; i <= n ; i++) {//first i people
	//cout << i << ": \n";
		for (int j = 0 ; j <= i ; j++) {// have how many people
			//cout << j << ": ";
			for (int k = 1 ; k <= j+1 ; k++) {// get how many people
				dp[i][j][k] = dp[i-1][j][k];
				if (j > 0) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k] + (a[i] / k));
				if (k > 1 && b[i] != -1) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k-1] + b[i] / (k-1));
				//cout << dp[i][j][k] <<" ";
				if (j >= K) ans = min(ans, dp[i][j][k]);
			}
			//cout << "\n";
		}
	}
	cout << fixed << setprecision(6) << ans << "\n";
	//for (auto &i : v) cout << i.first <<" " << i.second << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 1018452 KB Output is correct
2 Correct 366 ms 1018452 KB Output is correct
3 Correct 371 ms 1018400 KB Output is correct
4 Correct 377 ms 1018348 KB Output is correct
5 Correct 421 ms 1018780 KB Output is correct
6 Correct 421 ms 1018424 KB Output is correct
7 Correct 413 ms 1018628 KB Output is correct
8 Correct 416 ms 1018468 KB Output is correct
9 Correct 433 ms 1018476 KB Output is correct
10 Correct 419 ms 1018372 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 1018452 KB Output is correct
2 Correct 366 ms 1018452 KB Output is correct
3 Correct 371 ms 1018400 KB Output is correct
4 Correct 377 ms 1018348 KB Output is correct
5 Correct 421 ms 1018780 KB Output is correct
6 Correct 421 ms 1018424 KB Output is correct
7 Correct 413 ms 1018628 KB Output is correct
8 Correct 416 ms 1018468 KB Output is correct
9 Correct 433 ms 1018476 KB Output is correct
10 Correct 419 ms 1018372 KB Output is correct
11 Correct 375 ms 1018524 KB Output is correct
12 Incorrect 455 ms 1018704 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 1018564 KB Output is correct
2 Correct 386 ms 1018548 KB Output is correct
3 Correct 361 ms 1018424 KB Output is correct
4 Incorrect 375 ms 1018596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 1018564 KB Output is correct
2 Correct 386 ms 1018548 KB Output is correct
3 Correct 361 ms 1018424 KB Output is correct
4 Incorrect 375 ms 1018596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 1018564 KB Output is correct
2 Correct 386 ms 1018548 KB Output is correct
3 Correct 361 ms 1018424 KB Output is correct
4 Incorrect 375 ms 1018596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 455 ms 1018588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 1018452 KB Output is correct
2 Correct 366 ms 1018452 KB Output is correct
3 Correct 371 ms 1018400 KB Output is correct
4 Correct 377 ms 1018348 KB Output is correct
5 Correct 421 ms 1018780 KB Output is correct
6 Correct 421 ms 1018424 KB Output is correct
7 Correct 413 ms 1018628 KB Output is correct
8 Correct 416 ms 1018468 KB Output is correct
9 Correct 433 ms 1018476 KB Output is correct
10 Correct 419 ms 1018372 KB Output is correct
11 Correct 375 ms 1018524 KB Output is correct
12 Incorrect 455 ms 1018704 KB Output isn't correct
13 Halted 0 ms 0 KB -