Submission #429275

#	Time	Username	Problem	Language	Result	Execution time	Memory
429275		Hegdahl	Painting Walls (APIO20_paint)	C++17	63 / 100	1588 ms	134748 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];

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);

  vector<int> can;

  unordered_map<int, int> dp, ndp;

  for (int i = n-1; i >= 0; --i) {
    for (int j : who[a[i]]) {
      auto it = dp.find((j+1)%m);
      int cnt = 1;
      if (it != dp.end()) cnt += it->second;
      ndp.emplace(j, cnt);
      if (cnt >= m) can.push_back(i);
    }

    swap(dp, ndp);
    ndp.clear();
  }
  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: 0 / 37