Submission #681791

#TimeUsernameProblemLanguageResultExecution timeMemory
681791dsyzLet's Win the Election (JOI22_ho_t3)C++17
10 / 100
635 ms4252 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define MAXN (300005) int main() { ios_base::sync_with_stdio(false);cin.tie(0); ll N,K; cin>>N>>K; pair<ll,ll> arr[N]; for(ll i = 0;i < N;i++){ cin>>arr[i].second>>arr[i].first; if(arr[i].first == -1) arr[i].first = 1e18; } sort(arr,arr + N); ld A[N], B[N]; for(ll i = 0;i < N;i++){ A[i] = arr[i].second; B[i] = arr[i].first; if(arr[i].first == 1e18){ arr[i].first = -1; B[i] = -1; } } ld dp[K + 1][N + 1]; //number of A fufilled, number of collaborators (excluding Rie herself) for(ll i = 0;i <= K;i++){ for(ll j = 0;j <= N;j++){ dp[i][j] = 1e18; } } dp[0][0] = 0; for(ll i = 0;i < N;i++){ for(ll a = min(K,i + 1);a >= 0;a--){ for(ll b = a;b >= 0;b--){ if(a == 0){ dp[a][b] = 0; }else if(b == 0){ dp[a][b] = min(dp[a][b],dp[a - 1][b] + A[i]); dp[a][b] = round(dp[a][b] * 1000) / 1000; }else if(B[i] == -1){ dp[a][b] = min(dp[a][b],dp[a - 1][b] + (A[i] / ld(b + 1))); dp[a][b] = round(dp[a][b] * 1000) / 1000; }else{ dp[a][b] = min(dp[a][b],min(dp[a - 1][b] + (A[i] / ld(b + 1)), dp[a - 1][b - 1] + (B[i] / ld(b)))); dp[a][b] = round(dp[a][b] * 1000) / 1000; } } } } ld minimum = 1e18; for(ll j = 0;j <= N;j++){ minimum = min(minimum,dp[K][j]); } cout<<minimum<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...