oj.uz

Submission #787242

# Submission time Handle Problem Language Result Execution time Memory
787242 2023-07-19T00:18:39 Z tvladm2009 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9;

int cnt[3];
int n, k;
string s;

int getcost(int x) {
  cnt[0] = cnt[1] = cnt[2] = 0;
  int cost = 0;
  while (x <= n) {
    int where = -1;
    if (s[x] == 'J') {
      where = 0;
    } else if (s[x] == 'O') {
      where = 1;
    } else {
      where = 2;
    }
    int mn = INF;
    for (int i = where - 1; i >= 0; i--) {
      mn = min(mn, cnt[i]);
    }
    if (mn < k || cnt[where] == k) {
      cost++;
    } else {
      cnt[where]++;
    }
    if (cnt[0] == k && cnt[1] == k && cnt[2] == k) {
      break;
    }
    x++;
  }
  if (cnt[0] != k || cnt[1] != k || cnt[2] != k) {
    cost = INF;
  }
  return cost;
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> k >> s;
  s = "#" + s;
  int sol = INF;
  int changes = 0;
  for (int i = 1; i <= n; i++) {
    if (getcost(i) == INF) {
      break;
    }
    if (i == 1) {
      continue;
    }
    changes += (getcost(i) > getcost(i - 1));
    sol = min(sol, getcost(i));
  }
  assert(changes <= 1);
  if (sol == INF) {
    cout << "-1";
    return 0;
  }
  cout << sol << "\n";
  return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -