oj.uz

Submission #534663

# Submission time Handle Problem Language Result Execution time Memory
534663 2022-03-08T13:23:09 Z Cookie197 Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 1104 ms 2308 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));
            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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 2236 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 3 ms 2244 KB Output is correct
10 Correct 3 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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 2236 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 3 ms 2244 KB Output is correct
10 Correct 3 ms 2252 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 112 ms 2308 KB Output is correct
13 Correct 143 ms 2304 KB Output is correct
14 Correct 92 ms 2308 KB Output is correct
15 Correct 341 ms 2308 KB Output is correct
16 Correct 388 ms 2300 KB Output is correct
17 Correct 190 ms 2300 KB Output is correct
18 Correct 450 ms 2308 KB Output is correct
19 Correct 500 ms 2300 KB Output is correct
20 Correct 193 ms 2304 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 1 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 1076 ms 2300 KB Output is correct
2 Correct 986 ms 2296 KB Output is correct
3 Correct 1000 ms 2300 KB Output is correct
4 Correct 1039 ms 2296 KB Output is correct
5 Correct 1065 ms 2300 KB Output is correct
6 Correct 1104 ms 2304 KB Output is correct
7 Correct 845 ms 2308 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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 2236 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 3 ms 2244 KB Output is correct
10 Correct 3 ms 2252 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 112 ms 2308 KB Output is correct
13 Correct 143 ms 2304 KB Output is correct
14 Correct 92 ms 2308 KB Output is correct
15 Correct 341 ms 2308 KB Output is correct
16 Correct 388 ms 2300 KB Output is correct
17 Correct 190 ms 2300 KB Output is correct
18 Correct 450 ms 2308 KB Output is correct
19 Correct 500 ms 2300 KB Output is correct
20 Correct 193 ms 2304 KB Output is correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -