Submission #1282933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282933		altern23	벽 칠하기 (APIO20_paint)	C++20	100 / 100	191 ms	13612 KiB

paint

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

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second

const int MAXN = 1e5;
const ll INF = 2e18;

ll L[MAXN + 5], R[MAXN + 5], dp[MAXN + 5];
vector<ll> components[MAXN + 5];

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 x : B[i]){
                  components[x].push_back(i);
            }
      }

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

      dp[0] = 0;

      deque<pii> dq;
      dq.push_back({0, 0});

      for(int i = 1; i <= N; i++){
            for(auto j : components[C[i - 1]]){
                  ll idx = (j - i + N) % M;
                  if(R[idx] == i) continue;
                  
                  if(L[idx] != 0 && R[idx] == i - 1){
                        R[idx]++;
                  }
                  else{
                        L[idx] = R[idx] = i;
                  }
                  if(R[idx] - L[idx] + 1 >= M && !dq.empty()){
                        dp[i] = min(dp[i], dq.front().fi + 1);
                  }
            }
            
            while(!dq.empty() && dq.back().fi >= dp[i]){
                  dq.pop_back();
            }
            while(!dq.empty() && dq.front().sec <= i - M){
                  dq.pop_front();
            }

            if(dp[i] != INF){
                  dq.push_back({dp[i], i});
            }
      }

      return (dp[N] == INF ? -1 : dp[N]);
}

/*

*/

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