oj.uz

Submission #597077

# Submission time Handle Problem Language Result Execution time Memory
597077 2022-07-15T13:17:06 Z AGE Maja (COCI18_maja) C++14
0 / 110
 451 ms 580 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pb push_back

using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;

int a[103][103];
int dp[103][103][2];
int idx[4]={1,-1,0,0};
int idy[4]={0,0,-1,1};
int n,m,indexx,indexy,k;

bool inside(int x,int y){
    return x<n&&y<m&&x>=0&&y>=0;
}

main()
{

    cin>>n>>m>>indexx>>indexy>>k;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j][0]=-1e18,dp[i][j][1]=-1e18;
        }
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];

    dp[indexx][indexy][0]=0;

    int num=min(n*m,k/2);

    for(int i=0;i<num;i++){
        for(int j=0;j<n;j++){
            for(int kk=0;kk<m;kk++){

                if(dp[j][kk][i%2]==-1)
                    continue;

                for(int step=0;step<4;step++){

                    int newx=j+idx[step];
                    int newy=kk+idy[step];

                    if(!inside(newx,newy))
                        continue;

                    dp[newx][newy][(i%2)^1]=max(dp[newx][newy][(i%2)^1],dp[j][kk][i%2]+a[newx][newy]);

                }
            }
        }
    }

    int ans=-1e18;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int step=0;step<4;step++){

                if(dp[i][j][num%2]==-1)
                    continue;

                int newx=i+idx[step];
                int newy=j+idx[step];

                if(!inside(newx,newy))
                    continue;

                ans=max(ans,2*dp[i][j][(num%2)]+((k/2-num)*(a[i][j]+a[newx][newy]))-a[i][j]);

            }
        }
    }

    cout<<ans<<endl;
    return 0;
}

Compilation message

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

Subtask #1
0 / 11.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 451 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 448 KB Output isn't correct
2 Halted 0 ms 0 KB -