Submission #801256

#	Time	Username	Problem	Language	Result	Execution time	Memory
801256		Tunglam07	Zemljište (COCI22_zemljiste)	C++17	70 / 70	301 ms	6664 KiB

Main

#include<bits/stdc++.h>
using namespace std;
 
long long n, m, a, b, c[501][501], price[501][501];

long long val(int x, int y, int u, int v)
{
	return price[u][v] - price[x - 1][v] - price[u][y - 1] + price[x - 1][y - 1];
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    cin >> n >> m >> a >> b;
    for(int i = 1; i <= n; i++)
	{
        for(int j = 1; j <= m; j++)
		{
            cin >> c[i][j];
        }
    }    
 
    for(int i = 1; i <= n; i++)
	{
        for(int j = 1; j <= m; j++)
		{
            price[i][j] = price[i - 1][j] + price[i][j - 1] - price[i - 1][j - 1] + c[i][j]; 
        }
    }
 
    long long ans = INT_MAX;
    if(a > b) 
	{
		swap(a, b);
	}
 
    for(int i = 1; i <= n; i++)
	{
         for(int j = i; j <= n; j++)
		 {
            long long p = 0;
 
            for(int k = 1; k <= m; k++)
			{
				while(p < k && val(i, 1, j, k) - val(i, 1, j, p) >= a) 
				{
					p++;
				}
                if(p < k) 
				{
					ans = min(ans, abs(val(i, 1, j, k) - val(i, 1, j, p) - a) + abs(val(i, 1, j, k) - val(i, 1, j, p) - b));
				}
                if(p >= 1) 
				{
					ans = min(ans, abs(val(i, 1, j, k) - val(i, 1, j, p - 1) - a) + abs(val(i, 1, j, k) - val(i, 1, j, p - 1) - b));
				}
            }
            
         }
    }
    cout << ans << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40