Submission #856825

# Submission time Handle Problem Language Result Execution time Memory
856825 2023-10-04T16:50:18 Z aymanrs Election (BOI18_election) C++14
28 / 100
3000 ms 2264 KB
#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();
}
# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 8 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 8 ms 344 KB Output is correct
6 Execution timed out 3066 ms 2264 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 8 ms 344 KB Output is correct
6 Execution timed out 3066 ms 2264 KB Time limit exceeded
7 Halted 0 ms 0 KB -