Submission #990130

#	Time	Username	Problem	Language	Result	Execution time	Memory
990130		Malix	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair

ll INF=1e18+10;
ll M=1e9+7;

    
int main() {   
//ios::sync_with_stdio(0);
//cin.tie(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
    int n,k;cin>>n>>k;
    pii a(n),b(n);
    REP(i,0,n)cin>>a[i].F>>b[i].F;
    REP(i,0,n){
        a[i].S=i;
        b[i].S=i;
    }
    pii p,q;
    REP(i,0,n)p.PB({a[i]});
    REP(i,0,n)if(b[i].F!=-1)q.PB({b[i]});
    sort(p.begin(),p.end());
    sort(q.begin(),q.end());
    int x=q.size();
    double ans=1000000000.0;
    while(x>=0){
        vi d(n,0);
        double c=0.0;
        int t=1;
        REP(i,0,x){
            c+=(double)q[i].F/(double)t;
            d[q[i].S]=1;
            t++;
        }
        int y=t-1;
        int pos=0;
        while(y<k){
            if(d[p[pos].S]==1){
                pos++;
                continue;
            }
            c+=(double)p[pos].F/t;
            pos++;
            y++;
        }
        //cout<<x<<" "<<c<<"\n";
        ans=min(ans,c);
        x--;
    }
    cout<<fixed<<setprecision(15)<<ans;
}

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