Submission #464508

#TimeUsernameProblemLanguageResultExecution timeMemory
464508QuentolosseT-Covering (eJOI19_covering)C++14
25 / 100
262 ms4228 KiB
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main ()
{
    int nbCol, nbLignes, total = 0;
    bool non = false;
    cin >> nbLignes >> nbCol;
    vector<vector<int>> cases;
    for (int i = 0; i < nbLignes; i++)
    {
        vector<int> ligne;
        for (int i = 0; i < nbCol; i++)
        {
            int entree;
            cin >> entree;
            ligne.push_back(entree);
        }
        cases.push_back(ligne);
    }
    vector<pair<int,int>> casesSpeciales;
    int nbCasesSpeciales;
    cin >> nbCasesSpeciales;
    for (int i = 0; i < nbCasesSpeciales; i++)
    {
        pair<int,int> entree;
        cin >> entree.first >> entree.second;
        casesSpeciales.push_back(entree);
        total += cases[entree.first][entree.second];
        cases[entree.first][entree.second] = -2;
    }
    for (int i = 0; i < nbCasesSpeciales; i++)
    {
        int ligne = casesSpeciales[i].first, colonne = casesSpeciales[i].second;
        vector<int> lig = {-1, 0, 0, 1}, col = {0, -1, 1, 0}, ligDiag = {-1, 1, -1, 1}, colDiag = {-1, -1, 1, 1};
        int nb1 = 0, nb2 = 0;
        pair<int,int> autreCase, casePasPrise;
        casePasPrise.first = -1; casePasPrise.second = -1;
        for (int i = 0; i < 4; i++)
        {
            if (ligne + lig[i] < nbLignes && ligne + lig[i] > -1 && colonne + col[i] < nbCol && colonne + col[i] > -1)
            {
                if (cases[ligne + lig[i]][colonne + col[i]] < 0)
                {
                    nb1 ++;
                }
            }
            else
            {
                nb1 ++;
            }
            if (ligne + ligDiag[i] < nbLignes && ligne + ligDiag[i] > 0 -1 && colonne + colDiag[i] < nbCol && colonne + colDiag[i] > -1)
            {
                if (cases[ligne + ligDiag[i]][colonne + colDiag[i]] < -1)
                {
                    nb2 ++;
                    autreCase.first = ligne + ligDiag[i];
                    autreCase.second = colonne + colDiag[i];
                }
            }
        }
        if (nb1 > 1 || nb2 > 1)
        {
            cout << "No";
            non = true;
            break;
        }
        if (nb2 == 1)
        {
            casePasPrise.first = autreCase.first;
            casePasPrise.second = colonne;
        }
        else
        {
            int min = 1001;
            for (int i = 0; i < 4; i++)
            {
                if (ligne + lig[i] < nbLignes && ligne + lig[i] > -1 && colonne + col[i] < nbCol && colonne + col[i] > -1)
                {
                    if (cases[ligne + lig [i]][colonne + col [i]] < min)
                    {
                        casePasPrise.first = ligne + lig [i];
                        casePasPrise.second = colonne + col [i];
                        min = cases[ligne + lig [i]][colonne + col [i]];
                    }
                }
                else
                {
                    casePasPrise.first = -1; casePasPrise.second = -1;
                    break;
                }
                
            }
        }
        for (int i = 0; i < 4; i++)
        {
            if (ligne + lig[i] < nbLignes && ligne + lig[i] > -1 && colonne + col[i] < nbCol && colonne + col[i] > -1 && (ligne + lig[i] != casePasPrise.first || colonne + col[i] != casePasPrise.second))
            {
                total += cases[ligne + lig[i]][colonne + col[i]];
            } 
        }
    }
    if (!non)
    {
        cout << total;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...