oj.uz

Submission #96817

# Submission time Handle Problem Language Result Execution time Memory
96817 2019-02-12T09:05:48 Z ami Maja (COCI18_maja) C++17
99 / 110
 2000 ms 760 KB 
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

int const MAXN=110;
int N,M,A,B,K;
int C[MAXN][MAXN];
ll f[2][MAXN][MAXN];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N>>M>>A>>B>>K;
	A--, B--;
	rep(i,0,N) rep(j,0,M) cin>>C[i][j];

	rep(x,0,N) rep(y,0,M) f[0][x][y]=-1;
	f[0][A][B]=0;

	//int L=4*max(N,M)*max(N,M);
	int L=100000;
	if (L%2!=0) L++;

	ll last=0;
	rep(k,0,min(K,L)) {
		auto curr=f[k%2];
		auto next=f[!(k%2)];

		rep(x,0,N) rep(y,0,M) next[x][y]=-1;

		rep(x,0,N) rep(y,0,M) if (curr[x][y]!=-1) {
			if (x-1>=0) next[x-1][y]=max(next[x-1][y],curr[x][y]+C[x-1][y]);
			if (x+1<N)  next[x+1][y]=max(next[x+1][y],curr[x][y]+C[x+1][y]);
			if (y-1>=0) next[x][y-1]=max(next[x][y-1],curr[x][y]+C[x][y-1]);
			if (y+1<M)  next[x][y+1]=max(next[x][y+1],curr[x][y]+C[x][y+1]);
		}

		if (curr[A][B]!=-1) last=curr[A][B];
	}

	ll res=f[0][A][B];
	if (K>L) {
		res+=(f[0][A][B]-last)*(K-L)/2;
	}

	cout<<res<<"\n";
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 412 KB Output is correct

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 512 KB Output is correct
2 Correct 52 ms 384 KB Output is correct
3 Correct 264 ms 732 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 444 KB Output is correct
2 Correct 1690 ms 632 KB Output is correct
3 Correct 270 ms 648 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 648 KB Output is correct
2 Execution timed out 2005 ms 760 KB Time limit exceeded

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 476 KB Output is correct
2 Correct 553 ms 512 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 480 KB Output is correct
2 Correct 98 ms 384 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 512 KB Output is correct
2 Correct 92 ms 384 KB Output is correct