Submission #534675

#TimeUsernameProblemLanguageResultExecution timeMemory
534675browntoadLet's Win the Election (JOI22_ho_t3)C++14
56 / 100
144 ms18788 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("Ofast", "unroll-loops") using namespace std; #define ll long long #define int ll #define FOR(i,a,b) for (int i = (a); i<(b); i++) #define REP(i,n) FOR(i,0,n) #define REP1(i,n) FOR(i,1,n+1) #define RREP(i,n) for (int i=(n)-1; i>=0; i--) #define f first #define s second #define pb push_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)(x.size()) #define SQ(x) (x)*(x) #define pdd pair<double ,double> #define pii pair<int, int> #define pcc pair<char, char> #define endl '\n' //#define TOAD #ifdef TOAD #define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl #define IOS() #else #define bug(...) #define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #endif const ll inf = 1ll<<60; const int iinf=2147483647; const ll mod = 1e9+7; const ll maxn=105; const double PI=acos(-1); ll pw(ll x, ll p, ll m=mod){ ll ret=1; while (p>0){ if (p&1){ ret*=x; ret%=m; } x*=x; x%=m; p>>=1; } return ret; } ll inv(ll a, ll m=mod){ return pw(a,m-2); } //======================================================================================= double dp[maxn][maxn][maxn]; bool cmp(pdd x, pdd y){ if (x.s==y.s&&x.s==-1){ return x.f<y.f; } if (x.s==-1||y.s==-1){ return x.s>y.s; } return x.s<y.s; } signed main (){ IOS(); cout<<fixed<<setprecision(9); int n, K; cin>>n>>K; vector<pdd> vc(n+1); REP1(i,n){ cin>>vc[i].f>>vc[i].s; } sort(ALL(vc), cmp); double ans=inf; REP(k, K+1){ /*if (k==0){ vector<double> cur; REP1(i,n) cur.pb(vc[i].f); sort(ALL(cur)); REP1(i, K){ ans+=cur[i]; } continue; } */ /*dp[1][1][1]=vc[1].s; dp[1][1][0]=vc[1].f/k; dp[1][0][0]=0; */ REP(i,maxn){ REP(j,maxn){ REP(l,maxn){ dp[i][j][l]=inf; } } } dp[1][1][1]=vc[1].s; dp[1][1][0]=vc[1].f/(k+1); dp[1][0][0]=0; FOR(i,2,n+1){ dp[i][0][0]=0.0; FOR(j, 1, i+1){ dp[i][j][0]=min(dp[i-1][j-1][0]+vc[i].f/(k+1), dp[i-1][j][0]); FOR(l, 1, j+1){ if (vc[i].s==-1){ dp[i][j][l]=min(dp[i-1][j-1][l]+vc[i].f/(k+1), dp[i-1][j][l]); } else dp[i][j][l]=min({dp[i-1][j-1][l-1]+vc[i].s/l, dp[i-1][j-1][l]+vc[i].f/(k+1), dp[i-1][j][l]}); } } } ans=min(ans, dp[n][K][k]); } cout<<ans<<endl; }
#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...