제출 #687298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
687298		alexdd	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	177 ms	32440 KiB

maxcomp

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
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;
}
int dp[1001][1001][2];
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);
            dp[i][j][0] = max(dp[i-1][j][0], 1LL*mat[i][j]+i+j);
            dp[i][j][1] = max(dp[i-1][j][1], 1LL*mat[i][j]+i-j);
        }
        int mxm=-INF;
        for(int j=1;j<=m;j++)
        {
            mxm=max(mxm, dp[i][j][0]);
            rez = max(rez, mxm-1LL*mat[i][j]-i-j-1);

        }
        mxm=-INF;
        for(int j=m;j>0;j--)
        {
            mxm=max(mxm, dp[i][j][1]);
            rez = max(rez, mxm-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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40