Submission #635379

#	Time	Username	Problem	Language	Result	Execution time	Memory
635379		Astrayt	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1460 ms	1018624 KiB

Main

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
//#define N 100005

void solve(){
    int N, K, cnt = 0; cin >> N >> K;
    vector<vector<vector<double>>> dp(505, vector<vector<double>>(505, vector<double>(505, 0)));
    double ans = 1e18;
    vector<pii> v(N + 1, pii(0, 0));
    for(int i = 1; i <= N; ++i){
        auto &[a, b] = v[i];
        cin >> a >> b;
        if(b != -1) ++cnt;
        else b = 1e18;
    }
    sort(v.begin(), v.end(), [](pii a, pii b){return a.ss < b.ss;});
    for(int goal = 0; goal <= min(K, cnt); ++goal){
        for(int i = 0; i <= N; ++i){
            for(int j = 0; j <= min(i, K); ++j){
                if(i == j){
                    for(int k = 0; k <= min(j, goal); ++k){
                        dp[i][j][k] = 1e18;
                    }
                }
                else dp[i][j][goal] = 1e18;
            }
        }
        dp[0][0][0] = 0;
        for(int i = 0; i < N; ++i){
            for(int j = max(0ll, K - N + i); j <= min(i, K); ++j){
                if(i == j){
                    for(int k = max(0ll, goal - N + i); k <= min(j, goal); ++k){
                        dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                        dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + 1.0 * v[i + 1].ff / (goal + 1));
                        dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + 1.0 * v[i + 1].ss / (k + 1));
                    }
                }else{
                    dp[i + 1][j][goal] = min(dp[i + 1][j][goal], dp[i][j][goal]);
                    dp[i + 1][j + 1][goal] = min(dp[i + 1][j + 1][goal], dp[i][j][goal] + 1.0 * v[i + 1].ff / (goal + 1));
                }
            }
        }
        ans = min(ans, dp[N][K][goal]);
    }
    cout << fixed << setprecision(9) << ans << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

• 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