oj.uz

Submission #824081

# Submission time Handle Problem Language Result Execution time Memory
824081 2023-08-13T13:22:38 Z ttamx Boarding Passes (BOI22_passes) C++14
100 / 100
 302 ms 192616 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],d[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 k=0;k<pos[i].size()-1;k++)d[i][j][k]=f[i][j][pos[i][k+1]]-f[i][j][pos[i][k]];
        }
    }
    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+=d[bit][i][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;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int k=0;k<pos[i].size()-1;k++)d[i][j][k]=f[i][j][pos[i][k+1]]-f[i][j][pos[i][k]];
      |                         ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 3728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 4368 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 4496 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 4496 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 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 844 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 844 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 852 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 844 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 844 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 848 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 6 ms 6612 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 7 ms 6612 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 12 ms 10328 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 11 ms 10324 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 11 ms 10452 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 12 ms 10332 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 11 ms 10196 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 11 ms 10152 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 11 ms 10124 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 11 ms 10192 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 11 ms 10212 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 12 ms 10144 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 3728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 4368 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 4496 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 4496 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 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 844 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 852 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 844 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 844 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 848 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 6 ms 6612 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 7 ms 6612 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 12 ms 10328 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 11 ms 10324 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 11 ms 10452 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 12 ms 10332 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 11 ms 10196 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 11 ms 10152 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 11 ms 10124 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 11 ms 10192 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 11 ms 10212 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 12 ms 10144 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 21 ms 2248 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 26 ms 3152 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 1 ms 336 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 3 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 4464 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 4624 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 4624 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 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 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 852 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 852 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 836 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 848 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 848 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 844 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 900 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 848 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 7 ms 6612 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 7 ms 6616 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 11 ms 10388 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 12 ms 10280 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 10 ms 10324 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 12 ms 10324 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 12 ms 10196 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 11 ms 10196 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 11 ms 10112 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 11 ms 10196 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 11 ms 10204 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 11 ms 10196 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 302 ms 192616 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 18 ms 2772 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 276 ms 192484 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 233 ms 192520 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 25 ms 3104 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 271 ms 192444 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 284 ms 192560 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 282 ms 192460 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 281 ms 192412 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 295 ms 192448 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 291 ms 192440 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 285 ms 192508 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 220 ms 168696 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 286 ms 192424 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'