제출 #387755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387755		AmShZ	벽 칠하기 (APIO20_paint)	C++11	51 / 100	435 ms	524292 KiB

paint

// khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <ll, ll>                                    pll;
typedef pair <pll,  ll>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 1e5 + 10;
const int xm = 5e4 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int dp[xn], last[xn], ptr, ans;
vector <int> vec[xn];
bitset <xn> bs[xm], ps[2][xm], tot;

int minimumInstructions(int n, int m, int k, vector <int> c, vector <int> a, vector <vector <int> > b){
	//cin >> n >> m >> k;
	//for (int i = 0; i < n; ++ i)
		//cin >> c[i], vec[c[i]].push_back(i);
	for (int i = 0; i < n; ++ i)
		vec[c[i]].push_back(i);
	//for (int i = 0; i < m; ++ i)
		//cin >> a[i];
	for (int i = 0; i < m; ++ i){
		for (int j = 0; j < a[i]; ++ j){
			int x = b[i][j];
			//cin >> x;
			//b[i].push_back(j);
			for (int ind : vec[x])
				bs[i][ind] = 1;
		}
	}
	for (int i = 0; i < m; ++ i){
		if (i)
			ps[0][i] = (ps[0][i - 1] & (bs[i] >> i));
		else
			ps[0][i] = bs[i];
	}
	for (int i = m - 1; i >= 0; -- i){
		if (i < m - 1)
			ps[1][i] = (bs[i] & (ps[1][i + 1] >> 1));
		else
			ps[1][i] = bs[i];
	}
	tot = ps[0][m - 1];
	for (int i = 1; i < m; ++ i)
		tot |= (ps[1][i] & (ps[0][i - 1] >> (m - i)));
	for (int i = 0; i < xn; ++ i){
		if (i)
			last[i] = last[i - 1];
		if (tot[i])
			last[i] = i;
	}
	if (!tot[0])
		return - 1;
	while (ptr + m < n){
		if (last[ptr + m] == ptr)
			return - 1;
		++ ans, ptr = last[ptr + m];
	}
	return ans + 1;
}


/*
int main(){
	InTheNameOfGod;

	
		
	return 0;
}
*/

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