oj.uz

Submission #601793

# Submission time Handle Problem Language Result Execution time Memory
601793 2022-07-22T10:11:59 Z CSQ31 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 2772 KB 
//consider scc graph
//u -> v
//if u bad then v must be bad
//so every ingoing edge into v must be good and sum of sub(tree?graph?) must be >= minimal parent
//i dont even need scc,only scc is if all values are equal okay yes
#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;
//l l = 0.5
//r r = 0.5
//l r = 0
//r l = 1
//always do prefix l and suffix r
const int MAXN = 1e5+5;
int g[MAXN];
ll dp[MAXN],pref[MAXN],suff[MAXN];
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);
	}
	m++;
	for(int mask=0;mask<(1<<m);mask++)dp[mask] = 1e18;
	dp[0] = 0;
	for(int mask=0;mask<(1<<m);mask++){
		for(int j=0;j<m;j++){
			if(mask&(1<<j))continue;
			ll a = 0,b = 0;
			ll cost = 0;
			for(int k=0;k<n;k++){
				if(g[k] == j){
					a++;
					cost+=2*b;
				}
				else if(mask&(1<<g[k]))b++;
				pref[k] = cost + a*(a-1)/2;
			}
			a = 0;
			b = 0;
			cost = 0;
			for(int k=n-1;k>=0;k--){
				if(g[k] == j){
					a++;
					cost+=2*b;
				}
				else if(mask&(1<<g[k]))b++;
				suff[k] = cost + a*(a-1)/2;
			}
			int nmask = mask+(1<<j);
			dp[nmask] = min(dp[nmask],min(pref[n-1],suff[0]) + dp[mask]);
			for(int i=0;i+1<n;i++)dp[nmask] = min(dp[nmask],pref[i]+suff[i+1] + dp[mask]);
		}
	}
	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 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 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2260 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 2388 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2388 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 308 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 308 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 308 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 308 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 308 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 308 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 308 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 308 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 308 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 308 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 308 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 308 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 304 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 43 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 42 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 291 ms 548 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 205 ms 544 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 207 ms 540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 232 ms 544 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 218 ms 536 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 216 ms 532 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 262 ms 540 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 231 ms 536 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 229 ms 468 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 222 ms 532 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 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 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 2004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2260 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 2388 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2388 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 308 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 308 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 308 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 308 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 308 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 304 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 308 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 308 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 308 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 304 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 43 ms 468 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 42 ms 468 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 291 ms 548 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 205 ms 544 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 207 ms 540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 232 ms 544 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 218 ms 536 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 216 ms 532 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 262 ms 540 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 231 ms 536 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 229 ms 468 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 222 ms 532 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 21 ms 468 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 54 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 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 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 2004 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 2388 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 2516 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 2480 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 46 ms 520 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 47 ms 528 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 321 ms 588 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 209 ms 532 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 239 ms 532 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 218 ms 528 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 223 ms 468 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 229 ms 516 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 227 ms 524 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 246 ms 524 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 229 ms 588 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 235 ms 536 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2076 ms 2772 KB Time limit exceeded
97 Halted 0 ms 0 KB -