oj.uz

Submission #619920

# Submission time Handle Problem Language Result Execution time Memory
619920 2022-08-02T17:15:08 Z errorgorn Zemljište (COCI22_zemljiste) C++17
70 / 70
 805 ms 4748 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,a,b;
int arr[505][505];
int pref[505];

int calc(int i){
	return abs(i-a)+abs(i-b);
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m>>a>>b;
	if (a>b) swap(a,b);
	
	rep(x,1,n+1){
		rep(y,1,m+1) cin>>arr[x][y];
	}
	
	int ans=1e18;
	rep(l,1,n+1){
		rep(y,1,m+1) pref[y]=0;
		rep(x,l,n+1){
			rep(y,1,m+1) pref[y]+=arr[x][y];
			rep(y,1,m+1) pref[y]+=pref[y-1];
			
			int c=1;
			rep(y,0,m+1){
				while (c<m && pref[c]-pref[y]<a) c++;
				ans=min({ans,calc(pref[c]-pref[y]),calc(pref[c-1]-pref[y])});
			}
			
			rep(y,m+1,1) pref[y]-=pref[y-1];
		}
	}
	
	cout<<ans<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 656 KB Output is correct
11 Correct 9 ms 732 KB Output is correct
12 Correct 9 ms 832 KB Output is correct
13 Correct 9 ms 832 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 7 ms 724 KB Output is correct
16 Correct 7 ms 724 KB Output is correct
17 Correct 9 ms 720 KB Output is correct
18 Correct 6 ms 724 KB Output is correct
19 Correct 8 ms 724 KB Output is correct
20 Correct 7 ms 724 KB Output is correct
21 Correct 9 ms 724 KB Output is correct
22 Correct 6 ms 712 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 656 KB Output is correct
11 Correct 9 ms 732 KB Output is correct
12 Correct 9 ms 832 KB Output is correct
13 Correct 9 ms 832 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 7 ms 724 KB Output is correct
16 Correct 7 ms 724 KB Output is correct
17 Correct 9 ms 720 KB Output is correct
18 Correct 6 ms 724 KB Output is correct
19 Correct 8 ms 724 KB Output is correct
20 Correct 7 ms 724 KB Output is correct
21 Correct 9 ms 724 KB Output is correct
22 Correct 6 ms 712 KB Output is correct
23 Correct 647 ms 4712 KB Output is correct
24 Correct 634 ms 4720 KB Output is correct
25 Correct 603 ms 4728 KB Output is correct
26 Correct 675 ms 4720 KB Output is correct
27 Correct 445 ms 3888 KB Output is correct
28 Correct 632 ms 4720 KB Output is correct
29 Correct 701 ms 4724 KB Output is correct
30 Correct 721 ms 4720 KB Output is correct
31 Correct 105 ms 2388 KB Output is correct
32 Correct 687 ms 4720 KB Output is correct
33 Correct 649 ms 4720 KB Output is correct
34 Correct 686 ms 4716 KB Output is correct
35 Correct 660 ms 4716 KB Output is correct
36 Correct 789 ms 4712 KB Output is correct
37 Correct 772 ms 4724 KB Output is correct
38 Correct 731 ms 4716 KB Output is correct
39 Correct 787 ms 4748 KB Output is correct
40 Correct 763 ms 4716 KB Output is correct
41 Correct 684 ms 3456 KB Output is correct
42 Correct 716 ms 3452 KB Output is correct
43 Correct 805 ms 3460 KB Output is correct
44 Correct 752 ms 3452 KB Output is correct