oj.uz

Submission #603248

# Submission time Handle Problem Language Result Execution time Memory
603248 2022-07-23T18:46:49 Z CSQ31 Boarding Passes (BOI22_passes) C++17
55 / 100
 45 ms 1732 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;
const int MAXN = 1e5+5;
int g[MAXN];
ll dp[MAXN],pref[MAXN],suff[MAXN];
ll cost[15][15][MAXN];
vector<int>p[15];
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 = 0;
				for(int x:v)c+=cost[x][j][k];
				c+=k*(k-1)/2;
				c+=(s1-k) * (s1-k-1)/2;
				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
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 1 ms 308 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 4 ms 1360 KB 1st numbers differ - expected: '772893586.0000000000', found: '-276172925.5000000000', error = '1.3573233502'
7 Halted 0 ms 0 KB -

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 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 1 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 1 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 564 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 1 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 568 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 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 1 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 1 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 564 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 1 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 568 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 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 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 560 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 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 468 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 468 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 1 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 564 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 9 ms 1168 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 8 ms 1108 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 37 ms 1620 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 36 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 40 ms 1732 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 43 ms 1620 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 35 ms 1692 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 35 ms 1592 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 35 ms 1600 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 35 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 35 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 45 ms 1656 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 1 ms 308 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 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 4 ms 1360 KB 1st numbers differ - expected: '772893586.0000000000', found: '-276172925.5000000000', error = '1.3573233502'
7 Halted 0 ms 0 KB -