답안 #395257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395257	2021-04-28T04:15:09 Z	khangal	벽 칠하기 (APIO20_paint)	C++14	12 / 100	135 ms	109572 KB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
#define pb push_back
#define ff first
#define ss second
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,mid,mn,T,sum,c[1234567],h1,h2,x,y,z,l,r,cnt,cnt1,ans;
vector<ll> vec[1234567];
bool ok[1234567],ok1;	
map<ll,ll> mp[1234567];
int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	for(int i=0;i<M;i++){
		for(auto u:B[i]) vec[u].pb(i);
	}
	for(int i=N-1;i>=0;i--){
		for(auto u:vec[C[i]]){
			mp[i][u]=1;
			//i dah toog u unguur ehlehed segment iin urtiig olno
			if(mp[i+1][(u+1)%M]>0 && i < N-1){
				mp[i][u]=max(mp[i][u],mp[i+1][(u+1)%M]+1);
			}
			if(mp[i][u] >= M){
				ok[i]=1;
				//i r tseg dres ehlej bolno
			}
		}
	}
	ll segnum=0;
	for(int i=0;i<N;i++)c[i]=-1;
	for(int i=0;i<N;i++){
		//buh tsegiig ali tsegees ehleh ve gdgig olno
		if(ok[i]==1)segnum=i;
		c[i]=segnum;
	}
	/*for(int i=0;i<N;i++){
		cout<<c[i]<<" ";
	}
	cout<<'\n';*/
	int i=0;
	while(i<N){
		//cout<<i<<" ";
		ans++;
		x=c[i];
		// x ees ehlene
		if(x==-1 || x+M <= i){
			return -1;
		}
		i = x+M;
		// i deer duusna
	}
	//cout<<'\n';
	if(i<n)return -1;
	else return ans;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	87192 KB	Output is correct
2	Correct	56 ms	87280 KB	Output is correct
3	Correct	54 ms	87216 KB	Output is correct
4	Correct	54 ms	87236 KB	Output is correct
5	Correct	55 ms	87268 KB	Output is correct
6	Correct	54 ms	87176 KB	Output is correct
7	Correct	53 ms	87212 KB	Output is correct
8	Correct	56 ms	87368 KB	Output is correct
9	Correct	54 ms	87244 KB	Output is correct
10	Correct	56 ms	87284 KB	Output is correct
11	Correct	58 ms	87232 KB	Output is correct
12	Correct	54 ms	87228 KB	Output is correct
13	Correct	55 ms	87220 KB	Output is correct
14	Correct	58 ms	87320 KB	Output is correct
15	Correct	55 ms	87252 KB	Output is correct
16	Correct	56 ms	87328 KB	Output is correct
17	Correct	53 ms	87340 KB	Output is correct
18	Correct	56 ms	87236 KB	Output is correct
19	Correct	56 ms	87256 KB	Output is correct
20	Correct	57 ms	87260 KB	Output is correct
21	Correct	55 ms	87268 KB	Output is correct
22	Correct	78 ms	91204 KB	Output is correct
23	Correct	77 ms	91204 KB	Output is correct
24	Correct	78 ms	91224 KB	Output is correct
25	Correct	58 ms	88872 KB	Output is correct
26	Correct	59 ms	88812 KB	Output is correct
27	Correct	61 ms	89360 KB	Output is correct
28	Correct	60 ms	89596 KB	Output is correct
29	Correct	61 ms	89780 KB	Output is correct
30	Correct	62 ms	89744 KB	Output is correct
31	Correct	67 ms	89872 KB	Output is correct
32	Correct	66 ms	89668 KB	Output is correct
33	Correct	66 ms	89668 KB	Output is correct
34	Correct	67 ms	89688 KB	Output is correct
35	Correct	67 ms	89680 KB	Output is correct
36	Correct	66 ms	89764 KB	Output is correct
37	Correct	88 ms	94088 KB	Output is correct
38	Correct	88 ms	94112 KB	Output is correct
39	Correct	87 ms	94156 KB	Output is correct
40	Correct	75 ms	94584 KB	Output is correct
41	Correct	66 ms	91748 KB	Output is correct
42	Correct	80 ms	98160 KB	Output is correct
43	Correct	73 ms	95168 KB	Output is correct
44	Correct	72 ms	94788 KB	Output is correct
45	Correct	87 ms	100164 KB	Output is correct
46	Correct	112 ms	102372 KB	Output is correct
47	Correct	89 ms	96168 KB	Output is correct
48	Correct	94 ms	98656 KB	Output is correct
49	Correct	110 ms	102928 KB	Output is correct
50	Correct	120 ms	104036 KB	Output is correct
51	Correct	110 ms	102084 KB	Output is correct
52	Correct	77 ms	95092 KB	Output is correct
53	Correct	78 ms	95152 KB	Output is correct
54	Correct	81 ms	98216 KB	Output is correct
55	Correct	82 ms	99372 KB	Output is correct
56	Correct	84 ms	99824 KB	Output is correct
57	Correct	83 ms	100164 KB	Output is correct
58	Correct	119 ms	104092 KB	Output is correct
59	Correct	121 ms	104140 KB	Output is correct
60	Correct	124 ms	104168 KB	Output is correct
61	Correct	121 ms	104092 KB	Output is correct
62	Correct	119 ms	104112 KB	Output is correct
63	Correct	120 ms	104088 KB	Output is correct
64	Correct	135 ms	109572 KB	Output is correct
65	Correct	134 ms	109572 KB	Output is correct
66	Correct	134 ms	109508 KB	Output is correct

