제출 #1156375

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

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=5e2+5;

int n,k;

double dp[2][maxN];

pair<double,double> val[maxN];

inline double DP(int G){
    fill(dp[0],dp[0]+k+1,1e18);
    fill(dp[1],dp[1]+k+1,1e18);
    dp[0][0] = 0;
    for(int i = 1;i<=n;i++)for(int j = 0;j<=k;j++){
        dp[i&1][j] = dp[i&1^1][j];
        if(j)dp[i&1][j] = min(dp[i&1][j],dp[i&1^1][j-1]+(j<=G?val[i].first/j:val[i].second/(G+1)));
    }
    return dp[n&1][k];
}

int main(){
    IOS
    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        cin>>val[i].second>>val[i].first;
        if(val[i].first==-1)val[i].first = 1e10;
    }
    sort(val+1,val+n+1);
    double ans = 1e18;
    for(int i = 0;i<=k;i++)ans = min(ans,DP(i));
    cout<<fixed<<setprecision(15)<<ans<<'\n';
}

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