oj.uz

답안 #1031435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031435 2024-07-22T20:39:20 Z Unforgettablepl Chorus (JOI23_chorus) C++17
40 / 100
 7000 ms 604 KB 
#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int INF = 1e18;
 
struct fenwick{
	vector<int> tree;
	int n;
	fenwick(int n):n(n),tree(n+1){}
	void add(int k,int x){
		while(k<=n){
			tree[k]+=x;
			k+=k&-k;
		}
	}
	void reset(){
		fill(tree.begin(),tree.end(),0ll);
	}
	int get(int k){
		int ans = 0;
		while(k){
			ans+=tree[k];
			k-=k&-k;
		}
		return ans;
	}
};
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	s.insert(s.begin(),'$');
	vector<int> posA(n+1);
	vector<int> posB(n+1);
	int cntA = 0,cntB = 0;
	for(int i=1;i<=2*n;i++){
		if(s[i]=='A'){
			posA[++cntA]=i;
		} else {
			posB[++cntB]=i;
		}
	}
	fenwick addedA(2*n);
	fenwick addedB(2*n);
	auto solvemax = [&](int penalty){
		vector<pair<int,int>> DP(n+1,{INF,-INF});
		DP[0]={0,0};
		for(int i=1;i<=n;i++){
			int ans = penalty;
			addedA.reset();
			addedB.reset();
			for(int j=i+1;j<=n;j++)addedB.add(posB[j],1);
			for(int j=i;j;j--){
				ans+=i-j-addedA.get(posB[j]);
				addedB.add(posB[j],1);
				ans+=addedB.get(posA[j]);
				addedA.add(posA[j],1);
				DP[i]=min(DP[i],{DP[j-1].first+ans,DP[j-1].second-1});
			}
		}
		DP[n].second*=-1ll;
		return DP[n];
	};
	auto solvemin = [&](int penalty){
		vector<pair<int,int>> DP(n+1,{INF,-INF});
		DP[0]={0,0};
		for(int i=1;i<=n;i++){
			int ans = penalty;
			addedA.reset();
			addedB.reset();
			for(int j=i+1;j<=n;j++)addedB.add(posB[j],1);
			for(int j=i;j;j--){
				ans+=i-j-addedA.get(posB[j]);
				addedB.add(posB[j],1);
				ans+=addedB.get(posA[j]);
				addedA.add(posA[j],1);
				DP[i]=min(DP[i],{DP[j-1].first+ans,DP[j-1].second+1});
			}
		}
		return DP[n];
	};
	auto solve = [&](int penalty){
		auto mini = solvemin(penalty);
		auto maxi = solvemax(penalty);
		if(mini.second>k)return mini;
		if(maxi.second<=k)return maxi;
		return make_pair(mini.first,k);
	};
	int best_penalty = -1;
	for(int jump=(1ll<<50);jump;jump/=2ll){
		if(solve(best_penalty+jump).second>k)best_penalty+=jump;
	}
	// for(int i=0;i<=10;i++)cout<<solve(i).second<<'\n';
	best_penalty++;
	cout << solve(best_penalty).first-solve(best_penalty).second*best_penalty << '\n';
}

Compilation message

chorus.cpp: In constructor 'fenwick::fenwick(long long int)':
chorus.cpp:11:6: warning: 'fenwick::n' will be initialized after [-Wreorder]
   11 |  int n;
      |      ^
chorus.cpp:10:14: warning:   'std::vector<long long int> fenwick::tree' [-Wreorder]
   10 |  vector<int> tree;
      |              ^~~~
chorus.cpp:12:2: warning:   when initialized here [-Wreorder]
   12 |  fenwick(int n):n(n),tree(n+1){}
      |  ^~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 29 ms 348 KB Output is correct
18 Correct 237 ms 348 KB Output is correct
19 Correct 240 ms 348 KB Output is correct
20 Correct 262 ms 344 KB Output is correct
21 Correct 254 ms 344 KB Output is correct
22 Correct 255 ms 600 KB Output is correct
23 Correct 258 ms 344 KB Output is correct
24 Correct 247 ms 464 KB Output is correct
25 Correct 233 ms 348 KB Output is correct
26 Correct 228 ms 344 KB Output is correct
27 Correct 237 ms 344 KB Output is correct
28 Correct 243 ms 344 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 29 ms 348 KB Output is correct
18 Correct 237 ms 348 KB Output is correct
19 Correct 240 ms 348 KB Output is correct
20 Correct 262 ms 344 KB Output is correct
21 Correct 254 ms 344 KB Output is correct
22 Correct 255 ms 600 KB Output is correct
23 Correct 258 ms 344 KB Output is correct
24 Correct 247 ms 464 KB Output is correct
25 Correct 233 ms 348 KB Output is correct
26 Correct 228 ms 344 KB Output is correct
27 Correct 237 ms 344 KB Output is correct
28 Correct 243 ms 344 KB Output is correct
29 Execution timed out 7032 ms 604 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 29 ms 348 KB Output is correct
18 Correct 237 ms 348 KB Output is correct
19 Correct 240 ms 348 KB Output is correct
20 Correct 262 ms 344 KB Output is correct
21 Correct 254 ms 344 KB Output is correct
22 Correct 255 ms 600 KB Output is correct
23 Correct 258 ms 344 KB Output is correct
24 Correct 247 ms 464 KB Output is correct
25 Correct 233 ms 348 KB Output is correct
26 Correct 228 ms 344 KB Output is correct
27 Correct 237 ms 344 KB Output is correct
28 Correct 243 ms 344 KB Output is correct
29 Execution timed out 7032 ms 604 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 29 ms 348 KB Output is correct
18 Correct 237 ms 348 KB Output is correct
19 Correct 240 ms 348 KB Output is correct
20 Correct 262 ms 344 KB Output is correct
21 Correct 254 ms 344 KB Output is correct
22 Correct 255 ms 600 KB Output is correct
23 Correct 258 ms 344 KB Output is correct
24 Correct 247 ms 464 KB Output is correct
25 Correct 233 ms 348 KB Output is correct
26 Correct 228 ms 344 KB Output is correct
27 Correct 237 ms 344 KB Output is correct
28 Correct 243 ms 344 KB Output is correct
29 Execution timed out 7032 ms 604 KB Time limit exceeded
30 Halted 0 ms 0 KB -