Submission #542977

#	Time	Username	Problem	Language	Result	Execution time	Memory
542977		fcw	Nafta (COI15_nafta)	C++17	100 / 100	457 ms	102120 KiB

nafta

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

struct DP { // Modify at will:
	vector<vector<int>>cost;
	vector<int> old, cur;
	DP(const vector<vector<int>>&_cost, int n): cost(_cost), old(n, inf), cur(n, inf) {}
	int lo(int ind) { return 0; }
	int hi(int ind) { return ind; }
	lint f(int ind, int k) { return old[k] + cost[k][ind]; }
	void store(int ind, int k, lint v) { cur[ind] = (int)v; }
	void rec(int L, int R, int LO, int HI) {
		if (L >= R) return;
		int mid = (L + R) >> 1;
		pair<lint, int> best(LLONG_MAX, LO);
		for(int k = max(LO,lo(mid)); k <= min(HI,hi(mid)); ++k)
			best = min(best, make_pair(f(mid, k), k));
		store(mid, best.second, best.first);
		rec(L, mid, LO, best.second);
		rec(mid+1, R, best.second, HI);
	}
	void solve(int L, int R) { rec(L, R, INT_MIN, INT_MAX); }
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	/*
	ifstream cin;
	cin.open("cbarn.in");
	ofstream cout;
	cout.open("cbarn.out");
	*/
	int n, m;
	cin>>n>>m;
	vector<string>s(n);
	for(int i=0;i<n;i++) cin>>s[i];
	vector<vector<bool>>vis(n, vector<bool>(m));
	vector<int>sum, l, r;
	int comp = 0;
	vector<pair<int, int>>dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	auto dfs = [&](auto& self, int x, int y)->void{
		vis[x][y] = 1;
		l[comp] = min(l[comp], y);
		r[comp] = max(r[comp], y);
		sum[comp] += s[x][y] - '0';
		for(auto [a, b] : dir){
			int nx = x + a, ny = y + b;
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || s[nx][ny] == '.') continue;
			self(self, nx, ny);
		}
	};
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(!vis[i][j] && s[i][j] != '.'){
				sum.push_back(0);
				l.push_back(j);
				r.push_back(j);
				dfs(dfs, i, j);
				comp++;
			}
		}
	}
	vector<vector<int>>cost(m+1, vector<int>(m+1)), aux = cost;
	for(int i=0;i<comp;i++){
		for(int j=l[i];j<=r[i];j++) aux[l[i] + 1][j + 1] -= sum[i];
	}
	for(int i=m-1;i>=0;i--){
		for(int j=i+1;j<=m;j++){
			cost[i][j] = cost[i+1][j] + aux[i+1][j];
		}
	}
	DP dp(cost, m+1);
	dp.old[0] = 0;
	for(int i=0;i<m;i++){
		dp.rec(0, m+1, 0, m+1);
		swap(dp.old, dp.cur);
		int ans = inf;
		for(int j=1;j<=m;j++) ans = min(ans, dp.old[j]);
		cout<<-ans<<"\n";
	}
	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66