oj.uz

Submission #336635

# Submission time Handle Problem Language Result Execution time Memory
336635 2020-12-16T06:48:02 Z super_j6 Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 59884 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 2002, mxk = mxn * mxn, w = 2;
const int dx[w] = {1, 0};
const int dy[w] = {0, 1};
int n, m, k;
int s[mxk], l[mxk], r[mxk], par[mxk], rnk[mxk];
int a[mxn][mxn], f[mxn][mxn], dp[mxn][mxn];

int fnd(int x){
	return x == par[x] ? x : par[x] = fnd(par[x]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	memset(a, -1, sizeof(a));
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= m; j++){
		char c;
		cin >> c;
		if(isdigit(c)){
			s[k] = c - '0', l[k] = r[k] = j, par[a[i][j] = k] = k;
			for(int p = 0; p < 2; p++){
				int x = i - dx[p], y = j - dy[p];
				if(~a[x][y]){
					int u = fnd(k), v = fnd(a[x][y]);
					if(u == v) continue;
					if(rnk[u] < rnk[v]) swap(u, v);
					rnk[u] += rnk[u] == rnk[v];
					par[v] = u, s[u] += s[v];
					l[u] = min(l[u], l[v]), r[u] = max(r[u], r[v]);
				}
			}
			k++;
		}
	}
	
	for(int i = 0; i < k; i++) if(fnd(i) == i) f[l[i]][r[i]] += s[i];
	
	for(int i = 1; i <= m; i++)
	for(int j = m; j; j--){
		f[i][j] += f[i - 1][j] + f[i][j + 1] - f[i - 1][j + 1];
	}
	
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= m; j++)
		for(int p = j - 1; ~p; p--){
			dp[i][j] = max(dp[i][j], dp[i - 1][p] + f[j][j] - f[p][j]);
		}
		cout << (*max_element(dp[i] + 1, dp[i] + m + 1)) << endl;
	}

	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16492 KB Output is correct
2 Correct 10 ms 16512 KB Output is correct
3 Correct 10 ms 16504 KB Output is correct
4 Correct 9 ms 16512 KB Output is correct
5 Correct 11 ms 16492 KB Output is correct
6 Correct 10 ms 16620 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16492 KB Output is correct
2 Correct 10 ms 16512 KB Output is correct
3 Correct 10 ms 16504 KB Output is correct
4 Correct 9 ms 16512 KB Output is correct
5 Correct 11 ms 16492 KB Output is correct
6 Correct 10 ms 16620 KB Output is correct
7 Correct 35 ms 19820 KB Output is correct
8 Correct 36 ms 20180 KB Output is correct
9 Correct 40 ms 20480 KB Output is correct
10 Correct 35 ms 19692 KB Output is correct
11 Correct 34 ms 19692 KB Output is correct
12 Correct 35 ms 19820 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16492 KB Output is correct
2 Correct 10 ms 16512 KB Output is correct
3 Correct 10 ms 16504 KB Output is correct
4 Correct 9 ms 16512 KB Output is correct
5 Correct 11 ms 16492 KB Output is correct
6 Correct 10 ms 16620 KB Output is correct
7 Correct 35 ms 19820 KB Output is correct
8 Correct 36 ms 20180 KB Output is correct
9 Correct 40 ms 20480 KB Output is correct
10 Correct 35 ms 19692 KB Output is correct
11 Correct 34 ms 19692 KB Output is correct
12 Correct 35 ms 19820 KB Output is correct
13 Execution timed out 1052 ms 59884 KB Time limit exceeded
14 Halted 0 ms 0 KB -