oj.uz

Submission #846009

# Submission time Handle Problem Language Result Execution time Memory
846009 2023-09-07T05:31:49 Z damwuan Boarding Passes (BOI22_passes) C++17
55 / 100
 100 ms 5064 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+5;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,a[maxn],cost[(1<<15)+2][16],dp[(1<<15)+2],id[16],g=-1,pre[16][maxn],suf[16][maxn];
vector<int> L[16];
string s;
void sol()
{
    cin >> s;
    n=s.size();
    s=' '+s;
    for1(i,0,15) id[i]=-1;
    for1(i,1,n)
    {
        if (id[s[i]-'A']==-1)
        {
            id[s[i]-'A']=++g;
        }
        L[id[s[i]-'A']].pb(i);
        a[i]=id[s[i]-'A'];
        //cerr<< a[i]<<'\n';
    }
    g++;
    for1(i,1,n)
    {
        for1(j,0,g-1)
        {
            pre[j][i]=pre[j][i-1]+((a[i]==j)?1:0);
        }
    }
    for2(i,n,1)
    {
        for1(j,0,g-1)
        {
            suf[j][i]=suf[j][i+1]+((a[i]==j)?1:0);
        }
    }
    for1(i,0,g-1)
    {
        int k1=L[i].size()/2;
        int k2=L[i].size()-k1;
        cost[0][i]=(k1*(k1-1)+k2*(k2-1))/2;
    }
    for1(mask,1,(1<<g)-1)
    {
        for1(i,0,g-1)
        {
            int dem=0,tt=L[i].size();
            if (!((mask>>i)&1))
            {
                for2(k,tt-1,0)
                {
                    for1(j,0,g-1)
                    {
                        if ((mask>>j)&1)
                        {
                            dem+=suf[j][L[i][k]];
                        }
                    }
                }

                cost[mask][i]=dem*2+tt*(tt-1)/2;
//                if (mask==2 && i==0)
//                {
//                    cout <<cost[mask][i]<< " wtf\n";
//                }
                for1(k,0,tt-1)
                {
                    for1(j,0,g-1)
                    {
                        if ((mask>>j)&1)
                        {
                            dem+=pre[j][L[i][k]];
                            dem-=suf[j][L[i][k]];
                        }
                    }
                    cost[mask][i]=min(cost[mask][i],dem*2+(k+1)*k/2 + (tt-k-1)*(tt-k-2)/2);
                }
            }
        }
    }
    //bitset<4> xxx(2);
    //cout << xxx<<'\n';
    //cout << cost[2][0];
    for1(mask,0,(1<<g)-1) dp[mask]=inf;
    dp[0]=0;
    for1(mask,0,(1<<g)-1)
    {
        for1(i,0,g-1)
        {
            if (!((mask>>i)&1))
            {
                dp[mask^(1<<i)]=min(dp[mask^(1<<i)],dp[mask]+cost[mask][i]);
            }
        }
//        dbg(mask);
//        cout<<' '<<dp[mask]<<'\n';
    }
    //cerr<< g<<'\n';
    cout << dp[(1<<g)-1]/2;
    if (dp[(1<<g)-1]&1) cout << ".5";



}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("GROUPDIV.inp","r",stdin);
//    freopen("GROUPDIV.out","w",stdout);

    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

3 1
12345678
?11
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5064 KB 1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123'
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 2392 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2392 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2392 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 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 2392 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2392 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 2396 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 2396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 2904 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 2904 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 98 ms 4424 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 87 ms 4184 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 88 ms 4440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 89 ms 4184 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 94 ms 4184 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 95 ms 4184 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 96 ms 4360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 100 ms 4356 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 98 ms 4184 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 93 ms 4184 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5064 KB 1st numbers differ - expected: '772893586.0000000000', found: '500000000.0000000000', error = '0.3530804123'
7 Halted 0 ms 0 KB -