oj.uz

답안 #815794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815794 2023-08-08T23:29:36 Z beaboss Nafta (COI15_nafta) C++14
100 / 100
 362 ms 114560 KB 
// Source: https://oj.uz/problem/view/COI15_nafta

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

const int N = 2001;

int r, s;

int a[N][N];
bool vis[N][N];

vpii events[N];
int st[N];

int miny, maxy, cost;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int contr[N];
int overlap[N][N];

int dp[N][N];

int ans[N];

void compute(int l, int r, int j, int optl, int optr) {
	if (l > r) return;
	int i = (l + r) / 2;
	int cur_opt;
	int best = 0;
	
	for (int k = optl; k <= min(i, optr); k++) {
		if (dp[k][j-1] - overlap[k][i] >= best) {
			best = dp[k][j-1] - overlap[k][i];
			cur_opt = k;
		}
	}

	dp[i][j] = best + contr[i];

	ans[j] = max(dp[i][j], ans[j]);

	compute(l, i - 1, j,  optl, cur_opt);
	compute(i+1, r, j, cur_opt, optr);

}

void solve(int x, int y) {
	// cout << x << y << endl;
	miny = min(miny, y);
	maxy = max(maxy, y);
	cost += a[x][y];
	vis[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int newx = x + dx[i];
		int newy = y + dy[i];

		if (newx >= 0 && newx < r && newy >= 0 && newy < s && !vis[newx][newy] && a[newx][newy] != -1) solve(newx, newy);

	}	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// input
	cin >> r >> s;

	FOR(i, 0, r) {
		FOR(j, 0, s) {
			char inp;
			cin >> inp;
			if (inp == '.') a[i][j] = -1;
			else a[i][j] = inp - '0';
		}
	}

	// extract components
	FOR(i, 0, r) FOR(j, 0, s) {
		if (!vis[i][j] && a[i][j] != -1) {
			maxy = j;
			miny = j;
			cost = 0;
			solve(i, j);
			events[miny].pb({miny, cost});
			events[maxy+1].pb({miny, -cost});
			FOR(i, miny, maxy + 1) {
				dp[i][0] += cost;
				contr[i] += cost;
				ans[0] = max(ans[0],dp[i][0]);
			}
		}
	}

	// get overlap
	FOR(i, 0, s) {
		for (auto val: events[i]) st[val.f] += val.s;
		int cur_count = 0;
		FOR(j, 0, i + 1) {
			cur_count += st[j];
			overlap[j][i] = cur_count;
		}

	}


	cout << ans[0] << endl;
	FOR(i, 1, s) {
		compute(0, s-1, i, 0, s-1);
		cout << ans[i] << endl;
	}




}

Compilation message

nafta.cpp: In function 'void compute(int, int, int, int, int)':
nafta.cpp:59:9: warning: 'cur_opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |  compute(l, i - 1, j,  optl, cur_opt);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1160 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1160 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 6 ms 5908 KB Output is correct
8 Correct 8 ms 5644 KB Output is correct
9 Correct 8 ms 6908 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 5 ms 5616 KB Output is correct
12 Correct 5 ms 5476 KB Output is correct

Subtask #3
66.0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1160 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 6 ms 5908 KB Output is correct
8 Correct 8 ms 5644 KB Output is correct
9 Correct 8 ms 6908 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 5 ms 5616 KB Output is correct
12 Correct 5 ms 5476 KB Output is correct
13 Correct 305 ms 67500 KB Output is correct
14 Correct 333 ms 61060 KB Output is correct
15 Correct 362 ms 114560 KB Output is correct
16 Correct 262 ms 59404 KB Output is correct
17 Correct 226 ms 53744 KB Output is correct
18 Correct 228 ms 53564 KB Output is correct