oj.uz

Submission #672515

# Submission time Handle Problem Language Result Execution time Memory
672515 2022-12-16T12:20:17 Z LittleCube Boarding Passes (BOI22_passes) C++14
5 / 100
 6 ms 2204 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, G;
double pref[15][15][100005], suf[15][15][100005], cost[15][1 << 15], dp[1 << 15];
string s;

bool cmp(int i, int mask, int mid)
{
	double pre = 0, su = 0;
	for (int j = 0; j < G; j++)
		if (mask & (1 << j))
		{
			pre += pref[i][j][mid];
			su += suf[i][j][mid + 1];
		}
	pre += pref[i][i][mid];
	su += suf[i][i][mid + 1];
	return pre < su;
}

double sum(int i, int mask, int mid)
{
	double res = 0, pre = 0, su = 0;
	for (int j = 0; j < G; j++)
		if (mask & (1 << j))
			res += pref[i][j][mid] + suf[i][j][mid + 1];

	res += pref[i][i][mid] + suf[i][i][mid + 1];

	return res;
}

signed main()
{
	cin >> s;
	N = s.size();
	s = " " + s + " ";
	for (int i = 1; i <= N; i++)
		G = max(G, s[i] - 'A' + 1);
	for (int i = 0; i < G; i++)
	{
		int acc[15] = {};
		for (int j = 1; j <= N; j++)
		{
			if (s[j] - 'A' == i)
				for (int k = 0; k < G; k++)
					pref[i][k][j] += (i == k ? 0.5 * acc[k] : 1.0 * acc[k]);
			acc[s[j] - 'A']++;
			for (int k = 0; k < G; k++)
				pref[i][k][j] += pref[i][k][j - 1];
		}
	}
	for (int i = 0; i < G; i++)
	{
		int acc[15] = {};
		for (int j = N; j >= 1; j--)
		{
			if (s[j] - 'A' == i)
				for (int k = 0; k < G; k++)
					suf[i][k][j] += (i == k ? 0.5 * acc[k] : 1.0 * acc[k]);
			acc[s[j] - 'A']++;
			for (int k = 0; k < G; k++)
				suf[i][k][j] += suf[i][k][j + 1];
		}
	}
	// for(int i = 0; i < G; i++)
	//	for(int j = 0; j < G; j++)
	//	{
	//	cout << i << " " << j;
	//	for(int k = 0; k <= N; k++)
	//		cout << " " << pref[i][j][k] << " " << suf[i][j][k] << ",";
	//	cout << '\n';
	//	}
	for (int i = 0; i < G; i++)
		for (int mask = 0; mask < (1 << G); mask++)
			if ((mask & (1 << i)) == 0)
			{
				cost[i][mask] = 1e10;
				// cout << i << " ";
				int L = 0, R = N;
				while (R > L)
				{
					int mid = (L + R) / 2;
					if (cmp(i, mask, mid))
						L = mid + 1;
					else
						R = mid;
				}
				cost[i][mask] = min(cost[i][mask], sum(i, mask, L));

				// bitset<4> b = mask;
				// cout << '\n';
			}

	for (int mask = 0; mask < (1 << G); mask++)
	{
		dp[mask] = (mask == 0 ? 0.0 : 1e10);
		for (int i = 0; i < G; i++)
			if (mask & (1 << i))
				dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + cost[i][mask ^ (1 << i)]);
	}
	cout << fixed << setprecision(10) << dp[(1 << G) - 1] << '\n';
}

Compilation message

passes.cpp: In function 'double sum(int, int, int)':
passes.cpp:29:18: warning: unused variable 'pre' [-Wunused-variable]
   29 |  double res = 0, pre = 0, su = 0;
      |                  ^~~
passes.cpp:29:27: warning: unused variable 'su' [-Wunused-variable]
   29 |  double res = 0, pre = 0, su = 0;
      |                           ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 1752 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 6 ms 2020 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2204 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2148 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 432 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 1 ms 980 KB 1st numbers differ - expected: '1023.0000000000', found: '1048.5000000000', error = '0.0249266862'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 432 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 1 ms 980 KB 1st numbers differ - expected: '1023.0000000000', found: '1048.5000000000', error = '0.0249266862'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 308 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 1752 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 6 ms 2020 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2204 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2148 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 432 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Incorrect 1 ms 980 KB 1st numbers differ - expected: '1023.0000000000', found: '1048.5000000000', error = '0.0249266862'
13 Halted 0 ms 0 KB -