oj.uz

Submission #875827

# Submission time Handle Problem Language Result Execution time Memory
875827 2023-11-20T15:04:21 Z 1075508020060209tc Election (BOI18_election) C++14
28 / 100
 3000 ms 9816 KB 
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int Q;
string s;
int ar[500005];
int ps[500005];
int sf[500005];
int nn;

void solve(){
int ret=0;
int lps=0;
for(int i=1;i<=nn;i++){
    ret=max(ret,max(0ll,sf[i])+lps);
lps=max(lps,ps[i]);
}
cout<<ret<<"\n";
}

signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='T'){
            ar[i]=1;
        }else{
            ar[i]=-1;
        }
    }
    cin>>Q;
    while(Q--){
        int l;int r;
        cin>>l>>r;
        nn=r-l+1;
        for(int i=l;i<=r;i++){
            ps[i-l+1]=ar[i];
            ps[i-l+1]+=ps[i-l+1-1];
        }
        sf[nn+1]=0;
        for(int i=r;i>=l;i--){
            sf[i-l+1]=ar[i];
            sf[i-l+1]+=sf[i-l+1+1];
        }
        /*
        for(int i=1;i<=nn;i++){
            cout<<ps[i]<<" ";
        }cout<<"\n";
        for(int i=1;i<=nn;i++){
            cout<<sf[i]<<" ";
        }cout<<"\n";*/
        solve();
    }

}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4440 KB Output is correct
2 Correct 9 ms 4696 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 8 ms 4444 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4440 KB Output is correct
2 Correct 9 ms 4696 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 8 ms 4444 KB Output is correct
6 Execution timed out 3037 ms 9816 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4440 KB Output is correct
2 Correct 9 ms 4696 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 8 ms 4444 KB Output is correct
6 Execution timed out 3037 ms 9816 KB Time limit exceeded
7 Halted 0 ms 0 KB -