Submission #491207

#	Time	Username	Problem	Language	Result	Execution time	Memory
491207		macktvz	Nafta (COI15_nafta)	C++17	34 / 100	1000 ms	141880 KiB

nafta

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66