oj.uz

Submission #824071

# Submission time Handle Problem Language Result Execution time Memory
824071 2023-08-13T12:51:51 Z ttamx Boarding Passes (BOI22_passes) C++14
100 / 100
 313 ms 179628 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int G=20;
const int N=1e5+5;
const int M=(1<<G)+5;
const ll inf=1e18;

int n,g;
int a[N];
vector<int> pos[G];
ll dp[M],pref[N],suff[N];
ll f[G][G][N];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed;
    string s;
    cin >> s;
    n=s.size();
    for(int i=1;i<=n;i++){
        a[i]=s[i-1]-'A';
        g=max(g,a[i]+1);
    }
    for(int i=0;i<g;i++)pos[i].emplace_back(0);
    for(int i=1;i<=n;i++)pos[a[i]].emplace_back(i);
    for(int i=0;i<g;i++){
        for(int j=0;j<g;j++){
            int add=i==j?1:2;
            int cnt=0;
            for(int k=1;k<=n;k++){
                pref[k]=pref[k-1]+(a[k]==i?cnt:0);
                cnt+=a[k]==j?add:0;
            }
            cnt=0;
            for(int k=n;k>=1;k--){
                suff[k]=suff[k+1]+(a[k]==i?cnt:0);
                cnt+=a[k]==j?add:0;
            }
            for(int k=0;k<=n;k++)f[i][j][k]=pref[k]+suff[k+1];
        }
    }
    for(int mask=1;mask<1<<g;mask++){
        dp[mask]=inf;
        for(int bit=0;bit<g;bit++){
            if(mask>>bit&1){
                int mask2=1<<bit^mask;
                int l=0,r=pos[bit].size()-1;
                while(l<r){
                    ll m=(l+r)/2;
                    int dif=0;
                    for(int i=0;i<g;i++)if(mask>>i&1)dif+=f[bit][i][pos[bit][m+1]]-f[bit][i][pos[bit][m]];
                    if(dif>=0)r=m;
                    else l=m+1;
                }
                ll res=0;
                for(int i=0;i<g;i++)if(mask>>i&1)res+=f[bit][i][pos[bit][l]];
                dp[mask]=min(dp[mask],dp[mask2]+res);
            }
        }
    }
    cout << dp[(1<<g)-1]/2.l;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 3088 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 3600 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 3728 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 3728 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 0 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 0 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 7 ms 5972 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 7 ms 5972 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 11 ms 8936 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 12 ms 8992 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 10 ms 9044 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 10 ms 8912 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 10 ms 8776 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 11 ms 8824 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 10 ms 8800 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 10 ms 8828 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 10 ms 8788 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 10 ms 8828 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 3088 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 3600 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 3728 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 3728 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 0 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 0 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 7 ms 5972 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 7 ms 5972 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 11 ms 8936 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 12 ms 8992 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 10 ms 9044 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 10 ms 8912 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 10 ms 8776 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 11 ms 8824 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 10 ms 8800 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 10 ms 8828 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 10 ms 8788 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 10 ms 8828 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 22 ms 1860 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 29 ms 1912 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 3088 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 3600 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 3728 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 3728 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 0 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 596 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 596 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 596 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 6 ms 5972 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 7 ms 5972 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 11 ms 8916 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 11 ms 8932 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 10 ms 9012 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 11 ms 8876 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 10 ms 8796 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 10 ms 8788 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 10 ms 8768 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 10 ms 8832 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 10 ms 8792 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 10 ms 8824 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 291 ms 179352 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 15 ms 1620 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 276 ms 179548 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 223 ms 179532 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 27 ms 1876 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 272 ms 179456 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 283 ms 179468 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 299 ms 179628 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 313 ms 179424 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 285 ms 179468 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 285 ms 179532 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 295 ms 179484 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 217 ms 156644 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 287 ms 179536 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'