Submission #962936

#	Time	Username	Problem	Language	Result	Execution time	Memory
962936		RaresFelix	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1022 ms	4540 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<ii> V(n);
    for(int i = 0; i < n; ++i) {
        cin >> V[i].first >> V[i].second;
        if(V[i].second == -1) V[i].second = 1e9;
    }
    sort(all(V), [&](auto a, auto b) {
            if(a.second != b.second) return a.second < b.second;
            return a < b;
    });
    vi A(n), B(n);
    for(int i = 0; i < n; ++i) {
        A[i] = V[i].first;
        B[i] = V[i].second;
    }
    
    const ld INF = 1e18;
    vector<vector<ld> > DP(n, vector<ld>(k + 1, INF));
    ld re = INF;
    for(int nr = 0; nr <= k; ++nr) { /// cati b aleg
        for(int i = 0; i < n; ++i)
            for(int j = 0; j <= k; ++j) DP[i][j] = INF;
        ///DP[i][j] : 0...i alegand j A-uri
        ld fact = 1. / ld(nr + 1);
        if(nr)
            DP[0][0] = B[0];
        else DP[0][0] = 0.;
        DP[0][1] = A[0] * fact;
        for(int i = 0; i + 1 < n; ++i) {
            for(int j = 0; j <= min(i + 1, k - nr); ++j) {
                int curB = i + 1 - j;
                if(curB >= nr) {
                    DP[i + 1][j] = min(DP[i + 1][j], DP[i][j]); /// nu aleg nimic
                }
                ///aleg A
                if(j + 1 <= k)
                    DP[i + 1][j + 1] = min(DP[i + 1][j + 1], DP[i][j] + A[i + 1] * fact);
                ///aleg B
                if(curB < nr) {
                    DP[i + 1][j] = min(DP[i + 1][j], DP[i][j] + ld(B[i + 1]) / ld(curB + 1));
                }
            }
        }
        re = min(re, DP[n - 1][k - nr]);
    }
    cout << fixed << setprecision(10) << re << "\n";
    return 0;
}

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