Submission #641248

#	Time	Username	Problem	Language	Result	Execution time	Memory
641248		lto5	Zemljište (COCI22_zemljiste)	C++14	70 / 70	723 ms	6732 KiB

Main

//#pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

#include<bits/stdc++.h>
using namespace std;

#define int long long

int c[505][505];
int pre[505][505];
int pre_col[505];
int r, s, a, b;

int get(int u, int v, int x, int y) {
  return pre[x][y] - pre[u - 1][y] - pre[x][v - 1] + pre[u - 1][v - 1];
}

void solve(int row_1, int row_2, int& ans) {
  for (int col_1 = 1; col_1 <= s; col_1++) {
    pre_col[col_1] = pre_col[col_1 - 1] + get(row_1, col_1, row_2, col_1);
  }

  //sum<a
  int lower = 0;
  for (int col = 1; col <= s; col++) {
    while (lower < col && pre_col[col] > pre_col[lower] + a) {
      int cur_sum = pre_col[col] - pre_col[lower];
      ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
      lower++;
    }

    if (lower < col) {
      int cur_sum = pre_col[col] - pre_col[lower];
      ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
    }
  }

  //sum>b
  lower = 0;
  for (int col = 1; col <= s; col++) {
    while (lower < col && pre_col[col] >= pre_col[lower] + b) {
      int cur_sum = pre_col[col] - pre_col[lower];
      ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
      lower++;
    }
    if (lower < col) {
      int cur_sum = pre_col[col] - pre_col[lower];
      ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
    }
  }

  //a<sum<b
}

int32_t main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> r >> s >> a >> b;

  for (int i = 1; i <= r; i++) {
    for (int j = 1; j <= s; j++) {
      cin >> c[i][j];
      pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + c[i][j];
    }
  }

  if (a > b) {
    swap(a, b);
  }

  int ans = 1e18;

  for (int row_1 = 1; row_1 <= r; row_1++) {
    for (int row_2 = row_1; row_2 <= r; row_2++) {
      solve(row_1, row_2, ans);
    }
  }

  cout << ans;
  return 0;
}

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