Submission #21303

#	Time	Username	Problem	Language	Result	Execution time	Memory
21303		Ushio	Cultivation (JOI17_cultivation)	C++14	30 / 100	763 ms	262144 KiB

cultivation

#include <algorithm>
#include <iostream>
#include <vector>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int INF = 0x3f3f3f3f;

struct Cell {
    int x, y;
    Cell() = default;
    Cell(int _x, int _y):
        x(_x), y(_y) {}
};

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    vector<Cell> cells(k);
    for (int i = 0; i < k; ++i) {
        cin >> cells[i].x >> cells[i].y;
        cells[i].x--; cells[i].y--;
    }
    int64_t ans = 1LL << 62;
    for (int lenUp = 0; lenUp <= n; ++lenUp) {
        for (int lenDown = 0; lenDown <= n; ++lenDown) {
            vector<vector<int>> cols(n);
            for (const Cell& c: cells) {
                for (int i = 0; i <= lenUp && c.x - i >= 0; ++i) {
                    cols[c.x - i].push_back(c.y);
                }
                for (int i = 0; i <= lenDown && c.x + i < n; ++i) {
                    cols[c.x + i].push_back(c.y);
                }
            }
            bool ok = true;
            int lenLeft = 0, lenRight = 0;
            for (vector<int>& ccols: cols) {
                if (SZ(ccols) == 0) {
                    ok = false;
                    break;
                }
                sort(ccols.begin(), ccols.end());
                ccols.erase(unique(ccols.begin(), ccols.end()), ccols.end());
                lenLeft = max(lenLeft, ccols.front());
                lenRight = max(lenRight, m - 1 - ccols.back());
            }
            if (!ok) {
                continue;
            }
            int64_t cans = lenUp + lenDown + lenLeft + lenRight;
            int add = 0;
            for (const vector<int>& ccols: cols) {
                for (int i = 1; i < SZ(ccols); ++i) {
                    add = max(add,
                        (ccols[i] - lenLeft) - (ccols[i - 1] + lenRight) - 1);
                }
            }
            cans += add;
            ans = min(ans, cans);
        }
    }
    cout << ans << '\n';
}

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