Submission #679523

#	Time	Username	Problem	Language	Result	Execution time	Memory
679523		jamezzz	Boarding Passes (BOI22_passes)	C++17	100 / 100	944 ms	357784 KiB

passes

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005
#define maxm (1<<15)

void print2(ll x){
	if(x%2)pf("%lld.5\n",x/2);
	else pf("%lld\n",x/2);
}

int n,a[maxn],num[15],pos[15][maxn];
ll pfx[15][15][maxn],sfx[15][15][maxn];
ll memo[maxm+5],memo2[maxm+5][15];
char str[maxn];

ll cost(int mask,int x,int y){
	int p=pos[x][y],p2=pos[x][y+1];
	ll ans=0;
	for(int i=0;i<15;++i){
		if((mask&(1<<i))!=0)ans+=pfx[i][x][p]+sfx[i][x][p2];
	}
	ll b=y,a=num[x]-y;
	ans*=2;
	ans+=(b*(b-1)+a*(a-1))/2;
	return ans;
}

ll calc(int mask,int x){
	if(num[x]==0)return 0;
	if(memo2[mask][x]!=-1)return memo2[mask][x];
	int lo=0,hi=num[x];
	while(hi-lo>=3){
		int m1=lo+(hi-lo+1)/3,m2=m1+hi>>1;
		if(cost(mask,x,m1)<=cost(mask,x,m2))hi=m2;
		else lo=m1;
	}
	ll ans=LINF;
	for(int i=lo;i<=hi;++i){
		ans=min(ans,cost(mask,x,i));
	}
	return memo2[mask][x]=ans;
}

ll dp(int mask){
	if(mask==maxm-1)return 0;
	if(memo[mask]!=-1)return memo[mask];
	ll mn=LINF;int best=0;
	for(int i=0;i<15;++i){
		if((mask&(1<<i))!=0)continue;
		int nmask=mask^(1<<i);
		ll tmp=calc(mask,i)+dp(nmask);
		if(tmp<=mn){
			mn=tmp;best=i;
		}
	}
	return memo[mask]=mn;
}

int main(){
	sf(" %s",&str);
	n=strlen(str);
	for(int i=1;i<=n;++i){
		a[i]=str[i-1]-'A';
		++num[a[i]];
		pos[a[i]][num[a[i]]]=i;
		pos[a[i]][num[a[i]]+1]=n+1;
	}
	for(int i=0;i<maxm;++i){
		memo[i]=-1;
		for(int j=0;j<15;++j){
			memo2[i][j]=-1;
		}
	}
	
	for(int x=0;x<15;++x){
		for(int y=0;y<15;++y){
			int cnt=0;
			for(int i=1;i<=n;++i){
				pfx[x][y][i]=pfx[x][y][i-1];
				if(a[i]==x)++cnt;
				if(a[i]==y)pfx[x][y][i]+=cnt;
			}
			cnt=0;
			for(int i=n;i>=1;--i){
				sfx[x][y][i]=sfx[x][y][i+1];
				if(a[i]==x)++cnt;
				if(a[i]==y)sfx[x][y][i]+=cnt;
			}
		}
	}
	print2(dp(0));
}

Compilation message (stderr)

passes.cpp: In function 'll calc(int, int)':
passes.cpp:87:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int m1=lo+(hi-lo+1)/3,m2=m1+hi>>1;
      |                            ~~^~~
passes.cpp: In function 'll dp(int)':
passes.cpp:101:17: warning: variable 'best' set but not used [-Wunused-but-set-variable]
  101 |  ll mn=LINF;int best=0;
      |                 ^~~~
passes.cpp: In function 'int main()':
passes.cpp:114:8: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[100005]' [-Wformat=]
  114 |  sf(" %s",&str);
      |       ~^  ~~~~
      |        |  |
      |        |  char (*)[100005]
      |        char*
passes.cpp:114:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  sf(" %s",&str);
      |    ^

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