Submission #653708

#	Time	Username	Problem	Language	Result	Execution time	Memory
653708		someone	Let's Win the Election (JOI22_ho_t3)	C++14	0 / 100	2576 ms	392 KiB

Main

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

struct Region {
    int a, b, id, val = 0;
    
    bool operator <(const Region& other) const {
        return val < other.val;
    }
};

const int N = 5e2 + 42, INF = 1e7 + 42;

int n, k, nb, id = 0;
long double ans = INF;
Region reg[3][N], act[N];
bool chosen[N], pos[N][2];

void solve() {
    int x = 0;
    for(int i = 0; i < n; i++)
        if(pos[reg[0][i].id][0] || pos[reg[0][i].id][1]) {
            act[x] = reg[0][i];
            x++;
        }
    for(int i = 0; i <= k; i++) {
        long double cost = 0;
        if(i != 0)
            for(int j = 0; j < k; j++)
                act[j].val = (i+1) * act[j].b - i * act[j].a;
        sort(act, act + k);
        sort(act, act + i,
        [](Region a, Region b) {
            return a.b < b.b;
        });
        for(int j = 0; j < i; j++)
            cost += (long double)act[j].b / (j+1);
        for(int j = i; j < k; j++)
            cost += (long double)act[j].a / (i+1);
        ans = min(ans, cost);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    
    nb = n;
    for(int i = 0; i < n; i++) {
        cin >> reg[0][i].a >> reg[0][i].b;
        pos[i][1] = true;
        if(reg[0][i].b == -1)
            reg[0][i].b = INF;
        reg[0][i].id = i;
        reg[2][i] = reg[1][i] = reg[0][i];
    }
    
    sort(reg[1], reg[1] + n,
    [](Region a, Region b) {
        if(a.b == b.b)
            return a.a < b.a;
        return a.b < b.b;
    });
    sort(reg[2], reg[2] + n,
    [](Region a, Region b) {
        if(a.a == b.a)
            return a.b > b.b;
        return a.a > b.a;
    });
    
    for(int i = 0; i < n; i++) {
        pos[reg[1][i].id][0] = true;
        if(!pos[reg[1][i].id][1])
            nb++;
        while(id < n && nb > k) {
            pos[reg[2][id].id][1] = false;
            if(!pos[reg[2][id].id][0])
                nb--;
            id++;
        }
        if(nb == k)
            solve();
    }
    cout << setprecision(6) << fixed << ans;
}

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