Submission #1175790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175790		JelalTkm	Painting Walls (APIO20_paint)	C++20	51 / 100	211 ms	165420 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) {
  if (n <= 20000 && m <= 2000) {
    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;
  } else {
    vector<vector<int>> elems(k + 1, vector<int> ());
    for (int i = 0; i < n; i++)
      elems[c[i]].push_back(i);
    vector<int> dp(n + 1);
    vector<int> v;
    for (int j = m - 1; j >= 0; j--) {
      if (j == m - 1) {
        for (auto i: elems[b[j][0]]) {
          dp[i] = 1;
        }
      } else {
        for (auto i: elems[b[j][0]]) {
          if ((i + 1) < n && c[i + 1] == b[j + 1][0]) {
            dp[i] = dp[i + 1] + 1;
          }
        }
      }
    }

    for (int j = m - 1; j >= 0; j--) {
      if (j == m - 1) {
        for (auto i: elems[b[j][0]]) {
          if (j == 0) {
            if (dp[i] == m) {
              v.push_back(i);
            }
          } else {
            if (dp[i] == 1 && i + 1 < n && b[0][0] == c[i + 1] && dp[i + 1] >= (m - 1))
              v.push_back(i);
          }
        }
      } else {
        for (auto i: elems[b[j][0]]) {
          if ((i + 1) < n && c[i + 1] == b[j + 1][0]) {
            if (j == 0) {
              if (dp[i] == m)
                v.push_back(i);
            } else {
              if (dp[i] == (m - j) && i + (m - j) < n && c[i + (m - j)] == b[0][0] && dp[i + (m - j)] >= j)
                v.push_back(i);
            }
          }
        }
      }
    }

    sort(v.begin(), v.end());

    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 = {1, 2, 3};
//     vector<vector<int>> b = {{1}, {2}, {3}};
//     vector<int> a = {1, 1, 1};

//     cout << minimumInstructions(3, 3, 4, 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