Submission #35363

#	Time	Username	Problem	Language	Result	Execution time	Memory
35363		IvanC	Cultivation (JOI17_cultivation)	C++14	5 / 100	2000 ms	262144 KiB

cultivation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
vector<int> X,Y;
int R,C,N;
int best;
void brute(int qtd,vvi estado){  
  int flag = 1;
  for(int i = 0;i<R;i++){
    for(int j = 0;j<C;j++){
      flag &= estado[i][j];
    }
  }
  if(flag == 1){
    best = min(best,qtd);
    return;
  }
  vvi copia = estado;
  int any = 0;
  for(int i = 0;i<R;i++)
    for(int j = 0;j+1<C;j++){
      int old = copia[i][j];
      copia[i][j] |= copia[i][j+1];
      if(copia[i][j] != old) any = 1;
    }
  if(any) brute(qtd+1,copia);
  copia = estado;
  any = 0;
  for(int j = 0;j<C;j++)
    for(int i = 0;i + 1 < R;i++){
      int old = copia[i][j];
      copia[i][j] |= copia[i+1][j];
      if(copia[i][j] != old) any = 1;
    }
  if(any) brute(qtd+1,copia);
  copia = estado;
  any = 0;
  for(int i = 0;i<R;i++)for(int j = C-1;j>0;j--){
      int old = copia[i][j];
      copia[i][j] |= copia[i][j-1];
      if(old != copia[i][j]) any = 1;
    }
  if(any) brute(qtd+1,copia);
  copia = estado;
  any = 0;
  for(int j = 0;j<C;j++) for(int i = R - 1;i>0;i--){
      int old = copia[i][j];
      copia[i][j] |= copia[i-1][j];
      if(old != copia[i][j]) any = 1;
    }
  if(any) brute(qtd+1,copia);
}
int main(){
  best = 200;
  cin >> R >> C >> N;
  for(int i = 0;i<N;i++){
    int x,y;
    cin >> x >> y;
    X.push_back(x-1);
    Y.push_back(y-1);
  }
  vi vazio;
  vazio.assign(C,0);
  vvi matriz;
  matriz.assign(R,vazio);
  for(int i = 0;i<N;i++) matriz[X[i]][Y[i]] = 1;
  brute(0,matriz);
  printf("%d\n",best);
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20