oj.uz

Submission #789334

# Submission time Handle Problem Language Result Execution time Memory
789334 2023-07-21T09:23:15 Z 박상훈(#10042) Chorus (JOI23_chorus) C++17
0 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
char s[2002000];
int a[1001000], b[1001000], nxt[2002000], prv[2002000];
ll cst[505][505], dp_naive[505][505], sum[1001000];

inline ll cost(int l, int r){ // O(1)
	int r2 = min(r, prv[a[r]]);
	if (r2 < l) return 0;

	return (ll)(r+1) * (r2-l+1) - (sum[r2] - sum[l-1]);
}

ll naive(int n, int k){
	for (int i=1;i<=n;i++){
		for (int j=i;j<=n;j++){
			for (int k=i;k<=j;k++){
				cst[i][j] += max(j-nxt[b[k]]+1, 0);
			}
		}
	}

	for (int i=0;i<=n;i++){
		fill(dp_naive[i], dp_naive[i]+k+1, INF);
	}
	dp_naive[0][0] = 0;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=k;j++){
			for (int p=0;p<i;p++) dp_naive[i][j] = min(dp_naive[i][j], dp_naive[p][j-1] + cst[p+1][i]);
		}
	}

	return dp_naive[n][k];
}

ll dp[1001000];
int dp2[1001000];

struct Hull{
	vector<int> st, st2;
	int pt, cap;
	ll lambda;

	void init(int n, ll _lambda){
		st.clear();
		st2.clear();
		pt = 0;
		cap = n;
		lambda = _lambda;
	}

	inline ll calc(int f, int x){
		assert(f < x);
		return dp[f] + cost(f+1, x) * 2 + lambda;
	}

	int cross(int f, int g){
		int l = g+1, r = cap, ret = cap+1;
		while(l<=r){
			int mid = (l+r)>>1;
			if (calc(f, mid) > calc(g, mid)) ret = mid, r = mid-1;
			else l = mid+1;
		}

		return ret;

	}

	void push(int x){
		while(st.size() >= 2 && st2.back() >= x+1 && calc(st.back(), st2.back()) >= calc(x, st2.back())){
			st.pop_back();
			st2.pop_back();
		}

		if (st.size() >= 1 && calc(st.back(), cap) <= calc(x, cap)) return;

		if (st.size() >= 1) st2.push_back(cross(st.back(), x));
		st.push_back(x);

		assert(st2.empty() || st2.back() <= cap);
	}

	pair<ll, int> query(int x){
		pt = min(pt, (int)st.size()-1);
		while(pt+1<(int)st.size() && st2[pt] <= x) pt++;
		return {calc(st[pt], x), dp2[st[pt]]+1};
	}


}hull;

int alien(int n, ll lambda){ // y + \lambda x min
	// monotone queue opt
	hull.init(n, lambda);
	hull.push(0);

	for (int i=1;i<=n;i++){
		auto [val, cnt] = hull.query(i);
		dp[i] = val;
		dp2[i] = cnt;

		hull.push(i);
	}

	return dp2[n];
}

ll solve(int n, int k){
	ll l = 0, r = 1e12 + 100, opt = -1;
	while(l<=r){
		ll mid = (l+r) / 2;
		if (alien(n, mid*2-1) >= k) opt = mid, l = mid+1;
		else r = mid-1;
	}

	assert(opt >= 0);
	int cnt = alien(n, opt*2-1);
	ll val = (dp[n] - (opt*2-1) * cnt) / 2;

	if (cnt==k){
		return val;
	}

	int cnt2 = alien(n, opt*2+1);
	ll val2 = (dp[n] - (opt*2+1) * cnt2) / 2;
	assert(cnt2 < k);

	return val2 - opt * (k-cnt2);
}

int main(){
	int n, k;
	scanf("%d %d", &n, &k);

	hull.st.reserve(n+100);
	hull.st2.reserve(n+100);

	scanf("%s", s+1);
	int ptA = 1, ptB = 1;
	for (int i=1;i<=n*2;i++){
		if (s[i]=='A'){
			// mp[i] = ptA;
			prv[i] = ptB-1;
			a[ptA++] = i;
		} 
		else{
			// mp[i] = ptB;
			prv[i] = ptB;
			b[ptB++] = i;
		}
	}

	for (int i=n*2;i;i--){
		if (s[i]=='A') nxt[i] = --ptA;
		else nxt[i] = ptA;
	}

	for (int i=1;i<=n;i++) sum[i] = sum[i-1] + nxt[b[i]];

	printf("%lld\n", solve(n, k));	
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |  scanf("%s", s+1);
      |  ~~~~~^~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -