Submission #814960

#TimeUsernameProblemLanguageResultExecution timeMemory
814960MohamedAhmed04Let's Win the Election (JOI22_ho_t3)C++14
100 / 100
692 ms5980 KiB
#include <bits/stdc++.h> using namespace std ; const int MAX = 500 + 10 ; int arr[MAX] ; int n , k ; int a[MAX] , b[MAX] ; long double dp[MAX][MAX] ; int vis[MAX][MAX] ; int val[MAX][MAX] ; vector< pair<long double , long double> >vp ; int m ; long double solve(int idx , int cnt) { if(cnt == m) return (1.00L * val[idx][k-idx] / (1.00L * m)) ; if(idx == k) return 1e9 ; long double &ret = dp[idx][cnt] ; if(vis[idx][cnt] == m) return ret ; vis[idx][cnt] = m ; ret = solve(idx+1 , cnt+1) + (1.00L * vp[idx].second / (1.00L * cnt)) ; ret = min(ret , solve(idx+1 , cnt) + (1.00L * vp[idx].first / m)) ; return ret ; } int main() { memset(vis , -1 , sizeof(vis)) ; ios_base::sync_with_stdio(0) ; cin.tie(0) ; cin>>n>>k ; for(int i = 0 ; i < n ; ++i) { cin>>a[i]>>b[i] ; if(b[i] == -1) b[i] = 1e9 ; } for(int i = 0 ; i < n ; ++i) vp.emplace_back(b[i] , a[i]) ; sort(vp.begin() , vp.end()) ; for(auto &p : vp) swap(p.first , p.second) ; vector<int>v ; for(int i = n-1 ; i >= 0 ; --i) { v.push_back(vp[i].first) ; sort(v.begin() , v.end()) ; val[i][0] = 0 ; for(int j = 1 ; j <= n-i ; ++j) val[i][j] = val[i][j-1] + v[j-1] ; } long double ans = 1e18 ; for(int i = 1 ; i <= k ; ++i) { m = i ; ans = min(ans , solve(0 , 1)) ; } return cout<<fixed<<setprecision(12)<<ans<<"\n" , 0 ; }
#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...