제출 #546012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546012		amunduzbaev	벽 칠하기 (APIO20_paint)	C++17	40 / 100	1599 ms	423884 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;

const int MAXN = 1e5 + 5;
struct ST{
	int tree[MAXN << 2];
	ST(){
		memset(tree, 63, sizeof tree);
	}
	
	void sett(int i, int v, int lx = 0, int rx = MAXN, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = MAXN, int x = 1){
		if(lx > r || rx < l) return 1e9;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
	vector<vector<int>> rev(k);
	for(int i=0;i<m;i++){
		for(int j=0;j<a[i];j++){
			rev[b[i][j]].push_back(i);
		}
	}
	
	vector<map<int, int>> dp(n + 1);
	vector<int> is(n+1);
	for(int i=0;i<n;i++){
		for(auto j : rev[c[i]]){
			if(dp[i].count((j + m - 1) % m)){
				dp[i+1][j] = dp[i][(j + m - 1) % m] + 1;
			} else {
				dp[i+1][j] = 1;
			}
			if(dp[i+1][j] >= m) is[i+1] = 1;
		}
	}
	
	vector<int> tp(n + 1, 1e9);
	tree.sett(0, 0);
	for(int i=1;i<=n;i++){
		if(is[i]){
			tp[i] = min(tp[i], tree.get(i - m, i - 1) + 1);
			tree.sett(i, tp[i]);
		}
	}
	
	//~ for(int i=1;i<=n;i++) cout<<tree.get(i, i)<<" ";
	//~ cout<<"\n";
	
	//~ for(int i=1;i<=n;i++) cout<<is[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=1;i<=n;i++) cout<<tp[i]<<" ";
	//~ cout<<"\n";
	
	if(tp[n] == 1e9) return -1;
	else return tp[n];
}

/*

8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

*/

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