oj.uz

Submission #464508

# Submission time Handle Problem Language Result Execution time Memory
464508 2021-08-13T10:38:35 Z Quentolosse T-Covering (eJOI19_covering) C++14
25 / 100
 262 ms 4228 KB 
#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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 26 ms 588 KB Output is correct
4 Correct 82 ms 1504 KB Output is correct
5 Correct 256 ms 4220 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 26 ms 612 KB Output is correct
4 Correct 91 ms 1476 KB Output is correct
5 Correct 260 ms 4228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 432 KB Output is correct
3 Correct 26 ms 612 KB Output is correct
4 Correct 76 ms 1480 KB Output is correct
5 Correct 262 ms 4172 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 26 ms 588 KB Output is correct
4 Correct 82 ms 1504 KB Output is correct
5 Correct 256 ms 4220 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 8 ms 332 KB Output is correct
8 Correct 26 ms 612 KB Output is correct
9 Correct 91 ms 1476 KB Output is correct
10 Correct 260 ms 4228 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 8 ms 432 KB Output is correct
13 Correct 26 ms 612 KB Output is correct
14 Correct 76 ms 1480 KB Output is correct
15 Correct 262 ms 4172 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 26 ms 588 KB Output is correct
4 Correct 82 ms 1504 KB Output is correct
5 Correct 256 ms 4220 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 8 ms 332 KB Output is correct
8 Correct 26 ms 612 KB Output is correct
9 Correct 91 ms 1476 KB Output is correct
10 Correct 260 ms 4228 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 8 ms 432 KB Output is correct
13 Correct 26 ms 612 KB Output is correct
14 Correct 76 ms 1480 KB Output is correct
15 Correct 262 ms 4172 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -