제출 #1368394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368394		greedyaj	벽 칠하기 (APIO20_paint)	C++20	63 / 100	1595 ms	16460 KiB

paint

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

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
    vector<set<int>> liked_by(k);
    
    for(int i = 0; i < m; i++){
      for(int j = 0; j < a[i]; j++){
        liked_by[b[i][j]].insert(i);
      }
    }

    for(int i = 0; i < n; i++){
      if(liked_by[c[i]].empty()) return -1;
    }

    vector<bool> coloured(n,0);
    int ans = 0;

    for(int i = 0; i < n; i++){

      // cerr << i << endl;
      if(coloured[i]) continue;
      ans++;

      bool got = 0;
      
      for(int con : liked_by[c[i]]){
        int goLeft = 0, goRight = 0;
        int cc = con;
        for(int j = i - 1; j >= 0 && i - j + 1 <= m; j--){
          if(liked_by[c[j]].find((cc - 1 + m)%m) == liked_by[c[j]].end()) break;
          else{goLeft++; cc--;}
        }
        cc = con;
        for(int j = i + 1; j < n && j - i + 1 <= m; j++){
          if(liked_by[c[j]].find((cc + 1)%m) == liked_by[c[j]].end()) break;
          else{goRight++; cc++;}
        }

        if(goLeft + goRight + 1 >= m){
          got = 1;
          for(int j = i+1; j <= i +  goRight; j++){
            coloured[j] = 1;
          }
        }
              // cerr << con << " " << goLeft << " " << goRight << endl;
      }

      // cerr << endl;

      if(!got) return -1;
    }

    return ans;
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 15 / 15
• 서브태스크 3: 13 / 13
• 서브태스크 4: 23 / 23
• 서브태스크 5: 0 / 37