Submission #550676

#	Time	Username	Problem	Language	Result	Execution time	Memory
550676		LucaDantas	Cultivation (JOI17_cultivation)	C++17	15 / 100	2075 ms	1012 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;

constexpr int maxr = 41, maxn = 310, inf = 0x3f3f3f3f;

int n, r, c;

set<int> mark[maxr]; // salvo pra cada linha quais colunas tão ativas

struct par {
    int r, c;
} pares[maxn];

int get(int cima, int baixo) {
    // painting
    
    for(int i = 0; i < maxr; i++)
        mark[i].clear();

    for(int i = 0; i < n; i++)
        mark[pares[i].r].insert(pares[i].c);

    for(int row = 1; row < r; row++)
        for(int coluna : mark[row])
            for(int j = 1; j <= cima && row - j >= 0 && !mark[row-j].count(coluna); j++)
                mark[row-j].insert(coluna);

    for(int row = r-2; row >= 0; row--)
        for(int coluna : mark[row])
            for(int j = 1; j <= baixo && row + j < r && !mark[row+j].count(coluna); j++)
                mark[row+j].insert(coluna);

    // Tudo pintado pra cima e pra baixo agora vou ver quanto eu preciso pra pintar pros lados

    // Calculo a resposta separadamente pra cada linha

    int minSum = 0, minL = 0, minR = 0;
    for(int row = 0; row < r; row++) {
        if(!mark[row].size()) return inf; // pessimo
        minL = max(minL, *mark[row].begin());
        minR = max(minR, c-1 - *mark[row].rbegin());
        while(mark[row].size() >= 2)
            minSum = max(minSum, *next(mark[row].begin()) - *mark[row].begin() - 1), mark[row].erase(mark[row].begin());
    }

    return max(minSum, minL + minR);
}

int main() {
    scanf("%d %d", &r, &c);
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &pares[i].r, &pares[i].c), --pares[i].r, --pares[i].c;

    // printf("%d\n", get(0, 2));

    int ans = inf;
    for(int cima = 0; cima < maxr; cima++)
        for(int baixo = 0; baixo < maxr; baixo++)
            ans = min(ans, cima + baixo + get(cima, baixo));
    
    printf("%d\n", ans);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d", &r, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~
cultivation.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
cultivation.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d", &pares[i].r, &pares[i].c), --pares[i].r, --pares[i].c;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20