답안 #68631 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68631	2018-08-17T17:53:07 Z	AdrienVannson	Cultivation (JOI17_cultivation)	C++14	5 / 100	77 ms	720 KB

cultivation

// Sous-tâche 1 & 2

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <array>

using namespace std;

const int oo = 1000*1000*1000;

const int TAILLE_MAX_GRILLE_DEPART = 42;

const int TAILLE_MAX = 2 * TAILLE_MAX_GRILLE_DEPART;
const int NB_MAX_LIGNES = TAILLE_MAX;
const int NB_MAX_COLONNES = TAILLE_MAX;



int nbLignes, nbColonnes;
bool estPlein[NB_MAX_LIGNES][NB_MAX_COLONNES];


bool getEstPossible (const int nbBas, const int nbDroite)
{
    int nbRectangles[NB_MAX_LIGNES][NB_MAX_COLONNES];
    fill(*nbRectangles, *nbRectangles+NB_MAX_LIGNES*NB_MAX_COLONNES, 0);

    for (int iLigne=0; iLigne<nbLignes; iLigne++) {
        for (int iColonne=0; iColonne<nbColonnes; iColonne++) {
            if (estPlein[iLigne][iColonne]) {
                nbRectangles[iLigne][iColonne]++;
                nbRectangles[iLigne][iColonne+nbDroite+1]--;
                nbRectangles[iLigne+nbBas+1][iColonne]--;
                nbRectangles[iLigne+nbBas+1][iColonne+nbDroite+1]++;
            }
        }
    }

    // Pour chaque cellule, calculer par combien de rectangles elle est recouverte
    for (int iLigne=0; iLigne<NB_MAX_LIGNES-1; iLigne++) {
        for (int iColonne=0; iColonne<NB_MAX_COLONNES-1; iColonne++) {
            nbRectangles[iLigne][iColonne+1] += nbRectangles[iLigne][iColonne];
            nbRectangles[iLigne+1][iColonne] += nbRectangles[iLigne][iColonne];
            nbRectangles[iLigne+1][iColonne+1] -= nbRectangles[iLigne][iColonne];
        }
    }

    // Pour chaque cellule, calculer le nombre de cellules consecutives à droite
    int nbADroite[NB_MAX_LIGNES];
    fill(nbADroite, nbADroite+NB_MAX_LIGNES, 0);

    for (int iColonne=NB_MAX_COLONNES-1; iColonne>=0; iColonne--) {
        for (int iLigne=0; iLigne<NB_MAX_LIGNES; iLigne++) {

            nbADroite[iLigne]++;

            if (nbRectangles[iLigne][iColonne] == 0) {
                nbADroite[iLigne] = 0;
            }
        }

        // Vérification de la validité sur la colonne actuelle
        int iLigneDebut = -1; // Exclu (sur une cellule invalide)

        for (int iLigneFin=0; iLigneFin<NB_MAX_LIGNES; iLigneFin++) { // Inclus

            if (nbADroite[iLigneFin] < nbColonnes) {
                iLigneDebut = iLigneFin;
            }

            if (iLigneFin - iLigneDebut >= nbLignes) {
                return true;
            }

        }
    }

    return false;
}


int main ()
{
    scanf("%d %d", &nbLignes, &nbColonnes);

    if (nbLignes > 40 || nbColonnes > 40) {
        exit(42);
    }


    for (int iLigne=0; iLigne<nbLignes; iLigne++) {
        for (int iColonne=0; iColonne<nbColonnes; iColonne++) {
            estPlein[iLigne][iColonne] = false;
        }
    }

    int nbCellulesPleines;
    scanf("%d", &nbCellulesPleines);

    for (int iCellule=0; iCellule<nbCellulesPleines; iCellule++) {
        int iLigne, iColonne;
        scanf("%d %d", &iLigne, &iColonne);
        iLigne--, iColonne--;

        estPlein[iLigne][iColonne] = true;
    }

    int nbEtapesMin = +oo;

    for (int nbEtapesBas=0; nbEtapesBas<TAILLE_MAX_GRILLE_DEPART; nbEtapesBas++) {

        // TODO: dichotomie
        for (int nbEtapesDroite=0; nbEtapesDroite<TAILLE_MAX_GRILLE_DEPART; nbEtapesDroite++) {
            if (getEstPossible(nbEtapesBas, nbEtapesDroite)) {
                nbEtapesMin = min(nbEtapesBas+nbEtapesDroite, nbEtapesMin);
            }
        }
    }

    printf("%d\n", nbEtapesMin);

    return 0;
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &nbLignes, &nbColonnes);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &iLigne, &iColonne);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	376 KB	Output is correct
2	Correct	67 ms	376 KB	Output is correct
3	Correct	63 ms	432 KB	Output is correct
4	Correct	63 ms	560 KB	Output is correct
5	Correct	66 ms	680 KB	Output is correct
6	Correct	66 ms	680 KB	Output is correct
7	Correct	64 ms	680 KB	Output is correct
8	Correct	68 ms	680 KB	Output is correct
9	Correct	65 ms	720 KB	Output is correct
10	Correct	63 ms	720 KB	Output is correct
11	Correct	71 ms	720 KB	Output is correct
12	Correct	66 ms	720 KB	Output is correct
13	Correct	69 ms	720 KB	Output is correct
14	Correct	68 ms	720 KB	Output is correct
15	Correct	68 ms	720 KB	Output is correct
16	Correct	66 ms	720 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	376 KB	Output is correct
2	Correct	67 ms	376 KB	Output is correct
3	Correct	63 ms	432 KB	Output is correct
4	Correct	63 ms	560 KB	Output is correct
5	Correct	66 ms	680 KB	Output is correct
6	Correct	66 ms	680 KB	Output is correct
7	Correct	64 ms	680 KB	Output is correct
8	Correct	68 ms	680 KB	Output is correct
9	Correct	65 ms	720 KB	Output is correct
10	Correct	63 ms	720 KB	Output is correct
11	Correct	71 ms	720 KB	Output is correct
12	Correct	66 ms	720 KB	Output is correct
13	Correct	69 ms	720 KB	Output is correct
14	Correct	68 ms	720 KB	Output is correct
15	Correct	68 ms	720 KB	Output is correct
16	Correct	66 ms	720 KB	Output is correct
17	Correct	66 ms	720 KB	Output is correct
18	Correct	73 ms	720 KB	Output is correct
19	Correct	76 ms	720 KB	Output is correct
20	Correct	70 ms	720 KB	Output is correct
21	Incorrect	77 ms	720 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	376 KB	Output is correct
2	Correct	67 ms	376 KB	Output is correct
3	Correct	63 ms	432 KB	Output is correct
4	Correct	63 ms	560 KB	Output is correct
5	Correct	66 ms	680 KB	Output is correct
6	Correct	66 ms	680 KB	Output is correct
7	Correct	64 ms	680 KB	Output is correct
8	Correct	68 ms	680 KB	Output is correct
9	Correct	65 ms	720 KB	Output is correct
10	Correct	63 ms	720 KB	Output is correct
11	Correct	71 ms	720 KB	Output is correct
12	Correct	66 ms	720 KB	Output is correct
13	Correct	69 ms	720 KB	Output is correct
14	Correct	68 ms	720 KB	Output is correct
15	Correct	68 ms	720 KB	Output is correct
16	Correct	66 ms	720 KB	Output is correct
17	Correct	66 ms	720 KB	Output is correct
18	Correct	73 ms	720 KB	Output is correct
19	Correct	76 ms	720 KB	Output is correct
20	Correct	70 ms	720 KB	Output is correct
21	Incorrect	77 ms	720 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	720 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	720 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	376 KB	Output is correct
2	Correct	67 ms	376 KB	Output is correct
3	Correct	63 ms	432 KB	Output is correct
4	Correct	63 ms	560 KB	Output is correct
5	Correct	66 ms	680 KB	Output is correct
6	Correct	66 ms	680 KB	Output is correct
7	Correct	64 ms	680 KB	Output is correct
8	Correct	68 ms	680 KB	Output is correct
9	Correct	65 ms	720 KB	Output is correct
10	Correct	63 ms	720 KB	Output is correct
11	Correct	71 ms	720 KB	Output is correct
12	Correct	66 ms	720 KB	Output is correct
13	Correct	69 ms	720 KB	Output is correct
14	Correct	68 ms	720 KB	Output is correct
15	Correct	68 ms	720 KB	Output is correct
16	Correct	66 ms	720 KB	Output is correct
17	Correct	66 ms	720 KB	Output is correct
18	Correct	73 ms	720 KB	Output is correct
19	Correct	76 ms	720 KB	Output is correct
20	Correct	70 ms	720 KB	Output is correct
21	Incorrect	77 ms	720 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #68631

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0