Submission #576563

#	Time	Username	Problem	Language	Result	Execution time	Memory
576563		sare	Painting Walls (APIO20_paint)	C++17	100 / 100	508 ms	13184 KiB

paint

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#include "paint.h"
const int MAXN = 1e5 + 10;
int dp[2][MAXN], mx[MAXN];
vector<int> c[MAXN];

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 (int j : B[i]) {
			c[j].push_back(i);
		}
	}
	
	for (int i : c[C[0]]) {
		dp[0][i] = 1;
	}
	mx[0] = 1;

	for (int i = 1; i < N; i++) {
		for (int j : c[C[i]]){ 
			dp[i&1][j] = min(dp[!(i&1)][(j - 1 + M) % M] + 1, M);
			mx[i] = max(mx[i], dp[i&1][j]);
		}
		for (int j : c[C[i - 1]]) {
			dp[!(i&1)][j] = 0;
		}
	}
	
	int last = 0, cnt = 0, ans = 0;
    bool flag = 1;
    for (int i = N - 1; ~i; i--, cnt--) {
        if (mx[i] == M) {
            last = i;
            flag = 0;
        }
        if (!cnt) {
            if (flag) {
                return -1;
            }
            flag = 1;
            cnt = M - last + i;
            ans ++;
        }
    }

	return ans;
}

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