# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
569816 | aryan12 | Painting Walls (APIO20_paint) | C++17 | 1 ms | 300 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>
using namespace std;
int minimumInstructions(int N, int M, int K, vector<int> colors, vector<int> num, vector<vector<int> > likes)
{
vector<vector<int> > dp(2, vector<int> (M, -1e9));
vector<int> likings[K];
for(int contractor = 0; contractor < M; contractor++)
{
for(int j = 0; j < num[contractor]; j++)
{
likings[likes[contractor][j]].push_back(contractor);
}
}
vector<int> start_pos;
for(int i = N - 1; i >= 0; i--)
{
int omk_cur = i % 2, omk_prev = (i + 1) % 2;
bool flag = false;
for(int j = 0; j < likings[colors[i]].size(); j++)
{
int cur = likings[colors[i]][j];
if(i == N - 1 || dp[omk_prev][(cur + 1) % M] == -1e9)
{
dp[omk_cur][cur] = 1;
}
else
{
dp[omk_cur][cur] = dp[omk_prev][(cur + 1) % M] + 1;
}
if(dp[omk_cur][cur] >= M && i <= N - M && !flag)
{
start_pos.push_back(i);
flag = true;
}
}
// for(int j = 0; j < M; j++)
// {
// if(likings[j].count(colors[i]))
// {
// if(i == N - 1 || dp[i + 1][(j + 1) % M] == -1e9)
// {
// dp[i][j] = 1;
// }
// else
// {
// dp[i][j] = dp[i + 1][(j + 1) % M] + 1;
// }
// }
// // cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n";
// }
// cout << "\n\n\n\n";
}
// vector<int> start_pos;
// for(int i = N - M; i >= 0; i--)
// {
// for(int j = 0; j < M; j++)
// {
// if(dp[i][j] >= M)
// {
// start_pos.push_back(i);
// // cout << i << "\n";
// break;
// }
// }
// }
int ans = 0;
int min_x = N;
for(int i = 0; i < start_pos.size(); i++)
{
// cout << "start_pos[i] = " << start_pos[i] << ", M = " << M << ", minx = " << min_x << "\n";
if(start_pos[i] + M - 1 < min_x - 1)
{
return -1;
}
if(i == start_pos.size() - 1 || start_pos[i + 1] + M - 1 < min_x - 1 || start_pos[i] == 0)
{
min_x = start_pos[i];
ans++;
}
}
if(min_x != 0) return -1;
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |