답안 #68657 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68657	2018-08-17T19:49:53 Z	AdrienVannson	Cultivation (JOI17_cultivation)	C++14	15 / 100	981 ms	816 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 = 80;

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	808 ms	376 KB	Output is correct
2	Correct	769 ms	488 KB	Output is correct
3	Correct	761 ms	672 KB	Output is correct
4	Correct	793 ms	672 KB	Output is correct
5	Correct	764 ms	672 KB	Output is correct
6	Correct	810 ms	672 KB	Output is correct
7	Correct	828 ms	672 KB	Output is correct
8	Correct	862 ms	688 KB	Output is correct
9	Correct	798 ms	816 KB	Output is correct
10	Correct	797 ms	816 KB	Output is correct
11	Correct	795 ms	816 KB	Output is correct
12	Correct	809 ms	816 KB	Output is correct
13	Correct	808 ms	816 KB	Output is correct
14	Correct	836 ms	816 KB	Output is correct
15	Correct	865 ms	816 KB	Output is correct
16	Correct	866 ms	816 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	808 ms	376 KB	Output is correct
2	Correct	769 ms	488 KB	Output is correct
3	Correct	761 ms	672 KB	Output is correct
4	Correct	793 ms	672 KB	Output is correct
5	Correct	764 ms	672 KB	Output is correct
6	Correct	810 ms	672 KB	Output is correct
7	Correct	828 ms	672 KB	Output is correct
8	Correct	862 ms	688 KB	Output is correct
9	Correct	798 ms	816 KB	Output is correct
10	Correct	797 ms	816 KB	Output is correct
11	Correct	795 ms	816 KB	Output is correct
12	Correct	809 ms	816 KB	Output is correct
13	Correct	808 ms	816 KB	Output is correct
14	Correct	836 ms	816 KB	Output is correct
15	Correct	865 ms	816 KB	Output is correct
16	Correct	866 ms	816 KB	Output is correct
17	Correct	830 ms	816 KB	Output is correct
18	Correct	866 ms	816 KB	Output is correct
19	Correct	978 ms	816 KB	Output is correct
20	Correct	834 ms	816 KB	Output is correct
21	Correct	853 ms	816 KB	Output is correct
22	Correct	869 ms	816 KB	Output is correct
23	Correct	981 ms	816 KB	Output is correct
24	Correct	852 ms	816 KB	Output is correct
25	Correct	875 ms	816 KB	Output is correct
26	Correct	825 ms	816 KB	Output is correct
27	Correct	841 ms	816 KB	Output is correct
28	Correct	842 ms	816 KB	Output is correct
29	Correct	845 ms	816 KB	Output is correct
30	Correct	846 ms	816 KB	Output is correct
31	Correct	802 ms	816 KB	Output is correct
32	Correct	815 ms	816 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	808 ms	376 KB	Output is correct
2	Correct	769 ms	488 KB	Output is correct
3	Correct	761 ms	672 KB	Output is correct
4	Correct	793 ms	672 KB	Output is correct
5	Correct	764 ms	672 KB	Output is correct
6	Correct	810 ms	672 KB	Output is correct
7	Correct	828 ms	672 KB	Output is correct
8	Correct	862 ms	688 KB	Output is correct
9	Correct	798 ms	816 KB	Output is correct
10	Correct	797 ms	816 KB	Output is correct
11	Correct	795 ms	816 KB	Output is correct
12	Correct	809 ms	816 KB	Output is correct
13	Correct	808 ms	816 KB	Output is correct
14	Correct	836 ms	816 KB	Output is correct
15	Correct	865 ms	816 KB	Output is correct
16	Correct	866 ms	816 KB	Output is correct
17	Correct	830 ms	816 KB	Output is correct
18	Correct	866 ms	816 KB	Output is correct
19	Correct	978 ms	816 KB	Output is correct
20	Correct	834 ms	816 KB	Output is correct
21	Correct	853 ms	816 KB	Output is correct
22	Correct	869 ms	816 KB	Output is correct
23	Correct	981 ms	816 KB	Output is correct
24	Correct	852 ms	816 KB	Output is correct
25	Correct	875 ms	816 KB	Output is correct
26	Correct	825 ms	816 KB	Output is correct
27	Correct	841 ms	816 KB	Output is correct
28	Correct	842 ms	816 KB	Output is correct
29	Correct	845 ms	816 KB	Output is correct
30	Correct	846 ms	816 KB	Output is correct
31	Correct	802 ms	816 KB	Output is correct
32	Correct	815 ms	816 KB	Output is correct
33	Runtime error	2 ms	816 KB	Execution failed because the return code was nonzero
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	816 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	816 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	808 ms	376 KB	Output is correct
2	Correct	769 ms	488 KB	Output is correct
3	Correct	761 ms	672 KB	Output is correct
4	Correct	793 ms	672 KB	Output is correct
5	Correct	764 ms	672 KB	Output is correct
6	Correct	810 ms	672 KB	Output is correct
7	Correct	828 ms	672 KB	Output is correct
8	Correct	862 ms	688 KB	Output is correct
9	Correct	798 ms	816 KB	Output is correct
10	Correct	797 ms	816 KB	Output is correct
11	Correct	795 ms	816 KB	Output is correct
12	Correct	809 ms	816 KB	Output is correct
13	Correct	808 ms	816 KB	Output is correct
14	Correct	836 ms	816 KB	Output is correct
15	Correct	865 ms	816 KB	Output is correct
16	Correct	866 ms	816 KB	Output is correct
17	Correct	830 ms	816 KB	Output is correct
18	Correct	866 ms	816 KB	Output is correct
19	Correct	978 ms	816 KB	Output is correct
20	Correct	834 ms	816 KB	Output is correct
21	Correct	853 ms	816 KB	Output is correct
22	Correct	869 ms	816 KB	Output is correct
23	Correct	981 ms	816 KB	Output is correct
24	Correct	852 ms	816 KB	Output is correct
25	Correct	875 ms	816 KB	Output is correct
26	Correct	825 ms	816 KB	Output is correct
27	Correct	841 ms	816 KB	Output is correct
28	Correct	842 ms	816 KB	Output is correct
29	Correct	845 ms	816 KB	Output is correct
30	Correct	846 ms	816 KB	Output is correct
31	Correct	802 ms	816 KB	Output is correct
32	Correct	815 ms	816 KB	Output is correct
33	Runtime error	2 ms	816 KB	Execution failed because the return code was nonzero
34	Halted	0 ms	0 KB	-

답안 #68657

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.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
10.0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0