답안 #59859 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59859	2018-07-23T08:11:46 Z	koosaga(#1721)	Cultivation (JOI17_cultivation)	C++11	5 / 100	2000 ms	1120 KB

cultivation

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 305;

int n, r, c;
pi a[MAXN];

struct sweep{
	int pos, val, mode;
	bool operator<(const sweep &s)const{
		return pi(pos, -mode) < pi(s.pos, -s.mode);
	}
};

lint Do(int i, int j){
	vector<sweep> sw;
	for(int k=0; k<n; k++){
		int le = max(1, a[k].first - i);
		int ri = min(r, a[k].first + j);
		int v = a[k].second;
		sw.push_back({le, v, +1});
		sw.push_back({ri + 1, v, -1});
	}
	vector<int> v = {1, r + 1};
	for(int i=0; i<sw.size(); i++){ 
		v.push_back(sw[i].pos);
	}
	sort(sw.begin(), sw.end());
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	multiset<int> s;
	int ptr = 0;
	int lv = 0, rv = 0, sum = 0;
	for(int i=0; i+1<v.size(); i++){
		while(ptr < sw.size() && sw[ptr].pos == v[i]){
			if(sw[ptr].mode == 1) s.insert(sw[ptr].val);
			else s.erase(s.find(sw[ptr].val));
			ptr++;
		}
		if(s.size() == 0) return 1e18;
		lv = max(lv, *s.begin() - 1);
		rv = max(rv, c - *s.rbegin());
		auto it = s.begin();
		while(next(it) != s.end()){
			auto in = next(it);
			sum = max(*in - *it - 1, sum);
			it = in;
		}
	}
	return 1ll * max(lv + rv, sum) + i + j;
}

lint solve(){
	lint ans = 1e18;
	sort(a, a+n);
	for(int i=0; i<n; i++){
		int l = a[i].first - 1;
		vector<int> v;
		for(int j=0; j<n; j++){
			for(int k=j; k<n; k++){
				if(a[k].first - a[j].first >= l) v.push_back(a[k].first - a[j].first - l);
			}
			v.push_back(r - a[j].first);
		}
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
		for(auto &j : v){
			ans = min(ans, Do(l, j));
		}
	}
	return ans;
}

int main(){
	cin >> r >> c >> n;
	for(int i=0; i<n; i++){
		cin >> a[i].first >> a[i].second;
	}
	lint ans = solve();
	for(int i=0; i<n; i++) a[i].first = r + 1 - a[i].first;
	ans = min(ans, solve());
	cout << ans << endl;
}

Compilation message

cultivation.cpp: In function 'lint Do(int, int)':
cultivation.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<sw.size(); i++){
               ~^~~~~~~~~~
cultivation.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i+1<v.size(); i++){
               ~~~^~~~~~~~~
cultivation.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < sw.size() && sw[ptr].pos == v[i]){
         ~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	580 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	2 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	4 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	3 ms	624 KB	Output is correct
12	Correct	3 ms	624 KB	Output is correct
13	Correct	3 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	3 ms	624 KB	Output is correct
16	Correct	3 ms	624 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	580 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	2 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	4 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	3 ms	624 KB	Output is correct
12	Correct	3 ms	624 KB	Output is correct
13	Correct	3 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	3 ms	624 KB	Output is correct
16	Correct	3 ms	624 KB	Output is correct
17	Correct	6 ms	624 KB	Output is correct
18	Correct	98 ms	748 KB	Output is correct
19	Correct	17 ms	748 KB	Output is correct
20	Correct	5 ms	748 KB	Output is correct
21	Correct	92 ms	748 KB	Output is correct
22	Correct	573 ms	764 KB	Output is correct
23	Correct	15 ms	764 KB	Output is correct
24	Correct	1778 ms	1056 KB	Output is correct
25	Correct	926 ms	1056 KB	Output is correct
26	Execution timed out	2048 ms	1120 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	580 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	2 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	4 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	3 ms	624 KB	Output is correct
12	Correct	3 ms	624 KB	Output is correct
13	Correct	3 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	3 ms	624 KB	Output is correct
16	Correct	3 ms	624 KB	Output is correct
17	Correct	6 ms	624 KB	Output is correct
18	Correct	98 ms	748 KB	Output is correct
19	Correct	17 ms	748 KB	Output is correct
20	Correct	5 ms	748 KB	Output is correct
21	Correct	92 ms	748 KB	Output is correct
22	Correct	573 ms	764 KB	Output is correct
23	Correct	15 ms	764 KB	Output is correct
24	Correct	1778 ms	1056 KB	Output is correct
25	Correct	926 ms	1056 KB	Output is correct
26	Execution timed out	2048 ms	1120 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	1120 KB	Output is correct
2	Correct	43 ms	1120 KB	Output is correct
3	Correct	57 ms	1120 KB	Output is correct
4	Correct	53 ms	1120 KB	Output is correct
5	Correct	44 ms	1120 KB	Output is correct
6	Incorrect	33 ms	1120 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	1120 KB	Output is correct
2	Correct	43 ms	1120 KB	Output is correct
3	Correct	57 ms	1120 KB	Output is correct
4	Correct	53 ms	1120 KB	Output is correct
5	Correct	44 ms	1120 KB	Output is correct
6	Incorrect	33 ms	1120 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	580 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	2 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	4 ms	624 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	3 ms	624 KB	Output is correct
12	Correct	3 ms	624 KB	Output is correct
13	Correct	3 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	3 ms	624 KB	Output is correct
16	Correct	3 ms	624 KB	Output is correct
17	Correct	6 ms	624 KB	Output is correct
18	Correct	98 ms	748 KB	Output is correct
19	Correct	17 ms	748 KB	Output is correct
20	Correct	5 ms	748 KB	Output is correct
21	Correct	92 ms	748 KB	Output is correct
22	Correct	573 ms	764 KB	Output is correct
23	Correct	15 ms	764 KB	Output is correct
24	Correct	1778 ms	1056 KB	Output is correct
25	Correct	926 ms	1056 KB	Output is correct
26	Execution timed out	2048 ms	1120 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

답안 #59859

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0