oj.uz

Submission #965929

# Submission time Handle Problem Language Result Execution time Memory
965929 2024-04-19T08:04:58 Z pcc Painting Walls (APIO20_paint) C++17
0 / 100
 4 ms 5064 KB 
#include "paint.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int mxn = 2e4+10;
const int mxm = 2020;
#define pii pair<int,int>
#define fs first
#define sc second
vector<int> col[mxn];
bitset<mxn> able;
int N,M,K;
int arr[mxn];
int dp[mxn][mxm];
int rp[mxn];

namespace DP{
	void GO(){
		for(int i = N-1;i>=0;i--){
			for(auto &j:col[arr[i]]){
				int nx = j+1;
				if(nx>=M)nx -= M;
				dp[i][j] = dp[i+1][nx]+1;
				if(dp[i][j]>=M)able[i] = true,rp[i] = i+M;
			}
		}
		return;
	}
}

namespace GETANS{
	struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
		int seg[mxn*4];
		void build(int now,int l,int r){
			if(l == r){
				seg[now] = rp[l];
				return;
			}
			build(ls,l,mid);
			build(rs,mid+1,r);
			seg[now] = max(seg[ls],seg[rs]);
		}
		int getval(int now,int l,int r,int s,int e){
			if(l>=s&&e>=r){
				return seg[now];
			}
			if(mid>=e)return getval(ls,l,mid,s,e);
			else if(mid<s)return getval(rs,mid+1,r,s,e);
			else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
		}
#undef ls
#undef mid
#undef rs
	};
	SEG seg;

	int GO(){
		for(int i = 1;i<=N;i++)rp[i] = max(rp[i],rp[i-1]);
		int now = 0,ans = 0;
		while(ans<=N&&now<N){
			now = rp[now];
			ans++;
		}
		return (ans>N?-1:ans);
	}
}

int minimumInstructions(
    int NN, int MM, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		for(int j = 0;j<A[i];j++)col[B[i][j]].push_back(i);
	}
	for(int i = 0;i<N;i++)arr[i] = C[i];
	DP::GO();
	//for(int i = 0;i<N;i++)cerr<<able[i];cerr<<endl;
	return GETANS::GO();
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5064 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Runtime error 4 ms 1372 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5064 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Runtime error 4 ms 1372 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5064 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Runtime error 4 ms 1372 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5064 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Runtime error 4 ms 1372 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5064 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Runtime error 4 ms 1372 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -