oj.uz

Submission #534383

# Submission time Handle Problem Language Result Execution time Memory
534383 2022-03-08T06:21:22 Z Cookie197 Let's Win the Election (JOI22_ho_t3) C++14
5 / 100
 13 ms 18636 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<iomanip>
using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define mp make_pair
#define endl "\n"
#define out(x) cout << #x << " = " << x << endl
#define outp(x) cout << #x << ".first = " << x.first << "  " << #x << ".second = " << x.second << endl
#pragma GCC optimize("Ofast")
#define lll __int128

// enumerate the num of collaborators, from 0 to k-1
// it is optimal to collect all collaborators first, then give speeches
// if we know which collaborators to choose, it's better to choose the ones with smaller b first
void chmin(double &a, double x){
    if (x<a) a=x;
}
ll n,k;
pii arr[505];
bool subtask1 = true, subtask2 = true;
// 看到第i個人，拿到了j票，目前people = p，最少時間
double dp[105][105][105];

bool comp(pii a, pii b){
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>arr[i].first>>arr[i].second;
        if (arr[i].second != -1) subtask1 = false;
        if (arr[i].second != -1 && arr[i].second != arr[i].first) subtask2 = false;
        if (arr[i].second == -1) arr[i].second = 1e9;
    }

    if (subtask1){
        sort(arr+1,arr+n+1);
        int ans = 0;
        for (int i=1;i<=k;i++) ans+=arr[i].first;
        cout<<ans<<endl;
        return 0;
    }

    sort(arr+1,arr+1+n,comp);
    double best = 1e15;
    for (ll goalp=1;goalp<=k;goalp++){ // 枚舉要選幾個collab
        for (int i=1;i<=n;i++) for (int j=0;j<=100;j++) for (int p=0;p<=100;p++) dp[i][j][p] = 1e15;
        dp[1][0][1] = 0; dp[1][1][1] = arr[1].first/goalp; dp[1][1][2] = arr[1].second;
        for (ll i=1;i<=n;i++) for (int j=0;j<=i;j++) for (int p=1;p<=min(goalp,i+1);p++){
            //cout<<i<<"  "<<j<<"  "<<p<<"   "<<dp[i][j][p]<<endl;
            chmin(dp[i+1][j][p], dp[i][j][p]);
            chmin(dp[i+1][j+1][p], dp[i][j][p] + 1.0*arr[i+1].first/goalp); // 「只拿到票的」要等拿完所有collab再選
            if (arr[i+1].second != 1e9) chmin(dp[i+1][j+1][p+1], dp[i][j][p] + 1.0*arr[i+1].second/p);
        }
        best = min(best, dp[n][k][goalp]);
    }

    
    cout<<fixed<<setprecision(13);
    cout<<best<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Runtime error 13 ms 18636 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Incorrect 1 ms 844 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Incorrect 1 ms 844 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Incorrect 1 ms 844 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 18608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Runtime error 13 ms 18636 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -