Submission #586352

#	Time	Username	Problem	Language	Result	Execution time	Memory
586352		azberjibiou	Boarding Passes (BOI22_passes)	C++17	100 / 100	244 ms	209060 KiB

passes

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef unsigned int uint;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mxN=100010;
const int mxM=35000;
const int mxK=1000000000;
const int MOD=1e9+7;
const ll INF=2e18;
int N;
char S[mxN];
int pref[mxN][15];
ll cost[mxN][16][16];
vector <int> apos[16];
bool alph[mxN][16];
ll dp[mxM];
bool Chk[mxM];
ll sum(int s, int e, int idx)
{
    return pref[e][idx]-pref[s-1][idx];
}
ll calc(int now, ll pos, vector <int> &comp)
{
    ll val=0, nowpos=(pos==0 ? 0 : apos[now][pos-1]);
    for(int nxt : comp) if(nxt!=now)
    {
        val+=cost[nowpos][now][nxt];
    }
    ll siz=apos[now].size();
    val+=pos*(pos-1)/2+(siz-pos)*(siz-pos-1)/2;
    return val;
}
void dping(int idx)
{
    //printf("idx=%d\n", idx);
    vector <int> comp;
    for(int i=0;i<15;i++)   if((1<<i)&idx)
    {
        comp.push_back(i);
        if(!Chk[idx-(1<<i)])    dping(idx-(1<<i));
    }
    for(int ele : comp) if(apos[ele].empty())
    {
        dp[idx]=dp[idx-(1<<ele)];
        Chk[idx]=true;
        return;
    }
    dp[idx]=INF;
    for(int now : comp)
    {
        int s=0, e=apos[now].size();
        while(s<=e-3)
        {
            int mid1=(s+e)/2, mid2=(s+e)/2+1;
            if(calc(now, mid1, comp)<calc(now, mid2, comp)) e=mid2;
            else    s=mid1;
        }
        for(int i=s;i<=e;i++)
        {
            dp[idx]=min(dp[idx], dp[idx-(1<<now)]+calc(now, i, comp));
        }
    }
    Chk[idx]=true;
}
int main()
{
    gibon
    cin >> S+1;
    N=strlen(S+1);
    for(int i=0;i<15;i++)
    {
        for(int j=1;j<=N;j++)   if(S[j]==i+'A')
        {
            alph[j][i]=1;
            apos[i].push_back(j);
        }
    }
    for(int i=0;i<15;i++)   for(int j=1;j<=N;j++)   pref[j][i]=pref[j-1][i]+alph[j][i];
    for(int i=0;i<15;i++)
    {
        for(int j=0;j<15;j++)   if(i!=j && apos[i].size() && apos[j].size())
        {
            for(int ele : apos[i])  cost[0][i][j]+=2*sum(ele, N, j);
            int siz=apos[i].size();
            for(int k=0;k<apos[i].size();k++)
            {
                int now=apos[i][k], pre=(k==0 ? 0 : apos[i][k-1]);
                cost[now][i][j]=cost[pre][i][j]-2*sum(now, N, j)+2*sum(1, now, j);
                //printf("cost[%d][%d][%d]=%lld\n", now, i, j, cost[now][i][j]);
            }
        }
    }
    Chk[0]=true;
    for(int i=0;i<15;i++)   Chk[1<<i]=true;
    for(int i=0;i<15;i++)
    {
        ll nsiz=apos[i].size(), mid=nsiz/2;
        dp[1<<i]=mid*(mid-1)/2+(nsiz-mid)*(nsiz-mid-1)/2;
    }
    dping((1<<15)-1);
    if(dp[(1<<15)-1]%2==0)  cout << dp[(1<<15)-1]/2;
    else    cout << dp[(1<<15)-1]/2 << ".5";
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:81:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     cin >> S+1;
      |            ~^~
passes.cpp:98:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for(int k=0;k<apos[i].size();k++)
      |                         ~^~~~~~~~~~~~~~~
passes.cpp:97:17: warning: unused variable 'siz' [-Wunused-variable]
   97 |             int siz=apos[i].size();
      |                 ^~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40