제출 #1137821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137821		jackofall718	Zemljište (COCI22_zemljiste)	C++20	0 / 70	1 ms	328 KiB

Main

//COCI 2021-22 ROUND 6 PROBLEM 2
// COCI 2021-22 ROUND 6 PROBLEM 2
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
#define vn std::vector<ll>
using namespace std;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll r, s, a, b;
    cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);

    // 1) Use 1-based indexing. We'll store grid[i][j].
    vector<vn> grid(r + 1, vn(s + 1));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            cin >> grid[i][j];
        }
    }

    // Build prefix sums (vertical)
    // pref[i][j] = sum of grid[1..i][j].
    vector<vn> pref(r + 1, vn(s + 1, 0LL));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            pref[i][j] = pref[i - 1][j] + grid[i][j];
        }
    }

    // 2) Initialize ans to a large number (we want the minimum distance).
    ll ans = INF;  // changed from 0 to INF

    vn col(s + 1);
    bool check = false;

    for (int i = 1; i <= r; i++) {
        if (check) break;
        for (int j = i; j <= r; j++) {
            if (check) break;

            // 3) Fix the line that fills col[]:
            //    We want col[d] = sum of grid in column d, rows [i..j].
            for (int d = 1; d <= s; d++) {
                col[d] = pref[j][d] - pref[i - 1][d];  
                // ^ changed from "col[i] = pref[j][d] - pref[i][d];"
            }

            ll temp = 0;
            ll left = 1;

            for (ll right = 1; right <= s; right++) {
                temp += col[right];

                // Compute current distance:
                ll curDist = llabs(temp - a) + llabs(temp - b);

                // 4) Fix the single '=' to '==' AND the assignment to ans.
                //    If the distance == (b - a), we found a sum in [a, b].
                if (curDist == b - a) {  
                    ans = b - a;        // changed from "ans = a - b;"
                    check = true;
                }
                // 5) Store the distance in ans, not the sum.
                else if (curDist < ans) {
                    ans = curDist;      // changed from "ans = temp;"
                }

                // 6) The next condition "else if (temp > ans)" made no sense
                //    because ans is a distance, not a sum threshold.
                //    Usually, one shrinks the window if sum > b or so.
                //    Minimal fix: assume we meant sum > b => shrink.
                else if (temp > b) {
                    while (temp > b && left <= right) {
                        temp -= col[left];
                        left++;
                    }
                    // After shrinking, also check distance again
                    ll shrinkDist = llabs(temp - a) + llabs(temp - b);
                    if (shrinkDist == b - a) {
                        ans = b - a;
                        check = true;
                    }
                    else if (shrinkDist < ans) {
                        ans = shrinkDist;
                    }
                }

                // Originally there was a "temp -= col[left];" outside everything.
                // But removing col[left] unconditionally is incorrect. 
                // We removed that single line to avoid always shifting the window.
            }
        }
        
        
    }
    cout << ans << endl; 
}

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