Submission #940702

#	Time	Username	Problem	Language	Result	Execution time	Memory
940702		TAhmed33	Let's Win the Election (JOI22_ho_t3)	C++98	11 / 100	562 ms	8284 KiB

Main

#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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23