oj.uz

Submission #534668

# Submission time Handle Problem Language Result Execution time Memory
534668 2022-03-08T13:32:16 Z Cookie197 Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 1000 ms 2316 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[505][505][505];

// 看到第i個人，選了j個B類
double dp[505][505];

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;
    int good=n; 
    for (int i=1;i<=n;i++) {
        cin>>arr[i].first>>arr[i].second;
        if (arr[i].second == -1) arr[i].second = 1e9, good--;
    }

    double best = 1e9;
    sort(arr+1,arr+1+n,comp);
    for (int goal=0;goal<=k;goal++){
        if (goal>good) continue;
        for (int i=0;i<=n+3;i++) for (int j=0;j<=n+3;j++) dp[i][j] = 1e9;
        dp[1][0] = 1.0*arr[1].first/(goal+1); dp[1][1] = arr[1].second;

        for (int i=1;i<k;i++) for (int j=0;j<goal;j++){
            chmin(dp[i+1][j], dp[i][j] + 1.0*arr[i+1].first/(1+goal));
            if (arr[i].second != 1e9) chmin(dp[i+1][j+1], dp[i][j] + 1.0*arr[i+1].second/(1+j));
        }

        double now = 1e9;
        for (int pos=goal;pos<=k;pos++){ // position of last collaborator
            vector<int> tmp;
            for (int i=pos+1;i<=n;i++){ // 還要選k-pos個A類
                tmp.push_back(arr[i].first);
            }
            sort(tmp.begin(),tmp.end());
            double cost = 0;
            for (int i=0;i<k-pos;i++) cost += 1.0*tmp[i];
            cost /= (goal+1);
            now = min(now, cost + dp[pos][goal]);
        }
        best = min(now, best);
    }
    cout<<fixed<<setprecision(9)<<best<<endl;
    
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 4 ms 2216 KB Output is correct
10 Correct 2 ms 2252 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 70 ms 2300 KB Output is correct
13 Correct 115 ms 2252 KB Output is correct
14 Correct 91 ms 2304 KB Output is correct
15 Correct 252 ms 2252 KB Output is correct
16 Correct 364 ms 2300 KB Output is correct
17 Correct 170 ms 2300 KB Output is correct
18 Correct 466 ms 2300 KB Output is correct
19 Correct 432 ms 2296 KB Output is correct
20 Correct 162 ms 2252 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 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 948 ms 2304 KB Output is correct
2 Correct 1000 ms 2300 KB Output is correct
3 Correct 916 ms 2316 KB Output is correct
4 Correct 964 ms 2300 KB Output is correct
5 Correct 970 ms 2304 KB Output is correct
6 Correct 936 ms 2252 KB Output is correct
7 Correct 765 ms 2304 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 4 ms 2216 KB Output is correct
10 Correct 2 ms 2252 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 70 ms 2300 KB Output is correct
13 Correct 115 ms 2252 KB Output is correct
14 Correct 91 ms 2304 KB Output is correct
15 Correct 252 ms 2252 KB Output is correct
16 Correct 364 ms 2300 KB Output is correct
17 Correct 170 ms 2300 KB Output is correct
18 Correct 466 ms 2300 KB Output is correct
19 Correct 432 ms 2296 KB Output is correct
20 Correct 162 ms 2252 KB Output is correct
21 Incorrect 0 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -