oj.uz

Submission #1091700

# Submission time Handle Problem Language Result Execution time Memory
1091700 2024-09-21T20:13:17 Z LucaLucaM Election (BOI18_election) C++17
82 / 100
 3000 ms 4192 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int INF = 1e9;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n;
  std::cin >> n;
  
  std::string s;
  std::cin >> s;
  s = '$' + s;

  std::vector<int> pref(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'C') {
      pref[i] = pref[i - 1] + 1;
    } else {
      pref[i] = pref[i - 1] - 1;
    }
  }

  int q;
  std::cin >> q;
  while (q--) {
    int l, r;
    std::cin >> l >> r;
    int answer = INF;
    int mini = INF;
    for (int i = l - 1; i <= r; i++) {
      mini = std::min(mini, pref[i]);
      answer = std::min(answer, -pref[i] + mini);
    }
    std::cout << pref[l - 1] - answer - pref[r] << '\n';
    
  }

  return 0;
}

Compilation message

election.cpp:5:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    5 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 860 ms 1924 KB Output is correct
7 Correct 2925 ms 1992 KB Output is correct
8 Correct 1664 ms 1960 KB Output is correct
9 Correct 420 ms 2004 KB Output is correct
10 Correct 852 ms 1792 KB Output is correct
11 Correct 1851 ms 1992 KB Output is correct
12 Correct 847 ms 2184 KB Output is correct
13 Correct 838 ms 2068 KB Output is correct
14 Correct 823 ms 2132 KB Output is correct
15 Correct 837 ms 1968 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 860 ms 1924 KB Output is correct
7 Correct 2925 ms 1992 KB Output is correct
8 Correct 1664 ms 1960 KB Output is correct
9 Correct 420 ms 2004 KB Output is correct
10 Correct 852 ms 1792 KB Output is correct
11 Correct 1851 ms 1992 KB Output is correct
12 Correct 847 ms 2184 KB Output is correct
13 Correct 838 ms 2068 KB Output is correct
14 Correct 823 ms 2132 KB Output is correct
15 Correct 837 ms 1968 KB Output is correct
16 Execution timed out 3033 ms 4192 KB Time limit exceeded
17 Halted 0 ms 0 KB -