제출 #947365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947365		firewater	Chorus (JOI23_chorus)	C++14	61 / 100	7058 ms	11356 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],v[N],f[N],s[N];
char ss[N];
ll ask(ll k)
{
	for(ll i=1;i<=n;++i)
		f[i]=1000000000000ll,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[v[j+1]]-j*(i-v[j+1])+k,s[j]+1)<make_pair(f[i],s[i])){
				f[i]=f[j]+sum[i]-sum[v[j+1]]-j*(i-v[j+1])+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++,v[now]=max(now-1,x);
	}
	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);
    return 0;
}

컴파일 시 표준 에러 (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: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13