제출 #110488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110488		tincamatei	Cultivation (JOI17_cultivation)	C++14	15 / 100	2059 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.l < b.l;
}

struct Range {
	int l, r, dep;
	
	inline bool operator< (const Range &x) const {
		return l < x.l;
	}
};

int dif;
set<Range> ranges;

int expup, expdown, middle;

void insertRange(int l, int r, int dep) {
	set<Range>::iterator it, it2;
	vector<Range> toerase, toadd;

	it = ranges.lower_bound({l, 0, 0});
	if(it != ranges.begin()) {
		it2 = it;
		it2--;

		if(it2->r >= l) {
			if(it2->dep == 0)
				expup = max(expup, dep - it2->dep - 1);
			else
				middle = max(middle, dep - it2->dep - 1);
	
			toerase.push_back(*it2);
			if(it2->l < l)
				toadd.push_back({it2->l, l - 1, it2->dep});
			if(it2->r > r)
				toadd.push_back({r + 1, it2->r, it2->dep});
		}
	}

	while(it != ranges.end() && it->l <= r) {
		toerase.push_back(*it);
		
		if(it->dep == 0)
			expup = max(expup, dep - it->dep - 1);
		else
			middle = max(middle, dep - it->dep - 1);
		
		if(it->r > r)
			toadd.push_back({r + 1, it->r, it->dep});
		it++;
	}

	toadd.push_back({l, r, dep});

	for(auto it: toerase)
		ranges.erase(it);
	for(auto it: toadd)
		ranges.insert(it);
}

long long expand(int n, int r, int c, int expleft, int expright) {
	ranges.clear();
	ranges.insert({1, c, 0});
	
	expup = expdown = middle = 0;
	
	for(int i = 0; i < n; ++i) {
		insertRange(max(1, v[i].c - expleft), min(c, v[i].c + expright), v[i].l);
	}

	for(auto it: ranges)
		if(it.dep == 0) // empty gap
			return 1LL << 35;
		else
			expdown = max(expdown, r - it.dep);

	return expleft + expright + max(middle, expup + expdown);
}

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

	necleft = necright = 1000000001;

	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 'int main()':
cultivation.cpp:119: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:120: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:123: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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20