oj.uz

Submission #491207

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

using ll = long long;
// the value of k that minimizes dp[p-1][k-1] + (p[i]-p[k-1])^2
// is <= k that minimizes dp[p-1][k-1] + (p[i+1]-p[k-1])^2

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() {
	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 24 ms 48116 KB Output is correct
2 Correct 24 ms 48008 KB Output is correct
3 Correct 31 ms 48088 KB Output is correct
4 Correct 24 ms 47916 KB Output is correct
5 Correct 25 ms 47944 KB Output is correct
6 Correct 24 ms 47952 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 48116 KB Output is correct
2 Correct 24 ms 48008 KB Output is correct
3 Correct 31 ms 48088 KB Output is correct
4 Correct 24 ms 47916 KB Output is correct
5 Correct 25 ms 47944 KB Output is correct
6 Correct 24 ms 47952 KB Output is correct
7 Correct 41 ms 53440 KB Output is correct
8 Correct 43 ms 52692 KB Output is correct
9 Correct 42 ms 53832 KB Output is correct
10 Correct 40 ms 51868 KB Output is correct
11 Correct 44 ms 51936 KB Output is correct
12 Correct 42 ms 51864 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 48116 KB Output is correct
2 Correct 24 ms 48008 KB Output is correct
3 Correct 31 ms 48088 KB Output is correct
4 Correct 24 ms 47916 KB Output is correct
5 Correct 25 ms 47944 KB Output is correct
6 Correct 24 ms 47952 KB Output is correct
7 Correct 41 ms 53440 KB Output is correct
8 Correct 43 ms 52692 KB Output is correct
9 Correct 42 ms 53832 KB Output is correct
10 Correct 40 ms 51868 KB Output is correct
11 Correct 44 ms 51936 KB Output is correct
12 Correct 42 ms 51864 KB Output is correct
13 Correct 940 ms 141880 KB Output is correct
14 Execution timed out 1000 ms 140872 KB Time limit exceeded
15 Halted 0 ms 0 KB -