Submission #889044

#TimeUsernameProblemLanguageResultExecution timeMemory
889044nnhzzzMaja (COCI18_maja)C++14
110 / 110
244 ms856 KiB
/* [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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...