oj.uz

답안 #529593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529593 2022-02-23T08:50:08 Z fhvirus Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 285 ms 2300 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K; cin >> N >> K;
	vector< pair<int, int> > states(N);
	for (int i = 0; i < N; ++i) {
		cin >> states[i].second >> states[i].first;
		if (states[i].first == -1)
			states[i].first = 1'000'000'000;
	}
	sort(begin(states), end(states));

	double ans = 1e18;
	for (int g = 0; g <= K; ++g) {
		vector< vector<double> > dp(N + 1, vector<double>(K - g + 1, 1e18));
		dp[0][0] = 0;
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < K - g; ++j) {
				if (j < K - g)
					dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + (double) states[i].second / (g + 1));
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (i - j < g ? (double) states[i].first / (i - j + 1) : .0));
			}
		ans = min(ans, dp[N][K - g]);
	}

	cout << setprecision(9) << fixed << ans << '\n';
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 2296 KB Output is correct
2 Correct 247 ms 2260 KB Output is correct
3 Correct 248 ms 2288 KB Output is correct
4 Incorrect 239 ms 2300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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