Submission #634789

#	Time	Username	Problem	Language	Result	Execution time	Memory
634789		GusterGoose27	Nafta (COI15_nafta)	C++11	100 / 100	670 ms	130912 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2000;
int n, m;
int val[MAXN][MAXN];
pii uf[MAXN][MAXN];
int sum[MAXN][MAXN];
pii span[MAXN][MAXN];
map<int, int> intervals[MAXN];

pii get(pii arr[][MAXN], pii p) {
	return arr[p.first][p.second];
}

int get(int arr[][MAXN], pii p) {
	return arr[p.first][p.second];
}

pii find(pii p) {
	return (get(uf, p) == p) ? p : (uf[p.first][p.second] = find(get(uf, p)));
}

void merge(pii a, pii b) {
	if (get(val, a) < 0 || get(val, b) < 0) return;
	pii ia = find(a);
	pii ib = find(b);
	if (ia == ib) return;
	span[ia.first][ia.second] = pii(min(get(span, ia).first, get(span, ib).first), max(get(span, ia).second, get(span, ib).second));
	uf[ib.first][ib.second] = ia;
	sum[ia.first][ia.second] += get(sum, ib);
}

class linked_list {
public:
	int nextval[MAXN];
	int slope[MAXN];
	int lastval = 0;
	int firstval = 0;
	int findex;
	linked_list() {
		findex = m;
		lastval = 0;
		firstval = 0;
	}
	void adj(int p) {
		if (nextval[p] == m) {
			lastval += slope[p];
			slope[p] = 0;
			return;
		}
		if (slope[p] <= 0) return;
		slope[p] += slope[nextval[p]];
		nextval[p] = nextval[nextval[p]];
		adj(p);
	}
	void upd() {
		int p = findex;
		for (pii update: intervals[findex]) {
			firstval += update.second;
			while (nextval[p] <= update.first) p = nextval[p];
			slope[p] += update.second;
			adj(p);
		}
	}
	int best() {
		return lastval;
	}
	void ins(int nval) {
		findex--;
		nextval[findex] = findex+1;
		slope[findex] = nval-firstval;
		firstval = nval;
		adj(findex);
	}
};

linked_list *dp[MAXN+1];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			uf[i][j] = pii(i, j);
			span[i][j] = pii(j, j);
			if (s[j] == '.') val[i][j] = -1;
			else val[i][j] = s[j]-'0';
			sum[i][j] = val[i][j]; 
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m-1; j++) merge(pii(i, j), pii(i, j+1));
	}
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j < m; j++) merge(pii(i, j), pii(i+1, j));
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (uf[i][j] == pii(i, j) && val[i][j] >= 0) intervals[span[i][j].first][span[i][j].second] += sum[i][j];
		}
	}
	for (int i = 0; i <= m; i++) dp[i] = new linked_list();
	for (int i = m-1; i >= 0; i--) {
		for (int k = m; k > 0; k--) {
			dp[k]->ins(dp[k-1]->best());
			dp[k]->upd();
		}
	}
	for (int i = 1; i <= m; i++) cout << dp[i]->best() << "\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66