oj.uz

Submission #666521

# Submission time Handle Problem Language Result Execution time Memory
666521 2022-11-28T20:40:26 Z mychecksedad Boarding Passes (BOI22_passes) C++17
55 / 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){
        pref.clear();
        pref.resize(n);
        for(int j = 0; j < 15; ++j){
            if(mask&(1<<j)){
                for(int pos: v[j]) pref[pos] = 1;
            }
        }
        for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + pref[i];
        for(int j = 0; j < 15; ++j){
            if(mask&(1<<j)){
                double passes = 0;

                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]] - (s-i-1);
                }
                passes = cur + s*(s-1)/4.0;
                for(long long i = 1; i <= s; ++i){
                    cur -= pref[n - 1] - pref[v[j][i - 1]] - (s-(i-1)-1);
                    cur += pref[v[j][i - 1]] - i;
                    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 155 ms 468 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 4 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 4 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 4 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 173 ms 588 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2064 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 5 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 20 ms 584 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 21 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 22 ms 580 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 20 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 5 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 18 ms 584 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 580 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 584 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 580 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 10 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 20 ms 584 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 21 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 22 ms 580 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 20 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 5 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 18 ms 584 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 7 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 7 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 8 ms 580 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 584 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 9 ms 580 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 8 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 10 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 7 ms 576 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 20 ms 580 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 20 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 19 ms 588 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 20 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 6 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 17 ms 584 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 8 ms 584 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 8 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 8 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 7 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 580 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 9 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 7 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 8 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 8 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1731 ms 716 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1727 ms 704 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1752 ms 724 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 1704 ms 684 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 1673 ms 596 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 1692 ms 716 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 1669 ms 728 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 1671 ms 724 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 1681 ms 724 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 1663 ms 596 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 1667 ms 724 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 1663 ms 724 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 468 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 4 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 4 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 4 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 173 ms 588 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2064 ms 1424 KB Time limit exceeded
7 Halted 0 ms 0 KB -