Submission #570095

#	Time	Username	Problem	Language	Result	Execution time	Memory
570095		Tsiannis	Election (BOI18_election)	C++14	0 / 100	3084 ms	212 KiB

election

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 10000009
string s; 
ll solve1(ll l,ll r,ll cc,ll ct)
{
    if (ct>cc)
    return INF;
    if (l>r)
    return 0;
    if (s[l]=='C')
    return solve1(l+1,r,cc+1,ct);
    return min(solve1(l+1,r,cc,ct)+1,solve1(l+1,r,cc,ct+1));
}
ll solve2(ll l,ll r,ll cc,ll ct)
{
    if (ct>cc)
    return INF;
    if (l>r)
    return 0;
    if (s[r]=='C')
    return solve2(l,r-1,cc+1,ct);
    return min(solve2(l,r-1,cc,ct)+1,solve2(l,r-1,cc,ct+1));
}

int main ()
{
   ll n; cin>>n;
   cin>>s;
   ll q; cin>>q;
   while(q--)
   {
       ll l,r;
       cin>>l>>r; l--;r--;
       ll ans1=solve1(l,r,0,0);
       ll ans2=solve2(l,r,0,0);
       cout<<max(ans1,ans2)<<endl;
  }
    return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18