oj.uz

Submission #988214

# Submission time Handle Problem Language Result Execution time Memory
988214 2024-05-24T09:58:13 Z alexdd Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 12744 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
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] = 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] = cur;
            }
        }
    }
}
ld dp[100005];
void calc_dp()
{
    dp[1]=0;
    for(int i=2;i<=n;i++)
    {
        dp[i] = dp[i-1] + (ld)(i-1)/2;
        //cout<<i<<" "<<dp[i]<<"\n";
    }
}
ld rez[33000];
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)))
            {
                for(int cntle=0;cntle<=(int)pozs[i].size();cntle++)
                {
                    int aux=0;
                    for(int j=0;j<15;j++)
                        if(i!=j && ((1<<j)&config))
                            aux += prec[j][i][cntle];
                    rez[config] = min(rez[config], (ld)rez[config-(1<<i)] + (ld)aux + dp[cntle] + dp[(int)pozs[i].size()-cntle]);
                }
            }
        }
    }
    cout<<fixed<<setprecision(6)<<rez[(1<<15)-1];
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 2896 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 19 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 2932 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 21 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 339 ms 2892 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2062 ms 12744 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 52 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 69 ms 2896 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 67 ms 2652 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 57 ms 2652 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 28 ms 2848 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 40 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 2616 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 39 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 38 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 39 ms 2612 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 39 ms 2652 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 39 ms 2652 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 38 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 40 ms 2896 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 39 ms 2504 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 52 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 69 ms 2896 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 67 ms 2652 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 57 ms 2652 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 28 ms 2848 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 62 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 40 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 2616 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 39 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 38 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 39 ms 2612 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 39 ms 2652 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 39 ms 2652 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 38 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 40 ms 2896 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 39 ms 2504 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 22 ms 2648 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 54 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 66 ms 2652 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 66 ms 2560 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 57 ms 2788 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 26 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 61 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 39 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 39 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 39 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 40 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 39 ms 2660 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 39 ms 2632 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 40 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 38 ms 2648 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 39 ms 2652 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 38 ms 2652 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2032 ms 3960 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 2896 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 19 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 20 ms 2932 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 21 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 339 ms 2892 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2062 ms 12744 KB Time limit exceeded
7 Halted 0 ms 0 KB -