oj.uz

Submission #846006

# Submission time Handle Problem Language Result Execution time Memory
846006 2023-09-07T05:27:42 Z damwuan Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 27988 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=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 dbg(int mask)
{
    bitset<2> xxx(mask);
    cout << xxx;
}
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 1 ms 2512 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 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 Correct 3 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 3 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 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 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 2392 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 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2504 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 2396 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 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 2396 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 2392 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 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2504 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 2396 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 2396 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 2392 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 2396 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 2396 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 2908 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 102 ms 4444 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 98 ms 4184 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 99 ms 4440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 99 ms 4368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 104 ms 4384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 102 ms 4384 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 104 ms 4184 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 99 ms 4372 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 109 ms 4380 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 101 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 1 ms 2512 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 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 Correct 3 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 3 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 2396 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 2396 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 2392 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 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 2504 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 2396 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 2396 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 2392 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 2396 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 2396 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 2396 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 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 2392 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 2908 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 102 ms 4444 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 98 ms 4184 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 99 ms 4440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 99 ms 4368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 104 ms 4384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 102 ms 4384 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 104 ms 4184 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 99 ms 4372 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 109 ms 4380 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 101 ms 4184 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 35 ms 5200 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 2392 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 5064 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 5832 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 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 2396 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 2392 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 2504 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 2392 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 2396 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 2504 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 2592 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 2392 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 2392 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 2908 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 107 ms 4440 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 98 ms 4356 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 100 ms 4440 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 98 ms 4188 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 106 ms 4384 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 100 ms 4184 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 103 ms 4188 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 110 ms 4368 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 101 ms 4184 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 106 ms 4380 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2028 ms 27988 KB Time limit exceeded
97 Halted 0 ms 0 KB -