Subtask #2
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	87192 KB	Output is correct
2	Correct	56 ms	87280 KB	Output is correct
3	Correct	54 ms	87216 KB	Output is correct
4	Correct	54 ms	87236 KB	Output is correct
5	Correct	55 ms	87268 KB	Output is correct
6	Correct	54 ms	87176 KB	Output is correct
7	Correct	53 ms	87212 KB	Output is correct
8	Correct	56 ms	87368 KB	Output is correct
9	Correct	54 ms	87244 KB	Output is correct
10	Correct	56 ms	87284 KB	Output is correct
11	Correct	58 ms	87232 KB	Output is correct
12	Correct	54 ms	87228 KB	Output is correct
13	Correct	55 ms	87220 KB	Output is correct
14	Correct	58 ms	87320 KB	Output is correct
15	Correct	55 ms	87252 KB	Output is correct
16	Correct	56 ms	87328 KB	Output is correct
17	Correct	53 ms	87340 KB	Output is correct
18	Correct	56 ms	87236 KB	Output is correct
19	Correct	56 ms	87256 KB	Output is correct
20	Correct	57 ms	87260 KB	Output is correct
21	Correct	55 ms	87268 KB	Output is correct
22	Correct	54 ms	87164 KB	Output is correct
23	Correct	54 ms	87212 KB	Output is correct
24	Correct	56 ms	87236 KB	Output is correct
25	Incorrect	55 ms	87224 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	87164 KB	Output is correct
2	Correct	54 ms	87212 KB	Output is correct
3	Correct	55 ms	87192 KB	Output is correct
4	Correct	56 ms	87280 KB	Output is correct
5	Correct	54 ms	87216 KB	Output is correct
6	Correct	54 ms	87236 KB	Output is correct
7	Correct	55 ms	87268 KB	Output is correct
8	Correct	54 ms	87176 KB	Output is correct
9	Correct	53 ms	87212 KB	Output is correct
10	Correct	56 ms	87368 KB	Output is correct
11	Correct	54 ms	87244 KB	Output is correct
12	Correct	56 ms	87284 KB	Output is correct
13	Correct	58 ms	87232 KB	Output is correct
14	Correct	54 ms	87228 KB	Output is correct
15	Correct	55 ms	87220 KB	Output is correct
16	Correct	58 ms	87320 KB	Output is correct
17	Correct	55 ms	87252 KB	Output is correct
18	Correct	56 ms	87328 KB	Output is correct
19	Correct	53 ms	87340 KB	Output is correct
20	Correct	56 ms	87236 KB	Output is correct
21	Correct	56 ms	87256 KB	Output is correct
22	Correct	57 ms	87260 KB	Output is correct
23	Correct	55 ms	87268 KB	Output is correct
24	Correct	78 ms	91204 KB	Output is correct
25	Correct	77 ms	91204 KB	Output is correct
26	Correct	78 ms	91224 KB	Output is correct
27	Correct	56 ms	87236 KB	Output is correct
28	Incorrect	55 ms	87224 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	87164 KB	Output is correct
2	Correct	54 ms	87212 KB	Output is correct
3	Correct	55 ms	87192 KB	Output is correct
4	Correct	56 ms	87280 KB	Output is correct
5	Correct	54 ms	87216 KB	Output is correct
6	Correct	54 ms	87236 KB	Output is correct
7	Correct	55 ms	87268 KB	Output is correct
8	Correct	54 ms	87176 KB	Output is correct
9	Correct	53 ms	87212 KB	Output is correct
10	Correct	56 ms	87368 KB	Output is correct
11	Correct	54 ms	87244 KB	Output is correct
12	Correct	56 ms	87284 KB	Output is correct
13	Correct	58 ms	87232 KB	Output is correct
14	Correct	54 ms	87228 KB	Output is correct
15	Correct	55 ms	87220 KB	Output is correct
16	Correct	58 ms	87320 KB	Output is correct
17	Correct	55 ms	87252 KB	Output is correct
18	Correct	56 ms	87328 KB	Output is correct
19	Correct	53 ms	87340 KB	Output is correct
20	Correct	56 ms	87236 KB	Output is correct
21	Correct	56 ms	87256 KB	Output is correct
22	Correct	57 ms	87260 KB	Output is correct
23	Correct	55 ms	87268 KB	Output is correct
24	Correct	78 ms	91204 KB	Output is correct
25	Correct	77 ms	91204 KB	Output is correct
26	Correct	78 ms	91224 KB	Output is correct
27	Correct	58 ms	88872 KB	Output is correct
28	Correct	59 ms	88812 KB	Output is correct
29	Correct	61 ms	89360 KB	Output is correct
30	Correct	60 ms	89596 KB	Output is correct
31	Correct	61 ms	89780 KB	Output is correct
32	Correct	62 ms	89744 KB	Output is correct
33	Correct	67 ms	89872 KB	Output is correct
34	Correct	66 ms	89668 KB	Output is correct
35	Correct	66 ms	89668 KB	Output is correct
36	Correct	67 ms	89688 KB	Output is correct
37	Correct	67 ms	89680 KB	Output is correct
38	Correct	66 ms	89764 KB	Output is correct
39	Correct	88 ms	94088 KB	Output is correct
40	Correct	88 ms	94112 KB	Output is correct
41	Correct	87 ms	94156 KB	Output is correct
42	Correct	56 ms	87236 KB	Output is correct
43	Incorrect	55 ms	87224 KB	Output isn't correct
44	Halted	0 ms	0 KB	-

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	87164 KB	Output is correct
2	Correct	54 ms	87212 KB	Output is correct
3	Correct	55 ms	87192 KB	Output is correct
4	Correct	56 ms	87280 KB	Output is correct
5	Correct	54 ms	87216 KB	Output is correct
6	Correct	54 ms	87236 KB	Output is correct
7	Correct	55 ms	87268 KB	Output is correct
8	Correct	54 ms	87176 KB	Output is correct
9	Correct	53 ms	87212 KB	Output is correct
10	Correct	56 ms	87368 KB	Output is correct
11	Correct	54 ms	87244 KB	Output is correct
12	Correct	56 ms	87284 KB	Output is correct
13	Correct	58 ms	87232 KB	Output is correct
14	Correct	54 ms	87228 KB	Output is correct
15	Correct	55 ms	87220 KB	Output is correct
16	Correct	58 ms	87320 KB	Output is correct
17	Correct	55 ms	87252 KB	Output is correct
18	Correct	56 ms	87328 KB	Output is correct
19	Correct	53 ms	87340 KB	Output is correct
20	Correct	56 ms	87236 KB	Output is correct
21	Correct	56 ms	87256 KB	Output is correct
22	Correct	57 ms	87260 KB	Output is correct
23	Correct	55 ms	87268 KB	Output is correct
24	Correct	78 ms	91204 KB	Output is correct
25	Correct	77 ms	91204 KB	Output is correct
26	Correct	78 ms	91224 KB	Output is correct
27	Correct	58 ms	88872 KB	Output is correct
28	Correct	59 ms	88812 KB	Output is correct
29	Correct	61 ms	89360 KB	Output is correct
30	Correct	60 ms	89596 KB	Output is correct
31	Correct	61 ms	89780 KB	Output is correct
32	Correct	62 ms	89744 KB	Output is correct
33	Correct	67 ms	89872 KB	Output is correct
34	Correct	66 ms	89668 KB	Output is correct
35	Correct	66 ms	89668 KB	Output is correct
36	Correct	67 ms	89688 KB	Output is correct
37	Correct	67 ms	89680 KB	Output is correct
38	Correct	66 ms	89764 KB	Output is correct
39	Correct	88 ms	94088 KB	Output is correct
40	Correct	88 ms	94112 KB	Output is correct
41	Correct	87 ms	94156 KB	Output is correct
42	Correct	75 ms	94584 KB	Output is correct
43	Correct	66 ms	91748 KB	Output is correct
44	Correct	80 ms	98160 KB	Output is correct
45	Correct	73 ms	95168 KB	Output is correct
46	Correct	72 ms	94788 KB	Output is correct
47	Correct	87 ms	100164 KB	Output is correct
48	Correct	112 ms	102372 KB	Output is correct
49	Correct	89 ms	96168 KB	Output is correct
50	Correct	94 ms	98656 KB	Output is correct
51	Correct	110 ms	102928 KB	Output is correct
52	Correct	120 ms	104036 KB	Output is correct
53	Correct	110 ms	102084 KB	Output is correct
54	Correct	77 ms	95092 KB	Output is correct
55	Correct	78 ms	95152 KB	Output is correct
56	Correct	81 ms	98216 KB	Output is correct
57	Correct	82 ms	99372 KB	Output is correct
58	Correct	84 ms	99824 KB	Output is correct
59	Correct	83 ms	100164 KB	Output is correct
60	Correct	119 ms	104092 KB	Output is correct
61	Correct	121 ms	104140 KB	Output is correct
62	Correct	124 ms	104168 KB	Output is correct
63	Correct	121 ms	104092 KB	Output is correct
64	Correct	119 ms	104112 KB	Output is correct
65	Correct	120 ms	104088 KB	Output is correct
66	Correct	135 ms	109572 KB	Output is correct
67	Correct	134 ms	109572 KB	Output is correct
68	Correct	134 ms	109508 KB	Output is correct
69	Correct	56 ms	87236 KB	Output is correct
70	Incorrect	55 ms	87224 KB	Output isn't correct
71	Halted	0 ms	0 KB	-

답안 #395257

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 15.0

Subtask #3 0 / 13.0

Subtask #4 0 / 23.0

Subtask #5 0 / 37.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 15.0

Subtask #3
0 / 13.0

Subtask #4
0 / 23.0

Subtask #5
0 / 37.0