Submission #578336

#	Time	Username	Problem	Language	Result	Execution time	Memory
578336		kingfran1907	Boarding Passes (BOI22_passes)	C++14	100 / 100	211 ms	50728 KiB

passes

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 1e5+10;
const int maxg = 15;
const int off = (1 << maxg);

int n;
char niz[maxn];
llint dp[off + 10];
vector< int > pos[300];
llint cntl[maxg + 1][maxn], cntal[maxg + 1][maxg + 1][maxn];
llint cntr[maxg + 1][maxn], cntar[maxg + 1][maxg + 1][maxn];

llint get(int mask, int x, int wh) {
	llint out = cntal[x][x][wh] + cntar[x][x][wh + 1];
	for (int i = 0; i < maxg; i++) {
		if (mask & (1 << i)) {
			llint tren = cntal[x][i][wh] + cntar[x][i][wh + 1];
			out += tren * 2;
		}
	}
	//if (mask == 0 && x == 2) printf("get: %d %d %d --> %lld\n", mask, x, wh, out);
	return out;
}

llint f(int mask) {
	//printf("debug: %d\n", mask);
	if (mask == 0) return 0;
	llint &ret = dp[mask];
	if (ret != -1) return ret;
	
	ret = 1LL << 60;
	for (int i = 0; i < maxg; i++) {
		if (mask & (1 << i)) {
			llint cost = 1LL << 60;
			int tr = mask ^ (1 << i);
			llint base = f(tr);
			if (pos[i].size() == 0) {
				ret = min(ret, base);
				continue;
			}
			
			int lo = 0, hi = pos[i].size();
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				llint a = get(tr, i, mid);
				llint b = get(tr, i, mid + 1);
				if (a < b) hi = mid;
				else lo = mid + 1;
			}
			cost = base + get(tr, i, lo);
			ret = min(ret, cost);
		}
	}
	//printf("f: %d --> %lld\n", mask, ret);
	return ret;
}

int main() {
	scanf("%s", niz);
	n = strlen(niz);
	for (int i = 0; i < n; i++)
		pos[niz[i] - 'A'].push_back(i);
		
	for (int i = 0; i < maxg; i++) {
		int tren = 0;
		for (int j = 0; j < n; j++) {
			cntl[i][j] = tren;
			if (niz[j] == i + 'A') tren++;
		}
		
		tren = 0;
		for (int j = n - 1; j >= 0; j--) {
			cntr[i][j] = tren;
			if (niz[j] == i + 'A') tren++;
		}
	}
	
	for (int i = 0; i < maxg; i++) {
		for (int j = 0; j < maxg; j++) {
			for (int k = 0; k < pos[i].size(); k++) {
				cntal[i][j][k + 1] = cntal[i][j][k] + cntl[j][pos[i][k]];
			}
			cntal[i][j][pos[i].size() + 1] = cntal[i][j][pos[i].size()] + pos[j].size();
			
			for (int k = pos[i].size() - 1; k >= 0; k--) {
				cntar[i][j][k + 1] = cntar[i][j][k + 2] + cntr[j][pos[i][k]];
			}
			cntar[i][j][0] = cntar[i][j][1] + pos[j].size();
		}
	}
	
	for (int i = 0; i < off + 10; i++) 
		dp[i] = -1;
	
	llint sol = f((1 << maxg) - 1);
	printf("%lld", sol / 2);
	if (sol % 2 == 1) printf(".5");
	printf("\n");
	return 0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for (int k = 0; k < pos[i].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~~
passes.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%s", niz);
      |  ~~~~~^~~~~~~~~~~

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