Submission #1272525

#TimeUsernameProblemLanguageResultExecution timeMemory
1272525zulmuwZemljište (COCI22_zemljiste)C++20
0 / 70
1 ms568 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long 

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  int n, m, a, b; cin >> n >> m >> a >> b;
  
  vector<vector<int>> g(n+1, vector<int> (m+1, 0)), ps(n+1, vector<int> (m+1, 0)); 
  
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      cin >> g[i][j];
      ps[i][j] = g[i][j];
      ps[i][j] += ps[i-1][j];
    }
  }

  if (b < a) swap(a, b);
  

  int ans = 1e18; 
  for (int i=1; i<=n; ++i) {
    for (int j=i; j<=m; ++j) {
      int l = 1, sum = 0;
      for (int r = 1; r <= m; ++r) {
        sum += ps[j][r] - ps[i-1][r];        
        while (l <= r && sum > b) {
          sum -= ps[j][l] - ps[i-1][l];
          l++;
        } 
        ans = min(ans, abs(a - sum) + abs(b - sum));
      }
    }
  }
  cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...