Submission #1272279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272279		sakka	Zemljište (COCI22_zemljiste)	C++20	0 / 70	3 ms	5156 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<long long, long long>
#define fi first
#define sec second
#define ld long double
using namespace std;
void freop(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}
const ll INF = 1e18, mod = 1e9+7;
ll r, c, a, b;
vector<vector<ll>>val(502, vector<ll>(502));
vector<vector<ll>>pref(502, vector<ll>(502));

void solve(){
    cin >> r >> c >> a >> b;
    if(a > b) swap(a, b);
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            cin >> val[i][j];
        }
    }
    
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            pref[i][j] = val[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
            // cout << i << " " << j << " " << pref[i][j] << endl;
        }
    }

    ll ans = INF;
    for(int i=2; i<=r; i++){
        for(int j=2; j<=c; j++){
            for(int k=i-1; k>=0; k--){
                // last element smaller than a;
                ll l=0, r=j, cari = -1, cari2 = -1;
                while(l<=r){
                    ll mid = (l+r)/2;
                    // cout << mid << " " << pref[i][j] - pref[i][mid] - pref[k][j] + pref[k][mid] << endl;
                    if(pref[i][j] - pref[i][mid] - pref[k][j] + pref[k][mid] > a){
                        l = mid+1;
                        cari = mid;
                    }
                    else r = mid-1;
                }
                l=0; r=j;
                while(l<=r){
                    ll mid = (l+r)/2;
                    if(pref[i][j] - pref[i][mid] - pref[k][j] + pref[k][mid] > b){
                        l = mid+1;
                        cari2 = mid;
                    }
                    else r = mid-1;
                }
                // cout << cari << " " << cari2 << endl;
                if(cari != -1) ans = min(ans, abs(a-(pref[i][j]-pref[i][cari]-pref[k][j]+pref[k][cari])) + abs(b-(pref[i][j]-pref[i][cari]-pref[k][j]+pref[k][cari])));
                if(cari < j) ans = min(ans, abs(a-(pref[i][j]-pref[i][cari+1]-pref[k][j]+pref[k][cari+1])) + abs(b-(pref[i][j]-pref[i][cari+1]-pref[k][j]+pref[k][cari+1])));
                if(cari2 != -1) ans = min(ans, abs(a-(pref[i][j]-pref[i][cari2]-pref[k][j]+pref[k][cari2])) + abs(b-(pref[i][j]-pref[i][cari2]-pref[k][j]+pref[k][cari2])));
                if(cari2 < j) ans = min(ans, abs(a-(pref[i][j]-pref[i][cari2+1]-pref[k][j]+pref[k][cari2+1])) + abs(b-(pref[i][j]-pref[i][cari2+1]-pref[k][j]+pref[k][cari2+1])));
            }
        }
    }
    cout << ans << endl;
}

int main(){
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freop();
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void freop()':
Main.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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