Submission #35363

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
35363	2017-11-20T18:37:59 Z	IvanC	Cultivation (JOI17_cultivation)	C++14	5 / 100	2000 ms	262144 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	0 ms	2024 KB	Output is correct
13	Correct	0 ms	2024 KB	Output is correct
14	Correct	0 ms	2024 KB	Output is correct
15	Correct	3 ms	2024 KB	Output is correct
16	Correct	0 ms	2024 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	0 ms	2024 KB	Output is correct
13	Correct	0 ms	2024 KB	Output is correct
14	Correct	0 ms	2024 KB	Output is correct
15	Correct	3 ms	2024 KB	Output is correct
16	Correct	0 ms	2024 KB	Output is correct
17	Execution timed out	2000 ms	2156 KB	Execution timed out
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	0 ms	2024 KB	Output is correct
13	Correct	0 ms	2024 KB	Output is correct
14	Correct	0 ms	2024 KB	Output is correct
15	Correct	3 ms	2024 KB	Output is correct
16	Correct	0 ms	2024 KB	Output is correct
17	Execution timed out	2000 ms	2156 KB	Execution timed out
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	3 ms	262144 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	3 ms	262144 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	0 ms	2024 KB	Output is correct
13	Correct	0 ms	2024 KB	Output is correct
14	Correct	0 ms	2024 KB	Output is correct
15	Correct	3 ms	2024 KB	Output is correct
16	Correct	0 ms	2024 KB	Output is correct
17	Execution timed out	2000 ms	2156 KB	Execution timed out
18	Halted	0 ms	0 KB	-