oj.uz

Submission #687283

# Submission time Handle Problem Language Result Execution time Memory
687283 2023-01-26T08:59:59 Z alexdd Maxcomp (info1cup18_maxcomp) C++17
15 / 100
 2 ms 468 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1000000000007;
int n,m;
int mat[1001][1001];
int aint[4100][4];///aint[0] = stanga sus   val - lin - col
                  ///aint[1] = dreapta sus
void upd(int nod, int st, int dr, int poz, int 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]);
}
int 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<4;dim++)
            aint[i][dim]=-INF;
}
int solve()
{
    reset_aint();
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            upd(1,1,m,j,mat[i][j]+i+j,0);
            upd(1,1,m,j,mat[i][j]+i-j,1);
        }
        for(int j=1;j<=m;j++)
        {
            rez = max(rez, qry(1,1,m,1,j-1,0)-mat[i][j]-i-j-1);
            rez = max(rez, qry(1,1,m,j+1,m,1)-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];
    int 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -