Submission #1071055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071055		thinknoexit	Cultivation (JOI17_cultivation)	C++17	30 / 100	315 ms	796 KiB

cultivation

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 303;
int s[N], e[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int r, c;
    cin >> r >> c;
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> s[i] >> e[i];
    // iterate for all O(n ^ 2)
    ll mn = LLONG_MAX;
    for (int u = 0;u < r;u++) {
        for (int d = 0;d < r;d++) {
            bool ch = 1;
            int mx = 0;
            int dl = 0, dr = 0;
            multiset<int> ms;
            vector<vector<int>> event(r + 1);
            for (int i = 1;i <= n;i++) {
                for (int j = max(1, s[i] - u);j <= min(r, s[i] + d);j++)
                    event[j].push_back(e[i]);
            }
            for (int i = 1;i <= r;i++) {
                sort(event[i].begin(), event[i].end());
                event[i].resize(unique(event[i].begin(), event[i].end()) - event[i].begin());
                if (event[i].empty()) {
                    ch = 0;
                    break;
                }
                int sz = event[i].size();
                for (int j = 0;j < sz - 1;j++) {
                    mx = max(mx, event[i][j + 1] - event[i][j] - 1);
                }
                dl = max(dl, event[i][0] - 1);
                dr = max(dr, c - event[i][sz - 1]);
            }
            if (ch) {
                mn = min(mn, 0ll + u + d + max(dl + dr, mx));
                //cout << u << ' ' << d << ' ' << dl << ' ' << dr << ' ' << mx << '\n';
            }
        }
    }
    cout << mn << '\n';
    return 0;
}

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