답안 #68579 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68579	2018-08-17T11:37:40 Z	AdrienVannson	Cultivation (JOI17_cultivation)	C++14	15 / 100	290 ms	984 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 = 2*40;
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][NB_MAX_COLONNES];

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

            nbADroite[iLigne][iColonne] = 1;

            if (iColonne+1 < NB_MAX_COLONNES) {
                nbADroite[iLigne][iColonne] += nbADroite[iLigne][iColonne+1];
            }

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

    /*for (int iLigne=0; iLigne<10; iLigne++) {
        for (int iColonne=0; iColonne<10; iColonne++) {
            cerr << nbADroite[iLigne][iColonne] << " ";
        }
        cerr << "\n";
    }*/

    // Vérifier la validité
    for (int iColonne=0; iColonne<NB_MAX_COLONNES; iColonne++) {

        int iLigneDebut = -1; // Exclu (sur une cellule invalide)

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

            if (nbADroite[iLigneFin][iColonne] < 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);
        return 0;
    }


    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;
    }

    //cerr << getEstPossible(4, 1) << endl;

    int nbEtapesMin = +oo;

    for (int nbEtapesBas=0; nbEtapesBas<NB_MAX_LIGNES; nbEtapesBas++) {
        for (int nbEtapesDroite=0; nbEtapesDroite<NB_MAX_COLONNES; 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:96: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:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:115: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	214 ms	504 KB	Output is correct
2	Correct	227 ms	504 KB	Output is correct
3	Correct	216 ms	596 KB	Output is correct
4	Correct	215 ms	700 KB	Output is correct
5	Correct	216 ms	700 KB	Output is correct
6	Correct	217 ms	700 KB	Output is correct
7	Correct	219 ms	700 KB	Output is correct
8	Correct	215 ms	772 KB	Output is correct
9	Correct	215 ms	820 KB	Output is correct
10	Correct	221 ms	820 KB	Output is correct
11	Correct	223 ms	820 KB	Output is correct
12	Correct	227 ms	820 KB	Output is correct
13	Correct	226 ms	892 KB	Output is correct
14	Correct	223 ms	892 KB	Output is correct
15	Correct	217 ms	892 KB	Output is correct
16	Correct	214 ms	892 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	214 ms	504 KB	Output is correct
2	Correct	227 ms	504 KB	Output is correct
3	Correct	216 ms	596 KB	Output is correct
4	Correct	215 ms	700 KB	Output is correct
5	Correct	216 ms	700 KB	Output is correct
6	Correct	217 ms	700 KB	Output is correct
7	Correct	219 ms	700 KB	Output is correct
8	Correct	215 ms	772 KB	Output is correct
9	Correct	215 ms	820 KB	Output is correct
10	Correct	221 ms	820 KB	Output is correct
11	Correct	223 ms	820 KB	Output is correct
12	Correct	227 ms	820 KB	Output is correct
13	Correct	226 ms	892 KB	Output is correct
14	Correct	223 ms	892 KB	Output is correct
15	Correct	217 ms	892 KB	Output is correct
16	Correct	214 ms	892 KB	Output is correct
17	Correct	226 ms	932 KB	Output is correct
18	Correct	241 ms	932 KB	Output is correct
19	Correct	262 ms	932 KB	Output is correct
20	Correct	255 ms	932 KB	Output is correct
21	Correct	266 ms	984 KB	Output is correct
22	Correct	290 ms	984 KB	Output is correct
23	Correct	264 ms	984 KB	Output is correct
24	Correct	274 ms	984 KB	Output is correct
25	Correct	268 ms	984 KB	Output is correct
26	Correct	265 ms	984 KB	Output is correct
27	Correct	261 ms	984 KB	Output is correct
28	Correct	273 ms	984 KB	Output is correct
29	Correct	258 ms	984 KB	Output is correct
30	Correct	265 ms	984 KB	Output is correct
31	Correct	260 ms	984 KB	Output is correct
32	Correct	262 ms	984 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	214 ms	504 KB	Output is correct
2	Correct	227 ms	504 KB	Output is correct
3	Correct	216 ms	596 KB	Output is correct
4	Correct	215 ms	700 KB	Output is correct
5	Correct	216 ms	700 KB	Output is correct
6	Correct	217 ms	700 KB	Output is correct
7	Correct	219 ms	700 KB	Output is correct
8	Correct	215 ms	772 KB	Output is correct
9	Correct	215 ms	820 KB	Output is correct
10	Correct	221 ms	820 KB	Output is correct
11	Correct	223 ms	820 KB	Output is correct
12	Correct	227 ms	820 KB	Output is correct
13	Correct	226 ms	892 KB	Output is correct
14	Correct	223 ms	892 KB	Output is correct
15	Correct	217 ms	892 KB	Output is correct
16	Correct	214 ms	892 KB	Output is correct
17	Correct	226 ms	932 KB	Output is correct
18	Correct	241 ms	932 KB	Output is correct
19	Correct	262 ms	932 KB	Output is correct
20	Correct	255 ms	932 KB	Output is correct
21	Correct	266 ms	984 KB	Output is correct
22	Correct	290 ms	984 KB	Output is correct
23	Correct	264 ms	984 KB	Output is correct
24	Correct	274 ms	984 KB	Output is correct
25	Correct	268 ms	984 KB	Output is correct
26	Correct	265 ms	984 KB	Output is correct
27	Correct	261 ms	984 KB	Output is correct
28	Correct	273 ms	984 KB	Output is correct
29	Correct	258 ms	984 KB	Output is correct
30	Correct	265 ms	984 KB	Output is correct
31	Correct	260 ms	984 KB	Output is correct
32	Correct	262 ms	984 KB	Output is correct
33	Runtime error	2 ms	984 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	984 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	984 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	214 ms	504 KB	Output is correct
2	Correct	227 ms	504 KB	Output is correct
3	Correct	216 ms	596 KB	Output is correct
4	Correct	215 ms	700 KB	Output is correct
5	Correct	216 ms	700 KB	Output is correct
6	Correct	217 ms	700 KB	Output is correct
7	Correct	219 ms	700 KB	Output is correct
8	Correct	215 ms	772 KB	Output is correct
9	Correct	215 ms	820 KB	Output is correct
10	Correct	221 ms	820 KB	Output is correct
11	Correct	223 ms	820 KB	Output is correct
12	Correct	227 ms	820 KB	Output is correct
13	Correct	226 ms	892 KB	Output is correct
14	Correct	223 ms	892 KB	Output is correct
15	Correct	217 ms	892 KB	Output is correct
16	Correct	214 ms	892 KB	Output is correct
17	Correct	226 ms	932 KB	Output is correct
18	Correct	241 ms	932 KB	Output is correct
19	Correct	262 ms	932 KB	Output is correct
20	Correct	255 ms	932 KB	Output is correct
21	Correct	266 ms	984 KB	Output is correct
22	Correct	290 ms	984 KB	Output is correct
23	Correct	264 ms	984 KB	Output is correct
24	Correct	274 ms	984 KB	Output is correct
25	Correct	268 ms	984 KB	Output is correct
26	Correct	265 ms	984 KB	Output is correct
27	Correct	261 ms	984 KB	Output is correct
28	Correct	273 ms	984 KB	Output is correct
29	Correct	258 ms	984 KB	Output is correct
30	Correct	265 ms	984 KB	Output is correct
31	Correct	260 ms	984 KB	Output is correct
32	Correct	262 ms	984 KB	Output is correct
33	Runtime error	2 ms	984 KB	Execution failed because the return code was nonzero
34	Halted	0 ms	0 KB	-

답안 #68579

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