Submission #208924

#	Time	Username	Problem	Language	Result	Execution time	Memory
208924		eriksuenderhauf	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	14 ms	3704 KiB

ho_t2

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(x, a) for (const auto& x: a)
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
char s[N];
int nx[N][3];

int main() {
  int n, k; scanf("%d %d", &n, &k);
  scanf("%s", s);
  for (int i = 0; i < 3; i++)
    nx[n+1][i] = nx[n][i] = n+1;
  deque<int> pq[3];
  for (int i = n-1; ~i; i--) {
    if (s[i] == 'I')
      pq[2].push_front(i);
    if (s[i] == 'O')
      pq[1].push_front(i);
    if (s[i] == 'J')
      pq[0].push_front(i);
    for (int j = 0; j < 3; j++) {
      nx[i][j] = nx[i+1][j];
      while (sz(pq[j]) > k)
        pq[j].pop_back();
      if (sz(pq[j]) == k)
        nx[i][j] = pq[j].back() + 1;
    }
  }
  int ans = 2*N;
  for (int i = 0; i < n; i++) {
    if (nx[nx[nx[i][0]][1]][2] > n)
      continue;
    ans = min(ans, nx[nx[nx[i][0]][1]][2] - i - 3*k);
  }
  if (ans == 2*N)
    ans = -1;
  printf("%d\n", ans);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int n, k; scanf("%d %d", &n, &k);
             ~~~~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87