oj.uz

Submission #530913

# Submission time Handle Problem Language Result Execution time Memory
530913 2022-02-27T05:39:36 Z danielliu04 Nafta (COI15_nafta) C++17
100 / 100
 525 ms 144480 KB 
// 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1448 KB Output is correct
4 Correct 1 ms 1452 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1448 KB Output is correct
4 Correct 1 ms 1452 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 9 ms 8524 KB Output is correct
8 Correct 11 ms 8500 KB Output is correct
9 Correct 11 ms 9932 KB Output is correct
10 Correct 9 ms 8524 KB Output is correct
11 Correct 9 ms 8504 KB Output is correct
12 Correct 9 ms 8524 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1448 KB Output is correct
4 Correct 1 ms 1452 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 9 ms 8524 KB Output is correct
8 Correct 11 ms 8500 KB Output is correct
9 Correct 11 ms 9932 KB Output is correct
10 Correct 9 ms 8524 KB Output is correct
11 Correct 9 ms 8504 KB Output is correct
12 Correct 9 ms 8524 KB Output is correct
13 Correct 418 ms 84712 KB Output is correct
14 Correct 464 ms 84672 KB Output is correct
15 Correct 525 ms 144480 KB Output is correct
16 Correct 395 ms 84544 KB Output is correct
17 Correct 422 ms 84596 KB Output is correct
18 Correct 431 ms 84528 KB Output is correct