제출 #110387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110387		tincamatei	Cultivation (JOI17_cultivation)	C++14	5 / 100	2040 ms	384 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300;

struct Cell {
	int l, c;
} v[MAX_N];

bool cmp(Cell a, Cell b) {
	return a.c < b.c;
}

struct Event {
	bool toerase;
	int l, c;

	inline bool operator< (const Event &x) const {
		return c < x.c || (c == x.c && toerase < x.toerase);
	}
};

multiset<int> vert;

static inline int getAbove(int x, int r) {
	multiset<int>::iterator it = vert.upper_bound(x);
	if(it == vert.end())
		return r + 1;
	else
		return *it;
}

static inline int getBelow(int x) {
	multiset<int>::iterator it = vert.lower_bound(x);
	if(it == vert.begin())
		return 0;
	else {
		it--;
		return *it;
	}
}

long long expand(int n, int r, int c, int expleft, int expright) {
	long long auxrez;
	auxrez = expleft + expright;
	vector<Event> toadd, toerase;
	vector<Event> events(2 * n);
			
	for(int k = 0; k < n; ++k) {
		toadd.push_back({0, v[k].l, max(1, v[k].c - expleft)});
		toerase.push_back({1, v[k].l, min(c, v[k].c + expright)});
	}
	merge(toadd.begin(), toadd.end(), toerase.begin(), toerase.end(), events.begin());
			
	int p1, p2;
	int expup, expdown, middle;

	expup = expdown = middle = 0;
	p1 = 0;
			
	for(int k = 0; k < n - 1; ++k)
		if(v[k + 1].c - v[k].c - 1 > expleft + expright)
			expup = expdown = middle = 1 << 30;
	vert.clear();

	while(p1 < events.size()) {
		p2 = p1;
		while(p2 < events.size() && events[p1].c == events[p2].c && !events[p2].toerase) {
			vert.insert(events[p2].l);
			++p2;
		}

		p2 = p1;
		while(p2 < events.size() && events[p1].c == events[p2].c) {
			int down, up;
			up = getBelow(events[p2].l);
			down = getAbove(events[p2].l, r);

			if(up == 0)
				expdown = max(expdown, events[p2].l - 1);
			else
				middle = max(middle, events[p2].l - up - 1);
			if(down == r + 1)
				expup = max(expup, r - events[p2].l);
			else
				middle = max(middle, up - events[p2].l - 1);
			++p2;
		}

		p2 = p1;
		while(p2 < events.size() && events[p1].c == events[p2].c) {
			if(events[p2].toerase)
				vert.erase(vert.find(events[p2].l));
			++p2;
		}
			
		p1 = p2;
	}
	
	return auxrez + max(middle, expup + expdown);
}

long long getsol(int n, int r, int c) {
	long long rez = 1LL << 35;
	
	int necleft, necright;
	necleft = necright = 1<<30;

	for(int i = 0; i < n; ++i) {
		necleft = min(necleft, v[i].c - 1);
		necright = min(necright, c - v[i].c);
	}

	for(int expleft = necleft; expleft <= c; ++expleft)
		for(int expright = necright; expright <= c; ++expright)
			rez = min(rez, expand(n, r, c, expleft, expright));

	return rez;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, r, c;
	fscanf(fin, "%d%d", &r, &c);
	fscanf(fin, "%d", &n);

	for(int i = 0; i < n; ++i)
		fscanf(fin, "%d%d", &v[i].l, &v[i].c);

	sort(v, v + n, cmp);

	fprintf(fout, "%lld", getsol(n, r, c));

	fclose(fin);
	fclose(fout);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'long long int expand(int, int, int, int, int)':
cultivation.cpp:67:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(p1 < events.size()) {
        ~~~^~~~~~~~~~~~~~~
cultivation.cpp:69:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2 < events.size() && events[p1].c == events[p2].c && !events[p2].toerase) {
         ~~~^~~~~~~~~~~~~~~
cultivation.cpp:75:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2 < events.size() && events[p1].c == events[p2].c) {
         ~~~^~~~~~~~~~~~~~~
cultivation.cpp:92:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2 < events.size() && events[p1].c == events[p2].c) {
         ~~~^~~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:132:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d", &r, &c);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:133:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
cultivation.cpp:136:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &v[i].l, &v[i].c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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