oj.uz

Submission #687287

# Submission time Handle Problem Language Result Execution time Memory
687287 2023-01-26T09:03:56 Z alexdd Maxcomp (info1cup18_maxcomp) C++17
60 / 100
 500 ms 4308 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const long long INF = 10000000000007;
int n,m;
int mat[1001][1001];
long long aint[4100][2];///aint[0] = stanga sus   val - lin - col
                  ///aint[1] = dreapta sus
void upd(int nod, int st, int dr, int poz, long long newv, int dim)
{
    if(st==dr)
    {
        aint[nod][dim] = max(aint[nod][dim], newv);
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd(nod*2,st,mij,poz,newv,dim);
    else
        upd(nod*2+1,mij+1,dr,poz,newv,dim);
    aint[nod][dim] = max(aint[nod*2][dim], aint[nod*2+1][dim]);
}
long long qry(int nod, int st, int dr, int le, int ri, int dim)
{
    if(le>ri)
        return -INF;
    if(le==st && dr==ri)
        return aint[nod][dim];
    int mij=(st+dr)/2;
    return max(qry(nod*2,st,mij,le,min(mij,ri),dim),
               qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,dim));
}
void reset_aint()
{
    for(int i=0;i<4100;i++)
        for(int dim=0;dim<2;dim++)
            aint[i][dim]=-INF;
}
long long solve()
{
    reset_aint();
    long long rez=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            upd(1,1,m,j,1LL*mat[i][j]+i+j,0);
            upd(1,1,m,j,1LL*mat[i][j]+i-j,1);
        }
        for(int j=1;j<=m;j++)
        {
            rez = max(rez, qry(1,1,m,1,j-1,0)-1LL*mat[i][j]-i-j-1);
            rez = max(rez, qry(1,1,m,j+1,m,1)-1LL*mat[i][j]-i+j-1);
        }
    }
    return rez;
}
signed main()
{
    ios_base::sync_with_stdio(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mat[i][j];
    long long ceva = solve();
    for(int i=1;i<=n/2;i++)
        for(int j=1;j<=m;j++)
            swap(mat[i][j], mat[n-i+1][j]);
    ceva = max(ceva, solve());
    cout<<ceva;
    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 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 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 2 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 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 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 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 596 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 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 2 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Execution timed out 584 ms 4308 KB Time limit exceeded
19 Halted 0 ms 0 KB -