Submission #522659

#TimeUsernameProblemLanguageResultExecution timeMemory
522659maomao90Painting Walls (APIO20_paint)C++17
28 / 100
1504 ms8688 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define REP(i, j, k) for (int i = j; i < k; i++) #define RREP(i, j, k) for (int i = j; i >= k; i--) template <class T> inline bool mxto(T &a, T b) {return a < b ? a = b, 1 : 0;} template <class T> inline bool mnto(T &a, T b) {return a > b ? a = b, 1 : 0;} typedef long long ll; #define FI first #define SE second #define MP make_pair typedef pair<int, int> ii; #define pb push_back #define ALL(x) x.begin(), x.end() typedef vector<int> vi; #ifndef DEBUG #define cerr if (0) cerr #endif #define MAXN 100005 #define INF 1000000005 int n, m, k; vi c, a; vector<vi> b; vi mp[MAXN]; int dp[MAXN], pdp[MAXN]; int minimumInstructions(int n, int m, int k, vi c, vi a, vector<vi> b) { ::n = n; ::m = m; ::k = k; ::c = c; ::a = a; ::b = b; REP (i, 0, m) { for (int j : b[i]) { mp[j].pb(i); } } REP (i, 0, m) { dp[i] = pdp[i] = -INF; } vi rng; RREP (i, n - 1, 0) { if (i + 2 < n) { for (int j : mp[c[i + 2]]) { dp[j] = -INF; } } assert(mp[c[i]].size() <= 633); int mx = -INF; for (int j : mp[c[i]]) { dp[j] = i; int k = j + 1 == m ? 0 : j + 1; if (i != n - 1 && pdp[k] != -INF) { dp[j] = pdp[k]; } mxto(mx, dp[j]); } if (mx - i + 1 >= m) { rng.pb(i); } swap(dp, pdp); } reverse(ALL(rng)); if (rng.empty() || rng[0] != 0 || rng.back() != n - m) { return -1; } if (rng.size() == 1) { return 1; } int r = m; int ans = 2; REP (i, 1, rng.size() - 1) { if (rng[i] > r) { return -1; } if (rng[i + 1] > r) { r = rng[i] + m; ans++; } } if (n - m > r) return -1; return ans; }

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, vi, vi, std::vector<std::vector<int> >)':
paint.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define REP(i, j, k) for (int i = j; i < k; i++)
......
   76 |     REP (i, 1, rng.size() - 1) {
      |          ~~~~~~~~~~~~~~~~~~~~           
paint.cpp:76:5: note: in expansion of macro 'REP'
   76 |     REP (i, 1, rng.size() - 1) {
      |     ^~~
#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...