Submission #940717

#	Time	Username	Problem	Language	Result	Execution time	Memory
940717		TAhmed33	Let's Win the Election (JOI22_ho_t3)	C++98	100 / 100	512 ms	8836 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld inf = 1e16;
int n, k; 
const int MAXN = 525;
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) {
    	if (x.second == -1) return bool(0);
        return x.second == y.second ? x.first < y.first : ((y.second == -1) || (x.second < y.second));
    });
    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; 
    	}
    	pre[i][0] = 0;
    }
    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] = inf;
        	for (int j = 0; j <= min(sze, i); j++) {
        		if (i - 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]);
        	}
        	if (k == i) {
        		mn = min(mn, dp[i][sze]);
        	}
        }
    }
    cout << mn << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23