oj.uz

Submission #988217

# Submission time Handle Problem Language Result Execution time Memory
988217 2024-05-24T10:05:27 Z alexdd Boarding Passes (BOI22_passes) C++17
100 / 100
 302 ms 14688 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

int n;
string s;
vector<int> pozs[20];

vector<int> prec[15][15];
int pref[100005];
void calc_prec()
{
    for(int p=0;p<15;p++)
    {
        pref[0]=0;
        for(int i=1;i<=n;i++)
        {
            pref[i]=pref[i-1];
            if(s[i-1]-'A'==p)
                pref[i]++;
        }
        for(int u=0;u<15;u++)
        {
            if(u==p)
                continue;
            prec[p][u].resize((int)pozs[u].size()+2);
            int cur=0;
            for(auto x:pozs[u])
                cur += pref[n]-pref[x];
            prec[p][u][0] = 2*cur;
            for(int i=1;i<=(int)pozs[u].size();i++)
            {
                cur -= pref[n]-pref[pozs[u][i-1]];
                cur += pref[pozs[u][i-1]];
                prec[p][u][i] = 2*cur;
            }
        }
    }
}
int dp[100005];
void calc_dp()
{
    dp[1]=0;
    for(int i=2;i<=n;i++)
        dp[i] = dp[i-1] + (i-1);
}
int rez[33000];
int calc_sum(int config, int i, int cntle)
{
    int aux=0;
    for(int j=0;j<15;j++)
        if(i!=j && ((1<<j)&config))
            aux += prec[j][i][cntle];
    aux += dp[cntle] + dp[(int)pozs[i].size()-cntle];
    rez[config] = min(rez[config], rez[config-(1<<i)] + aux);
    return aux;
}
signed main()
{
    cin>>s;
    n=s.size();
    for(int i=1;i<=n;i++)
        pozs[s[i-1]-'A'].push_back(i);
    calc_prec();
    calc_dp();
    for(int config=1;config<(1<<15);config++)
    {
        rez[config]=INF;
        for(int i=0;i<15;i++)
        {
            if((((1<<i)&config)))
            {
                int st,dr,mij1,mij2;
                st=0;
                dr=pozs[i].size();
                while(dr-st+1>=5)
                {
                    mij1 = st + (dr-st+1)/3;
                    mij2 = mij1 + (dr-st+1)/3;
                    int val1 = calc_sum(config,i,mij1);
                    int val2 = calc_sum(config,i,mij2);
                    if(val1<val2)
                        dr=mij2;
                    else
                        st=mij1;
                }
                for(int j=st;j<=dr;j++)
                    calc_sum(config,i,j);
            }
        }
    }
    if(rez[(1<<15)-1]%2==0) cout<<rez[(1<<15)-1]/2;
    else cout<<rez[(1<<15)-1]/2<<".5";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 17 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 19 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 30 ms 860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 48 ms 11212 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 49 ms 13508 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 49 ms 14276 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 50 ms 14284 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 27 ms 552 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 69 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 69 ms 592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 32 ms 880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 70 ms 664 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 40 ms 692 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 40 ms 580 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 42 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 39 ms 636 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 42 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 39 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 40 ms 556 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 37 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 46 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 40 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 27 ms 552 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 69 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 69 ms 592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 32 ms 880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 70 ms 664 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 40 ms 692 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 40 ms 580 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 42 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 39 ms 636 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 42 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 39 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 40 ms 556 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 37 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 46 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 40 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 21 ms 624 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 27 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 69 ms 764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 68 ms 592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 32 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 69 ms 520 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 40 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 40 ms 652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 42 ms 508 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 39 ms 476 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 42 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 41 ms 768 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 39 ms 528 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 37 ms 588 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 41 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 40 ms 644 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 35 ms 1884 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 37 ms 1880 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 162 ms 1956 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 157 ms 1872 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 44 ms 1880 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 165 ms 2392 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 171 ms 1856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 159 ms 2008 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 164 ms 2076 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 160 ms 2060 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 171 ms 1872 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 169 ms 2236 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 17 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 17 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 19 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 30 ms 860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 48 ms 11212 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 49 ms 13508 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 49 ms 14276 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 50 ms 14284 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 23 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 27 ms 552 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 69 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 69 ms 592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 32 ms 880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 70 ms 664 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 40 ms 692 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 40 ms 580 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 42 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 39 ms 636 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 42 ms 672 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 39 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 40 ms 556 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 37 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 46 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 40 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 21 ms 624 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 27 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 69 ms 764 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 68 ms 592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 32 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 24 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 69 ms 520 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 40 ms 600 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 40 ms 652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 42 ms 508 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 39 ms 476 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 42 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 41 ms 768 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 39 ms 528 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 37 ms 588 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 41 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 40 ms 644 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 35 ms 1884 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 37 ms 1880 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 162 ms 1956 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 157 ms 1872 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 44 ms 1880 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 165 ms 2392 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 171 ms 1856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 159 ms 2008 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 164 ms 2076 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 160 ms 2060 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 171 ms 1872 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 169 ms 2236 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 27 ms 600 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 39 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 30 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 18 ms 696 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 18 ms 1012 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 19 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 30 ms 744 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 46 ms 11460 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 51 ms 13504 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 51 ms 14352 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 49 ms 14276 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 26 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 28 ms 600 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 69 ms 592 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 69 ms 680 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 35 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 27 ms 536 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 71 ms 528 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 43 ms 676 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 41 ms 700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 46 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 41 ms 628 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 43 ms 628 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 41 ms 592 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 40 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 39 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 41 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 41 ms 520 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 36 ms 1884 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 38 ms 1956 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 194 ms 1888 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 156 ms 1836 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 55 ms 1884 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 164 ms 1924 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 161 ms 1884 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 158 ms 1872 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 161 ms 1876 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 170 ms 2132 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 159 ms 2120 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 171 ms 1872 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 292 ms 14192 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 55 ms 604 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 287 ms 14068 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 64 ms 14284 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 35 ms 680 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 293 ms 14192 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 302 ms 14348 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 294 ms 14420 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 296 ms 14688 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 293 ms 14172 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 297 ms 14648 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 294 ms 14172 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 281 ms 14124 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 292 ms 14376 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'