Submission #138097

#	Time	Username	Problem	Language	Result	Execution time	Memory
138097		emaborevkovic	Nafta (COI15_nafta)	C++17	100 / 100	884 ms	59256 KiB

nafta

#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 (stderr)

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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66