oj.uz

Submission #603250

# Submission time Handle Problem Language Result Execution time Memory
603250 2022-07-23T18:51:32 Z CSQ31 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 13644 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
typedef long double ld;
const int MAXN = 1e5+5;
int g[MAXN];
ll dp[MAXN],pref[MAXN],suff[MAXN];
ll cost[15][15][MAXN];
vector<int>p[15];
ll comp(vector<int>&v,int j,int k){
	int s1 = sz(p[j]);
	ll c = 0;
	for(int x:v)c+=cost[x][j][k];
	c+=k * 1LL *(k-1)/2;
	c+=(s1-k) * 1LL *(s1-k-1)/2;
	return c;
	
}
int main()
{
	string s;
	cin>>s;
	int n = sz(s);
	int m = 0;
	for(int i=0;i<n;i++){
		g[i] = s[i] - 'A';
		m = max(g[i],m);
		p[g[i]].pb(i);
	}
	m++;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j)continue; //j go after i
			int s0 = sz(p[i]);
			int s1 = sz(p[j]);
			//last "l" at here
			int ptr = -1;
			ll a = 0,b = 0;
			for(int k=0;k<s1;k++){
				while(ptr+1<s0 && p[i][ptr+1] < p[j][k]){
					ptr++;
					a+=2;
				}
				b+=a;
				cost[i][j][k+1] = b;
			}
			a = b = 0;
			ptr = s0;
			for(int k=s1-1;k>=0;k--){
				while(ptr-1>=0 && p[i][ptr-1] > p[j][k]){
					ptr--;
					a+=2;
				}
				b+=a;
				cost[i][j][k]+= b;
			}
		}
	}
	for(int mask=0;mask<(1<<m);mask++)dp[mask] = 1e18;
	dp[0] = 0;
	for(int mask=0;mask<(1<<m);mask++){
		vector<int>v;
		for(int j=0;j<m;j++){
			if(mask&(1<<j))v.pb(j);
		}
		for(int j=0;j<m;j++){
			if(mask&(1<<j))continue;
			int s1 = sz(p[j]);
			for(int k=0;k<=s1;k++){
				ll c = comp(v,j,k);
				dp[mask+(1<<j)] = min(dp[mask+(1<<j)],dp[mask]+c);
			}
		}
	}
	ld ans = dp[(1<<m)-1];
	ans/=2;
	cout<<fixed<<setprecision(5)<<ans<<'\n';
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 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 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1352 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1360 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 1360 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.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 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.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 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 0 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 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 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 536 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 544 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 10 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 10 ms 1160 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 53 ms 1668 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 51 ms 1636 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 47 ms 1708 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 48 ms 1644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 49 ms 1648 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 49 ms 1648 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 53 ms 1652 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 44 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 46 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 62 ms 1652 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 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 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1352 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 1360 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 1360 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 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 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 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 536 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 544 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 10 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 10 ms 1160 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 53 ms 1668 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 51 ms 1636 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 47 ms 1708 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 48 ms 1644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 49 ms 1648 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 49 ms 1648 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 53 ms 1652 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 44 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 46 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 62 ms 1652 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 18 ms 1108 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 19 ms 1760 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 1276 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 1360 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 1312 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 10 ms 1156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 12 ms 1160 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 48 ms 1672 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 44 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 48 ms 1708 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 49 ms 1644 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 59 ms 1648 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 46 ms 1620 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 45 ms 1620 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 45 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 45 ms 1668 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 50 ms 1656 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2100 ms 13644 KB Time limit exceeded
97 Halted 0 ms 0 KB -