oj.uz

Submission #824082

# Submission time Handle Problem Language Result Execution time Memory
824082 2023-08-13T13:23:46 Z ttamx Boarding Passes (BOI22_passes) C++14
100 / 100
 301 ms 192456 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(auto k:pos[i])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 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 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 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 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 864 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 852 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 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 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 864 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 852 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 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 852 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 852 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 852 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 5 ms 2272 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 5 ms 2260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 11 ms 10324 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 9 ms 3668 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 8 ms 3284 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 10 ms 6176 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 13 ms 10088 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 13 ms 10196 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 11 ms 10196 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 11 ms 10068 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 11 ms 10196 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 11 ms 10196 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 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 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 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 864 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 852 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 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 852 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 852 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 852 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 852 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 5 ms 2272 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 5 ms 2260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 11 ms 10324 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 9 ms 3668 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 8 ms 3284 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 10 ms 6176 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 13 ms 10088 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 13 ms 10196 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 11 ms 10196 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 11 ms 10068 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 11 ms 10196 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 11 ms 10196 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 22 ms 2236 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 30 ms 3160 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 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 3728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 4368 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 4496 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 4496 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 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 852 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 852 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 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 852 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 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 5 ms 2260 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 5 ms 2260 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 11 ms 10340 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 8 ms 3580 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 8 ms 3276 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 11 ms 6144 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 11 ms 10160 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 12 ms 10196 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 11 ms 10212 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 11 ms 10068 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 11 ms 10152 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 11 ms 10068 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 300 ms 192328 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 17 ms 2644 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 229 ms 30020 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 171 ms 29152 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 26 ms 3028 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 254 ms 78096 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 292 ms 192456 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 287 ms 192376 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 301 ms 192376 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 293 ms 192372 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 290 ms 192356 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 295 ms 192380 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 217 ms 168432 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 294 ms 192308 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'