oj.uz

Submission #534093

# Submission time Handle Problem Language Result Execution time Memory
534093 2022-03-08T00:59:53 Z balbit Let's Win the Election (JOI22_ho_t3) C++14
21 / 100
 267 ms 2360 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<ll, ll>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template <typename T> void _do( T && x) {cerr<<x<<endl;}
template <typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 500+5;
const ll inf = 1ll<<62;

int A[maxn], B[maxn];

double dp[maxn][maxn];
ll mnsum[maxn];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    bug(1,2);

    int n, k; cin>>n>>k;
    vector<pii> bo(n);
    REP(i,n) {
        cin>>bo[i].s>>bo[i].f;
        if (bo[i].f == -1) bo[i].f = inf;
    }
    sort(ALL(bo));

    REP1(i,n) {
        A[i] = bo[i-1].s; B[i] = bo[i-1].f;
        bug(i,A[i],B[i]);
    }

    vector<ll> tmp;
    for (int i = n; i>=1; --i) {
        tmp.pb(A[i]);
        int need = k-i+1;
        sort(ALL(tmp));
        REP(j, need) mnsum[i] += tmp[j];
        bug(i, mnsum[i]);
    }
    double re = inf;
    for (int TC = 1; TC <=k; ++TC) {
        // total number of collaborators + 1
        REP(i, maxn) fill(dp[i], dp[i]+maxn, inf);
        dp[0][1] = 0;
        REP1(i,n) {
            REP1(t, TC+1) {
                if (t>1) MN(dp[i][t], dp[i-1][t-1] + B[i] / (double)(t-1));
                MN(dp[i][t], dp[i-1][t] +   A[i] / (double)(TC));
            }
            MN(re, dp[i][TC] + mnsum[i+1] / (double)TC);
        }

    }
    cout<<fixed<<setprecision(10)<<re<<endl;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2240 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 1 ms 2252 KB Output is correct
5 Correct 12 ms 2344 KB Output is correct
6 Correct 26 ms 2360 KB Output is correct
7 Correct 76 ms 2352 KB Output is correct
8 Correct 127 ms 2232 KB Output is correct
9 Correct 167 ms 2228 KB Output is correct
10 Correct 102 ms 2252 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2240 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 1 ms 2252 KB Output is correct
5 Correct 12 ms 2344 KB Output is correct
6 Correct 26 ms 2360 KB Output is correct
7 Correct 76 ms 2352 KB Output is correct
8 Correct 127 ms 2232 KB Output is correct
9 Correct 167 ms 2228 KB Output is correct
10 Correct 102 ms 2252 KB Output is correct
11 Correct 2 ms 2240 KB Output is correct
12 Correct 46 ms 2320 KB Output is correct
13 Correct 34 ms 2264 KB Output is correct
14 Correct 30 ms 2252 KB Output is correct
15 Correct 106 ms 2244 KB Output is correct
16 Correct 94 ms 2316 KB Output is correct
17 Correct 97 ms 2232 KB Output is correct
18 Correct 182 ms 2252 KB Output is correct
19 Correct 267 ms 2236 KB Output is correct
20 Correct 184 ms 2320 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 2320 KB Output is correct
2 Correct 170 ms 2320 KB Output is correct
3 Correct 173 ms 2324 KB Output is correct
4 Correct 215 ms 2320 KB Output is correct
5 Correct 171 ms 2252 KB Output is correct
6 Correct 167 ms 2348 KB Output is correct
7 Correct 171 ms 2324 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2240 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 1 ms 2252 KB Output is correct
5 Correct 12 ms 2344 KB Output is correct
6 Correct 26 ms 2360 KB Output is correct
7 Correct 76 ms 2352 KB Output is correct
8 Correct 127 ms 2232 KB Output is correct
9 Correct 167 ms 2228 KB Output is correct
10 Correct 102 ms 2252 KB Output is correct
11 Correct 2 ms 2240 KB Output is correct
12 Correct 46 ms 2320 KB Output is correct
13 Correct 34 ms 2264 KB Output is correct
14 Correct 30 ms 2252 KB Output is correct
15 Correct 106 ms 2244 KB Output is correct
16 Correct 94 ms 2316 KB Output is correct
17 Correct 97 ms 2232 KB Output is correct
18 Correct 182 ms 2252 KB Output is correct
19 Correct 267 ms 2236 KB Output is correct
20 Correct 184 ms 2320 KB Output is correct
21 Incorrect 1 ms 2244 KB Output isn't correct
22 Halted 0 ms 0 KB -