oj.uz

Submission #110835

# Submission time Handle Problem Language Result Execution time Memory
110835 2019-05-12T11:15:33 Z hugo_pm Bob (COCI14_bob) C++17
120 / 120
 193 ms 40524 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17272 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16876 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17244 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 17016 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 39300 KB Output is correct
2 Correct 93 ms 34424 KB Output is correct
3 Correct 88 ms 34628 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 40524 KB Output is correct
2 Correct 105 ms 34552 KB Output is correct
3 Correct 111 ms 34424 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 39724 KB Output is correct
2 Correct 100 ms 34512 KB Output is correct
3 Correct 103 ms 34352 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 40156 KB Output is correct
2 Correct 116 ms 34552 KB Output is correct
3 Correct 104 ms 34324 KB Output is correct