Submission #110835

#	Time	Username	Problem	Language	Result	Execution time	Memory
110835		hugo_pm	Bob (COCI14_bob)	C++17	120 / 120	193 ms	40524 KiB

bob

#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;
typedef pair<int, int> pii;

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

const int borne = 1005;
int tab[borne][borne];
int rel[borne][borne]; // rel on lig
int cteUntil[borne][borne];
stack<int> onCol[borne];

int dp[borne][borne];

int nbLig, nbCol;

void solve()
{
	cin >> nbLig >> nbCol;
	form(lig, nbLig) {
		form(col, nbCol) {
			cin >> tab[lig][col];
			if (col > 0) {
				rel[lig][col] = rel[lig][col-1];
				if (tab[lig][col] != tab[lig][col-1]) ++rel[lig][col];
			}
		}
		cteUntil[lig][nbCol-1] = nbCol-1;
		ford(col, nbCol-1) {
			cteUntil[lig][col] = cteUntil[lig][col+1];
			if (tab[lig][col] != tab[lig][col+1]) cteUntil[lig][col] = col;
		}
	}

	form(col, nbCol) onCol[col].push(nbLig);

	int rep = 0;

	ford(ligDeb, nbLig) ford(colDeb, nbCol) {
		int sousRep = 0;
		int ct = cteUntil[ligDeb][colDeb];

		int ligRepr = -1;
		while (!onCol[colDeb].empty()) {
			int potRepr = onCol[colDeb].top();

			bool leChoisir = false;
			if (potRepr == nbLig) leChoisir = true;
			else if (tab[potRepr][colDeb] != tab[ligDeb][colDeb]) leChoisir = true;
			else if (cteUntil[potRepr][colDeb] < cteUntil[ligDeb][colDeb]) leChoisir = true;

			if (leChoisir) {
				ligRepr = potRepr;
				break;
			}
			onCol[colDeb].pop();
		}
		assert(ligRepr != -1);

		sousRep += (ligRepr - ligDeb) * (ct - colDeb + 1);
		if (ligRepr < nbLig && tab[ligRepr][colDeb] == tab[ligDeb][colDeb]) sousRep += dp[ligRepr][colDeb];

		dp[ligDeb][colDeb] = sousRep;
		rep += sousRep;

		onCol[colDeb].push(ligDeb);
	}

	cout << rep << "\n";
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12