oj.uz

Submission #875322

# Submission time Handle Problem Language Result Execution time Memory
875322 2023-11-19T06:26:27 Z 12345678 Boarding Passes (BOI22_passes) C++17
55 / 100
 1174 ms 1140 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e4+5, kx=11;
int n, cnt, cnt2;
double dp[1<<kx], dpl[nx], dpr[nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>s;
    n=s.size();
    for (int i=1; i<(1<<kx); i++)
    {
        dp[i]=DBL_MAX;
        for (int j=0; j<kx; j++)
        {
            if (i&(1<<j))
            {
                cnt=cnt2=0;
                for (int k=1; k<=n; k++)
                {
                    if (s[k-1]-'A'==j) cnt2++, dpl[k]=dpl[k-1]+cnt+(cnt2-1)/2.0;
                    else if (i&(1<<(s[k-1]-'A'))) cnt++, dpl[k]=dpl[k-1];
                    else dpl[k]=dpl[k-1];
                }
                cnt=cnt2=0;
                for (int k=n; k>=1; k--)
                {
                    if (s[k-1]-'A'==j) cnt2++, dpr[k]=dpr[k+1]+cnt+(cnt2-1)/2.0;
                    else if (i&(1<<(s[k-1]-'A'))) cnt++, dpr[k]=dpr[k+1];
                    else dpr[k]=dpr[k+1];
                }
                for (int k=0; k<=n; k++) dp[i]=min(dp[i], dp[i-(1<<j)]+dpl[k]+dpr[k+1]);
            }
        }
    }
    printf("%.4f", dp[(1<<kx)-1]);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 468 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 74 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Runtime error 1 ms 1116 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 7 ms 472 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 488 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 7 ms 476 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 464 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 7 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 348 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 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 7 ms 472 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 10 ms 488 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 7 ms 476 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 464 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 7 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 3 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 3 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 3 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 4 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 7 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 10 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 8 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 8 ms 480 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 7 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 3 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 3 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 3 ms 432 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 3 ms 472 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 3 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 3 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 3 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 3 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 744 ms 872 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 746 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 1174 ms 644 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 742 ms 640 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 748 ms 644 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 740 ms 852 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 735 ms 640 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 736 ms 1140 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 735 ms 852 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 735 ms 628 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 739 ms 640 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 734 ms 640 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 468 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 74 ms 344 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Runtime error 1 ms 1116 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -