답안 #788591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788591	2023-07-20T11:43:12 Z	mindiyak	벽 칠하기 (APIO20_paint)	C++14	0 / 100	16 ms	27712 KB

paint

#include "paint.h"

#include <vector>
#include <unordered_set>
// #include <iostream>

using namespace std;

vector<int> dp(1000000,1e9);
vector<vector<int>> colors(1000000,vector<int>()); 

int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
  vector<unordered_set<int>> contrcatorColor(M,unordered_set<int>());

  for(int i=0;i<M;i++){
    for(int j=0;j<A[i];j++){
      colors[B[i][j]].push_back(i);
      contrcatorColor[i].insert(B[i][j]);
    }
  }

  bool possible = true;
  for(int i=0;i<=N-M;i++){
    // cout << "start pos is " << i << endl;
    bool coloured = false;
    for(int j=0;j<(int)colors[C[i]].size();j++){
      int contractorStart = colors[C[i]][j];
      possible = true;
      // cout << "contractor start " << contractorStart << endl;
      for(int k=0;k<M;k++){
        // cout << (contractorStart+k)%M << " contractor " << C[i+k] << " color " << contrcatorColor[(contractorStart+k)%M].count(C[i+k]) << endl;
        if(contrcatorColor[(contractorStart+k)%M].count(C[i+k]) == 0){
          possible = false;
          break;
        }
      }
      if(possible){
        // cout << "possible to paint " << i << " start from " << contractorStart << endl; 
        coloured = true;
        break;
      }
    }
    
    if(coloured){
      // cout << "i-" << i;
      if(i>0 and dp[i-1]!= -1){
        // cout << " dp[i-1]" << dp[i-1]; 
        dp[(M-1+i)] = dp[i-1]+1;
      }else{
        // cout << "start ";
        dp[(M-1+i)] = 1;
      }
      dp[(M-1+i)] = min(dp[(M-1+i)],dp[i]+1);
      dp[(M-1+i)] = min(dp[(M-1+i)],dp[i+1]+1);
      // cout << " pos-" << (M-1+i) << " dp[M-1]-" << dp[(M-1+i)] << endl;
    }
    // cout << endl;
  }

  // for(int i=0;i<N;i++){
  //   cout << dp[i] << " ";
  // }cout << endl;

  if(dp[N-1] >= 1e9){
    return -1;
  }
  return dp[N-1];
}

Subtask #1

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	27676 KB	Output is correct
2	Correct	14 ms	27604 KB	Output is correct
3	Correct	15 ms	27604 KB	Output is correct
4	Correct	13 ms	27604 KB	Output is correct
5	Correct	14 ms	27672 KB	Output is correct
6	Correct	14 ms	27608 KB	Output is correct
7	Correct	16 ms	27632 KB	Output is correct
8	Correct	14 ms	27584 KB	Output is correct
9	Correct	14 ms	27712 KB	Output is correct
10	Correct	14 ms	27672 KB	Output is correct
11	Correct	14 ms	27604 KB	Output is correct
12	Correct	14 ms	27684 KB	Output is correct
13	Incorrect	15 ms	27696 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	27676 KB	Output is correct
2	Correct	14 ms	27604 KB	Output is correct
3	Correct	15 ms	27604 KB	Output is correct
4	Correct	13 ms	27604 KB	Output is correct
5	Correct	14 ms	27672 KB	Output is correct
6	Correct	14 ms	27608 KB	Output is correct
7	Correct	16 ms	27632 KB	Output is correct
8	Correct	14 ms	27584 KB	Output is correct
9	Correct	14 ms	27712 KB	Output is correct
10	Correct	14 ms	27672 KB	Output is correct
11	Correct	14 ms	27604 KB	Output is correct
12	Correct	14 ms	27684 KB	Output is correct
13	Incorrect	15 ms	27696 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	27676 KB	Output is correct
2	Correct	14 ms	27604 KB	Output is correct
3	Correct	15 ms	27604 KB	Output is correct
4	Correct	13 ms	27604 KB	Output is correct
5	Correct	14 ms	27672 KB	Output is correct
6	Correct	14 ms	27608 KB	Output is correct
7	Correct	16 ms	27632 KB	Output is correct
8	Correct	14 ms	27584 KB	Output is correct
9	Correct	14 ms	27712 KB	Output is correct
10	Correct	14 ms	27672 KB	Output is correct
11	Correct	14 ms	27604 KB	Output is correct
12	Correct	14 ms	27684 KB	Output is correct
13	Incorrect	15 ms	27696 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	27676 KB	Output is correct
2	Correct	14 ms	27604 KB	Output is correct
3	Correct	15 ms	27604 KB	Output is correct
4	Correct	13 ms	27604 KB	Output is correct
5	Correct	14 ms	27672 KB	Output is correct
6	Correct	14 ms	27608 KB	Output is correct
7	Correct	16 ms	27632 KB	Output is correct
8	Correct	14 ms	27584 KB	Output is correct
9	Correct	14 ms	27712 KB	Output is correct
10	Correct	14 ms	27672 KB	Output is correct
11	Correct	14 ms	27604 KB	Output is correct
12	Correct	14 ms	27684 KB	Output is correct
13	Incorrect	15 ms	27696 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	27676 KB	Output is correct
2	Correct	14 ms	27604 KB	Output is correct
3	Correct	15 ms	27604 KB	Output is correct
4	Correct	13 ms	27604 KB	Output is correct
5	Correct	14 ms	27672 KB	Output is correct
6	Correct	14 ms	27608 KB	Output is correct
7	Correct	16 ms	27632 KB	Output is correct
8	Correct	14 ms	27584 KB	Output is correct
9	Correct	14 ms	27712 KB	Output is correct
10	Correct	14 ms	27672 KB	Output is correct
11	Correct	14 ms	27604 KB	Output is correct
12	Correct	14 ms	27684 KB	Output is correct
13	Incorrect	15 ms	27696 KB	Output isn't correct
14	Halted	0 ms	0 KB	-