Submission #1201396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201396		vincentbucourt1	Let's Win the Election (JOI22_ho_t3)	C++20	5 / 100	1285 ms	16220 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define ld long double

const int MAXN = 502;

int N, K;
struct State{ld vote, colab;};
bool cmpStates (const State& a, const State& b) {
    if (a.colab == -1) return false;
    else if (b.colab == -1) return true;
    else return a.colab < b.colab;
}
vector<State> states;
struct Situ{
    ld sumVote, sumColab;
    bool operator> (const Situ& other) const {
        if (sumVote+sumColab > other.sumVote+other.sumColab) return true;
        else if (sumVote+sumColab < other.sumVote+other.sumColab) return false;
        else return sumColab > other.sumColab;
    }
};
Situ dp[2][MAXN][MAXN];
ld ans = (ld)1e18;

signed main() {
    fastIO();
    cin >> N >> K;
    states.assign(N, State{(ld)0,(ld)0});
    for (int i = 0; i < N; i++) {
        cin >> states[i].vote >> states[i].colab;
    }
    sort(states.begin(), states.end(), cmpStates);
    // for (int i = 0; i < N; i++) cerr << states[i].vote << " " << states[i].colab << "\n";
    for (int numVote = 0; numVote <= K; numVote++) {
        for (int numColab = 0; numColab <= K; numColab++) {
            dp[0][numVote][numColab] = Situ{(ld)1e18, (ld)1e18};
            dp[1][numVote][numColab] = Situ{(ld)1e18, (ld)1e18};
        }
    }
    dp[0][0][0] = Situ{0, 0};
    for (int idx = 0; idx < N; idx++) {
        for (int numVote = 0; numVote <= K; numVote++) {
            for (int numColab = 0; numColab <= K; numColab++) {
                Situ situOn = dp[idx%2][numVote][numColab];
                if (dp[(idx+1)%2][numVote][numColab] > Situ{situOn.sumVote, situOn.sumColab}) {
                    dp[(idx+1)%2][numVote][numColab] = situOn;
                }
                if (numVote+1 <= K && dp[(idx+1)%2][numVote+1][numColab] > Situ{situOn.sumVote + states[idx].vote, situOn.sumColab}) {
                    dp[(idx+1)%2][numVote+1][numColab] = situOn;
                    dp[(idx+1)%2][numVote+1][numColab].sumVote += states[idx].vote;
                }
                if (numVote+1 <= K && numColab+1 <= K && states[idx].colab != -1 && dp[(idx+1)%2][numVote+1][numColab+1] > Situ{situOn.sumVote, situOn.sumColab + states[idx].colab/(numColab+1)}) {
                    dp[(idx+1)%2][numVote+1][numColab+1] = situOn;
                    dp[(idx+1)%2][numVote+1][numColab+1].sumColab += states[idx].colab/(numColab+1);
                }
            }
        }
    }
    for (int numColab = 0; numColab <= K; numColab++) {
        ans = min(ans, dp[N%2][K][numColab].sumColab + dp[N%2][K][numColab].sumVote/(numColab+1));
    }
    cout << fixed << setprecision(12) << ans << "\n";
}

• Subtask 1: 5 / 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