답안 #924256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924256	2024-02-08T17:58:47 Z	OAleksa	Let's Win the Election (JOI22_ho_t3)	C++14	11 / 100	2500 ms	5340 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 550;
int n, x;
pair<int, int> a[N];
double dp1[N][N], dp2[N][N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> x;
  	for (int i = 1;i <= n;i++) {
  		cin >> a[i].f >> a[i].s;
  		if (a[i].s == -1)
  			a[i].s = 1e9;
  	}
  	sort(a + 1, a + n + 1, [&](pair<int, int> x, pair<int, int> y) {
  		return x.s < y.s;
  	});
  	//prvih i, dobio sam j glasova, k ljudi ucestvuje
  	double ans = 1e9;
  	for (int s = 1;s <= n;s++) {
  		for (int j = 0;j <= n;j++) {
				for (int k = 0;k <= n;k++)
					dp1[j][k] = 1e9;
			}
			dp1[0][1] = 0;
	  	for (int i = 1;i <= n;i++) {
	  		for (int j = 1;j <= n;j++) {
	  			for (int k = 1;k <= n;k++) {
	  				dp2[j][k] = dp1[j][k];
	  				dp2[j][k] = min(dp2[j][k], dp1[j - 1][k] + (double)a[i].f / s);
	  				if (k > 1)
	  					dp2[j][k] = min(dp2[j][k], dp1[j - 1][k - 1] + (double)a[i].s / (k - 1));
	  			}
	  		}
	  		swap(dp1, dp2);
	  	}
	  	ans = min(ans, dp1[x][s]);
  	}
  	cout << fixed << setprecision(15) << ans;
  }
  return 0;
}

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Incorrect	5 ms	4956 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Incorrect	5 ms	4956 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	4952 KB	Output is correct
2	Correct	11 ms	5200 KB	Output is correct
3	Correct	11 ms	4956 KB	Output is correct
4	Correct	11 ms	4952 KB	Output is correct
5	Correct	12 ms	4956 KB	Output is correct
6	Correct	11 ms	4956 KB	Output is correct
7	Correct	11 ms	4956 KB	Output is correct
8	Correct	11 ms	4956 KB	Output is correct
9	Correct	11 ms	4956 KB	Output is correct
10	Correct	13 ms	5340 KB	Output is correct
11	Correct	11 ms	4952 KB	Output is correct
12	Correct	11 ms	4956 KB	Output is correct
13	Correct	12 ms	5200 KB	Output is correct
14	Correct	7 ms	4956 KB	Output is correct
15	Correct	11 ms	5200 KB	Output is correct

Subtask #4

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	4952 KB	Output is correct
2	Correct	11 ms	5200 KB	Output is correct
3	Correct	11 ms	4956 KB	Output is correct
4	Correct	11 ms	4952 KB	Output is correct
5	Correct	12 ms	4956 KB	Output is correct
6	Correct	11 ms	4956 KB	Output is correct
7	Correct	11 ms	4956 KB	Output is correct
8	Correct	11 ms	4956 KB	Output is correct
9	Correct	11 ms	4956 KB	Output is correct
10	Correct	13 ms	5340 KB	Output is correct
11	Correct	11 ms	4952 KB	Output is correct
12	Correct	11 ms	4956 KB	Output is correct
13	Correct	12 ms	5200 KB	Output is correct
14	Correct	7 ms	4956 KB	Output is correct
15	Correct	11 ms	5200 KB	Output is correct
16	Incorrect	78 ms	5176 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	4952 KB	Output is correct
2	Correct	11 ms	5200 KB	Output is correct
3	Correct	11 ms	4956 KB	Output is correct
4	Correct	11 ms	4952 KB	Output is correct
5	Correct	12 ms	4956 KB	Output is correct
6	Correct	11 ms	4956 KB	Output is correct
7	Correct	11 ms	4956 KB	Output is correct
8	Correct	11 ms	4956 KB	Output is correct
9	Correct	11 ms	4956 KB	Output is correct
10	Correct	13 ms	5340 KB	Output is correct
11	Correct	11 ms	4952 KB	Output is correct
12	Correct	11 ms	4956 KB	Output is correct
13	Correct	12 ms	5200 KB	Output is correct
14	Correct	7 ms	4956 KB	Output is correct
15	Correct	11 ms	5200 KB	Output is correct
16	Incorrect	78 ms	5176 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2597 ms	4952 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Incorrect	5 ms	4956 KB	Output isn't correct
5	Halted	0 ms	0 KB	-