oj.uz

Submission #666520

# Submission time Handle Problem Language Result Execution time Memory
666520 2022-11-28T20:32:18 Z mychecksedad Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 1424 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
const int N = 1e5 + 100;

int n;
string s;
double dp[N];
vector<int> v[15], pref, vis;

void solve(){
    cin >> s; n = s.length();

    for(int i = 0; i < n; ++i) v[s[i]-'A'].push_back(i);

    for(int i = 0; i < (1<<15); ++i) dp[i] = 1e15;

    dp[0] = 0;

    for(int mask = 1; mask < (1<<15); ++mask){
        for(int j = 0; j < 15; ++j){
            if(mask&(1<<j)){
                double passes = 0;

                pref.clear(); pref.resize(n);

                for(int i = 0; i < 15; ++i){
                    if(i != j && (mask&(1<<i)) > 0) for(int pos: v[i]) pref[pos] = 1; 
                }

                for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + pref[i];

                long long cur = 0;

                long long s = v[j].size();
                for(int i = 0; i < s; ++i){
                    cur += pref[n - 1] - pref[v[j][i]];
                }
                passes = cur + s*(s-1)/4.0;
                for(long long i = 1; i <= s; ++i){
                    cur -= pref[n - 1] - pref[v[j][i - 1]];
                    cur += pref[v[j][i - 1]];
                    long long k1 = s - i;
                    passes = min(passes, cur + (i*(i-1)+k1*(k1-1))/4.0);
                }

                dp[mask] = min(dp[mask], dp[mask^(1<<j)] + passes);
            }
        }
    }


    cout << dp[(1<<15)-1];
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    setp();
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:62:16: warning: unused variable 'aa' [-Wunused-variable]
   62 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 584 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 14 ms 580 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 909 ms 576 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2086 ms 1424 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 99 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 96 ms 564 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 95 ms 564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 98 ms 572 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 18 ms 584 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 81 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 30 ms 564 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 31 ms 584 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 33 ms 556 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 31 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 35 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 30 ms 584 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 32 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 31 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 30 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 32 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 99 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 96 ms 564 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 95 ms 564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 98 ms 572 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 18 ms 584 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 81 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 30 ms 564 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 31 ms 584 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 33 ms 556 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 31 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 35 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 30 ms 584 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 32 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 31 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 30 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 32 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 16 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 98 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 100 ms 564 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 99 ms 564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 100 ms 512 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 18 ms 568 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 81 ms 560 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 31 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 31 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 32 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 38 ms 564 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 34 ms 580 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 36 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 31 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 31 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 33 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 37 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2077 ms 596 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 584 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 14 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 14 ms 580 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 909 ms 576 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2086 ms 1424 KB Time limit exceeded
7 Halted 0 ms 0 KB -