Submission #47693

#	Time	Username	Problem	Language	Result	Execution time	Memory
47693		maksim_gaponov	Cultivation (JOI17_cultivation)	C++14	30 / 100	2053 ms	1120 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void openFiles() {
#ifdef KEK
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif
}

void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const ll INF = 1e12 + 10;
const int MAXN = 300;
const int MAX = 40;
ll x[MAXN], y[MAXN];

int main() {
	openFiles();
	IOoptimize();
    ll r, c;
    cin >> r >> c;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    ll ans = INF;
    for (ll up = 0; up <= r; up++)
    for (ll dn = 0; dn <= r; dn++) {
        //cout << up << " " << dn << "\n";
        ll we = 0;
        ll w = 0;
        ll e = 0;
        for (int i = 0; i < r; i++) {
            vector<ll> pos;
            for (int j = 0; j < n; j++) {
                if (x[j] - up <= i && i <= x[j] + dn)
                    pos.push_back(y[j]);
            }
            if (pos.size() == 0) {
                we = INF;
            }
            else {
                sort(pos.begin(), pos.end());
                for (int j = 1; j < pos.size(); j++) {
                    we = max(we, pos[j] - pos[j - 1] - 1);
                }
                w = max(w, pos[0]);
                e = max(e, c - pos.back() - 1);
            }
        }
        //cout << w << " " << e << " " << we << "\n";
        we = max(we, w + e);
        //cout << we << "\n";
        ans = min(ans, up + dn + we);
    }
    cout << ans;
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:54:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 1; j < pos.size(); j++) {
                                 ~~^~~~~~~~~~~~

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