oj.uz

Submission #653708

# Submission time Handle Problem Language Result Execution time Memory
653708 2022-10-27T18:56:41 Z someone Let's Win the Election (JOI22_ho_t3) C++14
0 / 100
 2500 ms 392 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++) {
        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 33 ms 380 KB Output is correct
7 Correct 297 ms 376 KB Output is correct
8 Correct 1108 ms 372 KB Output is correct
9 Execution timed out 2576 ms 340 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 33 ms 380 KB Output is correct
7 Correct 297 ms 376 KB Output is correct
8 Correct 1108 ms 372 KB Output is correct
9 Execution timed out 2576 ms 340 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2564 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 33 ms 380 KB Output is correct
7 Correct 297 ms 376 KB Output is correct
8 Correct 1108 ms 372 KB Output is correct
9 Execution timed out 2576 ms 340 KB Time limit exceeded
10 Halted 0 ms 0 KB -