oj.uz

Submission #1071404

# Submission time Handle Problem Language Result Execution time Memory
1071404 2024-08-23T07:11:00 Z 김은성(#11136) Cultivation (JOI17_cultivation) C++17
35 / 100
 2000 ms 668 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1.557e18;
vector<pair<ll, ll> > points;
ll r, c;
ll minc(ll rd, ll ru){
	vector<ll> crit;
	for(auto [y, x]: points){
		crit.push_back(max(y - rd, 1ll));
		crit.push_back(min(y + ru, r) + 1);
	}
	crit.push_back(1);
	crit.push_back(r+1);
	sort(crit.begin(), crit.end());
	crit.erase(unique(crit.begin(), crit.end()), crit.end());
	crit.pop_back();
	int sz = crit.size(), i, j;
	vector<vector<ll> > row(sz);
	for(auto [y, x]: points){
		int lo = lower_bound(crit.begin(), crit.end(), max(y - rd, 1ll)) - crit.begin();
		int hi = lower_bound(crit.begin(), crit.end(), min(y + ru, r) + 1) - crit.begin() - 1;
		for(i=lo; i<=hi; i++)
			row[i].push_back(x);
	}
	ll cd = 0, cu = 0, sum = 0;
	for(i=0; i<sz; i++){
		sort(row[i].begin(), row[i].end());
		if(row[i].empty()){
			sum = INF;
			break;
		}
		cd = max(cd, row[i].front() - 1);
		cu = max(cu, c - row[i].back());
		for(j=0; j+1<row[i].size(); j++){
			sum = max(sum, row[i][j+1] - row[i][j] - 1);
		}
	}
	return max(cd + cu, sum);
}
int main(){
	ll y, x, rd, ru;
	int n, i, j;
	scanf("%lld %lld %d", &r, &c, &n);
	for(i=1; i<=n; i++){
		scanf("%lld %lld", &y, &x);
		points.push_back(make_pair(y, x));
	}
	vector<ll> critd, critu, critdu;
	for(auto [y, x]: points){
		critd.push_back(y - 1);
		critu.push_back(r - y);
	}
	for(auto [y1, x1]: points){
		for(auto [y2, x2]: points){
			critdu.push_back(abs(y2-y1) - 1);
		}
	}
	ll ans = INF;
	for(auto rd: critd){
		for(auto ru: critu){
			ans = min(ans, rd + ru + minc(rd, ru));
		}
	}
	for(auto rd: critd){
		for(auto temp: critdu){
			ru = temp - rd;
			if(ru >= 0)
				ans = min(ans, rd + ru + minc(rd, ru));
		}
	}
	for(auto ru: critu){
		for(auto temp: critdu){
			rd = temp - ru;
			if(rd >= 0)
				ans = min(ans, rd + ru + minc(rd, ru));
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

cultivation.cpp: In function 'll minc(ll, ll)':
cultivation.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(j=0; j+1<row[i].size(); j++){
      |            ~~~^~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:43:12: warning: unused variable 'j' [-Wunused-variable]
   43 |  int n, i, j;
      |            ^
cultivation.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%lld %lld %d", &r, &c, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%lld %lld", &y, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 14 ms 348 KB Output is correct
18 Execution timed out 2061 ms 348 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 14 ms 348 KB Output is correct
18 Execution timed out 2061 ms 348 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 348 KB Output is correct
2 Correct 79 ms 348 KB Output is correct
3 Correct 109 ms 488 KB Output is correct
4 Correct 78 ms 460 KB Output is correct
5 Correct 82 ms 344 KB Output is correct
6 Correct 105 ms 460 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 69 ms 456 KB Output is correct
9 Correct 57 ms 344 KB Output is correct
10 Correct 111 ms 348 KB Output is correct
11 Correct 92 ms 464 KB Output is correct
12 Correct 87 ms 344 KB Output is correct
13 Correct 35 ms 348 KB Output is correct
14 Correct 59 ms 348 KB Output is correct
15 Correct 7 ms 348 KB Output is correct
16 Correct 91 ms 348 KB Output is correct
17 Correct 124 ms 344 KB Output is correct
18 Correct 8 ms 348 KB Output is correct
19 Correct 87 ms 480 KB Output is correct
20 Correct 72 ms 344 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 348 KB Output is correct
2 Correct 79 ms 348 KB Output is correct
3 Correct 109 ms 488 KB Output is correct
4 Correct 78 ms 460 KB Output is correct
5 Correct 82 ms 344 KB Output is correct
6 Correct 105 ms 460 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 69 ms 456 KB Output is correct
9 Correct 57 ms 344 KB Output is correct
10 Correct 111 ms 348 KB Output is correct
11 Correct 92 ms 464 KB Output is correct
12 Correct 87 ms 344 KB Output is correct
13 Correct 35 ms 348 KB Output is correct
14 Correct 59 ms 348 KB Output is correct
15 Correct 7 ms 348 KB Output is correct
16 Correct 91 ms 348 KB Output is correct
17 Correct 124 ms 344 KB Output is correct
18 Correct 8 ms 348 KB Output is correct
19 Correct 87 ms 480 KB Output is correct
20 Correct 72 ms 344 KB Output is correct
21 Execution timed out 2007 ms 668 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 14 ms 348 KB Output is correct
18 Execution timed out 2061 ms 348 KB Time limit exceeded
19 Halted 0 ms 0 KB -