oj.uz

Submission #653712

# Submission time Handle Problem Language Result Execution time Memory
653712 2022-10-27T19:09:17 Z someone Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 644 ms 396 KB 
#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++) {
        bool change = false;
        pos[reg[1][i].id][0] = true;
        if(!pos[reg[1][i].id][1]) {
            change = true;
            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 && (change || i == 0))
            solve();
    }
    cout << setprecision(10) << fixed << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 644 ms 372 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 644 ms 372 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 27 ms 340 KB Output is correct
14 Correct 35 ms 340 KB Output is correct
15 Correct 4 ms 392 KB Output is correct
16 Correct 211 ms 372 KB Output is correct
17 Correct 77 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 6 ms 340 KB Output is correct
20 Correct 6 ms 340 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 644 ms 372 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 27 ms 340 KB Output is correct
14 Correct 35 ms 340 KB Output is correct
15 Correct 4 ms 392 KB Output is correct
16 Correct 211 ms 372 KB Output is correct
17 Correct 77 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 6 ms 340 KB Output is correct
20 Correct 6 ms 340 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -