oj.uz

Submission #597081

# Submission time Handle Problem Language Result Execution time Memory
597081 2022-07-15T13:21:03 Z AGE Maja (COCI18_maja) C++14
11 / 110
 456 ms 572 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;

    indexx--;
    indexy--;
    
    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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 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 308 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 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 456 ms 572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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