oj.uz

Submission #672073

# Submission time Handle Problem Language Result Execution time Memory
672073 2022-12-14T16:53:18 Z LittleCube Boarding Passes (BOI22_passes) C++14
30 / 100
 460 ms 17232 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];
			// pre += pref[i][j][mid];
			// su += suf[i][j][mid + 1];
		}
	// pre += pref[i][i][mid];
	// su += suf[i][i][mid + 1];
	res += pref[i][i][mid] + suf[i][i][mid + 1];
	//	bitset<4> b = mask;
	// cout << (pre < su ? '<' : (pre == su ? '=' : '>')) << res << ' ';
	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 > 5000)
				{
					int mid = (L + R) / 2;
					if(cmp(i, mask, mid))
						L = mid;
					else R = mid;
				}
				for(int j = L; j <= R; j++)
					cost[i][mask] = min(cost[i][mask], sum(i, mask, j));	
							
				// 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:32:18: warning: unused variable 'pre' [-Wunused-variable]
   32 |  double res = 0, pre = 0, su = 0;
      |                  ^~~
passes.cpp:32:27: warning: unused variable 'su' [-Wunused-variable]
   32 |  double res = 0, pre = 0, su = 0;
      |                           ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 308 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 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 312 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 1748 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2044 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2148 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2168 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 436 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 820 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 436 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 820 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 1024 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 824 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 2 ms 868 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 68 ms 11092 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 70 ms 11132 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Incorrect 460 ms 17232 KB 1st numbers differ - expected: '12223392.0000000000', found: '12223400.0000000000', error = '0.0000006545'
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 308 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 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 312 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 1748 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 2044 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 2148 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2168 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 436 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 980 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 2 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 852 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 820 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 852 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 2 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 2 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 980 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 3 ms 1024 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 980 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 852 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 2 ms 980 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 824 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 852 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 852 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 852 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 852 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 852 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 2 ms 868 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 2 ms 852 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 852 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 2 ms 852 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 68 ms 11092 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 70 ms 11132 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Incorrect 460 ms 17232 KB 1st numbers differ - expected: '12223392.0000000000', found: '12223400.0000000000', error = '0.0000006545'
47 Halted 0 ms 0 KB -