oj.uz

Submission #875321

# Submission time Handle Problem Language Result Execution time Memory
875321 2023-11-19T06:24:56 Z 12345678 Boarding Passes (BOI22_passes) C++17
25 / 100
 744 ms 756 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=1; k<=n; k++) cout<<i<<' '<<dpl[k]<<' '<<dpr[k]<<'\n';
                for (int k=0; k<=n; k++) dp[i]=min(dp[i], dp[i-(1<<j)]+dpl[k]+dpr[k+1]);
            }
        }
        //cout<<"here "<<b<<' '<<dp[i]<<'\n';
    }
    cout<<dp[(1<<kx)-1]<<'\n';
}

/*
AABBAA
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 344 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 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 8 ms 480 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 11 ms 472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 8 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 348 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 472 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 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 428 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
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 8 ms 480 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 11 ms 472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 8 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 8 ms 348 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 472 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 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 428 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 4 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 3 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 3 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 344 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 11 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 8 ms 756 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 8 ms 472 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 2 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 7 ms 484 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 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 344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 3 ms 348 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 3 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 742 ms 628 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 744 ms 636 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 344 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -