Submission #802975

#	Time	Username	Problem	Language	Result	Execution time	Memory
802975		radaiosm7	Painting Walls (APIO20_paint)	C++11	51 / 100	132 ms	23884 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, m, x, y, l, s, i, mn;
int j, cc;
vector<pair<int, int> > segs;
bool ok;
stack<pair<int, int> > S;
vector<int> ava[100005];
int dp[2][5005];
  
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
  if (a.Y == b.Y) return a.X < b.X;
  return a.Y < b.Y;
}
  
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int> > B) {
  for (i=0; i < M; ++i) for (j=0; j < A[i]; ++j) ava[B[i][j]].push_back(i);
  fill(dp[1], dp[1]+M, 0);

  for (y=0; y < N; ++y) {
    cc = y&1;
    fill(dp[cc], dp[cc]+M, 0);
    ok = false;

    for (auto x : ava[C[y]]) {
      if (x == 0) dp[cc][x] = dp[1-cc][M-1]+1;
      else dp[cc][x] = dp[1-cc][x-1]+1;

      if (!ok && dp[cc][x] >= M) {
        segs.push_back(make_pair(y-M+1, y));
        ok = true;
      }
    }
  }
  
  sort(segs.begin(), segs.end(), cmp);
  s = (int)segs.size();
  if (s == 0) return -1;
  mn = segs[0].X;
  S.push(segs[0]);
  
  for (i=1; i < s; ++i) {
    if (segs[i].X > S.top().Y+1) continue;
    if (segs[i].Y == S.top().Y) continue;
    while (!S.empty() && S.top().X >= segs[i].X) S.pop();
  
    if (!S.empty()) S.push(make_pair(S.top().Y+1, segs[i].Y));
    else S.push(segs[i]);
    mn = min(mn, segs[i].X);
  }
  
  if (mn > 0 || S.top().Y < N-1) return -1;
  return (int)S.size();
}

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