oj.uz

Submission #681800

# Submission time Handle Problem Language Result Execution time Memory
681800 2023-01-14T11:39:04 Z sysia Let's Win the Election (JOI22_ho_t3) C++17
11 / 100
 2500 ms 348 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
typedef long double ld;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n, k; cin >> n >> k;
    vector<T>a(n);
    int power = 1;
    for (int i = 1; i<=n; i++) power *= 3;
    for (int i = 0; i<n; i++) {
        cin >> a[i].first >> a[i].second;
        if (a[i].second == -1) a[i].second = oo;
    }

    auto change = [&](int x){
        string s;
        while (x){
            s += (char)((x%3) + '0');
            x/=3;
        }
        reverse(s.begin(), s.end());
        return s;
    };
    ld ans = oo;
    vector<int>ord(n);
    iota(ord.begin(), ord.end(), 0);
    do{
        vector<T>b(n);
        for (int i = 0; i<n; i++) b[i] = a[ord[i]];
        for (int mask = 1; mask < power; mask++){
            string s = change(mask);
            // debug(mask, s);
            ld curr = 0;
            int col = 1, vote = 0;
            for (int i = 0; i<n; i++){
                if (s[i] == '0'){
                    continue;
                } else if (s[i] == '1'){
                    curr += (ld)(b[i].first)/(ld)(col);
                    vote++;
                } else {
                    if (a[i].second == oo) break;
                    curr += (ld)(b[i].second)/(ld)(col);
                    col++;
                    vote++;
                }
                if (vote == k) {
                    ans = min(ans, curr);
                    break;
                }
            }
            
        }
    } while (next_permutation(ord.begin(), ord.end()));
    cout << fixed << setprecision(15) << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Execution timed out 2567 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Execution timed out 2567 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 296 KB Output is correct
2 Correct 606 ms 296 KB Output is correct
3 Correct 599 ms 312 KB Output is correct
4 Correct 650 ms 300 KB Output is correct
5 Correct 688 ms 304 KB Output is correct
6 Correct 732 ms 300 KB Output is correct
7 Correct 676 ms 296 KB Output is correct
8 Correct 687 ms 304 KB Output is correct
9 Correct 706 ms 304 KB Output is correct
10 Correct 679 ms 304 KB Output is correct
11 Correct 675 ms 304 KB Output is correct
12 Correct 667 ms 212 KB Output is correct
13 Correct 679 ms 308 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 669 ms 296 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 296 KB Output is correct
2 Correct 606 ms 296 KB Output is correct
3 Correct 599 ms 312 KB Output is correct
4 Correct 650 ms 300 KB Output is correct
5 Correct 688 ms 304 KB Output is correct
6 Correct 732 ms 300 KB Output is correct
7 Correct 676 ms 296 KB Output is correct
8 Correct 687 ms 304 KB Output is correct
9 Correct 706 ms 304 KB Output is correct
10 Correct 679 ms 304 KB Output is correct
11 Correct 675 ms 304 KB Output is correct
12 Correct 667 ms 212 KB Output is correct
13 Correct 679 ms 308 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 669 ms 296 KB Output is correct
16 Execution timed out 2567 ms 348 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 296 KB Output is correct
2 Correct 606 ms 296 KB Output is correct
3 Correct 599 ms 312 KB Output is correct
4 Correct 650 ms 300 KB Output is correct
5 Correct 688 ms 304 KB Output is correct
6 Correct 732 ms 300 KB Output is correct
7 Correct 676 ms 296 KB Output is correct
8 Correct 687 ms 304 KB Output is correct
9 Correct 706 ms 304 KB Output is correct
10 Correct 679 ms 304 KB Output is correct
11 Correct 675 ms 304 KB Output is correct
12 Correct 667 ms 212 KB Output is correct
13 Correct 679 ms 308 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 669 ms 296 KB Output is correct
16 Execution timed out 2567 ms 348 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2572 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Execution timed out 2567 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -