oj.uz

Submission #197081

# Submission time Handle Problem Language Result Execution time Memory
197081 2020-01-18T14:11:22 Z Pankin Maxcomp (info1cup18_maxcomp) C++14
60 / 100
 500 ms 5008 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, t[4 * N], curVal[N], pt[4 * N], ans = 0;

inline void push(int v, int tl, int tr) {
    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) {
    push(v, tl, tr);
    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);
    make_val((v<<1)|1, tm + 1, tr, i, val);

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

void update(int v, int tl, int tr, int i, int val) {
    push(v, tl, tr);
    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);
    update((v<<1)|1, tm + 1, tr, i, val);

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

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

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

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

inline void repeat() {
    for (int i = 0; i < N; i++) {
        curVal[i] = INF;
    }
    for (int i = 0; i < 4 * N; i++) {
        t[i] = INF;
        pt[i] = 0;
    }
    int coef = 1, x = 0, y = 0;
    for (int i = 0; i < m; i++) {
        if (a[x][i] - x < curVal[i]) {
            update(1, 0, m - 1, i, a[x][i] - x + abs(i - y));
            curVal[i] = a[x][i];
        }
    }
    while(true) {
        ans = max(ans, a[x][y] - t[1] - x);

        if (!(y + coef >= 0 && y + coef < m)) {
            if (x == n - 1)
                break;

            x++; coef *= -1;
            for (int i = 0; i < m; i++) {
                if (a[x][i] - x < curVal[i]) {
                    update(1, 0, m - 1, i, a[x][i] - x + abs(i - y));
                    curVal[i] = a[x][i];
                }
            }

            continue;
        }

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

        y += coef;
    }
}

signed main() {
    fast_io;

    //getfiles;

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

    repeat();

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

    repeat();

    cout << ans - 1;

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 4 ms 636 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 4 ms 504 KB Output is correct
15 Correct 4 ms 636 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 3 ms 504 KB Output is correct
18 Execution timed out 769 ms 5008 KB Time limit exceeded
19 Halted 0 ms 0 KB -