oj.uz

Submission #570095

# Submission time Handle Problem Language Result Execution time Memory
570095 2022-05-28T14:26:38 Z Tsiannis Election (BOI18_election) C++14
0 / 100
 3000 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -