Submission #568238

#	Time	Username	Problem	Language	Result	Execution time	Memory
568238		hibiki	Painting Walls (APIO20_paint)	C++11	0 / 100	4 ms	5088 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second

int n,m,k;
int dp[100100];
deque<int> dq;
vector<int> v[100100];
map<int,int> train;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B)
{
    n = N, m = M, k = K;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < A[i]; j++)
            v[B[i][j]].pb(i);
    dp[n] = 0;
    dq.pb(n);
    for(int i = n - 1; i >= 0; i--)
    {
        bool fi = false;
        map<int,int> temp = train;
        // for(auto val:temp)
        //     printf("%d %d\n",val.f,val.s);
        // printf("---\n");
        train.clear();
        while(dq.back() > i + m)dq.pop_back();
        if(dq.empty())return -1;
        for(int j = 0; j < v[C[i]].size(); j++)
        {
            int cur = v[C[i]][j];
            if(temp[(cur + 1) % m])
                train[cur] = temp[(cur + 1) % m] + 1;
            else
                train[cur] = 1;
            if(train[cur] >= m)
                fi = true;
        }
        if(fi)
        {
            dp[i] = dp[dq.back()] + 1;
            dq.push_front(i);
        }
    }
    if(dp[0] == 0) return -1;
    return dp[0];
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j = 0; j < v[C[i]].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~

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