oj.uz

Submission #27834

# Submission time Handle Problem Language Result Execution time Memory
27834 2017-07-14T07:39:33 Z suhgyuho_william Cultivation (JOI17_cultivation) C++14
5 / 100
 2000 ms 2172 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){
    if(l+r >= ans) return;
	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)+1,-a[i].y});
	}
	sort(tmp.begin(),tmp.end());
	if(tmp[0].first != 1 || tmp.back().first != R+1) return;
	for(int i=0; i<tmp.size(); i++){
        int e;
        for(int j=i; j<tmp.size(); j++){
            if(tmp[i].first != tmp[j].first) break;
            e = j;
        }
        for(int j=i; j<=e; j++){
            if(tmp[j].second > 0) S.insert(tmp[j].second);
            else S.erase(S.find(-tmp[j].second));
        }
        if(S.empty() && tmp[i].first <= R) return;
        if(S.empty()) break;
        auto it = S.end(); it--;
        ly = max(ly,*S.begin()-1);
        ry = max(ry,C-(*it));
        lld bef;
        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,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;
	vector<int> X;
	a[N+1].x = R+1;
	for(int i=0; i<N+1; i++){
        for(int j=i+1; j<=min(N+1,i+10); j++){
            X.pb(a[j].x-a[i].x);
            X.pb(a[j].x-a[i].x+1);
            X.pb(max((lld)0,a[j].x-a[i].x-1));
        }
	}
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	for(auto &i : X){
		for(auto &j : X){
			process(i,j);
		}
	}
	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:36:23: 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:71: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:71:32: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
cultivation.cpp:69: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:71: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:40:23: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
         for(int j=i; j<=e; j++){
                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 0 ms 2032 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 0 ms 2032 KB Output is correct
10 Correct 0 ms 2032 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct
13 Correct 0 ms 2032 KB Output is correct
14 Correct 0 ms 2032 KB Output is correct
15 Correct 0 ms 2032 KB Output is correct
16 Correct 0 ms 2032 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 0 ms 2032 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 0 ms 2032 KB Output is correct
10 Correct 0 ms 2032 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct
13 Correct 0 ms 2032 KB Output is correct
14 Correct 0 ms 2032 KB Output is correct
15 Correct 0 ms 2032 KB Output is correct
16 Correct 0 ms 2032 KB Output is correct
17 Correct 0 ms 2032 KB Output is correct
18 Correct 0 ms 2032 KB Output is correct
19 Correct 3 ms 2032 KB Output is correct
20 Correct 0 ms 2032 KB Output is correct
21 Correct 3 ms 2032 KB Output is correct
22 Correct 3 ms 2032 KB Output is correct
23 Correct 0 ms 2032 KB Output is correct
24 Correct 3 ms 2172 KB Output is correct
25 Incorrect 3 ms 2172 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 0 ms 2032 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 0 ms 2032 KB Output is correct
10 Correct 0 ms 2032 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct
13 Correct 0 ms 2032 KB Output is correct
14 Correct 0 ms 2032 KB Output is correct
15 Correct 0 ms 2032 KB Output is correct
16 Correct 0 ms 2032 KB Output is correct
17 Correct 0 ms 2032 KB Output is correct
18 Correct 0 ms 2032 KB Output is correct
19 Correct 3 ms 2032 KB Output is correct
20 Correct 0 ms 2032 KB Output is correct
21 Correct 3 ms 2032 KB Output is correct
22 Correct 3 ms 2032 KB Output is correct
23 Correct 0 ms 2032 KB Output is correct
24 Correct 3 ms 2172 KB Output is correct
25 Incorrect 3 ms 2172 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 2032 KB Output is correct
2 Execution timed out 2000 ms 2032 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 2032 KB Output is correct
2 Execution timed out 2000 ms 2032 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 0 ms 2032 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 0 ms 2032 KB Output is correct
10 Correct 0 ms 2032 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct
13 Correct 0 ms 2032 KB Output is correct
14 Correct 0 ms 2032 KB Output is correct
15 Correct 0 ms 2032 KB Output is correct
16 Correct 0 ms 2032 KB Output is correct
17 Correct 0 ms 2032 KB Output is correct
18 Correct 0 ms 2032 KB Output is correct
19 Correct 3 ms 2032 KB Output is correct
20 Correct 0 ms 2032 KB Output is correct
21 Correct 3 ms 2032 KB Output is correct
22 Correct 3 ms 2032 KB Output is correct
23 Correct 0 ms 2032 KB Output is correct
24 Correct 3 ms 2172 KB Output is correct
25 Incorrect 3 ms 2172 KB Output isn't correct
26 Halted 0 ms 0 KB -