oj.uz

Submission #768841

# Submission time Handle Problem Language Result Execution time Memory
768841 2023-06-28T18:08:58 Z raysh07 Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 310 ms 17628 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e3 + 69;
int seg[2 * N][4];
int a[N][N];
int ok;

void update(int l, int r, int pos, int x, int v, int i){
    x--;
    int n = ok;
    x += n;
    if (seg[x][i] > v) return;
    for (seg[x][i] = v; x; x >>= 1){
        seg[x >> 1][i] = max(seg[x][i], seg[x ^ 1][i]);
    }
}

int query(int ll, int rr, int pos, int l, int r, int i){
    l--;
    int ans = -INF;
    int n = ok;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1){
        if (l & 1) ans = max(ans, seg[l++][i]);
        if (r & 1) ans = max(ans, seg[--r][i]);
    }
    
    return ans;
}

void Solve() 
{
    int n, m; cin >> n >> m;
    ok = m;
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    
    for (int i = 0; i < 2 * N; i++){
        for (int j = 0; j < 4; j++) {
            seg[i][j] = -INF;
        }
    }
    
    int ans = -1;
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            // 0 --> a, y -, - 
            // 1 --> a, y +, - 
            // 2 --> a, y -, +
            // 3 --> a, y +, + 
            
            ans = max(ans, query(1, m, 1, j, m, 0) + a[i][j] + j - i - 1);
            ans = max(ans, query(1, m, 1, j, m, 1) - a[i][j] + j - i - 1);
            ans = max(ans, query(1, m, 1, 1, j, 2) + a[i][j] - j - i - 1);
            ans = max(ans, query(1, m, 1, 1, j, 3) - a[i][j] - j - i - 1);
            
            update(1, m, 1, j, -a[i][j] - j + i, 0);
            update(1, m, 1, j, a[i][j] - j + i, 1);
            update(1, m, 1, j, -a[i][j] + j + i, 2);
            update(1, m, 1, j, a[i][j] + j + i, 3);
        }
    }
    
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 257 ms 8752 KB Output is correct
19 Correct 310 ms 17280 KB Output is correct
20 Correct 245 ms 16944 KB Output is correct
21 Correct 282 ms 17276 KB Output is correct
22 Correct 272 ms 17280 KB Output is correct
23 Correct 269 ms 17168 KB Output is correct
24 Correct 303 ms 17628 KB Output is correct