oj.uz

Submission #940702

# Submission time Handle Problem Language Result Execution time Memory
940702 2024-03-07T13:44:47 Z TAhmed33 Let's Win the Election (JOI22_ho_t3) C++
11 / 100
 562 ms 8284 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld inf = 1e16;
int n, k; 
const int MAXN = 501;
pair <int, int> a[MAXN];
ld pre[MAXN][MAXN];
int main () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    cout << fixed << setprecision(9);
    sort(a + 1, a + n + 1, [&] (pair <int, int> &x, pair <int, int> &y) {
        return x.second < y.second || y.second == -1;
    });
    for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) pre[i][j] = inf;
    for (int i = 1; i <= n; i++) {
    	vector <int> xx;
    	for (int j = i; j <= n; j++) xx.push_back(a[j].first);
    	sort(xx.begin(), xx.end());
    	int sum = 0;
    	for (int j = 0; j < (int)xx.size(); j++) {
    		sum += xx[j];
    		pre[i][j + 1] = sum; 
    	}
    }
    ld mn = 1e18;
    for (int sze = 0; sze <= k; sze++) {
        ld dp[n + 1][sze + 1];
        for (int j = 1; j <= sze; j++) {
            dp[0][j] = inf;
        }
        dp[0][0] = 0; 
        mn = min(mn, 1.0 * pre[1][k] / (sze + 1) + dp[0][sze]);
        for (int i = 1; i <= n; i++) {
        	for (int j = 0; j <= sze; j++) {
        		dp[i][j] = dp[i - 1][j] + 1.0 * a[i].first / (sze + 1);
        		if (a[i].second != -1 && j) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1.0 * a[i].second / j);
        	}
        	if (k >= i) {
        		mn = min(mn, 1.0 * pre[i + 1][k - i] / (sze + 1) + dp[i][sze]);
        	}
        }
    }
    cout << mn << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4216 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4216 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 4184 KB Output is correct
3 Incorrect 2 ms 4188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 4184 KB Output is correct
3 Incorrect 2 ms 4188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 4184 KB Output is correct
3 Incorrect 2 ms 4188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 8284 KB Output is correct
2 Correct 481 ms 8160 KB Output is correct
3 Correct 512 ms 8256 KB Output is correct
4 Correct 528 ms 8052 KB Output is correct
5 Correct 484 ms 8272 KB Output is correct
6 Correct 515 ms 8228 KB Output is correct
7 Correct 562 ms 8276 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4216 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -