Submission #947363

#	Time	Username	Problem	Language	Result	Execution time	Memory
947363		firewater	Chorus (JOI23_chorus)	C++14	0 / 100	2 ms	6488 KiB

chorus

#include<bits/stdc++.h>
#define ll long long
#define N 2024000
using namespace std;
ll n,k,x,now,l,r,a[N],sum[N],f[N],s[N];
char ss[N];
ll ask(ll k)
{
	for(ll i=1;i<=n;++i)
		f[i]=1000000000,s[i]=0;
    f[0]=0,s[0]=0;
	for(ll i=1;i<=n;++i)
		for(ll j=0;j<i;++j)
            if(make_pair(f[j]+sum[i]-sum[j]-j*(i-j)+k,s[j]+1)<make_pair(f[i],s[i])){
				f[i]=f[j]+sum[i]-sum[j]-j*(i-j)+k;
				s[i]=s[j]+1;
			}
	return s[n];
}
signed main()
{
	scanf("%lld%lld%s",&n,&k,ss+1);
	x=now=0;
	for(ll i=1;i<=n*2;++i){
		if(ss[i]=='A'){
			a[++x]=now;
			sum[x]=sum[x-1]+a[x];
		}
		else now++;
	}
	l=0;
	r=1000000000000ll;
	while(l<r){
		ll mid=l+r>>1;
		if(ask(mid)<=k)r=mid;
		else l=mid+1;
	}
    x=ask(l);
    printf("%lld\n",f[n]-l*k);
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:34:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   ll mid=l+r>>1;
      |          ~^~
chorus.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%lld%lld%s",&n,&k,ss+1);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13