Submission #794443

#TimeUsernameProblemLanguageResultExecution timeMemory
794443Theo830Let's Win the Election (JOI22_ho_t3)C++17
10 / 100
1196 ms1008728 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training double dp[505][505][505]; ll n,k; vector<ii>ar; double solve(ll idx,ll i,ll j){ if(j >= k){ return 0; } if(idx == n){ return 1e18; } if(dp[idx][i][j] != -1){ return dp[idx][i][j]; } double ans = solve(idx + 1,i,j); ans = min(ans,solve(idx + 1,i,j+1) + (double)(-ar[idx].S) / (double)(i)); ans = min(ans,solve(idx + 1,i+1,j+1) + (double)(ar[idx].F) / (double)(i)); return dp[idx][i][j] = ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>k; f(i,0,n+5){ f(j,0,n+5){ f(u,0,n+5){ dp[i][j][u] = -1; } } } ll a[n],b[n]; f(i,0,n){ cin>>a[i]>>b[i]; if(b[i] == -1){ b[i] = 1e18; } ar.pb(ii(b[i],-a[i])); } sort(all(ar)); cout<<fixed<<setprecision(6)<<solve(0,1,0)<<"\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...