제출 #530913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530913		danielliu04	Nafta (COI15_nafta)	C++17	100 / 100	525 ms	144480 KiB

nafta

// Link: https://oj.uz/problem/view/COI15_nafta

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

#define ll long long
#define ld long double
// #define lc (node<<1)+1
// #define rc (node<<1)+2
#define endl '\n'
// #define INF 1e18


const int max_n = 2002;

int n, m;

int matrix[max_n][max_n];
int I[max_n][max_n];
int W[max_n][max_n];
bool visited[max_n][max_n];
int opt[max_n][max_n]; // this is the optimal index for each dp

int dp[max_n][max_n];

int curr_sum, left_most, right_most;

int vr[4] = {0, 0, -1, 1};
int vc[4] = {1, -1, 0, 0};

bool valid(int i, int j){
	return i >= 0 && j >= 0 && i < n && j < m && !visited[i][j] && matrix[i][j] != -1;
}
void dfs(int i, int j){
	visited[i][j] = 1;
	curr_sum += matrix[i][j];
	left_most = min(left_most, j);
	right_most = max(right_most, j);

	for(int x = 0; x < 4; x ++){
		int ni = i + vr[x], nj = j + vc[x];
		if(valid(ni, nj)) dfs(ni, nj);
	}
}

int get_w(int i, int j){
	if(i == -1) return W[i+1][j] + I[i+1][j];
	else return W[i][j];
}

int get_dp(int i, int j){
	if(i == -1) return 0;
	else return dp[i][j];
}

void compute(int j, int left = 0, int right = m-1, int optl = -1, int optr = m-1){

	if(left > right) return;

	int mid = (left + right) / 2;
	// find the best answer for mid

	int opt_i = -2, res = 0;

	for(int k = optl; k <= min(mid-1, optr); k ++){
		if(opt_i == -2 || get_w(k, mid) + get_dp(k, j-1) > res){
			opt_i = k;
			res = get_w(k, mid) + get_dp(k, j-1);
		}
	}

	dp[mid][j] = res;
	opt[mid][j] = opt_i;

	compute(j, left, mid-1, optl, opt_i);
	compute(j, mid + 1, right, opt_i, optr);
}

int main() {

	// ios_base::sync_with_stdio(0);
	// cin.tie(0);	

	cin >> n >> m;

	for(int i = 0; i < n; i ++){
		string row; cin >> row;
		for(int j = 0; j < m; j ++){
			if(row[j] == '.') matrix[i][j] = -1;
			else matrix[i][j] = row[j] - '0';
		}
	}

	// cout << "here" << endl;


	// find all connected components and compute I
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			if(matrix[i][j] != -1 && !visited[i][j]){
				curr_sum = 0; left_most = right_most = j;
				dfs(i, j);
				I[left_most][left_most] += curr_sum;
				I[left_most][right_most + 1] -= curr_sum;
			}
		}
	}

	// cout << "here" << endl;

	for(int i = 0; i < m; i ++){
		for(int j = 1; j < m; j ++){
			I[i][j] += I[i][j-1];
		}
	}

	// then compute W
	for(int j = 0; j < m; j ++){
		W[j][j] = 0; // no way
		for(int i = j-1; i >= 0; i --){
			W[i][j] = W[i+1][j] + I[i+1][j];
		}
	}

	// cout << "here" << endl;

	// Now do the most simple dp transition
	// dp[i][j] -> maximum oil using the i-th col as the last with j pumps

	for(int i = 0; i <= m; i ++){
		for(int j = 0; j <= m; j ++){
			opt[i][j] = -1;
		}
	}

	// for(int j = 1; j <= m; j ++){
	// 	for(int i = j - 1; i < m; i ++){
	// 		for(int k = i - 1; k >= j-2; k --){
	// 			if(opt[i][j] == -1 || get_w(k, i) + get_dp(k, j - 1) >= dp[i][j]){
	// 				opt[i][j] = k;
	// 				dp[i][j] = get_w(k, i) + get_dp(k, j - 1);
	// 			}
	// 		}
	// 	}
	// }

	for(int j = 1; j <= m; j ++){
		compute(j);
	}

	for(int j = 1; j <= m; j ++){
		int res = 0;
		for(int i = 0; i < m; i ++){
			res = max(res, dp[i][j]);
		}
		cout << res << endl;
	}
}	

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