Submission #874377

#	Time	Username	Problem	Language	Result	Execution time	Memory
874377		mgl_diamond	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	4 ms	2020 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 1e5+5;
int n, k;
char c[N];
string s;
vector<int> pos[3];

int main() {
  setIO();

  cin >> n >> k >> s;
  foru(i, 0, n-1) {
    if (s[i] == 'J') pos[0].push_back(i);
    else if (s[i] == 'O') pos[1].push_back(i);
    else pos[2].push_back(i);
  }

  if (sz(pos[0]) < k || sz(pos[1]) < k || sz(pos[1]) < k) {
    cout << -1;
    return 0;
  }

  int x = -1, y = 0, z = sz(pos[2]), ans = n+1;
  
  foru(y, 0, sz(pos[1])-k) {
    while (x+1 < sz(pos[0]) && pos[0][x+1] < pos[1][y])
      ++x;
    
    while (z-1 >= 0 && pos[2][z-1] > pos[1][y+k-1])
      --z;
    while (z < sz(pos[2]) && pos[2][z] < pos[1][y+k-1])
      ++z;
    
    if (x-k+1 >= 0 && z+k-1 < sz(pos[2])) {
      int ff = (pos[0][x] - pos[0][x-k+1] + 1 - k);
      int ss = (pos[1][y+k-1] - pos[1][y] + 1 - k);
      int th = (pos[2][z+k-1] - pos[2][z] + 1 - k);
      minimize(ans, ff + ss + th + pos[1][y] - pos[0][x] - 1 + pos[2][z] - pos[1][y+k-1] - 1);
    }
  }

  cout << (ans == n+1 ? -1 : ans);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:48:15: warning: unused variable 'y' [-Wunused-variable]
   48 |   int x = -1, y = 0, z = sz(pos[2]), ans = n+1;
      |               ^
ho_t2.cpp: In function 'void setIO()':
ho_t2.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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