oj.uz

Submission #643292

# Submission time Handle Problem Language Result Execution time Memory
643292 2022-09-21T17:08:59 Z Kripton Election (BOI18_election) C++14
28 / 100
 3000 ms 2400 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Execution timed out 3060 ms 2400 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Execution timed out 3060 ms 2400 KB Time limit exceeded
7 Halted 0 ms 0 KB -