제출 #685530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685530		Nursik	Painting Walls (APIO20_paint)	C++14	100 / 100	618 ms	15052 KiB

paint

#include "paint.h"

#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <cmath>

using namespace std;

#define pb push_back
#define f first
#define s second
#define ll long long

const int maxn = 1e5 + 200, maxm = 1e3 + 200, inf = 1e9;

int n, m, k;
int dp[maxn], is[maxn], lst[maxn], prv[maxn], cur[maxn], mx[maxn], t[maxn * 4];
vector<int> g[maxn];
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    n = N, m = M, k = K;
    for (int j = 0; j < m; ++j){
        prv[j] = -inf;
        cur[j] = -inf;
    }
    for (int i = 0; i < m; ++i){
        for (auto it : B[i]){
            g[it].pb(i);
        }
    }
    for (int i = n - 1; i >= 0; --i){
        mx[i] = -inf;
        for (auto x : g[C[i]]){
            int nx = (x + 1) % m;
            if (i + 1 < n && prv[nx] != -inf){
                cur[x] = min(m, prv[nx] + 1);
            }
            cur[x] = max(cur[x], 1);
            mx[i] = max(mx[i], cur[x]);
        }
        if (i + 1 < n){
            for (auto x : g[C[i + 1]]){
                prv[x] = -inf;
            }
        }
        for (auto x : g[C[i]]){
            prv[x] = cur[x];
            cur[x] = -1;
        }
    }
  //  for (int i = 0; 
    if (mx[0] >= m){
        int ans = 1;
        int pos = m - 1;
        int uk = 1;
        while (pos != n - 1){
            int go = -1;
            while (uk <= pos + 1){
                if (mx[uk] >= m){
                    go = uk + mx[uk] - 1;
                }
                uk += 1;
            }
            if (go == -1){
                return -1;
            }
            ans += 1;
            pos = go;
        }
        return ans;
    }
    else{
        return -1;
    }
}

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