Submission #1216197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216197		mychecksedad	Painting Walls (APIO20_paint)	C++20	0 / 100	0 ms	404 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int sz, T[N];
void build(int n){
  sz=n;
  for(int i = 0; i <= 2*sz+2; ++i) T[i] = 0;
}
void add(int v, int x){
  ++v;
  v += sz;
  T[v] += x;
  for(v >>= 1; v; v >>= 1) T[v] = max(T[v<<1], T[v<<1|1]);
}

int minimumInstructions(int n, int m, int k, std::vector<int> CC, std::vector<int> A, std::vector<std::vector<int>> B) {
  vector<vi> COL(k);
  for(int i = 0; i < m; ++i){
    for(int j = 0; j < A[i]; ++j) COL[B[i][j]].pb(i);
  }
      
  int C = 2*m;
  int D = m;
  build(C);
  for(int j = 0; j + 1 < m; ++j){
    for(int pos: COL[CC[j]]) add((j-pos+2*m)%(2*m), 1);
    for(int pos: COL[CC[j]]) add((j-pos+m-1+2*m)%(2*m), 1);
  }
  vector<bool> ok(n);
  for(int i = 0; i < n - m; ++i){
    for(int pos: COL[CC[i + m - 1]]) add((i+m-1-pos+C)%C, 1);
    for(int pos: COL[CC[i + m - 1]]) add((i+m-1-pos+D+C)%C, 1);
    
    if(T[1] == m){
      ok[i] = 1;
    }

    for(int pos: COL[CC[i]]) add((i-pos+C)%C, -1);
    for(int pos: COL[CC[i]]) add((i-pos+D+C)%C, -1);
  }

  if(ok[0] == 0 || ok[n-m-1] == 0) return -1;
  vi dp(n);
  int last = 0;
  dp[0] = 1;
  for(int i = 1; i < n-m; ++i){
    if(ok[i]) last = i;
    if(last <= i - m) return -1;
    if(ok[i]) dp[i] = i < m ? 2 : dp[i - m] + 1;
    else dp[i] = dp[i - 1];
    // cerr << dp[i] << ' ';
  }

  return dp[n-m-1];
}

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