Submission #855852

#	Time	Username	Problem	Language	Result	Execution time	Memory
855852		NeroZein	Election (BOI18_election)	C++17	0 / 100	6 ms	344 KiB

election

#include "bits/stdc++.h"
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  string s;
  cin >> s;
  int q;
  cin >> q;
  auto construct = [&](int l, int r) {
    vector<int> ret;
    for (int i = l; i <= r; ++i) {
      int j = i;
      while (j + 1 <= r && s[j + 1] == s[j]) {
        j++; 
      }
      ret.push_back((j - i + 1) * (s[j] == 'C' ? 1 : -1));
      i = j;       
    }
    return ret;
  }; 
  auto solve = [&](vector<int> v) {
    int ps = 0; 
    vector<int> mx(v.size()); 
    for (int i = 0; i < (int) v.size(); ++i) {
      ps += v[i];
      if (ps < 0) {
        mx[i] = max(mx[i], -ps); 
        ps = 0; 
      }
    }
    ps = 0; 
    for (int i = (int) v.size() - 1; i >= 0; --i) {
      ps += v[i];
      if (ps < 0) {
        mx[i] = max(mx[i], -ps);
        ps = 0; 
      }
    }
    return accumulate(mx.begin(), mx.end(), 0);
  };
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    vector<int> v = construct(l, r); 
    cout << solve(v) << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18