Submission #652913

#	Time	Username	Problem	Language	Result	Execution time	Memory
652913		GusterGoose27	Nafta (COI15_nafta)	C++11	100 / 100	606 ms	111972 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2000;

int val[MAXN][MAXN];
int uf[MAXN*MAXN];
int sum[MAXN*MAXN];
pii uf_range[MAXN*MAXN];
int n, m;
map<pii, int> ranges;
int bit[MAXN];
int single_val[MAXN][MAXN]; // placing at i, drills j and above
int dp[MAXN+1][MAXN+1]; // pos i and above, j drills

class stree {
public:
	int sum = 0;
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
		}
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			sum += v;
			return;
		}
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
	}
	int get(int p) {
		if (lp > p || rp < p) return 0;
		if (lp == rp) return sum;
		return sum+l->get(p)+r->get(p);
	}
};

int hsh(int i, int j) {
	return i*m+j;
}

int find(int i) {
	return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		uf[a] = b;
		sum[b] += sum[a];
		uf_range[b] = pii(min(uf_range[b].first, uf_range[a].first), max(uf_range[b].second, uf_range[a].second));
	}
}

void make_dp(int pos, int lp, int rp, int nlp, int nrp) {
	if (rp < lp) return;
	int cur = (lp+rp)/2;
	int best = nlp;
	int bestval = -1;
	for (int i = nlp; i <= nrp; i++) {
		int cval = single_val[i][pos]+dp[i+1][cur-1];
		if (cval > bestval) {
			bestval = cval;
			best = i;
		}
	}
	dp[pos][cur] = bestval;
	make_dp(pos, lp, cur-1, best, nrp);
	make_dp(pos, cur+1, rp, nlp, best);
}

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++) {
			int cur = hsh(i, j);
			if (s[j] == '.') val[i][j] = -1;
			else val[i][j] = s[j]-'0';
			sum[cur] = val[i][j];
			uf_range[cur] = pii(j, j);
			uf[cur] = -1;
		}
	}
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j < m; j++) {
			if (val[i][j] >= 0 && val[i+1][j] >= 0) merge(hsh(i, j), hsh(i+1, j));
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m-1; j++) {
			if (val[i][j] >= 0 && val[i][j+1] >= 0) merge(hsh(i, j), hsh(i, j+1));
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cur = hsh(i, j);
			if (val[i][j] >= 0 && uf[cur] == -1) ranges[uf_range[cur]] += sum[cur];
		}
	}
	stree *tree = new stree(0, m-1);
	auto r_pos = ranges.rbegin();
	for (int j = m-1; j >= 0; j--) {
		while (r_pos != ranges.rend() && r_pos->first.first >= j) {
			tree->upd(r_pos->first.first, r_pos->first.second, r_pos->second);
			r_pos++;
		}
		for (int i = j; i < m; i++) single_val[i][j] = tree->get(i);
	}
	for (int j = m-1; j >= 0; j--) make_dp(j, 1, m-j, j, m-1);
	for (int i = 1; i <= m; i++) cout << dp[0][i] << "\n";
}

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