oj.uz

Submission #988215

# Submission time Handle Problem Language Result Execution time Memory
988215 2024-05-24T10:00:23 Z alexdd Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 11476 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];
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], rez[config-(1<<i)] + aux + dp[cntle] + dp[(int)pozs[i].size()-cntle]);
                }
            }
        }
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 604 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 16 ms 612 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 19 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 278 ms 648 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2096 ms 11476 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 46 ms 588 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 58 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 58 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 48 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 23 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 55 ms 592 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 35 ms 592 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 592 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 34 ms 656 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 33 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 36 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 33 ms 600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 38 ms 796 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 32 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 34 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 33 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 46 ms 588 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 58 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 58 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 48 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 23 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 55 ms 592 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 35 ms 592 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 39 ms 592 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 34 ms 656 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 33 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 36 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 33 ms 600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 38 ms 796 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 32 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 34 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 33 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 20 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 44 ms 592 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 60 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 58 ms 532 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 52 ms 936 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 26 ms 604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 54 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 33 ms 568 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 34 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 34 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 33 ms 540 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 34 ms 556 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 37 ms 600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 35 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 32 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 33 ms 672 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 33 ms 600 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2057 ms 2240 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 604 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 16 ms 612 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 19 ms 600 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 278 ms 648 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2096 ms 11476 KB Time limit exceeded
7 Halted 0 ms 0 KB -