oj.uz

Submission #98287

# Submission time Handle Problem Language Result Execution time Memory
98287 2019-02-21T21:44:54 Z DebDoDab Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 194 ms 17132 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ull =  unsigned long long;
using ld = long double;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
using t3 = tuple<int, int, int>;

#define endl "\n"
#define ft first
#define sd second
#define openfiles ifstream cin ("input.txt"); ofstream cout ("output.txt");
#define pb push_back
#define eb emplace_back
#define in insert
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int INF = 1000000010;
const ll INFLL = 1000000000000000010;
const ld EPS = 0.00001;
const ll MOD = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define mt make_tuple
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define int ll 
int n, m;
vector<vector<int>> A;
vector<int> F;

int get(int r) {
    int ans = INF;
    for (; r >= 0; r = (r & (r + 1)) - 1) {
        ans = min(ans, F[r]);
    }
    return ans;
}
void upd(int pos, int c) {
    for (; pos < m; pos |= pos + 1) {
        F[pos] = min(F[pos], c);
    }
}

//#define KlishkevichVadimka
signed main()
{
#ifdef KlishkevichVadimka
    openfiles
#endif
    faster;
    clock_t zzz = clock();

    cin >> n >> m;
    A.resize(n, vector<int>(m));

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

    int ans = 0;
    F.assign(m, INF);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            upd(j, A[i][j] - i - j);
            ans = max(ans, A[i][j] - get(j) - i - j);
        }
    }

    F.assign(m, INF);
    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            upd(m - j - 1, A[i][j] - i - m + 1 + j);
            ans = max(ans, A[i][j] - get(m - j - 1) - i - m + 1 + j);
        }
    }

    F.assign(m, INF);
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            upd(j, A[i][j] - n + 1 + i - j);
            ans = max(ans, A[i][j] - get(j) - n + 1 + i - j);
        }
    }

    F.assign(m, INF);
    for (int i = n-1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            upd(m - j - 1, A[i][j] - n + 1 + i - m + j + 1);
            ans = max(ans, A[i][j] - get(m - j - 1) - n + i + 1 - m + j + 1);
        }
    }

    cout << ans - 1 << endl;


//    cerr << endl << "Time : " << ld(clock() - zzz) / CLOCKS_PER_SEC;
}

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:62:13: warning: unused variable 'zzz' [-Wunused-variable]
     clock_t zzz = clock();
             ^~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 396 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 171 ms 16732 KB Output is correct
19 Correct 194 ms 16756 KB Output is correct
20 Correct 166 ms 16120 KB Output is correct
21 Correct 172 ms 16692 KB Output is correct
22 Correct 171 ms 16672 KB Output is correct
23 Correct 172 ms 16684 KB Output is correct
24 Correct 192 ms 17132 KB Output is correct