oj.uz

Submission #824084

# Submission time Handle Problem Language Result Execution time Memory
824084 2023-08-13T13:26:08 Z ttamx Boarding Passes (BOI22_passes) C++14
100 / 100
 298 ms 179448 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(auto k:pos[i])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 3556 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 0 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 1 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 1 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 1 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 0 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 0 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 1 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 1 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 1 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 0 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 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 1 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 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 1 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 1 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 0 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 4 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 5 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 10 ms 8916 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 8 ms 2332 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 7 ms 2004 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 9 ms 4820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 10 ms 8848 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 11 ms 8772 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 10 ms 8788 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 10 ms 8788 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 10 ms 8800 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 10 ms 8748 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 3556 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 0 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 1 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 1 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 1 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 0 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 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 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 1 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 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 1 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 1 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 0 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 4 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 5 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 10 ms 8916 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 8 ms 2332 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 7 ms 2004 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 9 ms 4820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 10 ms 8848 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 11 ms 8772 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 10 ms 8788 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 10 ms 8788 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 10 ms 8800 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 10 ms 8748 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 23 ms 1844 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 29 ms 1868 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 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 0 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 2 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 3764 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 1 ms 596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 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 1 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 5 ms 1620 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 6 ms 1620 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 11 ms 8928 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 8 ms 2260 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 8 ms 2004 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 10 ms 4820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 10 ms 8756 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 8788 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 10 ms 8744 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 10 ms 8788 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 10 ms 8868 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 298 ms 179352 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 17 ms 1556 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 225 ms 16948 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 162 ms 16236 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 26 ms 1868 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 241 ms 65068 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 289 ms 179412 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 297 ms 179404 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 290 ms 179384 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 291 ms 179448 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 291 ms 179324 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 296 ms 179376 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 211 ms 156524 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 291 ms 179388 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'