제출 #1135103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135103		Unforgettablepl	Let's Win the Election (JOI22_ho_t3)	C++20	56 / 100	456 ms	1114112 KiB

Main

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

#define int long long
typedef long double ld;

const int INF = 1e10;


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vector<pair<int,int>> arr(n);
    for(auto&[a,b]:arr){cin>>b>>a;if(a==-1)a=INF;}
    sort(arr.begin(), arr.end());
    arr.insert(arr.begin(),{0,0});
    vector DP(n+1,vector(n+1,vector(n+1,(ld)INF)));
    DP[0][0][0]=0;
    auto solve = [&](ld x) {
        for(int i=1;i<=n;i++) {
            for(ld j=0;j<=x;j++) {
                DP[i][i][j]=INF;
                if(j)DP[i][i][j]=min(DP[i][i][j],DP[i-1][i-1][j-1]+(arr[i].first)/(j));
                DP[i][i][j]=min(DP[i][i][j],DP[i-1][i-1][j]+(arr[i].second)/(x+1));
            }
            for(ld j=x;j<=i;j++) {
                if(j!=i)DP[i][j][x]=INF;
                if(j)DP[i][j][x]=min(DP[i][j][x],DP[i-1][j-1][x]+(arr[i].second)/(x+1));
                DP[i][j][x]=min(DP[i][j][x],DP[i-1][j][x]);
            }
        }
        return DP[n][k][x];
    };
    ld ans = INF;
    for(int x=0;x<=k;x++)ans=min(solve(x),ans);
    cout << setprecision(10) << ans << '\n';
}

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