Submission #522659

#	Time	Username	Problem	Language	Result	Execution time	Memory
522659		maomao90	Painting Walls (APIO20_paint)	C++17	28 / 100	1504 ms	8688 KiB

paint

#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) {
      |     ^~~

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