Submission #839702

#TimeUsernameProblemLanguageResultExecution timeMemory
839702sleepntsheepJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
13 ms10068 KiB
#include <cstdio> #include <cstring> #include <algorithm> #define N 200005 int n, k, f[N][4], far_pos[N][4], near_pos[N][4]; char s[N]; int cnt(int l, int r, int c) { return f[r][c] - f[l-1][c]; } int suf(int l, int c) { return f[n][c] - f[l-1][c]; } #define chmax(a, b) a = std::max(a, b) #define chmin(a, b) a = std::min(a, b) int ok(int m) { /* get O's from l to r */ /* * --JJJJOOOOOOOOOOOOOIIII- * l r */ int cost[4] = {0}; for (int r = 1; r <= n; ++r) { /* c[r][1] - c[l-1][1] == k * c[l-1][1] == c[r][1] - m */ if (f[r][2] < k) continue; int l = far_pos[f[r][2] - k][2] + 1; cost[2] = r-l+1-k; /* f[l-1][1] - c[l0-1][1] == m * c[l0-1][1] == f[l-1][1] - m */ if (f[l-1][1] < k) continue; int l0 = far_pos[f[l-1][1] - k][1] + 1; //if (l0 > 1e9) continue; cost[1] = l-1-l0+1-k; /* f[r1][3] - f[r][3] == k * f[r1][3] == k + f[r][3] */ int r1 = near_pos[k + f[r][3]][3]; if (r1 == -1) continue; cost[3] = r1-r-k; if (cost[1] + cost[2] + cost[3] <= m) { //printf("(%d@%d): %d %d - %d %d - %d %d\n",m,r,l0,l-1,l,r,r+1,r1); return 1; } } return 0; } int main() { scanf("%d%d%s", &n, &k, s + 1); for (int i = 1; i <= n; ++i) for (int j = 0; j < 3; ++j) if (j["JOI"] == s[i]) s[i] = j + 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= 3; ++j) f[i][j] = f[i-1][j]; ++f[i][s[i]]; } memset(far_pos, -1, sizeof far_pos); memset(near_pos, 63, sizeof near_pos); for (int i = 0; i <= n; ++i) for (int j = 1; j <= 3; ++j) far_pos[f[i][j]][j] = i; for (int i = n; i >= 1; --i) for (int j = 1; j <= 3; ++j) near_pos[f[i][j]][j] = i; //for (int i = 1; i <= n; ++i) for (int j = 1; j <= 3; ++j) chmax(far_pos[f[i][j]][j], far_pos[f[i][j]-1][j]); int l = 0, r = n - 1, z = -1; while (l <= r) { int m = (l+r)/2; if (ok(m)) r=m-1, z=m; else l=m+1; } printf("%d", z); return 0; }

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:56:96: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |     for (int i = 1; i <= n; ++i) { for (int j = 1; j <= 3; ++j) f[i][j] = f[i-1][j]; ++f[i][s[i]]; }
      |                                                                                             ~~~^
ho_t2.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d%s", &n, &k, s + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...