Submission #97340

#	Time	Username	Problem	Language	Result	Execution time	Memory
97340		hugo_pm	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	300 ms	56652 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 1005;
int nbLig, nbCol;
int grille[borne][borne];
int dp[borne][borne][5];

// gauche, haut, droite, bas
int dlt[4][2] {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int gdp(int lig, int col, int dir);

int calc(int lig, int col, int dir, int dd) 
{
	int nl = lig+dlt[dd][0], nc = col+dlt[dd][1];
	if (nl < 0 || nc < 0 || nl >= nbLig || nc >= nbCol) return BIG;
	return gdp(nl, nc, dir)+1;
}

int gdp(int lig, int col, int dir)
{
	int &rep = dp[lig][col][dir];
	if (rep != -1) return rep;
	rep = grille[lig][col]+1;
	chmin(rep, calc(lig, col, dir, dir));
	chmin(rep, calc(lig, col, dir, (dir+1)%4));
	chmin(dp[lig][col][4], rep);
	return rep;
}


void solve()
{
	fill_n(&dp[0][0][0],borne*borne*5, -1);
	form(i, borne) form(j, borne) dp[i][j][4] = BIG;
	cin >> nbLig >> nbCol;
	form(i, nbLig) form(j, nbCol) cin >> grille[i][j];
	form(i, nbLig) form(j, nbCol) gdp(i, j, 0);
	form(i, nbLig) ford(j, nbCol) gdp(i, j, 1);
	ford(i, nbLig) ford(j, nbCol) gdp(i, j, 2);
	ford(i, nbLig) form(j, nbCol) gdp(i, j, 3);
	int rep = -BIG;
	form(lig, nbLig) form(col, nbCol) {
		chmax(rep, grille[lig][col] - dp[lig][col][4]);
	}
	cout << rep << "\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40