oj.uz

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();
}

Subtask #1
28.0 / 28.0

# 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

Subtask #2
0 / 54.0

# 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 -

Subtask #3
0 / 18.0

# 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 -