Submission #1175760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175760		JelalTkm	Painting Walls (APIO20_paint)	C++20	51 / 100	1575 ms	523460 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

// const int N = 1000 + 10;
// const int md = 1e9 + 7;
// const int INF = 5e6;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
  vector<vector<bool>> ok(n + 1, vector<bool> (m + 1));
  for (int i = 0; i < m; i++) {
    vector<bool> qw(k + 1);
    for (int j = 0; j < a[i]; j++)
      qw[b[i][j]] = 1;
    for (int j = 0; j < n; j++) {
      if (qw[c[j]] == 1)
        ok[j][i] = 1;
    }
  }

  vector<vector<int>> dp(n + 2, vector<int> (m + 2));
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j < m; j++) {
      if (ok[i][j]) {
        dp[i][j] = dp[i + 1][j + 1] + 1;
      }
    }
  }

  vector<int> v;
  for (int i = 0; i <= (n - m); i++) {
    for (int j = 0; j < m; j++) {
      if (j == 0) {
        if (dp[i][j] == m)
          v.push_back(i);
      } else {
        if (dp[i][j] == (m - j) && dp[i + (m - j)][0] >= j)
          v.push_back(i);
      }
    }
  }

  int ans = 0;
  int el = n - 1;
  while (el != -1) {
    int l = lower_bound(v.begin(), v.end(), (el - m + 1)) - v.begin();
    if (l == (int) v.size() || v[l] > el) {
      ans = -1;
      break;
    } else {
      ans++;
      el = v[l] - 1;
    }
  }

  return ans;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {

//     vector<int> c = {3, 3, 1, 3, 4, 4, 2, 2};
//     vector<vector<int>> b = {{0, 1, 2}, {2, 3}, {3, 4}};
//     vector<int> a = {3, 2, 2};

//     cout << minimumInstructions(8, 3, 5, c, a, b) << '\n';
//   }

//   return 0;
// }

• Subtask 1: 0 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 0 / 37