oj.uz

Submission #197077

# Submission time Handle Problem Language Result Execution time Memory
197077 2020-01-18T13:02:03 Z Pankin Maxcomp (info1cup18_maxcomp) C++14
60 / 100
 500 ms 8740 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int N = 1005;
int a[N][N], n, m, tUp[4 * N], tDown[4 * N], ptUp[4 * N], curVal[N], ptDown[4 * N], sufMin[N][N], ans = -INF;

inline void push(int v, int tl, int tr, int t[4 * N], int pt[4 * N]) {
    t[v] += pt[v];
    if (tl != tr) {
        pt[v<<1] += pt[v];
        pt[(v<<1)|1] += pt[v];
    }
    pt[v] = 0;
}

void make_val(int v, int tl, int tr, int i, int val, int t[N], int pt[N]) {
    push(v, tl, tr, t, pt);
    if (i < tl || i > tr)
        return;
    if (tl == tr) {
        t[v] = val;
        return;
    }

    int tm = (tl + tr) >> 1;
    make_val(v<<1, tl, tm, i, val, t, pt);
    make_val((v<<1)|1, tm + 1, tr, i, val, t, pt);

    t[v] = min(t[v<<1], t[(v<<1)|1]);
}

void update(int v, int tl, int tr, int i, int val, int t[N], int pt[N]) {
    push(v, tl, tr, t, pt);
    if (i < tl || i > tr)
        return;
    if (tl == tr) {
        t[v] = min(val, t[v]);
        return;
    }

    int tm = (tl + tr) >> 1;
    update(v<<1, tl, tm, i, val, t, pt);
    update((v<<1)|1, tm + 1, tr, i, val, t, pt);

    t[v] = min(t[v<<1], t[(v<<1)|1]);
}

void inc(int v, int tl, int tr, int l, int r, int delta, int t[N], int pt[N]) {
    push(v, tl, tr, t, pt);
    if (tl > r || tr < l)
        return;
    if (tl >= l && tr <= r) {
        pt[v] += delta;
        push(v, tl, tr, t, pt);
        return;
    }

    int tm = (tl + tr) >> 1;
    inc(v<<1, tl, tm, l, r, delta, t, pt);
    inc((v<<1)|1, tm + 1, tr, l, r, delta, t, pt);

    t[v] = min(t[v<<1], t[(v<<1)|1]);
}

void init() {
    for (int i = 0; i < N; i++) {
        sufMin[i][n] = INF;
        curVal[i] = INF;
    }
    for (int i = 0; i < 4 * N; i++) {
        tUp[i] = INF;
        tDown[i] = INF;
    }

    for (int j = 0; j < m; j++) {
        for (int i = n - 1; i >= 0; i--) {
            sufMin[j][i] = min(a[i][j] + i, sufMin[j][i + 1]);
        }
    }

    for (int i = 0; i < m; i++) {
        make_val(1, 0, m - 1, i, sufMin[i][0] + i, tDown, ptDown);
    }
}

clock_t tim = clock();
inline bool tooLate() {
    return (double)(clock() - tim) / CLOCKS_PER_SEC > 0.497;
}

signed main() {
    fast_io;

    //ifstream cin("input.txt");

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    init();

    int coef = 1, x = 0, y = 0;
    while(!tooLate()) {
        ans = max(ans, a[x][y] - tUp[1] - x);
        ans = max(ans, a[x][y] - tDown[1] + x);

        if (!(y + coef >= 0 && y + coef < m)) {
            if (x == n - 1)
                break;
            for (int i = 0; i < m; i++) {
                if (sufMin[i][x + 1] != sufMin[i][x])
                    make_val(1, 0, m - 1, i, sufMin[i][x + 1] + abs(i - y), tDown, ptDown);
                if (a[x][i] - x < curVal[i]) {
                    update(1, 0, m - 1, i, a[x][i] - x + abs(i - y), tUp, ptUp);
                    curVal[i] = a[x][i];
                }
            }

            x++; coef *= -1;
            continue;
        }

        if (coef == 1) {
            inc(1, 0, m - 1, 0, y, 1, tDown, ptDown);
            inc(1, 0, m - 1, y + 1, m - 1, -1, tDown, ptDown);
            inc(1, 0, m - 1, 0, y, 1, tUp, ptUp);
            inc(1, 0, m - 1, y + 1, m - 1, -1, tUp, ptUp);
        }
        else {
            inc(1, 0, m - 1, y, m, 1, tDown, ptDown);
            inc(1, 0, m - 1, 0, y - 1, -1, tDown, ptDown);
            inc(1, 0, m - 1, y, m, 1, tUp, ptUp);
            inc(1, 0, m - 1, 0, y - 1, -1, tUp, ptUp);
        }

        y += coef;
    }

    cout << ans - 1;

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 5 ms 4344 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 5 ms 4344 KB Output is correct
5 Correct 5 ms 4344 KB Output is correct
6 Correct 5 ms 4344 KB Output is correct
7 Correct 1 ms 4388 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4344 KB Output is correct
2 Correct 7 ms 4344 KB Output is correct
3 Correct 7 ms 4344 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 5 ms 4344 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 5 ms 4344 KB Output is correct
5 Correct 5 ms 4344 KB Output is correct
6 Correct 5 ms 4344 KB Output is correct
7 Correct 1 ms 4388 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 9 ms 4604 KB Output is correct
10 Correct 9 ms 4600 KB Output is correct
11 Correct 9 ms 4600 KB Output is correct
12 Correct 10 ms 4600 KB Output is correct
13 Correct 9 ms 4600 KB Output is correct
14 Correct 9 ms 4600 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 5 ms 4344 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 5 ms 4344 KB Output is correct
5 Correct 5 ms 4344 KB Output is correct
6 Correct 5 ms 4344 KB Output is correct
7 Correct 1 ms 4388 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 8 ms 4344 KB Output is correct
10 Correct 7 ms 4344 KB Output is correct
11 Correct 7 ms 4344 KB Output is correct
12 Correct 9 ms 4604 KB Output is correct
13 Correct 9 ms 4600 KB Output is correct
14 Correct 9 ms 4600 KB Output is correct
15 Correct 10 ms 4600 KB Output is correct
16 Correct 9 ms 4600 KB Output is correct
17 Correct 9 ms 4600 KB Output is correct
18 Incorrect 500 ms 8740 KB Output isn't correct
19 Halted 0 ms 0 KB -