Submission #1198924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198924		hengliao	Painting Walls (APIO20_paint)	C++20	100 / 100	309 ms	15176 KiB

paint

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

#define F first 
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
  const int inf=1e9;
}

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> sz, vector<vector<int>> a) {
  vector<vector<int>> con(k);
  for(int i=0;i<m;i++){
    for(int j=0;j<sz[i];j++){
      con[a[i][j]].pb(i);
    }
  }
  vector<int> mp(m);
  auto f=[&](int v1, int v2){
    int tep=v2-v1;
    tep%=m;
    if(tep<0) tep+=m;
    return tep;
  };

  vector<bool> good(n);
  int cnt=0;
  auto add=[&](int tar){
    mp[tar]++;
    if(mp[tar]==m){
      cnt++;
    }
  };

  auto rem=[&](int tar){
    if(mp[tar]==m) cnt--;
    mp[tar]--;
  };
  for(int i=0;i<m;i++){
    for(auto &it:con[c[i]]){
      add(f(it, i));
    }
  }
  if(cnt>0){
    good[0]=1;
  }
  for(int i=1;i<=n-m;i++){
    for(auto &it:con[c[i-1]]){
      rem(f(it, i-1));
    }
    for(auto &it:con[c[i+m-1]]){
      add(f(it, i+m-1));
    }
    if(cnt>0){
      good[i]=1;
    }
  }
  vector<int> dp(n-m+1, inf);
  multiset<int> st;
  if(!good[0]){
    return -1;
  }
  dp[0]=1;
  st.insert(dp[0]);
  for(int i=1;i<=n-m;i++){
    if(i-m-1>=0) st.erase(st.find(dp[i-m-1]));
    if(!good[i]){
      st.insert(dp[i]);
      continue;
    }
    dp[i]=min(dp[i], (*st.begin())+1);
    st.insert(dp[i]);
  }
  if(dp[n-m]==inf){
    return -1;
  }
  return dp[n-m];
}

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