제출 #429270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429270		Hegdahl	벽 칠하기 (APIO20_paint)	C++17	40 / 100	1198 ms	524292 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];
unordered_map<int, int> dp[mxN+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);

  vector<int> can;

  for (int i = n-1; i >= 0; --i) {
    for (int j : who[a[i]]) {
      auto it = dp[i+1].find((j+1)%m);
      int cnt = 1;
      if (it != dp[i+1].end()) cnt += it->second;
      dp[i].emplace(j, cnt);
      if (cnt >= m) can.push_back(i);
    }
  }
  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: 0 / 23
• Subtask 5: 0 / 37