Submission #429280

#	Time	Username	Problem	Language	Result	Execution time	Memory
429280		Hegdahl	Painting Walls (APIO20_paint)	C++17	100 / 100	810 ms	266892 KiB

paint

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

using namespace std;

const int mxN = 1e5;
const int mxK = 1e5;

vector<int> who[mxK+1];

int minimumInstructions(int n, int m, int k,
    vector<int> a, vector<int> g_sz, vector<vector<int>> g) {
  for (int i = 0; i < m; ++i)
    for (int j : g[i])
      who[j].push_back(i);

  a.push_back(k);

  vector<int> can, dp(m), ndp(m);

  for (int i = n-1; i >= 0; --i) {
    for (int j : who[a[i]]) {
      ndp[j] = dp[(j+1)%m] + 1;
      if (ndp[j] >= m) can.push_back(i);
    }

    swap(dp, ndp);

    for (int j : who[a[i+1]])
      ndp[j] = 0;
  }
  reverse(can.begin(), can.end());

  int i = 0, ans = 0;
  while (i < n) {
    auto it = upper_bound(can.begin(), can.end(), i);
    if (it == can.begin()) break;
    int ni = *(--it) + m;
    if (ni <= i) break;

    i = ni;
    ++ans;
  }

  if (i < n) return -1;

  return ans;
}

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