Submission #580516

#	Time	Username	Problem	Language	Result	Execution time	Memory
580516		haojiandan	Boarding Passes (BOI22_passes)	C++14	60 / 100	116 ms	80704 KiB

passes

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    t=0; char ch=getchar(); int f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
    if (t<0) { putchar('-'); write(-t); return; }
    if (t>9) write(t/10);
    putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int maxn=(1e4)+10;
int n,N;
char s[maxn*10],lsh[maxn*10];
int m,pre[1<<10][maxn],suf[1<<10][maxn];
vector<int> vec[30];
ll dp[1<<10];
void output(ll ans) {
    if (ans&1) printf("%lld.5\n",ans/2);
    else printf("%lld\n",ans/2);
    exit(0);
}
int main() {
    scanf("%s",s+1); n=strlen(s+1);
    for (int i=1;i<=n;i++) lsh[++N]=s[i];
    sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
    for (int i=1;i<=n;i++) s[i]=lower_bound(lsh+1,lsh+N+1,s[i])-lsh+'A'-1;
    for (int i=1;i<=n;i++) m=max(m,s[i]-'A'),vec[s[i]-'A'].push_back(i);
    if (m==0) {
        m=n/2;
        ll ans=(ll)m*(m-1)/2+(ll)(n-m)*(n-m-1)/2;
        output(ans);
    }
    m++;
    for (int t=0;t<(1<<m);t++) {
        for (int i=1;i<=n;i++) pre[t][i]=pre[t][i-1]+(t>>(s[i]-'A')&1);
        for (int i=n;i>=1;i--) suf[t][i]=suf[t][i+1]+(t>>(s[i]-'A')&1);
        dp[t]=INF;
    }
    dp[0]=0;
    for (int t=0;t<(1<<m);t++) {
        for (int i=0;i<m;i++) if (!(t>>i&1)) {
            ll tmp=0;
            for (int &x : vec[i]) tmp+=min(pre[t][x]*2+pre[1<<i][x-1],suf[t][x]*2+suf[1<<i][x+1]);
            dp[t^(1<<i)]=min(dp[t^(1<<i)],dp[t]+tmp);
        }
    }
    output(dp[(1<<m)-1]);
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
 
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
   
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
   
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%s",s+1); n=strlen(s+1);
      |     ~~~~~^~~~~~~~~~

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