oj.uz

Submission #315118

# Submission time Handle Problem Language Result Execution time Memory
315118 2020-10-22T02:44:01 Z neihcr7j Painting Walls (APIO20_paint) C++14
0 / 100
 1500 ms 8320 KB 
#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 < x) return -1;

    x = i + m - 1;
  }


  if (x != n)
    return -1;

  return cnt;

  return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8320 KB Output is correct
3 Execution timed out 1592 ms 8192 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8192 KB Output is correct
3 Correct 6 ms 8192 KB Output is correct
4 Correct 6 ms 8320 KB Output is correct
5 Execution timed out 1592 ms 8192 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8192 KB Output is correct
3 Correct 6 ms 8192 KB Output is correct
4 Correct 6 ms 8320 KB Output is correct
5 Execution timed out 1592 ms 8192 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8192 KB Output is correct
3 Correct 6 ms 8192 KB Output is correct
4 Correct 6 ms 8320 KB Output is correct
5 Execution timed out 1592 ms 8192 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8192 KB Output is correct
3 Correct 6 ms 8192 KB Output is correct
4 Correct 6 ms 8320 KB Output is correct
5 Execution timed out 1592 ms 8192 KB Time limit exceeded
6 Halted 0 ms 0 KB -