oj.uz

Submission #138097

# Submission time Handle Problem Language Result Execution time Memory
138097 2019-07-29T10:32:46 Z emaborevkovic Nafta (COI15_nafta) C++17
100 / 100
 884 ms 59256 KB 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define ll long long

const int N = 2005;
char a[N][N];
int n, m;
bool bio[N][N];
queue <pair <int,int> > q;
int b[N][N], c[N][N], d[N];
int dp[N][N];

void func(int l, int r, int ol, int orr, int kk) {
	if (r < l) return;
	int mid = (l+r)/2;
	int pos = ol;
	for (int i=max(mid+1, ol);i<=orr;i++) {
		if (dp[mid][kk] < dp[i][kk-1] + c[mid][i]) {
			dp[mid][kk] = dp[i][kk-1] + c[mid][i];
			pos = i;
		}
	}
	func(l, mid-1, ol, pos, kk);
	func(mid+1, r, pos, orr, kk);
}

int main() {
	cin >> n >> m;
	for (int i=0;i<n;i++) {
		for (int j=0;j<m;j++) {
			scanf(" %c", &a[i][j]);
		}
	}
	for (int j=0;j<m;j++) {
		for (int i=0;i<n;i++) {
			if (a[i][j] == '.') continue;
			if (bio[i][j]) continue;
			q.push(mp(i,j));
			int suma = 0;
			int x, y, my = 0;
			while (!q.empty()) {
				x = q.front().first;
				y = q.front().second;
				my = max(my, y);
				suma += a[x][y] - '0';
				q.pop();
				bio[x][y] = 1;
				for (int kk=-1;kk<2;kk++) {
					for (int l=-1;l<2;l++) {
						if (kk != 0 && l != 0) continue;
						x += kk; y += l;
						if (x > n-1 || x < 0 || y > m-1 || y < 0);
						else if (bio[x][y]); 
						else if (a[x][y] == '.');
						else if (!bio[x][y]) {
							bio[x][y] = 1;
							q.push(mp(x, y));
						}
						x -= kk; y -= l;
					}
				}
			}
			b[j][j]+=suma;
			b[j][my+1]-=suma;
		}
	}
	for (int i=0;i<m;i++) {
		for (int j=1;j<m;j++) {
			b[i][j] += b[i][j-1];
		}
	}
	for (int i=0;i<m;i++) {
		for (int j=m-2;j>=0;j--) {
			c[j][i] = c[j+1][i] + b[j+1][i];
		}
	}
	for (int i=0;i<m;i++) dp[i][1] = 0;
	for (int i=2;i<=m;i++) {
		func(0, m-1, 0, m-1, i);
	}
	for (int i=0;i<m;i++) {
		for (int j=0;j<=i;j++) d[i] += b[j][i];	
	}
	for (int i=1;i<=m;i++) {
		int res = 0;
		for (int j=0;j<m;j++) {
			dp[j][i] += d[j];
			res = max(res, dp[j][i]);
		}
		printf("%d\n", res);
	}
	return 0;
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:40:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 17 ms 6136 KB Output is correct
8 Correct 18 ms 6136 KB Output is correct
9 Correct 20 ms 6108 KB Output is correct
10 Correct 16 ms 6136 KB Output is correct
11 Correct 16 ms 6136 KB Output is correct
12 Correct 16 ms 6136 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 17 ms 6136 KB Output is correct
8 Correct 18 ms 6136 KB Output is correct
9 Correct 20 ms 6108 KB Output is correct
10 Correct 16 ms 6136 KB Output is correct
11 Correct 16 ms 6136 KB Output is correct
12 Correct 16 ms 6136 KB Output is correct
13 Correct 792 ms 55316 KB Output is correct
14 Correct 866 ms 55296 KB Output is correct
15 Correct 884 ms 55368 KB Output is correct
16 Correct 736 ms 59168 KB Output is correct
17 Correct 686 ms 59220 KB Output is correct
18 Correct 671 ms 59256 KB Output is correct