제출 #1262100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262100		dhuyyyy	Zemljište (COCI22_zemljiste)	C++20	70 / 70	477 ms	2428 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;

const int N = 505;
const int INF = 1e9;
const int MOD = 998244353;

int n,m,a,b,res = 1e18;
int pre[N][N],sum[N];

int calc(int r,int l){
    if (l == 0) return 0;
    return sum[r] - sum[l-1];
}
int get(int x1,int y1,int x2,int y2){
    return pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> pre[i][j];
            pre[i][j] += pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
        }
    }
    for (int i = 1; i <= m; i++){
        for (int j = i; j <= m; j++){
            for (int r = 1; r <= n; r++) sum[r] = sum[r-1] + get(r,i,r,j);
            int l1,l2,l3,l4;
            l1 = l2 = l3 = l4 = 1;
            for (int r = 1; r <= n; r++){
                while (2 * calc(r,l1) >= a + b && l1 <= r) l1++;
                if (2 * calc(r,l1-1) >= a + b && calc(r,l1-1) >= max(a,b)) res = min(res,2 * calc(r,l1-1) - (a + b));
                while (2 * calc(r,l2) >= a + b && l2 + 1 <= r) l2++;
                if (2 * calc(r,l2) < a + b && calc(r,l2) < min(a,b)) res = min(res,(a + b) - 2 * calc(r,l2));
                while (calc(r,l3) >= a && l3 <= r) l3++;
                if(calc(r,l3-1) < b && calc(r,l3-1) >= a) res = min(res,b - a);
                while (calc(r,l4) >= b && l4 <= r) l4++;
                if (calc(r,l4-1) < a && calc(r,l4-1) >= b) res = min(res,a - b);
            }
        }
    }
    cout << res;
    return 0;
}

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