oj.uz

Submission #1010369

# Submission time Handle Problem Language Result Execution time Memory
1010369 2024-06-29T02:00:30 Z 12345678 Boarding Passes (BOI22_passes) C++17
100 / 100
 308 ms 179640 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, kx=15;

ll n, p[kx][kx][nx], dp[(1<<kx)+5];
string s;
vector<ll> d[kx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>s;
    n=s.size();
    s=' '+s;
    for (int i=0; i<kx; i++) d[i].push_back(0);
    for (int i=1; i<=n; i++) d[s[i]-'A'].push_back(i);
    for (int i=0; i<kx; i++)
    {
        for (int j=0; j<kx; j++)
        {
            ll v=(i==j)?1:2, tmp=0, cnt=0;
            vector<ll> pref(n+2), suf(n+2);
            for (int k=1; k<=n; k++)
            {
                if (s[k]-'A'==i) cnt+=tmp;
                if (s[k]-'A'==j) tmp+=v;
                pref[k]=cnt;
            }
            tmp=cnt=0;
            for (int k=n; k>=1; k--)
            {
                if (s[k]-'A'==i) cnt+=tmp;
                if (s[k]-'A'==j) tmp+=v;
                suf[k]=cnt;
            }
            for (int k=0; k<=n; k++) p[i][j][k]=pref[k]+suf[k+1];
        }
    }
    for (int i=1; i<(1<<kx); i++)
    {
        dp[i]=LLONG_MAX;
        for (int j=0; j<kx; j++)
        {
            if (i&(1<<j))
            {
                ll l=0, r=d[j].size()-1;
                while (l<r)
                {
                    ll md=(l+r)/2, df=0;
                    for (int k=0; k<kx; k++) if (i&(1<<k)) df+=p[j][k][d[j][md+1]]-p[j][k][d[j][md]];
                    if (df>=0) r=md;
                    else l=md+1;
                }
                //cout<<"here "<<d[j][l]<<'\n';
                ll vl=0;
                for (int k=0; k<kx; k++) if (i&(1<<k)) vl+=p[j][k][d[j][l]];
                dp[i]=min(dp[i], dp[i^(1<<j)]+vl);
            }
        }
        //cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    }
    printf("%.4f\n", dp[((1<<kx)-1)]/2.0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3420 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 12 ms 1884 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 1784 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 12 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 19 ms 3676 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 159 ms 142004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 190 ms 169044 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 198 ms 179192 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 199 ms 179088 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 1880 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 21 ms 1904 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 21 ms 2100 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 19 ms 1880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 17 ms 1884 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 19 ms 1916 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 21 ms 1880 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 19 ms 1976 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 1884 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 24 ms 1880 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 20 ms 1856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 1884 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 23 ms 1884 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 22 ms 1880 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 1856 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 1884 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 13 ms 1880 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 21 ms 1904 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 21 ms 2100 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 19 ms 1880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 17 ms 1884 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 19 ms 1916 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 21 ms 1880 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 19 ms 1976 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 1884 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 24 ms 1880 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 20 ms 1856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 1884 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 23 ms 1884 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 22 ms 1880 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 1856 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 1884 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 13 ms 1884 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 13 ms 1968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 22 ms 1880 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 21 ms 1880 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 20 ms 1884 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 19 ms 1884 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 19 ms 1880 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 21 ms 1892 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 19 ms 1884 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 20 ms 1944 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 22 ms 1884 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 19 ms 1800 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 20 ms 1772 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 20 ms 1956 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 22 ms 1884 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 20 ms 1880 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 21 ms 1884 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 26 ms 19740 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 25 ms 19800 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 59 ms 19648 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 51 ms 19636 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 43 ms 19796 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 51 ms 19680 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 56 ms 19392 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 59 ms 19236 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 68 ms 19368 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 56 ms 19268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 64 ms 19380 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 58 ms 20200 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3420 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 12 ms 1884 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 15 ms 1784 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 12 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 19 ms 3676 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 159 ms 142004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 190 ms 169044 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 198 ms 179192 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 199 ms 179088 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 15 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 13 ms 1880 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 21 ms 1904 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 21 ms 2100 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 19 ms 1880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 17 ms 1884 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 19 ms 1916 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 21 ms 1880 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 19 ms 1976 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 21 ms 1884 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 24 ms 1880 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 20 ms 1856 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 23 ms 1884 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 23 ms 1884 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 22 ms 1880 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 21 ms 1856 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 20 ms 1884 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 13 ms 1884 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 13 ms 1968 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 22 ms 1880 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 21 ms 1880 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 20 ms 1884 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 19 ms 1884 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 19 ms 1880 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 21 ms 1892 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 19 ms 1884 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 20 ms 1944 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 22 ms 1884 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 19 ms 1800 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 20 ms 1772 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 20 ms 1956 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 22 ms 1884 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 20 ms 1880 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 21 ms 1884 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 26 ms 19740 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 25 ms 19800 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 59 ms 19648 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 51 ms 19636 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 43 ms 19796 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 51 ms 19680 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 56 ms 19392 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 59 ms 19236 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 68 ms 19368 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 56 ms 19268 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 64 ms 19380 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 58 ms 20200 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 18 ms 1884 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 22 ms 1768 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 14 ms 3424 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 10 ms 1944 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 11 ms 1884 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 12 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 15 ms 3672 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 159 ms 142104 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 182 ms 168952 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 209 ms 179096 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 205 ms 179024 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 13 ms 1880 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 13 ms 1884 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 22 ms 2004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 21 ms 2084 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 18 ms 1880 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 16 ms 1792 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 20 ms 1960 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 19 ms 2000 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 22 ms 1960 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 19 ms 1884 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 23 ms 1880 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 19 ms 1884 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 22 ms 1940 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 23 ms 1884 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 23 ms 1884 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 22 ms 1920 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 22 ms 1936 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 31 ms 19808 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 28 ms 19804 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 58 ms 19616 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 57 ms 19672 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 32 ms 19796 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 60 ms 19516 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 65 ms 19240 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 56 ms 19256 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 63 ms 19256 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 58 ms 19256 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 55 ms 19264 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 56 ms 19268 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 293 ms 179392 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 23 ms 1880 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 274 ms 179196 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 224 ms 178880 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 19 ms 1880 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 260 ms 179396 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 283 ms 179640 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 291 ms 179500 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 287 ms 179524 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 299 ms 179520 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 279 ms 179576 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 285 ms 179488 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 275 ms 179548 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 308 ms 179572 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'