Submission #465184

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465184	2021-08-15T10:09:12 Z	kilikuma	Colouring a rectangle (eJOI19_colouring)	C++14	20 / 100	2000 ms	460 KB

colouring

#include <bits/stdc++.h> 
using namespace std;
#define long long long 
bool etatBas[30]; 
int nbLigs, nbCols; 
long diagBas[30], diagHaut[30]; 
long  miniCur = (1e12); 
long  mini(long a, long b) {
  if (a<b)return a; else return b; 
}
void recur(int niveau) {
  if( niveau > (nbLigs+nbCols-1)) {
    // code important
    long tot = 0; 
    bool A[13][13] = {false}; 
   
    for (int diag = 1; diag <= nbLigs; diag ++) {
      if (etatBas[diag]) {
        tot += diagBas[diag];
        int lig = diag; int col = nbCols; 
        while ((lig>=1) && (col>=1)) {
          A[lig][col] = true; 
          lig --; col --; 
        }
      }
    }int lo = nbLigs+1; 
    for (int diag = nbCols-1; diag >= 1; diag --) {
      if (etatBas[lo]) {
        tot += diagBas[lo];
        int lig = nbLigs; int col = diag; 
        while ((lig>=1) && (col>=1)) {
          A[lig][col] = true; 
          lig --; col --; 
        }
      }
      lo ++; 
    }
  //   if (etatBas[1] && etatBas[3]){

    // }
    for (int diag = 1; diag <= nbLigs; diag ++) {
      bool cond = true; 
      int lig = diag; int col = 1; 
      while ((lig >=1)&&(col<=nbCols)) {
        if (!A[lig][col]) cond = false; 
        A[lig][col] = true; 
        lig --; col ++; 
      }
      if (!cond) tot += diagHaut[diag]; 
    }
    for (int diag = 2; diag <= nbCols; diag ++) {
      bool cond = true; 
      int lig = nbLigs; int col = diag; 
      while ((lig >=1)&&(col<=nbCols)) {
        if (!A[lig][col]) cond = false; 
        A[lig][col] = true; 
        lig --; col ++; 
      }
      if (!cond) tot += diagHaut[diag-1+nbLigs]; 
    }

    miniCur = mini(miniCur, tot); 
    return ;
  }
  else {
    etatBas[niveau+1] = false; 
    recur(niveau+1); 
    etatBas[niveau+1] =true; 
    recur(niveau+1);
    etatBas[niveau+1] = false;  
  }
  return;
}
int main() {
  scanf("%d%d",&nbLigs,&nbCols); 
  for (int i = 1; i <= nbLigs+nbCols-1;i ++) cin >> diagBas[i];
  for (int i = 1; i <= nbLigs+nbCols-1;i ++) cin >> diagHaut[i]; 
  recur(0); 
  cout << miniCur; 
}

Compilation message

colouring.cpp: In function 'int main()':
colouring.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d",&nbLigs,&nbCols);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	241 ms	272 KB	Output is correct
12	Correct	5 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	227 ms	272 KB	Output is correct
17	Correct	3 ms	204 KB	Output is correct
18	Correct	229 ms	272 KB	Output is correct
19	Correct	120 ms	204 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	241 ms	272 KB	Output is correct
12	Correct	5 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	227 ms	272 KB	Output is correct
17	Correct	3 ms	204 KB	Output is correct
18	Correct	229 ms	272 KB	Output is correct
19	Correct	120 ms	204 KB	Output is correct
20	Execution timed out	2082 ms	204 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	241 ms	272 KB	Output is correct
12	Correct	5 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	227 ms	272 KB	Output is correct
17	Correct	3 ms	204 KB	Output is correct
18	Correct	229 ms	272 KB	Output is correct
19	Correct	120 ms	204 KB	Output is correct
20	Execution timed out	2082 ms	204 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	460 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	460 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	241 ms	272 KB	Output is correct
12	Correct	5 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	227 ms	272 KB	Output is correct
17	Correct	3 ms	204 KB	Output is correct
18	Correct	229 ms	272 KB	Output is correct
19	Correct	120 ms	204 KB	Output is correct
20	Execution timed out	2082 ms	204 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Submission #465184

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 10.0

Subtask #4 0 / 20.0

Subtask #5 0 / 10.0

Subtask #6 0 / 20.0

Subtask #7 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 10.0

Subtask #4
0 / 20.0

Subtask #5
0 / 10.0

Subtask #6
0 / 20.0

Subtask #7
0 / 20.0