Submission #979753

#TimeUsernameProblemLanguageResultExecution timeMemory
979753vjudge1Painting Walls (APIO20_paint)C++17
100 / 100
1149 ms506724 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; using ll = long long; int n, m; const int N = 100100; const int K = 100100; bool able[N] = {}; int to[N] = {}; vector<int> inst[K]; vector<vector<int>> g; vector<vector<int>> f; int minimumInstructions( int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) { n = N, m = M; for (int i = 0; i < m; i++) { for (int x : B[i]) { inst[x].push_back(i); } } for (int i = 0; i < K; i++) sort(inst[i].begin(), inst[i].end()); g.resize(n + 1); for (int i = 0; i < n; i++) g[i] = inst[C[i]]; auto get = [&](int i, int j) -> int { int x = lower_bound(g[i].begin(), g[i].end(), j) - g[i].begin(); if (x != (int)g[i].size() && g[i][x] == j) return f[i][x]; return 0; }; f.resize(n + 1); for (int i = n - 1; i >= 0; i--) { f[i].resize((int)g[i].size()); for (int j = 0; j < (int)f[i].size(); j++) { f[i][j] = 1 + get(i + 1, (g[i][j] + 1) % m); } } for (int i = 0; i <= n - m; i++) { for (int c : f[i]) if (c >= m) able[i] = true; } if (!able[0]) return -1; int nxt = 0; for (int i = 0; i < n; i++) { if (able[i]) nxt = (i + m); to[i] = max(nxt, i); } int res = 1e9; int x = 0, ans = 0; while (x < n && x != to[x]) { ans++; x = to[x]; } if (x == n) return ans; return -1; }

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:73:9: warning: unused variable 'res' [-Wunused-variable]
   73 |     int res = 1e9;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...