Submission #550680

#	Time	Username	Problem	Language	Result	Execution time	Memory
550680		LucaDantas	Cultivation (JOI17_cultivation)	C++17	30 / 100	875 ms	916 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() {
    // 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());
        for(auto it = mark[row].begin(); next(it) != mark[row].end(); ++it)
            minSum = max(minSum, *next(it) - *it - 1);
    }

    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;

    int ans = inf;
    for(int cima = 0; cima < r; cima++) {
        // painting
    
        for(int i = 0; i < r; 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 j = 1; j <= cima && row - j >= 0; j++)
                for(int coluna : mark[row])
                        mark[row-j].insert(coluna);

        for(int baixo = 0; baixo < r; baixo++) {
            ans = min(ans, cima + baixo + get());

            for(int row = r-2; row >= 0; row--)
                for(int coluna : mark[row])
                    mark[row+1].insert(coluna);
        }
    }
    
    printf("%d\n", ans);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d", &r, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~
cultivation.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
cultivation.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         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: 15 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20