oj.uz

Submission #584319

# Submission time Handle Problem Language Result Execution time Memory
584319 2022-06-27T08:07:04 Z radal Election (BOI18_election) C++17
28 / 100
 4 ms 848 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse4,avx2")
//#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e3+20,mod = 1e9+7,inf = 1e9+10,base = 233;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int ps[N],cal[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    string s;
    cin >> n >> s >> q;
    s = '#'+s;
    rep(i,1,n+1){
        if (s[i] == 'C') ps[i] = ps[i-1]+1;
        else ps[i] = ps[i-1]-1;
    }
    while (q--){
        int l,r;
        cin >> l >> r;
        cal[l-1] = 0;
        int mx = 0;
        rep(i,l,r+1){
            mx = max(mx,ps[l-1]-ps[i]);
            cal[i] = mx;
        }
        int ans = 0;
        mx = 0;
        repr(i,r,l){
            mx = max(mx,-ps[r]+ps[i-1]);
            ans = max(ans,mx+cal[i-1]);
        }
        cout << ans << endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 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 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Runtime error 1 ms 848 KB Execution killed with signal 11
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 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Runtime error 1 ms 848 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -