Submission #383538

#	Time	Username	Problem	Language	Result	Execution time	Memory
383538		BartolM	Painting Walls (APIO20_paint)	C++17	100 / 100	497 ms	255920 KiB

paint

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int M=5e4+5;

int n, m, k;
vector <int> boja[N];
vector <int> dp[N];
int maxi[N];
int res[N];
deque <int> Q;

int minimumInstructions( int NN, int MM, int KK, vector<int> C, vector<int> A, vector<vector<int> > B) {
    n=NN; m=MM; k=KK;
    for (int i=0; i<m; ++i) {
        for (int x:B[i]) boja[x].pb(i);
    }
    for (int i=0; i<n; ++i) if (boja[C[i]].empty()) return -1;

    dp[n-1].resize((int)boja[C[n-1]].size(), 1);
    maxi[n-1]=1;

    for (int i=n-2; i>=0; --i) {
        int x=C[i], y=C[i+1];
        dp[i].resize(boja[x].size(), 1);
        int ind=0;

        for (int j=0; j<(int)boja[x].size(); ++j) {

            while (ind<(int)boja[y].size() && boja[y][ind]<=boja[x][j]) ++ind;

            if (boja[x][j]==m-1) dp[i][j]= boja[y][0]==0 ? dp[i+1][0]+1 : 1;
            else if (ind!=(int)boja[y].size() && boja[y][ind]==boja[x][j]+1) dp[i][j]=max(dp[i][j], dp[i+1][ind]+1);

            maxi[i]=max(maxi[i], dp[i][j]);
        }
//        printf("i: %d, maxi: %d\nradnici: ", i, maxi[i]);
//        for (int a:boja[x]) printf("%d ", a);
//        printf("\ndp: ");
//        for (int a:dp[i]) printf("%d ", a);
//        printf("\n\n");
    }

    res[0]=maxi[0]>=m ? 1 : INF;
    Q.pb(0);
    for (int i=1; i<=n-m; ++i) {
        res[i]=INF;
        if (maxi[i]>=m && !Q.empty()) {
            res[i]=res[Q.front()]+1;
            while (!Q.empty() && res[i]<=res[Q.back()]) Q.pop_back();
            Q.pb(i);
        }
        if (Q.front()==i-m) Q.pop_front();
    }

    return res[n-m]>=INF ? -1 : res[n-m];
}

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