oj.uz

답안 #582123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582123 2022-06-23T11:59:40 Z amunduzbaev Boarding Passes (BOI22_passes) C++17
5 / 100
 3 ms 3156 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int G = 15;
const int N = 1e5 + 5;
int dp[1 << G]; 
int pref[G][G][N], cc[G][N];
int suff[G][G][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	string s; cin>>s;
	int n = s.size(), g = 0;
	for(int i=0;i<n;i++){
		g = max(g, (ll)s[i] - 'A' + 1);
	}
	for(int i=0;i<n;i++){
		if(i){
			for(int j=0;j<g;j++) cc[j][i] = cc[j][i-1];
		}
		
		cc[s[i] - 'A'][i]++;
	}
	
	for(int a=0;a<g;a++){
		for(int b=0;b<g;b++){
			for(int i=0;i<n;i++){
				if(i) pref[a][b][i] = pref[a][b][i - 1];
				if(s[i] - 'A' == a){
					pref[a][b][i] += cc[b][i] * 2;
				}
			}
			for(int i=n-1;~i;i--){
				suff[a][b][i] = suff[a][b][i + 1];
				if(s[i] - 'A' == a){
					suff[a][b][i] += (cc[b][n - 1] - cc[b][i]) * 2;
				}
			}
		}
	}
	
	memset(dp, 63, sizeof dp);
	dp[0] = 0;
	for(int mask=0;mask < (1 << g);mask++){
		int b = __builtin_popcount(mask);
		//~ if((mask >> b) == 0){
			//~ for(int k=0;k<g;k++) cout<<(mask >> k & 1);
			//~ cout<<" : "<<dp[mask]<<"\n";
		//~ }
		
		for(int j=0;j<g;j++){
			if(mask >> j & 1) continue;
			auto check = [&](int i){
				int res = 0;
				for(int k=0;k<g;k++){
					if(mask >> k & 1){
						if(i) res += pref[j][k][i - 1];
						res += suff[j][k][i];
					}
				}
				if(i){
					int m = cc[j][i - 1];
					if(m) res = res + m * (m - 1) / 2;
				}
				
				int m = cc[j][n - 1] - (i ? cc[j][i - 1] : 0);
				if(m) res = res + m * (m - 1) / 2;
				return res;
			};
			
			int l = 0, r = n, d = check(0);
			while(l + 1 < r - 1){
				int m = (l + r) >> 1;
				if(check(m) <= check(m + 1)) d = min(d, check(m)), r = m;
				else d = min(d, check(m + 1)), l = m + 1;
			}
			
			int res = min({check(l), check(r), check(l + 1), d});
			//~ if((mask >> b) == 0){
				//~ for(int k=0;k<=n;k++){
					//~ cout<<check(k)<<" ";
				//~ } cout<<"\n";
				//~ cout<<res<<"\n";
			//~ }
			
			dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + res);
		}
	}
	
	int res = dp[(1 << g) - 1];
	cout<<res/2;
	if(res&1) cout<<".5";
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:50:7: warning: unused variable 'b' [-Wunused-variable]
   50 |   int b = __builtin_popcount(mask);
      |       ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2940 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Incorrect 1 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Incorrect 1 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2940 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Incorrect 1 ms 1236 KB Output isn't correct
13 Halted 0 ms 0 KB -