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
#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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# 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
# 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
# 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 -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -