| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 638629 | browntoad | Let's Win the Election (JOI22_ho_t3) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 pii pair<int, int>
#define pdd pair<double ,double>
#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=505;
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);
}
//=======================================================================================
int n, k;
vector<pii> vc;
bool cmp(pii a, pii b){
if (a.s==-1&&b.s==-1){
return a.f<b.f;
}
if (a.s==-1||b.s==-1){
return a.s>b.s;
}
return a.s<b.s;
}
double dp[maxn][maxn], sf[maxn][maxn];
signed main (){
IOS();
cout<<fixed<<setprecision(15);
cin>>n>>k;
REP(i, n){
int x, y; cin>>x>>y;
vc.pb({x, y});
}
sort(ALL(vc), cmp);
REP(i, maxn){
REP(j, maxn){
if (j==0) sf[i][j]=0;
else sf[i][j]=inf;
}
}
RREP(i, n){
vector<int> cur;
FOR(j, i, n){
cur.pb(vc[j].f);
}
sort(ALL(cur));
REP1(j, k){
if (j>SZ(cur)) break;
else sf[i][j]=sf[i][j-1]+cur[j-1];
}
}
long double res=sf[0][k];
REP1(t, k){
REP(i, n){
REP(j, t+1){
dp[i][j]=inf;
}
}
REP(i, n){
if (i==0){
dp[i][0]=(0.0+vc[i].f)/(t+1);
if (vc[i].s!=-1) dp[i][1]=(0.0+vc[i].s);
continue;
}
REP(j, t+1){
if (j>i+1) break;
if (j==0){
dp[i][0]=dp[i-1][0]+(0.0+vc[i].f)/(t+1);
}
else dp[i][j]=min(dp[i-1][j]+(0.0+vc[i].f)/(t+1), ((vc[i].s!=-1)?(dp[i-1][j-1]+(0.0+vc[i].s)/(j)):(0.0+inf)));
}
}
REP(i, n){
res=min(res, dp[i][t]+sf[i+1][k-t]/(t+1));
}
//res=min(res, dp[t-1][t]+(0.0+sf[t][k-t])/(t+1)); // 0 base
}
cout<<res<<endl;
}