oj.uz

Submission #27820

# Submission time Handle Problem Language Result Execution time Memory
27820 2017-07-14T07:13:09 Z 서규호(#1160) Cultivation (JOI17_cultivation) C++14
0 / 100
 2000 ms 2032 KB 
#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007LL

using namespace std;

int N; lld R,C,ans;
struct data{
	lld x,y;
}a[302];
multiset<lld> S;

void process(lld l,lld r){
	lld ly,ry,lry;
	ly = ry = lry = 0;

	vector<pll> tmp;
	for(int i=1; i<=N; i++){
		tmp.pb({max((lld)1,a[i].x-l),-a[i].y});
		tmp.pb({min(R,a[i].x+r),a[i].y});
	}
	sort(tmp.begin(),tmp.end());
	if(tmp.back().first != R) return;
	lld bef = 0;
	for(int i=0; i<tmp.size(); i++){
		if(tmp[i].second > 0){
			S.erase(S.find(tmp[i].second));
			bef = tmp[i].first;
			if(S.empty()) continue;
			{
			    auto it = S.end(); it--;
                ly = max(ly,*S.begin()-1);
                ry = max(ry,C-(*it));
                for(it = S.begin(); it != S.end(); it++){
                    if(it == S.begin()){
                        bef = *it;
                        continue;
                    }
                    lry = max(lry,*it-bef-1);
                    bef = *it;
                }
			}
			continue;
		}
		if(S.empty() && bef+1 < tmp[i].first) return;
		bef = tmp[i].first;
		int e;
		for(int j=i; j<tmp.size(); j++){
			if(tmp[j].first != tmp[i].first || tmp[j].second > 0) break;
			e = j;
		}
		for(int j=i; j<=e; j++){
			S.insert(-tmp[j].second);
		}
		auto it = S.end(); it--;
		ly = max(ly,*S.begin()-1);
		ry = max(ry,C-(*it));
		for(it = S.begin(); it != S.end(); it++){
			if(it == S.begin()){
				bef = *it;
				continue;
			}
			lry = max(lry,*it-bef-1);
			bef = *it;
		}
		i = e;
	}
	if(ly > ry) swap(ly,ry);
	if(ly+ry < lry){
		ry = lry-ly;
	}
	ans = min(ans,min(l,r)+min(ly,ry)+l+r+ly+ry);
}

int main(){
    //freopen("input.txt","r",stdin);
	scanf("%lld %lld %d",&R,&C,&N);
	for(int i=1; i<=N; i++){
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+N+1,[&](data &x,data &y){
		return x.x < y.x;
	});
	ans = Linf;
	for(int i=0; i<=R-1; i++){
		for(int j=0; j<=R-1; j++){
			process(i,j);
		}
	}
	process(3,0);
	printf("%lld\n",ans);

	return 0;
}

Compilation message

cultivation.cpp: In function 'void process(long long int, long long int)':
cultivation.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<tmp.size(); i++){
                ^
cultivation.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i; j<tmp.size(); j++){
                 ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:88:32: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d %d",&a[i].x,&a[i].y);
                                ^
cultivation.cpp:88:32: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
cultivation.cpp:86:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %d",&R,&C,&N);
                                ^
cultivation.cpp:88:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].x,&a[i].y);
                                 ^
cultivation.cpp: In function 'void process(long long int, long long int)':
cultivation.cpp:61:17: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   for(int j=i; j<=e; j++){
                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2032 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2032 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2032 KB Output isn't correct
2 Halted 0 ms 0 KB -