oj.uz

Submission #846011

# Submission time Handle Problem Language Result Execution time Memory
846011 2023-09-07T05:33:20 Z damwuan Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 27732 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=1e18;
const ll block_sz=317;
const ll inf=1e18;
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
5.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 2552 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 5064 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 5576 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 5832 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 5832 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 1 ms 2648 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2396 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 2396 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2396 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 1 ms 2648 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2396 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 2396 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2396 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 1 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 2392 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 2392 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 2392 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 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 2396 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 101 ms 4188 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 89 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 88 ms 4184 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 93 ms 4184 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 94 ms 4184 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 92 ms 4364 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 93 ms 4184 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 93 ms 4376 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 97 ms 4368 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 2552 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 5064 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 5576 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 5832 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 5832 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 2392 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 2648 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 2396 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 2392 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 2396 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 2904 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 2904 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 101 ms 4188 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 89 ms 4184 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 88 ms 4440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 88 ms 4184 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 93 ms 4184 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 94 ms 4184 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 92 ms 4364 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 93 ms 4184 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 93 ms 4376 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 97 ms 4368 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 2392 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 33 ms 5204 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 2392 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 2392 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 5068 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 5576 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 5836 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 5832 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 2596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 2392 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 2396 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 2396 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 2392 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 2396 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 2904 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 2904 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 96 ms 4188 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 87 ms 4184 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 89 ms 4440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 88 ms 4184 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 95 ms 4184 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 93 ms 4184 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 100 ms 4196 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 112 ms 4184 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 93 ms 4184 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 97 ms 4364 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2025 ms 27732 KB Time limit exceeded
97 Halted 0 ms 0 KB -