Submission #568241

#	Time	Username	Problem	Language	Result	Execution time	Memory
568241		hibiki	Painting Walls (APIO20_paint)	C++11	100 / 100	1427 ms	15188 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];
int train_p[100100],train_n[100100];

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;
        // for(auto val:temp)
        //     printf("%d %d\n",val.f,val.s);
        // printf("---\n");
        while(dq.size() && 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];
            train_n[cur] = train_p[(cur + 1) % m] + 1;
            if(train_n[cur] >= m)
                fi = true;
        }
        if(i != n - 1)
            for(int j = 0; j < v[C[i + 1]].size(); j++)
            {
                int cur = v[C[i + 1]][j];
                train_p[cur] = 0;
            }
        for(int j = 0; j < v[C[i]].size(); j++)
        {
            int cur = v[C[i]][j];
            train_p[cur] = train_n[cur];
        }
        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:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j = 0; j < v[C[i]].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~
paint.cpp:41:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int j = 0; j < v[C[i + 1]].size(); j++)
      |                            ~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 0; j < v[C[i]].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~

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