Submission #465184

#	Time	Username	Problem	Language	Result	Execution time	Memory
465184		kilikuma	Colouring a rectangle (eJOI19_colouring)	C++14	20 / 100	2082 ms	460 KiB

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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20