답안 #965740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965740	2024-04-19T06:43:21 Z	Darren0724	벽 칠하기 (APIO20_paint)	C++17	0 / 100	1 ms	440 KB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
  	vector<int> dp(N+1,INF);
	vector<unordered_set<int>> s(M);
	for(int i=0;i<M;i++){
		for(int j:B[i]){
			s[i].insert(j);
		}
	}
	auto check=[&](int st,int now)->int {
		for(int i=st;i<st+M;i++){
			if(!s[now].count(C[i]))return 0;
			now++;
			now%=M;
		}
		return 1;
	};	
	deque<int> d;
	for(int i=0;i<M;i++){
		d.push_back(i);
	}
	dp[0]=0;
	for(int i=M;i<=N;i++){
		while(d.size()&&d.front()<i-M){
			d.pop_front();
		}
		int flag=0;
		for(int j=0;j<M;j++){
			flag|=check(i-M,j);
		}
		if(flag){
			dp[i]=dp[d.front()]+1;
		}
		while(d.size()&&dp[d.back()]>dp[i]){
			d.pop_back();
		}
		d.push_back(i);
	}
	return (dp[N]==INF?-1:dp[N]);

	return 0;
}

Subtask #1

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	440 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	440 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	440 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	440 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	440 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Halted	0 ms	0 KB	-