oj.uz

Submission #1036143

# Submission time Handle Problem Language Result Execution time Memory
1036143 2024-07-27T04:04:03 Z vjudge1 Zemljište (COCI22_zemljiste) C++17
0 / 70
 0 ms 348 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  ll n, m, a, b;
  cin >> n >> m >> a >> b;
  if(a > b) swap(a, b);
  ll c[n][m];
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j ++)
      cin >> c[i][j];

  ll ans = 1e18;
  ll pref[n + 1][m + 1];
  for(int i = 0; i <= n; i ++)
    for(int j = 0; j <= m; j ++)
      pref[i][j] = 0;

  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j ++)
      pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + c[i][j];

  for(int x1 = 1; x1 <= n; x1++)
    {
      for(int x2 = 0; x2 < x1; x2++)
	{
	  set<ll> pos, neg;
	  ll mi = 1e18, mx = -1e18;
	  if(pref[x2][0] - pref[x1][0] >= 0) mi = min(mi, pref[x2][0] - pref[x1][0]), pos.insert(pref[x2][0] - pref[x1][0]);
	  if(pref[x2][0] - pref[x1][0] <= 0) mx = min(mx, pref[x2][0] - pref[x1][0]), neg.insert(pref[x2][0] - pref[x1][0]);
	  
	  for(int y1 = 1; y1 <= m; y1++)
	    {
	      ll sm = pref[x1][y1] - pref[x2][y1];
	      // a <= b

	      if(sm < a)
		{
		  while(pos.size() > 1 && *(++pos.rbegin()) >= sm - a) pos.erase(--pos.end());
		  
		  auto it = --pos.end();
		  
		  ll fsm = *it + sm;
		  ans = min(ans, abs(a - fsm) + abs(b - fsm));
		  it = --neg.end();
		  fsm = *it + sm;
		  ans = min(ans, abs(a - fsm) + abs(b - fsm));
		}
	      else if(sm > b)
		{
		  while(neg.size() > 1 && *(++neg.begin()) <= sm - a) neg.erase(neg.begin());
		  auto it = neg.begin();
		  ll fsm = *it + sm;
		  ans = min(ans, abs(a - fsm) + abs(b - fsm));
		  it = pos.begin();
		  fsm = *it + sm;
		  ans = min(ans, abs(a - fsm) + abs(b - fsm));
		  
		}
	      else
		{
		  // a <= sm <= b
		  ll fsm = mx + sm;
		  // cerr << fsm << endl;
		  ans = min(ans, abs(a - fsm) + abs(b - fsm));
		  fsm = mi + sm;
		  // cerr << fsm << endl;
		  ans = min(ans, abs(a - fsm) + abs(b - fsm));
		}
	    	      
	      if(pref[x2][y1] - pref[x1][y1] >= 0) mi = min(mi, pref[x2][y1] - pref[x1][y1]), pos.insert(pref[x2][y1] - pref[x1][y1]);
	      if(pref[x2][y1] - pref[x1][y1] <= 0) mx = min(mx, pref[x2][y1] - pref[x1][y1]), neg.insert(pref[x2][y1] - pref[x1][y1]);

	    }
	}
    }
  // assert(ans != 1e18);
  cout << ans << endl;
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -