oj.uz

Submission #634789

# Submission time Handle Problem Language Result Execution time Memory
634789 2022-08-25T04:21:19 Z GusterGoose27 Nafta (COI15_nafta) C++11
100 / 100
 670 ms 130912 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 9 ms 10580 KB Output is correct
8 Correct 11 ms 10664 KB Output is correct
9 Correct 10 ms 10580 KB Output is correct
10 Correct 10 ms 10580 KB Output is correct
11 Correct 10 ms 10580 KB Output is correct
12 Correct 9 ms 10580 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 9 ms 10580 KB Output is correct
8 Correct 11 ms 10664 KB Output is correct
9 Correct 10 ms 10580 KB Output is correct
10 Correct 10 ms 10580 KB Output is correct
11 Correct 10 ms 10580 KB Output is correct
12 Correct 9 ms 10580 KB Output is correct
13 Correct 378 ms 130248 KB Output is correct
14 Correct 567 ms 130912 KB Output is correct
15 Correct 344 ms 129868 KB Output is correct
16 Correct 372 ms 130460 KB Output is correct
17 Correct 670 ms 130120 KB Output is correct
18 Correct 636 ms 129960 KB Output is correct