oj.uz

Submission #9803

# Submission time Handle Problem Language Result Execution time Memory
9803 2014-09-28T09:12:55 Z shashack On grid (kriii2_O) C++14
0 / 4
 0 ms 1676 KB 
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <bitset>
#include <limits.h>

using namespace std;

#define MP make_pair
#define REP(v, repeat) for(int v=0; v<(repeat); ++v)
#define REPD(v, repeat) for(int v=(repeat)-1; v>=0; --v)
#define FOR(v, pos, end) for(int v=(pos); v<=(end); ++v)
#define FORD(v, pos, end) for(int v=(pos); v>=(end); --v)
#define ROUNDING(x, dig) (floor((x) * pow(10, dig) + 0.11f) / pow(10, dig))

typedef pair<int, int> PI;
typedef vector <bool> VB;
typedef vector <int> VI;
typedef vector <VI> VVI;
typedef vector <vector <PI>> ADJ;
typedef vector <string> VS;
typedef long long ll;
typedef unsigned long long ull;

const int INF = 987654321;
int r, c;
vector <vector <ll>> table, cache;

ll maxScore(const int & y, const int & x)
{
	if (x <= 1 || y <= 1) return table[y][x];

	ll & ret = cache[y][x];
	if (ret != -INF) return ret;

	FOR(i, 0, y - 1)
	{
		FOR(j, 0, x - 1)
		{
			ret = max(ret, maxScore(i, j) + (table[y][x] - table[i][x] - table[y][j] + table[i][j]));
		}
	}
	return ret;
}

int main()
{
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w+", stdout);
#endif

	scanf("%d%d", &r, &c);
	table = vector <vector <ll>>(r + 1, vector <ll>(c + 1, 0));
	cache = vector <vector <ll>>(r + 1, vector <ll>(c + 1, -INF));

	FOR(i, 1, r) FOR(j, 1, c) scanf("%lld", &table[i][j]);
	FOR(i, 1, r) FOR(j, 1, c) table[i][j] = table[i][j] + table[i - 1][j] + table[i][j - 1] - table[i - 1][j - 1];

	printf("%lld\n", maxScore(r, c));

	return 0;
}

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Correct 0 ms 1676 KB Output is correct
3 Incorrect 0 ms 1676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -