Submission #617089


Source Code Expand

#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <limits>
#include <ctime>
#include <cassert>
#include <map>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <stack>
#include <queue>
#include <numeric>
#include <iterator>
#include <bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)

// #pragma comment(linker,"/STACK:36777216")

template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }

template<class T> void chmax(T& l, const T r) { l = max(l, r); }
template<class T> void chmin(T& l, const T r) { l = min(l, r); }
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }

#include <unordered_map>
#include <unordered_set>

vector<vector<ll>> rot(vector<vector<ll>>& v) {
	int n = sz(v), m = sz(v[0]);
	vector<vector<ll>> ret(m, vector<ll>(n));

	FOR(i, m) FOR(j, n) ret[i][j] = v[j][i];
	return ret;
}

vector<vector<ll>> f(vector<vector<ll>>& v) {
	const int h = sz(v);
	const int w = sz(v[0]);
	vector<vector<ll>> ret(h, vector<ll>(w, numeric_limits<ll>::min()));
	v = rot(v);

	FOR(i, h) {
		vector<ll> hmax(i + 1);
		FOR(j, w) {
			ll curv = 0;
			ll curmax = -ten(9) - 10;
			for (int ch = i; ch >= 0; ch--) {
				curv += v[j][ch];
				ll sm = curv + hmax[ch];
				chmax(curmax, sm);
				if (sm < 0) sm = 0;
				hmax[ch] = sm;
			}
			ret[i][j] = curmax;
		}
	}

	FOR(i, h) FOR(j, w) {
		if (i > 0) chmax(ret[i][j], ret[i - 1][j]);
		if (j > 0) chmax(ret[i][j], ret[i][j - 1]);
	}

	return ret;
}

int main() {
	int h, w;
	ll b[300][300];

	reader(h, w);
	FOR(i, h) FOR(j, w) reader(b[i][j]);

	vector<vector<ll>> v1, v2, v3, v4;

	{
		vector<vector<ll>> v(h, vector<ll>(w));
		FOR(i, h) FOR(j, w) v[i][j] = b[i][j];
		v1 = f(v);
	}
	{
		vector<vector<ll>> v(h, vector<ll>(w));
		FOR(i, h) FOR(j, w) v[i][j] = b[i][w - 1 - j];
		v2 = f(v);
	}
	{
		vector<vector<ll>> v(h, vector<ll>(w));
		FOR(i, h) FOR(j, w) v[i][j] = b[h-1-i][j];
		v3 = f(v);
	}
	{
		vector<vector<ll>> v(h, vector<ll>(w));
		FOR(i, h) FOR(j, w) v[i][j] = b[h-1-i][w - 1 - j];
		v4 = f(v);
	}

	ll ans = numeric_limits<ll>::min();
	FOR(i, h - 1) {
		ll a1 = v1[i][w-1];
		ll a3 = v3[h - 2 - i][w-1];
		ll y = a1 + a3;
		ans = max(ans, y);
	}
	FOR(j, w - 1) {
		ll a1 = v1[h-1][j];
		ll a2 = v2[h-1][w - 2 - j];
		ll y = a1 + a2;
		ans = max(ans, y);
	}
	FOR(i, h - 1) FOR(j, w - 1) {
		ll a1 = v1[i][j];
		ll a2 = v2[i][w - 2 - j];
		ll a3 = v3[h - 2 - i][j];
		ll a4 = v4[h - 2 - i][w - 2 - j];

		ll x[4] = { a1, a2, a3, a4 };
		sort(x, x + 4);
		ll y = x[2] + x[3];
		ans = max(ans, y);
	}

	writerLn(ans);
	
	return 0;
}

Submission Info

Submission Time
Task D - 庭園
User math
Language C++11 (GCC 4.9.2)
Score 100
Code Size 5504 Byte
Status AC
Exec Time 178 ms
Memory 5272 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 4
AC × 15
AC × 30
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 29 ms 776 KB
sample1.txt AC 24 ms 816 KB
sample2.txt AC 23 ms 924 KB
sample3.txt AC 25 ms 928 KB
subtask0_0.txt AC 26 ms 1052 KB
subtask0_1.txt AC 26 ms 1052 KB
subtask0_10.txt AC 24 ms 1052 KB
subtask0_11.txt AC 26 ms 928 KB
subtask0_12.txt AC 26 ms 924 KB
subtask0_13.txt AC 24 ms 928 KB
subtask0_14.txt AC 26 ms 1048 KB
subtask0_2.txt AC 26 ms 992 KB
subtask0_3.txt AC 24 ms 1052 KB
subtask0_4.txt AC 24 ms 928 KB
subtask0_5.txt AC 24 ms 1052 KB
subtask0_6.txt AC 26 ms 1052 KB
subtask0_7.txt AC 24 ms 968 KB
subtask0_8.txt AC 26 ms 924 KB
subtask0_9.txt AC 24 ms 1056 KB
subtask1_0.txt AC 146 ms 4544 KB
subtask1_1.txt AC 158 ms 4892 KB
subtask1_10.txt AC 145 ms 4476 KB
subtask1_11.txt AC 172 ms 5112 KB
subtask1_12.txt AC 152 ms 4736 KB
subtask1_13.txt AC 177 ms 5272 KB
subtask1_14.txt AC 156 ms 4756 KB
subtask1_2.txt AC 173 ms 5200 KB
subtask1_3.txt AC 149 ms 4668 KB
subtask1_4.txt AC 154 ms 4832 KB
subtask1_5.txt AC 169 ms 5080 KB
subtask1_6.txt AC 164 ms 4900 KB
subtask1_7.txt AC 154 ms 4720 KB
subtask1_8.txt AC 178 ms 5260 KB
subtask1_9.txt AC 155 ms 4816 KB