oj.uz

Submission #496901

# Submission time Handle Problem Language Result Execution time Memory
496901 2021-12-22T06:14:55 Z kingline Maxcomp (info1cup18_maxcomp) C++17
30 / 100
 500 ms 33864 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;

const int N = 1e3 + 5;
const int lg = 21;

int n, m, a[N][N], ans = -1, used[N][N];

multiset < int > st;
vector < pii > path;
void rec(int i, int j, int len) {
    if(i > n || j > m || j < 1 || i < 1) return;
    ans = max(ans, (*st.rbegin()) - (*st.begin()) - len);
    if(!used[i + 1][j]) {
        path.pb({i + 1, j});
        st.insert(a[i + 1][j]);
        used[i + 1][j] = 1;
        rec(i + 1, j, len + 1);
        st.erase(st.find(a[i + 1][j]));
    }
    if(!used[i][j + 1]) {
        path.pb({i, j + 1});
        used[i][j + 1] = 1;
        st.insert(a[i][j + 1]);
        rec(i, j + 1, len + 1);
        st.erase(st.find(a[i][j + 1]));
    }
    if(!used[i][j - 1]) {
        path.pb({i, j - 1});
        used[i][j - 1] = 1;
        st.insert(a[i][j - 1]);
        rec(i, j - 1, len + 1);
        st.erase(st.find(a[i][j - 1]));
    }
}

void rec1(int i, int j, int len) {
    if(i > n || j > m) return;
    ans = max(ans, (*st.rbegin()) - (*st.begin()) - len);
    st.insert(a[i + 1][j]);
    rec1(i + 1, j, len + 1);
    st.erase(st.find(a[i + 1][j]));
    st.insert(a[i][j + 1]);
    rec1(i, j + 1, len + 1);
    st.erase(st.find(a[i][j + 1]));
}

main() {
    //file("pieaters");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    if(n != 1) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                used[i][j] = 1;
                st.insert(a[i][j]);
                rec(i, j, 1);
                st.erase(st.find(a[i][j]));
                used[i][j] = 0;
                for(int k = 0; k < path.size(); k++) {
                    used[path[k].first][path[k].second] = 0;
                }
            }
        }
    } else {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                st.insert(a[i][j]);
                rec1(i, j, 1);
                st.erase(st.find(a[i][j]));
            }
        }
    }
    cout << ans;
}

Compilation message

maxcomp.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main() {
      | ^~~~
maxcomp.cpp: In function 'int main()':
maxcomp.cpp:85:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for(int k = 0; k < path.size(); k++) {
      |                                ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 440 KB Output is correct
2 Correct 112 ms 332 KB Output is correct
3 Correct 113 ms 460 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Execution timed out 1086 ms 33864 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 123 ms 440 KB Output is correct
10 Correct 112 ms 332 KB Output is correct
11 Correct 113 ms 460 KB Output is correct
12 Execution timed out 1086 ms 33864 KB Time limit exceeded
13 Halted 0 ms 0 KB -