Submission #601317

#	Time	Username	Problem	Language	Result	Execution time	Memory
601317		patrikpavic2	Boarding Passes (BOI22_passes)	C++17	100 / 100	171 ms	28892 KiB

passes

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define PB push_back
#define int long long

using namespace std;


const int INF = (int)1e18;
const int N = 1e5 + 500;
const int ALP = 15;
const int MSK = (1 << ALP);

int P[N][ALP], sol[N][ALP], n, tmp[ALP];
int cst[MSK][ALP], dp[MSK];
char s[N];

int f(int msk){
	if(msk == MSK - 1) return 0;
	if(dp[msk] != -1) return dp[msk];
	dp[msk] = INF;
	for(int a = 0;a < ALP;a++)
		if(!((1 << a) & msk))
			dp[msk] = min(dp[msk], f(msk | (1 << a)) + cst[msk][a]);
	return dp[msk];
}

signed main(){
	memset(dp, -1, sizeof(dp));
	scanf("%s", s); n = strlen(s);
	for(int i = 0;i < n;i++){
		for(int j = 0;j < ALP;j++)
			P[i][j] = (i ? P[i - 1][j] : 0);
		P[i][s[i] - 'A']++;
	}
	for(int j = 0;j < ALP;j++){
		vector < int > pos;
		memset(tmp, 0, sizeof(tmp));
		for(int i = 0;i < n;i++){
			if(s[i] - 'A' != j) continue;
			pos.PB(i);
			for(int a = 0;a < ALP;a++){
				tmp[a] += P[i][a] - (a == j);
				sol[i][a] += tmp[a] * (1 + (a != j));
			}
		}
		memset(tmp, 0, sizeof(tmp));
		for(int i = n - 1;i >= 0;i--){
			if(s[i] - 'A' != j) continue;
			for(int a = 0;a < ALP;a++){
				sol[i][a] += tmp[a] * (1 + (a != j));
				tmp[a] += P[n - 1][a] - P[i][a];
			}
		}
		for(int msk = 0;msk < (1 << ALP);msk++){
			if(msk & (1 << j)) continue;
			int uk = 0;
			for(int a = 0;a < ALP;a++) 
				if(msk & (1 << a))
					uk += 2 * P[n - 1][a];
			uk += P[n - 1][j] - 1;
			int naj = -1;
			for(int k = 18;k >= 0;k--){
				if(naj + (1 << k) >= (int)pos.size()) continue;
				naj += (1 << k);
				int kol = 0;
				for(int b = 0;b < ALP;b++)
					if(msk & (1 << b)) kol += 2 * P[pos[naj]][b];
				kol += naj;
				if(kol > uk - kol)
					naj -= (1 << k);
			}
			for(int a = 0;a < ALP;a++)
				if((1 << a) & (msk + (1 << j)))
					cst[msk][j] += (naj > -1 ? sol[pos[naj]][a] : (tmp[a] * (1 + (a != j))));
		}
	}
	int fin = f(0);
	printf("%lld", fin / 2);
	if(fin & 1) printf(".5");
	printf("\n");
	return 0;
}

Compilation message (stderr)

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

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