| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88224 |
2018-12-04T15:45:36 Z |
kjain_1810 |
Maja (COCI18_maja) |
C++11 |
|
111 ms |
836 KB |
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define ind2(a, b) scanf("%d%d", &a, &b)
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
#define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)
using namespace std;
const int N=105+5;
const int MOD=1e9+7;
typedef long long ll;
typedef long double ld;
ll n, m, stx, sty, k, dp[2][N][N], arr[N][N];
int main()
{
inlld2(n, m);
inlld2(stx, sty);
inlld(k);
for(ll a=1; a<=n; a++)
for(ll b=1; b<=m; b++)
{
inlld(arr[a][b]);
for(ll c=0; c<=n+m; c++)
dp[c][a][b]=-1e18;
}
dp[0][stx][sty]=0;
for(ll steps=1; steps<=min(k/2, n*m-1); steps++)
for(ll a=1; a<=n; a++)
for(ll b=1; b<=m; b++)
{
if(a>1)
dp[steps%2][a][b]=max(dp[steps%2][a][b], dp[(steps-1)%2][a-1][b]+arr[a][b]);
if(b>1)
dp[steps%2][a][b]=max(dp[steps%2][a][b], dp[(steps-1)%2][a][b-1]+arr[a][b]);
if(a<n)
dp[steps%2][a][b]=max(dp[steps%2][a][b], dp[(steps-1)%2][a+1][b]+arr[a][b]);
if(b<m)
dp[steps%2][a][b]=max(dp[steps%2][a][b], dp[(steps-1)%2][a][b+1]+arr[a][b]);
// printf("%lld %lld %lld %lld\n", steps, a, b, dp[steps][a][b]);
}
if(k/2<=n*m-1)
{
ll ans=0;
for(ll a=1; a<=n; a++)
for(ll b=1; b<=m; b++)
ans=max(ans, 2*dp[(k/2)%2][a][b]-arr[a][b]);
printf("%lld\n", ans);
return 0;
}
ll ans=0;
for(ll a=1; a<=n; a++)
for(ll b=1; b<=m; b++)
{
ll here=dp[(n*m-1)%2][a][b];
ll toadd=0;
if(a>1)
toadd=max(toadd, arr[a-1][b]);
if(a<n)
toadd=max(toadd, arr[a+1][b]);
if(b<m)
toadd=max(toadd, arr[a][b+1]);
if(b>1)
toadd=max(toadd, arr[a][b-1]);
ans=max(ans, 2*here+(k-2*n*m+2)*(toadd+arr[a][b])-arr[a][b]);
}
printf("%lld\n", ans);
}
// ll n, m, stx, sty, k, arr[N][N], dp[2][N][N];
// ll changex[]={1, -1, 0, 0}, changey[]={0,0,1,-1};
// int main()
// {
// inlld2(n, m);
// inlld3(stx, sty, k);
// for(ll a=1; a<=n; a++)
// for(ll b=1; b<=m; b++)
// {
// dp[0][a][b]=-1e18;
// dp[1][a][b]=-1e18;
// inlld(arr[a][b]);
// }
// k/=2;
// ll maxi=min(n*m-1, k);
// dp[0][stx][sty]=0;
// for(ll a=1; a<=maxi; a++)
// {
// ll here=a&1;
// for(ll b=1; b<=n; b++)
// for(ll c=1; c<=m; c++)
// for(ll d=0; d<=3; d++)
// {
// ll nexb=b+changex[d];
// ll nexc=c+changey[d];
// if(nexb<=n && nexb>=1 && nexc<=m && nexc>=1)
// {
// dp[here][nexb][nexc]=max(dp[here][nexb][nexc], dp[1-here][a][b]+arr[nexb][nexc]);
// }
// }
// }
// ll en=maxi&1, ans=0;
// for(ll a=1; a<=n; a++)
// for(ll b=1; b<=m; b++)
// {
// ll toadd=0;
// for(ll c=0; c<=3; c++)
// {
// ll nexa=a+changex[c];
// ll nexb=b+changey[c];
// if(nexa>=1 && nexa<=n && nexb>=1 && nexb<=m)
// toadd=max(toadd, arr[nexa][nexb]);
// }
// ans=max(ans, dp[en][a][b]*2+(k-maxi)*(toadd+arr[a][b])-arr[a][b]);
// }
// printf("%lld\n", ans);
// return 0;
// }
Compilation message
maja.cpp: In function 'int main()':
maja.cpp:8:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
~~~~~^~~~~~~~~~~~~~~~~~~~
maja.cpp:24:5: note: in expansion of macro 'inlld2'
inlld2(n, m);
^~~~~~
maja.cpp:8:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
~~~~~^~~~~~~~~~~~~~~~~~~~
maja.cpp:25:5: note: in expansion of macro 'inlld2'
inlld2(stx, sty);
^~~~~~
maja.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define inlld(a) scanf("%lld", &a)
~~~~~^~~~~~~~~~~~
maja.cpp:26:5: note: in expansion of macro 'inlld'
inlld(k);
^~~~~
maja.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define inlld(a) scanf("%lld", &a)
~~~~~^~~~~~~~~~~~
maja.cpp:30:13: note: in expansion of macro 'inlld'
inlld(arr[a][b]);
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
