Submission #962929

#	Time	Username	Problem	Language	Result	Execution time	Memory
962929		RaresFelix	Let's Win the Election (JOI22_ho_t3)	C++17	56 / 100	2562 ms	1048576 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<vector<ld> > > DP(n, vector(k + 1, vector<ld>(k + 1, INF)));
    ld re = INF;
    for(int nr = 0; nr <= k; ++nr) { 
        for(int i = 0; i < n; ++i)
            for(int j = 0; j <= k; ++j)
                for(int w = 0; w <= k; ++w) DP[i][j][w] = INF;
        ld fact = 1. / ld(nr + 1);
        DP[0][1][0] = fact * A[0];
        DP[0][0][1] = B[0]; 
        DP[0][0][0] = 0.;
        for(int i = 0; i + 1 < n; ++i) {
            for(int j = 0; j <= k; ++j) //nr A
                for(int w = 0; w <= k; ++w) {
                    if(j + 1 <= k)
                        DP[i + 1][j + 1][w] = min(DP[i + 1][j + 1][w], DP[i][j][w] + fact * A[i + 1]);
                    if(w + 1 <= k)
                        DP[i + 1][j][w + 1] = min(DP[i + 1][j][w + 1], DP[i][j][w] + B[i + 1] / ld(w + 1));
                    DP[i + 1][j][w] = min(DP[i + 1][j][w], DP[i][j][w]);
                }
        }
        re = min(re, DP[n - 1][k - nr][nr]);
    }
    cout << fixed << setprecision(10) << re << "\n";
    return 0;
}

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