oj.uz

Submission #542977

# Submission time Handle Problem Language Result Execution time Memory
542977 2022-03-28T15:29:29 Z fcw Nafta (COI15_nafta) C++17
100 / 100
 457 ms 102120 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7 ms 1820 KB Output is correct
8 Correct 8 ms 1620 KB Output is correct
9 Correct 9 ms 2772 KB Output is correct
10 Correct 6 ms 1744 KB Output is correct
11 Correct 5 ms 1584 KB Output is correct
12 Correct 5 ms 1620 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7 ms 1820 KB Output is correct
8 Correct 8 ms 1620 KB Output is correct
9 Correct 9 ms 2772 KB Output is correct
10 Correct 6 ms 1744 KB Output is correct
11 Correct 5 ms 1584 KB Output is correct
12 Correct 5 ms 1620 KB Output is correct
13 Correct 313 ms 62440 KB Output is correct
14 Correct 359 ms 59636 KB Output is correct
15 Correct 457 ms 102120 KB Output is correct
16 Correct 300 ms 59416 KB Output is correct
17 Correct 295 ms 56568 KB Output is correct
18 Correct 281 ms 56412 KB Output is correct