Submission #1210963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210963		VMaksimoski008	Let's Win the Election (JOI22_ho_t3)	C++20	61 / 100	2618 ms	984788 KiB

Main

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 5;

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, x, cnt=0; cin >> n >> x;
    vector<ar<ll, 2> > a(n+1);

    for(int i=1; i<=n; i++) {
        cin >> a[i][1] >> a[i][0];
        if(a[i][0] != -1) cnt++;
    }
    sort(a.begin()+1, a.end());

    double ans = 1e18, dp[n+1][x+1][x+1];
    for(int c=0; c<=min(x, cnt); c++) {
        for(int i=0; i<=n; i++)
            for(int j=0; j<=x; j++)
                for(int k=0; k<=c; k++)
                    dp[i][j][k] = 1e18;
        dp[0][0][0] = 0;

        for(int i=1; i<=n; i++) {
            for(int j=0; j<=x; j++) {
                for(int k=0; k<=min(j, c); k++) {
                    dp[i][j][k] = dp[i-1][j][k];

                    if(j) {
                        dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k] + (double)a[i][1] / (1 + c));
                    }

                    if(k && a[i][0] != -1) {
                        dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k-1] + (double)a[i][0] / k);
                    }
                }
            }
        }

        ans = min(ans, dp[n][x][c]);
    }

    cout << setprecision(3) << fixed << ans << '\n';
}

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