oj.uz

Submission #875271

# Submission time Handle Problem Language Result Execution time Memory
875271 2023-11-18T22:23:41 Z Cyber_Wolf Zemljište (COCI22_zemljiste) C++17
0 / 70
 1 ms 348 KB 
// Problem: #3 - Izbori
// Contest: DMOJ - COCI '21 Contest 4
// URL: https://dmoj.ca/problem/coci21c4p3
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 505;

lg v[N][N];

lg get_sum(lg a, lg b, lg c, lg d)
{
	if(c > d)	swap(c, d);
	if(a > b)	swap(a, b);
	return v[b][d]-v[a-1][d]-v[b][c-1]+v[a-1][c-1];
}

int main()
{
	fastio;
	lg n, m, a, b;
	cin >> n >> m >> a >> b;
	if(b < a)	swap(a, b);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> v[i][j];
			v[i][j] += v[i-1][j]+v[i][j-1]-v[i-1][j-1];

		}
	}
	lg ans = 2e18;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= i; j++)
		{
			lg ptr1 = 1, ptr2 = m;
			for(int k = 1; k <= m; k++)
			{
				while(ptr1 < k && get_sum(j, i, k, ptr1) > b)	ptr1++;
				lg y = get_sum(j, i, k, ptr1);
				ans = min(ans, abs(y-a)+abs(y-b));
			}
			for(int k = m; k; k--)
			{
				while(ptr2 >= k && get_sum(j, i, k, ptr2) >= a)	ptr2--;
				ptr2++;
				lg y = get_sum(j, i, k, ptr2);
				ans = min(ans, abs(y-a)+abs(y-b));
			}
		}
	}
	cout << ans << '\n';

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -