I enjoyed the contest, will we be able to upsolve it somehow? I got the 4th problem just one minute after the contest (made a small mistake in my last submission) 
Could I at least see if it’s right?
And why was the time limit for that one so tight? My lazy prop solution TLE’d, I feel as if increasing the TL to 2s would still not allow N^3 solutions to pass, while allowing this a bit less smart than the intended to pass. 
Great contest tho! Had a lot of fun solving!
Been late 1.5h for the contest, still made to top 12, so I’m satisfied 
UPD: It still fails some test I feel a bit better about myself, it’s now in Practice mode. Thanks again for the contest!
UPD 2: I found the error in my code and fixed by comparing to fellow programmer’s code.
But can anyone tell why this code TLE’s, isn’t the complexity O(N^2 log N), right?
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 2e18;
int t, n;
int ar[1005][1005];
int arr[1005];
int tarr[1005];
int lazy[4005];
int tree[4005];
void build(int v, int tl, int tr) {
lazy[v] = 0;
if (tl == tr) {
tree[v] = arr[tl] - tl;
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
}
int query(int v, int tl, int tr, int l, int r) {
if (lazy[v]) {
tree[v] += lazy[v];
if (tl != tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (tl > tr || tl > r || tr < l) return -INF;
if (tl >= l && tr <= r) return tree[v];
int tm = (tl + tr) / 2;
return max(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}
void update(int v, int tl, int tr, int l, int r, int p) {
if (lazy[v]) {
tree[v] += lazy[v];
if (tl != tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (tl > tr || tl > r || tr < l) return;
if (tl >= l && tr <= r) {
tree[v] += p;
if (tl != tr) {
lazy[2 * v] += p;
lazy[2 * v + 1] += p;
}
return;
}
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r, p);
update(2 * v + 1, tm + 1, tr, l, r, p);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ar[i][j];
}
}
if (n == 1) {
cout << ar[0][0] << '\n';
continue;
}
for (int i = 0; i < n; i++) {
tarr[i] = ar[n - 1][i];
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (!j) {
for (int k = 0; k < n; k++) {
arr[k] = tarr[k];
}
build(1, 0, n - 1);
}
tarr[j] = query(1, 0, n - 1, 0, n - 1) + ar[i][j];
if (j < n - 1) {
update(1, 0, n - 1, 0, j, -1);
update(1, 0, n - 1, j + 1, n - 1, +1);
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, tarr[i]);
cout << ans << '\n';
}
return 0;
}
