Submission #532408

#	Time	Username	Problem	Language	Result	Execution time	Memory
532408		Marceantasy	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	203 ms	2304 KiB

Main

#include <bits/stdc++.h>
using namespace std; 

#define ll long long 
#define ar array

typedef pair<int, int> pi;

const int mxN = 505, M = 1e9+7;
int n, k; 
pair<int, int> a[mxN];
double dp[mxN][mxN];


int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cout << fixed << setprecision(12);
    cin >> n >> k; 
    for(int i = 0; i<n; ++i){
        cin >> a[i].first >> a[i].second;
        if(a[i].second == -1) a[i].second = 1e8;
    }
    sort(a, a+n, [&](const pi &a, const pi &b){
        return a.second < b.second;
    });
    double ret = 1e9;
    for(int i = 0; i<=k; ++i){
        for(int j = 0; j<=k-i; ++j){
            dp[0][j] = 1e9;
        }
        dp[0][0] = 0;
        for(int j = 1; j<=n; ++j){
            for(int b = 0; b<=k-i; ++b){
                int ord = j-b;
                dp[j][b] = dp[j-1][b] + (1<=ord && ord <= i ? 1.0 * a[j-1].second / ord : 0);
                if(b){
                    dp[j][b] = min(dp[j][b], dp[j-1][b-1] + 1.0*a[j-1].first / (i+1));
                }
            }
        }
        ret = min(ret, dp[n][k-i]);
    }
    cout << ret;
}

• 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