oj.uz

Submission #947363

# Submission time Handle Problem Language Result Execution time Memory
947363 2024-03-16T03:00:13 Z firewater Chorus (JOI23_chorus) C++14
0 / 100
 2 ms 6488 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -