Submission #597083

#	Time	Username	Problem	Language	Result	Execution time	Memory
597083		AGE	Maja (COCI18_maja)	C++14	110 / 110	977 ms	592 KiB

maja

#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+idy[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 (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11