oj.uz

Submission #578273

# Submission time Handle Problem Language Result Execution time Memory
578273 2022-06-16T09:54:31 Z IvanJ Boarding Passes (BOI22_passes) C++17
5 / 100
 5 ms 3660 KB 
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int n, M;
string s;
double dp[(1 << 15)];
vector<int> C[maxn];
double E[maxn];

double rek(int mask) {
	if(__builtin_popcount(mask) == M)
		return 0;
	if(dp[mask] != -1) 
		return dp[mask];
	
	
	vector<double> pref(n, 0);
	for(int i = 0;i < n;i++) {
		pref[i] += ((1 << (s[i] - 'A')) & mask) ? 1 : 0;
		if(i) pref[i] += pref[i - 1];
	}
	
	double ret = 1e18;
	for(int i = 0;i < M;i++) {
		if((1 << i) & mask) continue;
		double sum = 0, R = rek(mask | (1 << i));
		int m = C[i].size();
		if(m == 0) {
			ret = min(ret, R);
			continue;
		}
		for(int j : C[i])
			sum += pref[j];
		ret = min(ret, sum + E[m] + R);
		//cout << mask << " " << i << " " << sum + E[m] << "\n";
		for(int j = m - 1;j >= 0;j--) {
			sum -= pref[C[i][j]];
			sum += pref[n - 1];
			if(C[i][j]) sum -= pref[C[i][j] - 1];
			ret = min(ret, sum + E[j] + E[m - j] + R);
			//cout << mask << " " << i << " " << sum + E[j] + E[m - j] << " " << R << "\n";
		}
	}
	
	//cout << mask << " " << ret << " dp\n";
	return dp[mask] = ret;
}

int main() {
	cin >> s;
	n = s.size();
	if(n <= 100) M = 15;
	else M = 10;
	for(int i = 2;i <= n;i++) 
		E[i] = (double)i * (i - 1) / 4;
	double sol = 1e18;
	for(int i = 0;i <= n;i++)
		sol = min(sol, E[i] + E[n - i]);
	if(round(sol) != floor(sol)) printf("%.1lf\n", sol);
	else printf("%.0lf\n", sol);
	return 0;
	for(int i = 0;i < n;i++)
		C[s[i] - 'A'].pb(i);
		
	for(int i = 0;i < (1 << M);i++) 
		dp[i] = -1.0;
	double ans = rek(0);
	printf("%.1lf\n", ans);
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 3412 KB Output is correct
7 Correct 4 ms 3540 KB Output is correct
8 Correct 4 ms 3660 KB Output is correct
9 Correct 4 ms 3540 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 3412 KB Output is correct
7 Correct 4 ms 3540 KB Output is correct
8 Correct 4 ms 3660 KB Output is correct
9 Correct 4 ms 3540 KB Output is correct
10 Incorrect 2 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -