Submission #1063707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063707		Matthewwww	Nafta (COI15_nafta)	C++17	11 / 100	1094 ms	2136 KiB

nafta

bool DEBUG
#ifdef LOCAL
= true;
#include <bits/stdc++.h>
#include <atcoder/all>
#include <local/debug>
#define nyoom 69
#define freopen(...) 69
#else
;
#include <bits/stdc++.h>
#define debug(x) x
#define dbg(x, y) x
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#define nyoom ios_base::sync_with_stdio(false); cin.tie(nullptr)
#endif
#ifdef ATCODER
#include <atcoder/all>
using namespace atcoder;
#endif
#define int long long
#define all(x) x.begin(), x.end()
#define err if (DEBUG) cout
#define f first
#define s second
using namespace std;

const int dir[5] = {1, 0, -1, 0, 1};

int n, m;

void dfs (int i, int j, vector<vector<int>> &grid, vector<pair<pair<int, int>, int>> &loose){
	if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '.'-'0')
		return;
	loose.back().s += grid[i][j];
	grid[i][j] = '.'-'0';
	loose.back().f.s = max(loose.back().f.s, j);
	loose.back().f.f = min(loose.back().f.f, j);
	for (int k = 0; k < 4; k++)
		dfs(i+dir[k], j+dir[k+1], grid, loose);
}

signed main(){
	nyoom;
	cin >> n >> m;
	vector<vector<int>> grid(n, vector<int>(m));
	vector<pair<pair<int, int>, int>> ranges;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			char a;
			cin >> a;
			grid[i][j] = a-'0';
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (grid[i][j] != '.'-'0'){
				ranges.push_back({{INT_MAX, INT_MIN}, 0});
				dfs(i, j, grid, ranges);
			}
		}
	}
	sort(ranges.begin(), ranges.end());
	int k = m;
	int dp[k][m];
	for (int i = 0; i < k; i++)
		for (int j = 0; j < m; j++)
			dp[i][j] = 0;
#define in(x, y) (x.f <= y && y <= x.s)
	for (int i = 0; i < m; i++)
		for (auto j : ranges)
			dp[0][i] += in(j.f, i)*j.s;
	for (int i = 1; i < k; i++){
		for (int j = 0; j < m; j++){
			for (int f = 0; f < j; f++){
				int cur = dp[i-1][f];
				for (auto idfk : ranges)
					cur -= (in(idfk.f, f) && in(idfk.f, j))*idfk.s;
				dp[i][j] = max(dp[i][j], cur);
			}
			for (auto f : ranges)
				dp[i][j] += in(f.f, j)*f.s;
		}
	}
	for (int i = 0; i < k; i++)
		cout << *max_element(dp[i], dp[i]+m) << "\n";
}



#undef int
#undef all
#undef err
#undef f
#undef s

/*
*
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃   ━   ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃   ┻   ┃ 
* ┗━┓   ┏━┛  + + 
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the llama protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*   ┃        ┏┛
*   ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

//thanks cindy

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