Submission #21593

#	Time	Username	Problem	Language	Result	Execution time	Memory
21593		kingpig9	Cultivation (JOI17_cultivation)	C++11	30 / 100	416 ms	7240 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 310, MAXS = 1e5 + 10;

void setmin (int &a, int b) {
	if (a > b) {
		a = b;
	}
}

void setmax (int &a, int b) {
	if (a < b) {
		a = b;
	}
}

int R, C, N;
int X[MAXN], Y[MAXN];
set<int> sty[MAXS];

int main() {
	//monica lewinsky
	scanf("%d %d %d", &R, &C, &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &X[i], &Y[i]);
	}

	int ans = INT_MAX;
	for (int nup = 0; nup < R; nup++) {
		for (int i = 1; i <= R; i++) {
			sty[i].clear();
		}

		for (int i = 1; i <= N; i++) {
			for (int x = X[i]; x && x >= X[i] - nup; x--) {
				sty[x].insert(Y[i]);
			}
		}

		for (int ndown = 0; ndown < R; ndown++) {
			for (int i = 1; i <= N; i++) {
				int nx = ndown + X[i];
				if (nx <= R) {
					sty[nx].insert(Y[i]);
				}
			}

			//ok find the min difference
			bool bad = false;
			for (int i = 1; i <= R; i++) {
				if (sty[i].empty()) {
					bad = true;
					break;
				}
			}
			if (bad) {
				continue;
			}

			//left or right
			int nleft = 0, nright = 0;
			for (int i = 1; i <= R; i++) {
				setmax(nleft, *sty[i].begin()  - 1);
				setmax(nright, C - *sty[i].rbegin());
			}

			int nadd = 0;
			for (int i = 1; i <= R; i++) {
				for (auto it = sty[i].begin(); next(it) != sty[i].end(); it++) {
					int y1 = *it + nright, y2 = *next(it) - nleft;
					//how many are between those two
					setmax(nadd, y2 - y1 - 1);
				}
			}

			setmin(ans, nup + ndown + nleft + nright + nadd);
		}
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &R, &C, &N);
                               ^
cultivation.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &X[i], &Y[i]);
                               ^

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