Submission #1226614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226614		jacklog	Zemljište (COCI22_zemljiste)	C++20	0 / 70	0 ms	576 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair <int, int>
#define iii pair <int, ii>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(mask, i) ((mask) >> (i) & 1)
#define NAME "dautu"
#define int long long
using namespace std;
const int oo = 1e18;
const int N = 5e2 + 10;
int n, m, A, B;
int a[N][N], pre[N][N];

int get(int x1, int y1, int x2, int y2)
{
    int res = pre[x2][y2] - pre[x2][y1 - 1] - pre[x1 - 1][y2] + pre[x1 - 1][y1 - 1];
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(NAME".inp", "r"))
    {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }

    cin >> n >> m >> A >> B;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            pre[i][j] = a[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
        }

    int ans = oo;
    for (int i1 = 1; i1 <= n; i1++)
        for (int i2 = i1; i2 <= n; i2++)
        {
            vector <int> ds;
            ds.clear();
            int it1 = -1, it2 = -1, it3 = -1;
            for (int j = 1; j <= m; j++)
            {
                int now = get(i1, 1, i2, j);
                if(now >= A and now <= B)
                {
                    cout << B - A;
                    exit(0);
                }
                if(ds.size())
                {
                    if(now >= A)
                    {
                        while(it1 < ds.size() - 1 and ds[it1 + 1] < now - A)
                            it1++;
                        if(it1 != -1 and it1 < ds.size() - 1 and ds[it1 + 1] >= now - A)
                        {
                            int Q = now - ds[it1 + 1];
                            ans = min(ans, abs(Q - A) + abs(Q - B));
                        }
                    }

                    if(now >= B)
                    {
                        while(it2 < ds.size() - 1 and ds[it2 + 1] <= now - B)
                            it2++;
                        if(it2 != -1 and ds[it2] <= now - B)
                        {
                            int Q = now - ds[it2];
                            ans = min(ans, abs(Q - A) + abs(Q - B));
                        }

                        while(it3 < ds.size() - 1 and ds[it3 + 1] < now - B)
                            it3++;
                        if(it3 != -1 and it3 < ds.size() - 1 and ds[it3 + 1] <= now - A)
                        {
                            int Q = now - ds[it3 + 1];
                            ans = min(ans, abs(Q - A) + abs(Q - B));
                        }
                    }

                }
                ans = min(ans, abs(now - A) + abs(now - B));
                ds.pb(now);
            }
        }
    cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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