Submission #290557

#	Time	Username	Problem	Language	Result	Execution time	Memory
290557		Lawliet	Painting Walls (APIO20_paint)	C++17	100 / 100	518 ms	255216 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;
const int INF = 1000000010;

int m;

int dp[MAXN];

vector<int> dpComp[MAXN];
vector<int> company[MAXN];

multiset<int> minDP;

bool isGood(int i)
{
	for(int j = 0 ; j < (int)dpComp[i].size() ; j++)
		if( dpComp[i][j] >= m ) return true;

	return false;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector< vector<int> > B) 
{
	m = M;
	C.push_back( K + 1 );

	for(int i = 0 ; i < M ; i++)
		for(int j = 0 ; j < A[i] ; j++)
			company[ B[i][j] ].push_back( i );

	for(int i = N - 1 ; i >= 0 ; i--)
	{
		dpComp[i].resize( company[ C[i] ].size() , 0 );

		int pB = 0;
		int maxB = (int)company[ C[i + 1] ].size();

		for(int pA = 0 ; pA < (int)company[ C[i] ].size() ; pA++)
		{
			while( pB < maxB )
			{
				int nxt = company[ C[i + 1] ][pB];
				if( company[ C[i] ][pA] < nxt ) break;

				pB++;
			}

			if( pB < maxB && company[ C[i] ][pA] == company[ C[i + 1] ][pB] - 1 )
				dpComp[i][pA] = dpComp[i + 1][pB];
		}

		if( !company[ C[i] ].empty() && !company[ C[i + 1] ].empty() )
		{
			int ind = (int)company[ C[i] ].size() - 1;

			if( company[ C[i] ].back() == M - 1 && company[ C[i + 1] ].front() == 0 )
				dpComp[i][ind] = dpComp[i + 1][0];
		}

		for(int j = 0 ; j < (int)dpComp[i].size() ; j++)
			dpComp[i][j]++;
	}

	dp[N] = 0;

	for(int i = 0 ; i < N ; i++)
		dp[i] = INF;

	for(int i = N - M + 1 ; i <= N ; i++)
		minDP.insert( dp[i] );

	for(int i = N - M ; i >= 0 ; i--)
	{
		if( isGood( i ) )
			dp[i] = *minDP.begin() + 1;

		minDP.insert( dp[i] );
		minDP.erase( minDP.find( dp[i + M] ) );
	}

	if( dp[0] >= INF ) return -1;
	return dp[0];
}

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