oj.uz

Submission #491209

# Submission time Handle Problem Language Result Execution time Memory
491209 2021-11-30T18:11:17 Z macktvz Nafta (COI15_nafta) C++17
100 / 100
 814 ms 160708 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int R = 2e3+1;

bool vis1[R][R];
bool vis2[R][R];
int id[R][R];
int grid[R][R];
int n,m;
int oil[R*R];
vector<int> dp_cur(R,0),dp_last(R,0);
vector<int> Li(R*R,R);
vector<int> Ri(R*R,-1);
int poil[R];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<vector<int>> bad(R,vector<int>(R,0));
int bit[R*R];
int ans[R];
void update(int i, int val) {
	for (; i <= m; i+=i&(-i)) {
		bit[i]+=val;
	}
}
int qry(int i) {
	int ret = 0;
	for(;i>0;i-=i&(-i)){
		ret += bit[i];
	}
	return ret;
}
int qry(int i, int j) {
	return qry(j)-qry(i-1);
}
bool chk(int i, int j) {return i>=0 && j>=0 && i < n && j < m && grid[i][j]!=-1;}

int dfs1(int x,int y) {
	if (!chk(x,y) || vis1[x][y]) return 0;
	vis1[x][y] = true;
	int sum =grid[x][y] ;
	for(int i = 0; i < 4; i++) {
		sum += dfs1(x+dx[i],y+dy[i]);
	}
	return sum;
}

void dfs2(int x, int y, int cid) {
	if (!chk(x,y) || vis2[x][y]) return;
	vis2[x][y] = true;
	id[x][y] = cid;
	Li[cid] = min(Li[cid],y);
	Ri[cid] = max(Ri[cid],y);
	for(int i = 0; i < 4; i++) {
		dfs2(x+dx[i],y+dy[i],cid);
	}
}

void solve(int l, int r, int dl, int dr) {
	if (l > r) return;
	int mid = (l+r) >> 1;
	pair<int,int> best = {1e9,-1};
	for(int k = dl; k <= min(mid,dr); k++) {
		best = min(best,{dp_last[k] + bad[k][mid] - poil[mid],k});
	} 

	dp_cur[mid] = best.first;
	int opt = best.second;
	solve(l,mid-1,dl,opt);
	solve(mid+1,r,opt,dr);
}

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	char c;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> c;
			if (c=='.') grid[i][j]=-1;
			else grid[i][j]=c-'0';
		}
	}
	int currs;
	int cid=0;
    set<int> seen;
	for(int j = 0; j < m; j++) {
		seen.clear();
		poil[j] = 0;
		for(int i = 0; i < n; i++) {
			if (grid[i][j] != -1 && !vis1[i][j]) {
				currs = dfs1(i,j);
				dfs2(i,j,cid++);
				oil[cid-1]=currs;
				seen.insert(cid-1);
				poil[j] += currs;
			} else if (grid[i][j] != -1) {
				if (seen.find(id[i][j]) == seen.end()) {
					poil[j] += oil[id[i][j]];
					seen.insert(id[i][j]);
				}
			}
		}
	}
	vector<pair<int,pair<int,int>>> events;
	for(int i = 0; i < m; i++) {
		for(int j = i+1; j < m; j++) {
			events.push_back({j+1,{i+1,-1}});
		}
	}
	for(int i = 0; i < cid; i++) {
		events.push_back({Li[i]+1,{i,1}});
		events.push_back({Ri[i]+1,{i,0}});

	}
	sort(begin(events),end(events),[&](auto a, auto b) {
		return (a.first==b.first?a.second.second < b.second.second:a.first < b.first);
	});
	int active = 0;
	for(auto e : events){
		if (e.second.second == -1) {
			bad[e.second.first-1][e.first-1] = active-qry(e.second.first+1,m);
		} else if(e.second.second==1) {
			active += oil[e.second.first];
			update(e.first,oil[e.second.first]);
		} else {
			active -= oil[e.second.first];
			update(Li[e.second.first]+1,-oil[e.second.first]);
		}
	}
    for(int i = 0; i <m;i++) bad[i][i] = poil[i];
	for(int i = 0; i < m; i++) {
		dp_last[i] = -poil[i];
		ans[0] = min(dp_last[i],ans[0]);
	}
	for(int i = 1; i<m; i++) {
		solve(0,m-1,0,m-1);
		dp_last = dp_cur;
		for(int j = 0; j < m; j++) {
			ans[i] = min(ans[i],dp_last[j]);
		}
	}
	for(int i = 0; i < m; i++) {
		cout << -ans[i] << endl;
	}
	
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48076 KB Output is correct
2 Correct 23 ms 48092 KB Output is correct
3 Correct 25 ms 48048 KB Output is correct
4 Correct 24 ms 47928 KB Output is correct
5 Correct 23 ms 47924 KB Output is correct
6 Correct 23 ms 47960 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48076 KB Output is correct
2 Correct 23 ms 48092 KB Output is correct
3 Correct 25 ms 48048 KB Output is correct
4 Correct 24 ms 47928 KB Output is correct
5 Correct 23 ms 47924 KB Output is correct
6 Correct 23 ms 47960 KB Output is correct
7 Correct 37 ms 53412 KB Output is correct
8 Correct 38 ms 52596 KB Output is correct
9 Correct 38 ms 53660 KB Output is correct
10 Correct 36 ms 51816 KB Output is correct
11 Correct 35 ms 51784 KB Output is correct
12 Correct 36 ms 51784 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48076 KB Output is correct
2 Correct 23 ms 48092 KB Output is correct
3 Correct 25 ms 48048 KB Output is correct
4 Correct 24 ms 47928 KB Output is correct
5 Correct 23 ms 47924 KB Output is correct
6 Correct 23 ms 47960 KB Output is correct
7 Correct 37 ms 53412 KB Output is correct
8 Correct 38 ms 52596 KB Output is correct
9 Correct 38 ms 53660 KB Output is correct
10 Correct 36 ms 51816 KB Output is correct
11 Correct 35 ms 51784 KB Output is correct
12 Correct 36 ms 51784 KB Output is correct
13 Correct 727 ms 137992 KB Output is correct
14 Correct 814 ms 137016 KB Output is correct
15 Correct 780 ms 160708 KB Output is correct
16 Correct 700 ms 137028 KB Output is correct
17 Correct 668 ms 111536 KB Output is correct
18 Correct 669 ms 111536 KB Output is correct