Submission #805987

#	Time	Username	Problem	Language	Result	Execution time	Memory
805987		winter0101	Boarding Passes (BOI22_passes)	C++14	100 / 100	177 ms	29104 KiB

passes

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#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 lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
#define int long long
const long long inf=1e15;
const int maxn=1e5+9;
long long f[1<<15];
int a[maxn][15],b[maxn][15];
int cnt[15];
vector<int>id[15];
string s;
vector<int>bit[1<<15];
long long g(int gr,int k,int mask){
long long cost=0;
int mp=sz(id[gr]);
for (auto v:bit[mask]){
    if (mp==0)continue;
    if (k==0){
    cost+=2*b[id[gr][0]][v];
    }
    else if (k==mp){
    cost+=2*a[id[gr].back()][v];
    }
    else {
    int id1=id[gr][k-1],id2=id[gr][k];
    cost+=2*a[id1][v]+2*b[id2][v];
    }
}
cost+=k*(k-1)/2;
cost+=(mp-k)*(mp-k-1)/2;
return cost;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.ANS","w",stdout);
    f[0]=0;
    cin>>s;
    int n=sz(s);
    s=" "+s;
    for1(i,1,n){
    for1(j,0,14){
    a[i][j]=cnt[j];
    }
    cnt[s[i]-'A']++;
    id[s[i]-'A'].pb(i);
    }
    memset(cnt,0,sizeof(cnt));
    for2(i,n,1){
    for1(j,0,14){
    b[i][j]=cnt[j];
    }
    cnt[s[i]-'A']++;
    }
    for1(i,0,14){
    for1(j,1,sz(id[i])-1){
    for1(k,0,14){
    a[id[i][j]][k]+=a[id[i][j-1]][k];
    }
    }
    for2(j,sz(id[i])-2,0){
    for1(k,0,14){
    b[id[i][j]][k]+=b[id[i][j+1]][k];
    }
    }
    }
    for1(i,0,(1<<15)-1){
    for1(j,0,14){
    if (i>>j&1)bit[i].pb(j);
    }
    f[i]=inf;
    }
    f[0]=0;
    for1(i,0,(1<<15)-1){
    if (f[i]>=inf)continue;
    for1(j,0,14){
    if (i>>j&1)continue;
    int l=0,r=sz(id[j]);
    while (l!=r){
        int mid=(l+r)/2;
        if (g(j,mid,i)>g(j,mid+1,i)){
            l=mid+1;
        }
        else r=mid;
    }
    f[i+(1<<j)]=min(f[i+(1<<j)],f[i]+g(j,l,i));
    }
    }
    long double answ=f[(1<<15)-1];
    answ=answ*0.5;
    cout<<setprecision(4)<<fixed<<answ;
}

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