Submission #856825

#	Time	Username	Problem	Language	Result	Execution time	Memory
856825		aymanrs	Election (BOI18_election)	C++14	28 / 100	3066 ms	2264 KiB

election

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n, q;
    cin >> n;
    string ST;
    cin >> ST;
    int p[n+2], s[n+2];
    p[0] = s[n+1] = 0;
    for(int i = 0;i < n;i++){
        if(ST[i]=='T') p[i+1]=s[i+1]=1;
        else p[i+1]=s[i+1]=-1;
        p[i+1]+=p[i];
    }
    for(int i = n;i >= 0;i--) s[i]+=s[i+1];
    cin >> q;
    while(q--){
        int l, r;cin >> l >> r;
        int ans = 0;
        int P[n+2], S[n+2];
        P[l-1]=S[r+1]=0;
        for(int i = l;i <= r;i++) P[i] = max(P[i-1], p[i]-p[l-1]);
        for(int i = r;i >= l;i--) S[i] = max(S[i+1], s[i]-s[r+1]);
        for(int i = l-1;i <= r;i++) ans = max(ans, P[i]+S[i+1]);
        cout << ans << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

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