답안 #1067432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067432	2024-08-20T16:56:22 Z	Whisper	Let's Win the Election (JOI22_ho_t3)	C++17	21 / 100	214 ms	4444 KB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX                 505
int N, K;
double A[MAX], B[MAX];

double dp[MAX][MAX], cost[MAX][MAX];
void process(void){
    cin >> N >> K;
    for (int i = 1; i <= N; ++i){
        cin >> A[i] >> B[i];
        if(B[i] == -1) B[i] = 1e9;
    }
    vector<int> order(N + 1);
    iota(order.begin(), order.end(), 0);

    sort(order.begin() + 1, order.end(), [&](int &i, int &j){
        return B[i] < B[j];
    });

    vector<double> vals;
    FOR(i, 0, N) FOR(j, 0, N) cost[i][j] = 1e9;
    for (int i = N; i >= 1; --i){
        vals.push_back(A[order[i]]);
        sort(vals.begin(), vals.end());
        double sm = 0;
        cost[i][0] = 0;
        for (int j = 0; j < (int)vals.size(); ++j){
            sm += vals[j];
            cost[i][j + 1] = sm;
        }
    }
    double ans = cost[1][K];
    for (int tak = 0; tak <= K; ++tak){
        for (int i = 0; i <= K; ++i){
            for (int j = 0; j <= K; ++j){
                dp[i][j] = 1e9;
            }
        }
        dp[0][0] = 0;
        for (int i = 1; i <= K; ++i){
            for (int j = 0; j <= i; ++j){
                dp[i][j] = dp[i - 1][j] + (double)A[order[i]] / (double)(tak + 1);
                if(j > 0)
                    minimize(dp[i][j], dp[i - 1][j - 1] + (double)B[order[i]] / (double)(j));
                if(j == tak){
                    int need = K - j;
                    minimize(ans, dp[i][j] + (double)cost[i + 1][need] / (double)(tak + 1));
                }
            }
        }
    }
    cout << setprecision(10) << fixed << ans;
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	3 ms	2672 KB	Output is correct
6	Correct	6 ms	2908 KB	Output is correct
7	Correct	23 ms	3416 KB	Output is correct
8	Correct	68 ms	3928 KB	Output is correct
9	Correct	152 ms	4444 KB	Output is correct
10	Correct	55 ms	3676 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	3 ms	2672 KB	Output is correct
6	Correct	6 ms	2908 KB	Output is correct
7	Correct	23 ms	3416 KB	Output is correct
8	Correct	68 ms	3928 KB	Output is correct
9	Correct	152 ms	4444 KB	Output is correct
10	Correct	55 ms	3676 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	9 ms	3232 KB	Output is correct
13	Correct	8 ms	2908 KB	Output is correct
14	Correct	8 ms	3072 KB	Output is correct
15	Correct	58 ms	3676 KB	Output is correct
16	Correct	58 ms	3676 KB	Output is correct
17	Correct	59 ms	3676 KB	Output is correct
18	Correct	156 ms	4444 KB	Output is correct
19	Correct	155 ms	4440 KB	Output is correct
20	Correct	158 ms	4440 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Incorrect	348 KB	Output isn't correct
10	Halted	0 KB	-

Subtask #4
0 / 12.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Incorrect	348 KB	Output isn't correct
10	Halted	0 KB	-

Subtask #5
0 / 33.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Incorrect	348 KB	Output isn't correct
10	Halted	0 KB	-

Subtask #6
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	4428 KB	Output is correct
2	Correct	172 ms	4440 KB	Output is correct
3	Correct	163 ms	4188 KB	Output is correct
4	Correct	190 ms	4444 KB	Output is correct
5	Correct	214 ms	4440 KB	Output is correct
6	Correct	162 ms	4444 KB	Output is correct
7	Correct	168 ms	4444 KB	Output is correct

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	3 ms	2672 KB	Output is correct
6	Correct	6 ms	2908 KB	Output is correct
7	Correct	23 ms	3416 KB	Output is correct
8	Correct	68 ms	3928 KB	Output is correct
9	Correct	152 ms	4444 KB	Output is correct
10	Correct	55 ms	3676 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	9 ms	3232 KB	Output is correct
13	Correct	8 ms	2908 KB	Output is correct
14	Correct	8 ms	3072 KB	Output is correct
15	Correct	58 ms	3676 KB	Output is correct
16	Correct	58 ms	3676 KB	Output is correct
17	Correct	59 ms	3676 KB	Output is correct
18	Correct	156 ms	4444 KB	Output is correct
19	Correct	155 ms	4440 KB	Output is correct
20	Correct	158 ms	4440 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Incorrect	0 ms	348 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #1067432

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 11.0

Subtask #4 0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 11.0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
11.0 / 11.0

Subtask #7
0 / 23.0