답안 #68660 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68660	2018-08-17T20:15:39 Z	AdrienVannson	Cultivation (JOI17_cultivation)	C++14	15 / 100	138 ms	752 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 = 2*40;

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++) {

        if (getEstPossible(nbEtapesBas, 0)) {
            nbEtapesMin = min(nbEtapesBas, nbEtapesMin);
            continue;
        }

        int debut = 0;
        int fin = TAILLE_MAX_GRILLE_DEPART;

        while (fin-debut > 1) {
            const int milieu = (debut + fin) / 2;

            if (getEstPossible(nbEtapesBas, milieu)) {
                fin = milieu;
            }
            else {
                debut = milieu;
            }
        }

        if (fin < TAILLE_MAX_GRILLE_DEPART) {
            nbEtapesMin = min(nbEtapesBas+fin, 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	75 ms	380 KB	Output is correct
2	Correct	17 ms	520 KB	Output is correct
3	Correct	76 ms	564 KB	Output is correct
4	Correct	80 ms	728 KB	Output is correct
5	Correct	15 ms	728 KB	Output is correct
6	Correct	74 ms	728 KB	Output is correct
7	Correct	74 ms	728 KB	Output is correct
8	Correct	16 ms	728 KB	Output is correct
9	Correct	93 ms	728 KB	Output is correct
10	Correct	77 ms	728 KB	Output is correct
11	Correct	75 ms	728 KB	Output is correct
12	Correct	82 ms	728 KB	Output is correct
13	Correct	75 ms	728 KB	Output is correct
14	Correct	83 ms	748 KB	Output is correct
15	Correct	80 ms	748 KB	Output is correct
16	Correct	81 ms	748 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	380 KB	Output is correct
2	Correct	17 ms	520 KB	Output is correct
3	Correct	76 ms	564 KB	Output is correct
4	Correct	80 ms	728 KB	Output is correct
5	Correct	15 ms	728 KB	Output is correct
6	Correct	74 ms	728 KB	Output is correct
7	Correct	74 ms	728 KB	Output is correct
8	Correct	16 ms	728 KB	Output is correct
9	Correct	93 ms	728 KB	Output is correct
10	Correct	77 ms	728 KB	Output is correct
11	Correct	75 ms	728 KB	Output is correct
12	Correct	82 ms	728 KB	Output is correct
13	Correct	75 ms	728 KB	Output is correct
14	Correct	83 ms	748 KB	Output is correct
15	Correct	80 ms	748 KB	Output is correct
16	Correct	81 ms	748 KB	Output is correct
17	Correct	80 ms	748 KB	Output is correct
18	Correct	102 ms	748 KB	Output is correct
19	Correct	89 ms	748 KB	Output is correct
20	Correct	90 ms	748 KB	Output is correct
21	Correct	91 ms	748 KB	Output is correct
22	Correct	81 ms	748 KB	Output is correct
23	Correct	138 ms	748 KB	Output is correct
24	Correct	60 ms	748 KB	Output is correct
25	Correct	80 ms	748 KB	Output is correct
26	Correct	64 ms	748 KB	Output is correct
27	Correct	52 ms	748 KB	Output is correct
28	Correct	84 ms	748 KB	Output is correct
29	Correct	41 ms	748 KB	Output is correct
30	Correct	48 ms	748 KB	Output is correct
31	Correct	61 ms	748 KB	Output is correct
32	Correct	43 ms	752 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	380 KB	Output is correct
2	Correct	17 ms	520 KB	Output is correct
3	Correct	76 ms	564 KB	Output is correct
4	Correct	80 ms	728 KB	Output is correct
5	Correct	15 ms	728 KB	Output is correct
6	Correct	74 ms	728 KB	Output is correct
7	Correct	74 ms	728 KB	Output is correct
8	Correct	16 ms	728 KB	Output is correct
9	Correct	93 ms	728 KB	Output is correct
10	Correct	77 ms	728 KB	Output is correct
11	Correct	75 ms	728 KB	Output is correct
12	Correct	82 ms	728 KB	Output is correct
13	Correct	75 ms	728 KB	Output is correct
14	Correct	83 ms	748 KB	Output is correct
15	Correct	80 ms	748 KB	Output is correct
16	Correct	81 ms	748 KB	Output is correct
17	Correct	80 ms	748 KB	Output is correct
18	Correct	102 ms	748 KB	Output is correct
19	Correct	89 ms	748 KB	Output is correct
20	Correct	90 ms	748 KB	Output is correct
21	Correct	91 ms	748 KB	Output is correct
22	Correct	81 ms	748 KB	Output is correct
23	Correct	138 ms	748 KB	Output is correct
24	Correct	60 ms	748 KB	Output is correct
25	Correct	80 ms	748 KB	Output is correct
26	Correct	64 ms	748 KB	Output is correct
27	Correct	52 ms	748 KB	Output is correct
28	Correct	84 ms	748 KB	Output is correct
29	Correct	41 ms	748 KB	Output is correct
30	Correct	48 ms	748 KB	Output is correct
31	Correct	61 ms	748 KB	Output is correct
32	Correct	43 ms	752 KB	Output is correct
33	Runtime error	2 ms	752 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	752 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	752 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	380 KB	Output is correct
2	Correct	17 ms	520 KB	Output is correct
3	Correct	76 ms	564 KB	Output is correct
4	Correct	80 ms	728 KB	Output is correct
5	Correct	15 ms	728 KB	Output is correct
6	Correct	74 ms	728 KB	Output is correct
7	Correct	74 ms	728 KB	Output is correct
8	Correct	16 ms	728 KB	Output is correct
9	Correct	93 ms	728 KB	Output is correct
10	Correct	77 ms	728 KB	Output is correct
11	Correct	75 ms	728 KB	Output is correct
12	Correct	82 ms	728 KB	Output is correct
13	Correct	75 ms	728 KB	Output is correct
14	Correct	83 ms	748 KB	Output is correct
15	Correct	80 ms	748 KB	Output is correct
16	Correct	81 ms	748 KB	Output is correct
17	Correct	80 ms	748 KB	Output is correct
18	Correct	102 ms	748 KB	Output is correct
19	Correct	89 ms	748 KB	Output is correct
20	Correct	90 ms	748 KB	Output is correct
21	Correct	91 ms	748 KB	Output is correct
22	Correct	81 ms	748 KB	Output is correct
23	Correct	138 ms	748 KB	Output is correct
24	Correct	60 ms	748 KB	Output is correct
25	Correct	80 ms	748 KB	Output is correct
26	Correct	64 ms	748 KB	Output is correct
27	Correct	52 ms	748 KB	Output is correct
28	Correct	84 ms	748 KB	Output is correct
29	Correct	41 ms	748 KB	Output is correct
30	Correct	48 ms	748 KB	Output is correct
31	Correct	61 ms	748 KB	Output is correct
32	Correct	43 ms	752 KB	Output is correct
33	Runtime error	2 ms	752 KB	Execution failed because the return code was nonzero
34	Halted	0 ms	0 KB	-

답안 #68660

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