Submission #437561

#	Time	Username	Problem	Language	Result	Execution time	Memory
437561		Sohsoh84	Painting Walls (APIO20_paint)	C++14	100 / 100	450 ms	47984 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 2e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

int n, m, k, C[MAXN];
vector<int> L[MAXN];
pair<int, int> W[2][MAXN];
ll dp[MAXN];

int minimumInstructions(
	int N, int M, int K, std::vector<int> tC,
	std::vector<int> tA, std::vector<std::vector<int>> tB) {
	
	n = N, m = M, k = K;
	for (int i = 0; i < n; i++) C[i] = tC[i];
	for (int i = 0; i < m; i++)
		for (int e : tB[i])
		       L[e].push_back(i);	
	
	set<pll> dp_st;
	dp_st.insert({0, n});
	for (int i = 0; i < MAXN; i++) W[n & 1][i] = {0, n};

	for (int i = n - 1; i >= 0; i--) {
		int ind = i & 1;
		dp[i] = INF;
					
		dp_st.erase({dp[i + m + 1], i + m + 1});
		ll t = dp_st.begin() -> X;

		for (int p : L[C[i]]) {
			int l = 1, r = (p + 1) % m;
			if (W[1 - ind][r].Y == i + 1) l = 1 + W[1 - ind][r].X;
			if (l >= m) dp[i] = t + 1;
			W[ind][p] = {l, i};
		}
		
		dp_st.insert({dp[i], i});
	}

	if (dp[0] >= INF) return -1;
	return dp[0];
}

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