Submission #536028

#	Time	Username	Problem	Language	Result	Execution time	Memory
536028		zaneyu	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	931 ms	4364 KiB

Main

/*input
20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll sub(ll a,ll b){
    ll x=a-b;
    while(x<0) x+=MOD;
    while(x>MOD) x-=MOD;
    return x;
}
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const ll maxn=500+5;
const ll maxlg=__lg(maxn)+2; 
ld dp[maxn][maxn],ndp[maxn][maxn];
pii arr[maxn];
int main(){
    int n,k;
    cin>>n>>k;
    int cnt=0;
    REP1(i,n){
        cin>>arr[i].s>>arr[i].f;
        if(arr[i].f==-1) arr[i].f=INF;
        else ++cnt;
    }
    sort(arr+1,arr+n+1);
    REP1(i,n){
        swap(arr[i].f,arr[i].s);
    }
    ld ans=INF;
    REP(a,min(k,cnt)+1){
        REP(i,n+1) REP(j,k-a+1) dp[i][j]=INF;
        dp[0][0]=0;
        REP1(i,n){
            REP(j,i+1){
                if(i-j>a){
                    dp[i][j]=dp[i-1][j];
                    if(j) MNTO(dp[i][j],dp[i-1][j-1]+(ld)arr[i].f/(a+1));
                }
                else{
                    dp[i][j]=(dp[i-1][j]+(ld)arr[i].s/(i-j));
                    if(j) MNTO(dp[i][j],dp[i-1][j-1]+(ld)arr[i].f/(a+1));
                }
            }
        }
        MNTO(ans,dp[n][k-a]);
    }
    cout<<fixed<<setprecision(20)<<ans<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23