Submission 836 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
836	15/05/2013 23:00:41	leandro	D - Ratoneras	Accepted	125	3.5 KiB	GNU G++ 5.1.0

Code

/*
username: leandro
*/
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <set>
#include <map>
#include <sstream>
#include <queue>
#include <stack>

using namespace std;

//////////////////////////////////////
typedef long long i64;
typedef complex<double> pnt;
typedef pair<int, int> pii;
typedef vector<int> vi;
//////////////////////////////////////
const int oo = 1 << 30;
const double PI = M_PI;
const double EPS = 1e-15;
//////////////////////////////////////
#define F first
#define S second
#define foreach(i, u) \
		for (typeof(u.begin()) i = u.begin(); i != u.end(); i++)
#define REP(i, n) \
		for (int i = 0; i < (n); i++)
#define FOR(i, n) \
		for (int i = 1; i <= (n); i++)
//////////////////////////////////////
#define DEBUG(x) \
		cout << #x << " = " << x << endl

const int
	MaxN = 255;

int N, K;
int a[MaxN][MaxN];
int dp[MaxN][MaxN][8];

int getDescription(int a, int b)
{
	int description = 0;
	if (a ==     1) description |= 1;
	if (b ==     1) description |= 2;
	if (b == N-K+1) description |= 4;
	return description;
}

int main()
{
	cin.sync_with_stdio(false);

cin >> N >> K;
	for (int i = 1; i <= N; i++)
	for (int j = 1; j <= N; j++)
	{
		cin >> a[i][j];
		a[i][j] = a[i][j] + a[i][j-1];
	}

/* base case */
	for (int i = 1; i <= N - K + 1; i++)
	{
		for (int o = 0; o < 8; o++)
			dp[1][i][o] = -oo;
		dp[1][i][ getDescription(1, i) ] = a[1][i + K - 1] - a[1][i - 1];
	}

/* dp */
	for (int i = 2; i <= N; i++)
		for (int j = 1; j <= N - K + 1; j++)
		{
			int d = getDescription(i, j);
			int c = a[i][j + K - 1] - a[i][j - 1];

for (int t = 1; t <= N - K + 1; t++)
			{
				if (t + K - 1 < j || t > j + K - 1)
				{
					for (int o = 0; o < 8; o++)
						if (!(o & 2) || !(o & 4))
						{
							dp[i][j][d] = max(dp[i][j][d], dp[i - 1][t][o] + c);
						}
				}
				else
				{
					for (int o = 0; o < 8; o++)
						dp[i][j][d | o] = max(dp[i][j][d | o], dp[i - 1][t][o] + c);
				}
			}
		}

int answer = 0;
	for (int j = 1; j <= N - K + 1; j++)
		for (int o = 0; o < 8; o++)
		{
			if (((o & 2) && (o & 4)) || (o & 1)) continue;
			answer = max(answer, dp[N][j][o]);
		}

cout << answer << endl;

return 0;
}

Judgement Details

Test 01: 0.019 0.000 1428K ok
Test 02: 0.108 0.094 3200K ok
Test 03: 0.164 0.125 3448K ok
Test 04: 0.193 0.109 3628K ok
Test 05: 0.199 0.031 1404K ok
Test 06: 0.013 0.000 1420K ok
Test 07: 0.016 0.000 1464K ok
Test 08: 0.013 0.000 1500K ok
Test 09: 0.015 0.000 1636K ok
Test 10: 0.018 0.000 1740K ok
Test 11: 0.030 0.031 2112K ok
Test 12: 0.058 0.047 2644K ok
Accepted

Matcom Online Grader