# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
979575 | vjudge1 | Painting Walls (APIO20_paint) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e9;
ll eq(ll *c, ll p, vector<ll> *b, ll m)
{
ll ok = 1;
for(ll i = p; i < p + m; ++i)
{
ll _ok = 0;
for(ll j : b[i - p])
_ok |= c[i] == j;
ok &= _ok;
}
return ok;
}
void sdvig(vector<ll> *b, ll m)
{
for(ll i = 0; i < m - 1; ++i)
swap(b[i], b[i + 1]);
}
ll minimumInstructions(ll n, ll m, ll k, ll *c, ll *a, vector<ll> *b)
{
ll i, j;
ll dp[n + 5] = {};
for(i = 0; i <= n - m; ++i)
{
for(ll t = 0; t < m && !dp[i]; ++t)
{
if(eq(c, i, b, m))
dp[i] = 1;
sdvig(b, m);
}
}
ll ans = 1, cur = 0;
while(cur < n - m)
{
ll lst = INF;
for(i = cur + 1; i <= cur + m; ++i)
if(dp[i])
lst = i;
cur = lst;
++ans;
}
// for(i = 0; i < n; ++i)
// cout << dp[i] << ' ';
// return;
return (cur < INF ? ans : -1);
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// solve();
//}
//8 3 5
//3 3 1 3 4 4 2 2
//3 0 1 2
//2 2 3
//2 3 4