제출 #1286627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286627		mdobric	Nafta (COI15_nafta)	C++20	0 / 100	2 ms	1340 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2005;
int r, s;
char c[maxn][maxn];
int dp[maxn][maxn], suma[maxn][maxn], bio[maxn][maxn], ukp[maxn][maxn];
queue <pair <int, int> > q;
int desno, val, lijevo;
int pomakx[4] = {1, 0, 0, -1};
int pomaky[4] = {0, 1, -1, 0};
vector <int> pl[maxn], mi[maxn];

void bfs (){
	while (!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++){
			int novix = x + pomakx[i];
			int noviy = y + pomaky[i];
			if (novix >= 0 and novix < r and noviy >= 0 and noviy < s and bio[novix][noviy] == 0 and c[novix][noviy] != '.'){
				q.push({novix, noviy});
				if (noviy > desno) desno = noviy;
				if (noviy < lijevo) lijevo = noviy;
				val += c[novix][noviy] - '0';
				bio[novix][noviy] = 1;
			}
		}
	}
}

void solve (int low, int high, int x, int y, int k){
	if (low > high) return;
	int mid = (low + high) / 2;
	dp[mid][k] = -1;
	int opt;
	for (int i = x; i <= min(y, mid - 1); i++){
		if (dp[i][k - 1] + suma[i][mid] > dp[mid][k]){
			dp[mid][k] = dp[i][k - 1] + suma[i][mid];
			opt = i;
		}
	}
	solve(low, mid - 1, x, opt, k);
	solve(mid + 1, high, opt, y, k);
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> r >> s;
	for (int i = 0; i < r; i++){
		for (int j = 0; j < s; j++){
			cin >> c[i][j];
		}
	}
	for (int i = 0; i < r; i++){
		for (int j = 0; j < s; j++){
			if (bio[i][j] == 0 and c[i][j] != '.'){
				q.push({i, j});
				bio[i][j] = 1;
				desno = j, lijevo = j, val = c[i][j] - '0';
				bfs();
				ukp[lijevo][desno] += val;
				pl[lijevo].push_back(val);
				mi[desno+1].push_back(val);
			}
		}
	}
	int tr = 0;
	for (int i = 0; i < s; i++){
		for (int j = 0; j < pl[i].size(); j++) tr += pl[i][j];
		for (int j = 0; j < mi[i].size(); j++) tr -= mi[i][j];
		dp[i][1] = tr;
	}
	for (int i = s - 1; i >= 0; i--){
		int dodaj = 0;
		for (int j = s - 1; j >= i + 1; j--){
			dodaj += ukp[i+1][j];
			suma[i][j] = suma[i + 1][j] + dodaj;
			//cout << i << " " << j << " " << suma[i][j] << endl;
		}
	}
	//cout << endl;
	int ans = 0;
	for (int i = 0; i < s; i++){
		ans = max(ans, dp[i][1]);
		//cout << dp[i][1] << endl;
	}
	cout << ans << endl;
	for (int k = 2; k <= s; k++){
		solve(0, s - 1, 0, s - 1, k);
		ans = 0;
		for (int i = 0; i < s; i++) ans = max(ans, dp[i][k]);
		cout << ans << "\n";
	}
	
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66