Submission #645502

#	Time	Username	Problem	Language	Result	Execution time	Memory
645502		Tenis0206	Painting Walls (APIO20_paint)	C++11	40 / 100	1595 ms	20116 KiB

paint

#include <bits/stdc++.h>

#include "paint.h"

using namespace std;

const int oo = INT_MAX;

vector<int> dp[100005];
vector<int> l[100005];

int lmax[100005],dp_rez[100005];

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
{
    for(int i=0;i<m;i++)
    {
        for(auto it : b[i])
        {
            l[it].push_back(i);
        }
    }
    dp[0].resize(l[c[0]].size());
    for(int j=0;j<l[c[0]].size();j++)
    {
        dp[0][j] = 1;
    }
    lmax[0] = 1;
    for(int i=1;i<n;i++)
    {
        dp[i].resize(l[c[i]].size());
        for(int j=0;j<l[c[i]].size();j++)
        {
            dp[i][j] = 1;
            for(int p=0;p<l[c[i-1]].size();p++)
            {
                int aux1 = l[c[i-1]][p];
                int aux2 = l[c[i]][j];
                if(l[c[i-1]][p]==l[c[i]][j]-1 || (l[c[i-1]][p]==m-1 && l[c[i]][j]==0))
                {
                    dp[i][j] = max(dp[i][j],dp[i-1][p] + 1);
                }
            }
            lmax[i] = max(lmax[i],dp[i][j]);
        }
    }
    deque<int> q;
    for(int i=0;i<n;i++)
    {
        if(lmax[i] < m)
        {
            dp_rez[i] = oo;
            while(!q.empty() && dp_rez[q.back()] > dp_rez[i])
            {
                q.pop_back();
            }
            q.push_back(i);
            continue;
        }
        while(!q.empty() && q.front() < i - m)
        {
            q.pop_front();
        }
        if(i < m)
        {
            dp_rez[i] = 1;
        }
        else
        {
            int val = dp_rez[q.front()];
            if(val == oo)
            {
                dp_rez[i] = oo;
            }
            else
            {
                dp_rez[i] = 1 + val;
            }
        }
        while(!q.empty() && dp_rez[q.back()] > dp_rez[i])
        {
            q.pop_back();
        }
        q.push_back(i);
    }
    if(dp_rez[n-1]==oo)
    {
        dp_rez[n-1] = -1;
    }
    return dp_rez[n-1];
}

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:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=0;j<l[c[0]].size();j++)
      |                 ~^~~~~~~~~~~~~~~
paint.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=0;j<l[c[i]].size();j++)
      |                     ~^~~~~~~~~~~~~~~
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 p=0;p<l[c[i-1]].size();p++)
      |                         ~^~~~~~~~~~~~~~~~~
paint.cpp:37:21: warning: unused variable 'aux1' [-Wunused-variable]
   37 |                 int aux1 = l[c[i-1]][p];
      |                     ^~~~
paint.cpp:38:21: warning: unused variable 'aux2' [-Wunused-variable]
   38 |                 int aux2 = l[c[i]][j];
      |                     ^~~~

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