oj.uz

Submission #652913

# Submission time Handle Problem Language Result Execution time Memory
652913 2022-10-25T04:56:26 Z GusterGoose27 Nafta (COI15_nafta) C++11
100 / 100
 606 ms 111972 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 980 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 8 ms 6196 KB Output is correct
8 Correct 10 ms 6220 KB Output is correct
9 Correct 9 ms 6184 KB Output is correct
10 Correct 8 ms 6228 KB Output is correct
11 Correct 7 ms 6228 KB Output is correct
12 Correct 6 ms 6220 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 8 ms 6196 KB Output is correct
8 Correct 10 ms 6220 KB Output is correct
9 Correct 9 ms 6184 KB Output is correct
10 Correct 8 ms 6228 KB Output is correct
11 Correct 7 ms 6228 KB Output is correct
12 Correct 6 ms 6220 KB Output is correct
13 Correct 587 ms 111136 KB Output is correct
14 Correct 606 ms 111972 KB Output is correct
15 Correct 577 ms 110564 KB Output is correct
16 Correct 513 ms 111364 KB Output is correct
17 Correct 477 ms 110924 KB Output is correct
18 Correct 454 ms 110708 KB Output is correct