oj.uz

답안 #497888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497888 2021-12-24T04:23:02 Z kingline Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 132 ms 39832 KB 
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
//#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
//#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
#define pll pair < long long, long long >

using namespace std;

typedef long long ll;
const int N = 1e3 + 5;
const int M = 305;
const int mod = 1e9 + 7;

int n, m, a[N][N], uppref[N][N], downpref[N][N], upsuff[N][N], downsuff[N][N];

void calc() {
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            uppref[i][j] = upsuff[i][j] = downpref[i][j] = downsuff[i][j] = -1e10;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            uppref[i][j] = max(max(uppref[i - 1][j], uppref[i][j - 1]), (-a[i][j] + i + j));
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = m; j > 0; j--) {
            upsuff[i][j] = max(max(upsuff[i - 1][j], upsuff[i][j + 1]), (-a[i][j] + i - j));
        }
    }
    for(int i = n; i > 0; i--) {
        for(int j = 1; j <= m; j++) {
            downpref[i][j] = max(max(downpref[i + 1][j], downpref[i][j - 1]), (-a[i][j] - i + j));
        }
    }
    for(int i = n; i > 0; i--) {
        for(int j = m; j > 0; j--) {
            downsuff[i][j] = max(max(downsuff[i + 1][j], downsuff[i][j + 1]), (-a[i][j] - i - j));
        }
    }
}

int get(int i, int j) {
    int res = a[i][j] - i - j + max(uppref[i - 1][j], uppref[i][j - 1]);

    res = max(res, a[i][j] - i + j + max(upsuff[i - 1][j], upsuff[i][j + 1]));

    res = max(res, a[i][j] + i - j + max(downpref[i][j - 1], downpref[i + 1][j]));

    res = max(res, a[i][j] + i + j + max(downsuff[i + 1][j], downsuff[i][j + 1]));

    return res - 1;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //file("pieaters");
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    calc();
    int ans = -1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ans = max(ans, get(i, j));
            //cout << get(i, j) << " ";
            //cout << uppref[i][j] << " ";
        }
        //cout << endl;
    }
    cout << ans;
}

Compilation message

maxcomp.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 1 ms 1356 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 2 ms 1356 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 1 ms 1356 KB Output is correct
15 Correct 2 ms 1356 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 2 ms 1356 KB Output is correct
18 Correct 120 ms 39720 KB Output is correct
19 Correct 113 ms 39620 KB Output is correct
20 Correct 130 ms 39708 KB Output is correct
21 Correct 124 ms 39596 KB Output is correct
22 Correct 113 ms 39832 KB Output is correct
23 Correct 132 ms 39608 KB Output is correct
24 Correct 112 ms 37680 KB Output is correct