Submission #1036183

#TimeUsernameProblemLanguageResultExecution timeMemory
1036183vjudge1Zemljište (COCI22_zemljiste)C++17
70 / 70
682 ms6992 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); ll n, m, a, b; cin >> n >> m >> a >> b; if(a > b) swap(a, b); ll c[n][m]; for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) cin >> c[i][j]; ll ans = 1e18; ll pref[n + 1][m + 1]; for(int i = 0; i <= n; i ++) for(int j = 0; j <= m; j ++) pref[i][j] = 0; for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + c[i][j]; for(int x1 = 1; x1 <= n && ans > b - a; x1++) { for(int x2 = 0; x2 < x1 && ans > b - a; x2++) { deque<ll> st; st.push_back({pref[x2][0] - pref[x1][0]}); ll mi = 1e18, mx = -1e18; if(pref[x2][0] - pref[x1][0] >= 0) mi = min(mi, pref[x2][0] - pref[x1][0]); if(pref[x2][0] - pref[x1][0] <= 0) mx = max(mx, pref[x2][0] - pref[x1][0]); for(int y1 = 1; y1 <= m && ans > b - a; y1++) { ll sm = pref[x1][y1] - pref[x2][y1]; // is this incrasing or not // a <= b while(st.size() > 1 && st[1] >= a - sm) st.pop_front(); // a <= fsm <= b // if I want this if(sm < a || b < sm) { ll fsm = st.front() + sm; ans = min(ans, abs(a - fsm) + abs(b - fsm)); if(st.size() > 1) fsm = st[1] + sm; ans = min(ans, abs(a - fsm) + abs(b - fsm)); } else { ll fsm = mi + sm; ans = min(ans, abs(a - fsm) + abs(b - fsm)); fsm = mx + sm; ans = min(ans, abs(a - fsm) + abs(b - fsm)); } st.push_back(pref[x2][y1] - pref[x1][y1]); if(pref[x2][y1] - pref[x1][y1] >= 0) mi = min(mi, pref[x2][y1] - pref[x1][y1]); if(pref[x2][y1] - pref[x1][y1] <= 0) mx = max(mx, pref[x2][y1] - pref[x1][y1]); } } } // assert(ans != 1e18); cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...