Submission #643292

#	Time	Username	Problem	Language	Result	Execution time	Memory
643292		Kripton	Election (BOI18_election)	C++14	28 / 100	3060 ms	2400 KiB

election

#include <bits/stdc++.h>
using namespace std;
int mindr[500001];
int sumst[500001],sumdr[500002];
char s[500001];
int logue[500001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,i,j,q,a,b,minst;
    cin>>n>>ws>>(s+1)>>ws;
    for(i=1;i<=n;i++)
        sumst[i]=sumst[i-1]+(s[i]=='C')-(s[i]=='T');
    for(i=n;i>=1;i--)
        sumdr[i]=sumdr[i+1]+(s[i]=='C')-(s[i]=='T');
    cin>>q;
    while(q--)
    {
        cin>>a>>b;
        int ans=0;
        mindr[b+1]=1e9;
        for(i=b;i>=a;i--)
            mindr[i]=min(mindr[i+1],sumdr[i]);
        int minst=1e9;
        for(i=a;i<=b;i++)
        {
            minst=min(minst,sumst[i]);
            ans=max(ans,max(-(minst-sumst[a-1]),0)+max(-(mindr[i+1]-sumdr[b+1]),0));
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:12:13: warning: unused variable 'j' [-Wunused-variable]
   12 |     int n,i,j,q,a,b,minst;
      |             ^
election.cpp:12:21: warning: unused variable 'minst' [-Wunused-variable]
   12 |     int n,i,j,q,a,b,minst;
      |                     ^~~~~

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