oj.uz

Submission #597083

# Submission time Handle Problem Language Result Execution time Memory
597083 2022-07-15T13:22:11 Z AGE Maja (COCI18_maja) C++14
110 / 110
 977 ms 592 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+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

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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 360 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 894 ms 592 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct
2 Correct 577 ms 532 KB Output is correct
3 Correct 977 ms 568 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 520 KB Output is correct
2 Correct 773 ms 568 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 368 KB Output is correct
2 Correct 52 ms 488 KB Output is correct

Subtask #9
11.0 / 11.0

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

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 492 KB Output is correct
2 Correct 2 ms 340 KB Output is correct