Submission #315123

#	Time	Username	Problem	Language	Result	Execution time	Memory
315123		neihcr7j	Painting Walls (APIO20_paint)	C++14	40 / 100	1417 ms	524292 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"

#define oo 1000000000
#define maxn 100005

using namespace std;
typedef long long ll;

unordered_map < int, int > d[maxn];

int ok[maxn], las[maxn];
vector < int > g[maxn];

int minimumInstructions(int n, int m, int k, vector < int > c, vector < int > a, vector < vector < int > > b){

  for (int i = 0; i < m; ++i)
    for (auto x : b[i])
      g[x].push_back(i);

  for (int i = n - 1; i >= 0; --i)
    for (auto x : g[c[i]]) {
      d[i][x] = 1;

      if (i < n - 1 && d[i + 1].find((x + 1) % m) != d[i + 1].end())
        d[i][x] = max(d[i][x], d[i + 1][(x + 1) % m] + 1);

      if (d[i][x] >= m)
        ok[i + 1] = 1;
    }

  for (int i = 1; i <= n; ++i)
    las[i] = (ok[i] ? i : las[i - 1]);

  int x = 0, cnt = 0;

  while (x < n) {
    cnt++;
    int i = las[x + 1];

    if (i == 0 || i + m - 1 <= x) return -1;

    x = i + m - 1;
  }


  if (x != n)
    return -1;

  return cnt;

  return 0;
}

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