oj.uz

답안 #953514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953514 2024-03-26T05:04:35 Z PM1 Boarding Passes (BOI22_passes) C++17
55 / 100
 2000 ms 2904 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,mxg=15;
int g,n,a[mxn],cnt=0,all[mxg+5];
string s;
ll dp[(1<<mxg)],res[(1<<mxg)][mxg+5],z=1,sum[(1<<mxg)],num[mxg+5],rsum[(1<<mxg)],zz=2;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++){
		int x=s[i];
		a[x]=(a[x]==0)?++cnt:a[x];
		x=a[x];
		all[x]+=z;
		for(int j=0;j<(1<<mxg);j++){
			if(j&(1<<(x-1))){
				rsum[j]+=z;
			}
		}
	}
	for(int i=0;i<n;i++){
		int x=s[i];
		x=a[x];
		for(int j=0;j<(1<<cnt);j++){
			if(j&(1<<(x-1)))continue;
			res[j][x]+=min(sum[j]*2+num[x],rsum[j]*2+all[x]-num[x]-z);
		}
		for(int j=0;j<(1<<cnt);j++){
			if(j&(1<<(x-1))){
				rsum[j]-=z;
				sum[j]+=z;
			}
		}
		num[x]+=z;
	}
	for(int i=1;i<(1<<cnt);i++){
		dp[i]=1e18;
		for(int j=0;j<cnt;j++){
			if(i&(1<<j)){
				int y=i-(1<<j);
				dp[i]=min(dp[i],dp[y]+res[y][j+1]);
			}
		}
	}
	cout<<dp[(1<<cnt)-1]/2;
	if(dp[(1<<cnt)-1]%2)
		cout<<".5";
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2652 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 2652 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2021 ms 2904 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 3 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 2648 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 4 ms 2648 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 2648 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 2652 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 2 ms 2652 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 2652 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 2652 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 3 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 4 ms 2648 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 4 ms 2648 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 4 ms 2648 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 2 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 2652 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 2 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 2652 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 3 ms 2652 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 2652 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 2 ms 2652 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 2648 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 2652 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 2652 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 2652 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 4 ms 2652 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 4 ms 2648 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 4 ms 2652 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 4 ms 2652 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2652 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 4 ms 2460 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 2 ms 2652 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 2652 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 2660 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 2 ms 2648 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 2 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 2 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 3 ms 600 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 604 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 297 ms 736 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 317 ms 736 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 366 ms 2704 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 342 ms 2708 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 385 ms 2648 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 346 ms 2700 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 380 ms 2700 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 440 ms 736 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 371 ms 2704 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 372 ms 2704 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 366 ms 2700 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 377 ms 852 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2652 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2652 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2652 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 28 ms 2652 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2021 ms 2904 KB Time limit exceeded
7 Halted 0 ms 0 KB -