답안 #922710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922710	2024-02-06T03:44:22 Z	GrindMachine	Let's Win the Election (JOI22_ho_t3)	C++17	23 / 100	842 ms	1048576 KB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<pll> a(n);
    rep(i,n) cin >> a[i].ff >> a[i].ss;

    double dp[1<<n][n+5];
    rep(i,1<<n) rep(j,n+5) dp[i][j] = inf2;
    dp[0][1] = 0;

    rep(mask,1<<n){
        rep(i,n){
            if(mask&(1<<i)) conts;
            ll mask2 = mask|(1<<i);

            rep1(j,n){
                // get vote
                amin(dp[mask2][j],dp[mask][j]+(double)a[i].ff/j);

                // get vote + collab
                if(a[i].ss != -1){
                    amin(dp[mask2][j+1],dp[mask][j]+(double)a[i].ss/j);
                }
            }
        }
    }

    double ans = inf2;
    rep(mask,1<<n){
        if(setbits(mask) < k) conts;
        rep1(j,n+1){
            amin(ans,dp[mask][j]);
        }
    }

    cout << fixed << setprecision(11);
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Runtime error	558 ms	1048576 KB	Execution killed with signal 9
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Runtime error	558 ms	1048576 KB	Execution killed with signal 9
6	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	842 ms	205636 KB	Output is correct
17	Correct	815 ms	205636 KB	Output is correct
18	Correct	770 ms	205856 KB	Output is correct
19	Correct	798 ms	205628 KB	Output is correct
20	Correct	737 ms	205652 KB	Output is correct
21	Correct	707 ms	205628 KB	Output is correct
22	Correct	794 ms	205764 KB	Output is correct
23	Correct	734 ms	205652 KB	Output is correct
24	Correct	683 ms	205628 KB	Output is correct
25	Correct	806 ms	205628 KB	Output is correct
26	Correct	758 ms	205396 KB	Output is correct
27	Correct	796 ms	205628 KB	Output is correct
28	Correct	794 ms	205624 KB	Output is correct
29	Correct	798 ms	205624 KB	Output is correct
30	Correct	799 ms	205620 KB	Output is correct
31	Correct	820 ms	205804 KB	Output is correct
32	Correct	806 ms	205624 KB	Output is correct
33	Correct	811 ms	205628 KB	Output is correct
34	Correct	798 ms	205628 KB	Output is correct
35	Correct	800 ms	205628 KB	Output is correct
36	Correct	801 ms	205628 KB	Output is correct
37	Correct	798 ms	205624 KB	Output is correct
38	Correct	802 ms	205628 KB	Output is correct
39	Correct	800 ms	205652 KB	Output is correct
40	Correct	803 ms	205652 KB	Output is correct

Subtask #5
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	842 ms	205636 KB	Output is correct
17	Correct	815 ms	205636 KB	Output is correct
18	Correct	770 ms	205856 KB	Output is correct
19	Correct	798 ms	205628 KB	Output is correct
20	Correct	737 ms	205652 KB	Output is correct
21	Correct	707 ms	205628 KB	Output is correct
22	Correct	794 ms	205764 KB	Output is correct
23	Correct	734 ms	205652 KB	Output is correct
24	Correct	683 ms	205628 KB	Output is correct
25	Correct	806 ms	205628 KB	Output is correct
26	Correct	758 ms	205396 KB	Output is correct
27	Correct	796 ms	205628 KB	Output is correct
28	Correct	794 ms	205624 KB	Output is correct
29	Correct	798 ms	205624 KB	Output is correct
30	Correct	799 ms	205620 KB	Output is correct
31	Correct	820 ms	205804 KB	Output is correct
32	Correct	806 ms	205624 KB	Output is correct
33	Correct	811 ms	205628 KB	Output is correct
34	Correct	798 ms	205628 KB	Output is correct
35	Correct	800 ms	205628 KB	Output is correct
36	Correct	801 ms	205628 KB	Output is correct
37	Correct	798 ms	205624 KB	Output is correct
38	Correct	802 ms	205628 KB	Output is correct
39	Correct	800 ms	205652 KB	Output is correct
40	Correct	803 ms	205652 KB	Output is correct
41	Runtime error	1 ms	604 KB	Execution killed with signal 11
42	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	580 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Runtime error	558 ms	1048576 KB	Execution killed with signal 9
6	Halted	0 ms	0 KB	-

답안 #922710

Compilation message

Subtask #1 0 / 5.0

Subtask #2 0 / 5.0

Subtask #3 11.0 / 11.0

Subtask #4 12.0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
0 / 5.0

Subtask #3
11.0 / 11.0

Subtask #4
12.0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0