oj.uz

Submission #889044

# Submission time Handle Problem Language Result Execution time Memory
889044 2023-12-18T16:54:25 Z nnhzzz Maja (COCI18_maja) C++14
110 / 110
 244 ms 856 KB 
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <locale>
#include <map>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  (((i)>>(j))&1LL)
#define           MASK(i)  (1LL<<(i))
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define             vvpii  vector<vpii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
#define              endl  "\n"
#define                MP  make_pair
#define               int  ll

//-----------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{ c = getchar(); }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const  ll   LINF = 1e18;
const int    INF = 1e9;
const int    LOG = 20;
const int   MAXN = 1e2+3;
const int      N = 1e2+3;
const int    MOD = 1e9+7;
const int   BASE = 1e5;
const  ld    EPS = 1e-9;
const  ld     PI = acos(-1);
const int OFFSET = 1e3;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int c[MAXN][MAXN];
int n,m,k,A,B;

bool ok(int x, int y){
	return x>=1 && y>=1 && x<=n && y<=m;
}

namespace sub1{
	int dp[MAXN][MAXN][2];

	void solve(){
		memset(dp,-1,sizeof dp);
		int now = 1;
		dp[A][B][0] = 0;
		REP(l,1,k){
			now ^= 1;
			REP(i,1,n){
				REP(j,1,m){
					if(dp[i][j][now]==-1) continue;
					REP(t,0,3){
						int x = i+dx[t],y = j+dy[t];
						maxi(dp[x][y][now^1],dp[i][j][now]+c[x][y]);
					}
				}
			}
		}
		cout << dp[A][B][now^1];
	}
}

namespace sub2{
	int dp[MAXN][MAXN][2];

	void solve(){
		memset(dp,-1,sizeof dp);
		int now = 1,MAX = min(1LL*n*m,k>>1);
		dp[A][B][0] = 0;
		REP(l,1,MAX){
			now ^= 1;
			REP(i,1,n){
				REP(j,1,m){
					if(dp[i][j][now]==-1) continue;
					REP(t,0,3){
						int x = i+dx[t],y = j+dy[t];
						if(ok(x,y)==false) continue;
						maxi(dp[x][y][now^1],dp[i][j][now]+c[x][y]);
					}
				}
			}
		}
		int res = 0; now ^= 1;
		REP(i,1,n){
			REP(j,1,m){
				if(dp[i][j][now]==-1) continue;
				REP(t,0,3){
					int x = i+dx[t],y = j+dy[t];
					if(ok(x,y)==false) continue;
					maxi(res,dp[i][j][now]*2-c[i][j]+1LL*(k-MAX*2)/2*(c[i][j]+c[x][y]));
				}
			}
		}
		cout << res;
	}
}

void solve(){
	cin >> n >> m >> A >> B >> k;
	REP(i,1,n) REP(j,1,m) cin >> c[i][j];
	sub2::solve(); return ;
	if(k<=100000){
		sub1::solve();
		return ;
	}
	sub2::solve();
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    #define task1 "nnhzzz"
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

maja.cpp: In function 'int main()':
maja.cpp:184:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
maja.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
maja.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
maja.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 214 ms 600 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 178 ms 724 KB Output is correct
3 Correct 212 ms 604 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 604 KB Output is correct
2 Correct 244 ms 748 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 856 KB Output is correct
2 Correct 15 ms 604 KB Output is correct

Subtask #9
11.0 / 11.0

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

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct