oj.uz

Submission #796792

# Submission time Handle Problem Language Result Execution time Memory
796792 2023-07-28T18:19:01 Z ToniB Boarding Passes (BOI22_passes) C++17
0 / 100
 2000 ms 8564 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 2;
const int G = 15;

int n, g, cmp[27], pre[MAXN][G], suf[MAXN][G];
bool bio[27];
string s;
ll dp[1 << 15];
vector<int> group[MAXN];

ll f(int x){
	return (ll)x * (x - 1);
}

int cnt_lower(int i, int mask){
	int ret = 0;
	for(int j = 0; j < g; ++j){
		if(mask & 1 << j) ret += pre[i][j];
	}
	return 4 * ret;
}
int cnt_higher(int i, int mask){
	int ret = 0;
	for(int j = 0; j < g; ++j){
		if(mask & 1 << j) ret += suf[i][j];
	}
	return 4 * ret;
}

int main(){
	cin >> s;
	n = s.length();
	for(char c : s) bio[c - 'A'] = 1;
	for(int i = 0; i < 26; ++i){
		if(bio[i]) cmp[i] = g++;
	}
	for(int i = 0; i < n; ++i) group[cmp[s[i] - 'A']].push_back(i);

	pre[0][cmp[s[0] - 'A']] = 1;
	suf[n - 1][cmp[s[n - 1] - 'A']] = 1;
	for(int i = 1; i < n; ++i){
		for(int j = 0; j < n; ++j) pre[i][j] = pre[i - 1][j];
		++pre[i][cmp[s[i] - 'A']];
	}
	for(int i = n - 2; i >= 0; --i){
		for(int j = 0; j < n; ++j) suf[i][j] = suf[i + 1][j];
		++suf[i][cmp[s[i] - 'A']];
	}
	
	dp[0] = 0;
	for(int i = 1; i < (1 << g); ++i){
		dp[i] = 1e18;
		for(int j = 0; j < g; ++j){
			if(i & 1 << j){
				ll cur = 1e18;
				int sz = group[j].size();
				assert(sz);

				vector<ll> lower (sz), higher (sz);
				lower[0] = cnt_lower(group[j][0], i ^ 1 << j);
				higher[sz - 1] = cnt_higher(group[j][sz - 1], i ^ 1 << j);
				for(int idx = 1; idx < sz; ++idx){
					lower[idx] = lower[idx - 1] + cnt_lower(group[j][idx], i ^ 1 << j);
				}
				for(int idx = sz - 2; idx >= 0; --idx){
					higher[idx] = higher[idx + 1] + cnt_higher(group[j][idx], i ^ 1 << j);
				}

				cur = min(higher[0], lower[sz - 1]) + f(sz);
				for(int idx = 0; idx < sz - 1; ++idx){
					cur = min(cur, lower[idx] + higher[idx + 1] + f(idx + 1) + f(sz - idx - 1));
				}
				cur += dp[i ^ 1 << j];
				dp[i] = min(dp[i], cur);
			}
		}
	}
	ll ans = dp[(1 << g) - 1];
	cout << fixed << setprecision(7) << (long double)ans / 4LL;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2644 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2644 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 2772 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2063 ms 8564 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 2800 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 2 ms 2648 KB 1st numbers differ - expected: '1023.0000000000', found: '253.0000000000', error = '0.7526881720'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 2800 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 2 ms 2648 KB 1st numbers differ - expected: '1023.0000000000', found: '253.0000000000', error = '0.7526881720'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2644 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2644 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 2772 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2063 ms 8564 KB Time limit exceeded
7 Halted 0 ms 0 KB -