제출 #1278109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278109		g4yuhg	Nafta (COI15_nafta)	C++20	34 / 100	1086 ms	109688 KiB

nafta

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 2005
#define LOG 18
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

const ll hx[] = {1, -1, 0, 0};
const ll hy[] = {0, 0, 1, -1};

ll n, m;
ll b[N * N], par[N * N], cur, cur2, ax[N][N], L[N * N], R[N * N], sum[N * N];
ll cost[N][N];
pii p[N * N];

ll find(ll u) {
	if (par[u] < 0) return u;
	return par[u] = find(par[u]);
}

void join(ll u, ll v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (par[u] <= par[v]) {
		par[u] += par[v];
		par[v] = u;
	}
	else {
		par[v] += par[u];
		par[u] = v;
	}
}

char a[N][N];

struct piii {
	ll l, r, val;
};

bool cmp (piii a, piii b) {
	return a.l < b.l;
}

ll st[4 * N];

void update(ll id, ll l, ll r, ll i, ll v) {
	if (i > r || i < l) return;
	if (l == r) {
		st[id] += v;
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, i, v);
	update(id * 2 + 1, mid + 1, r, i, v);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

ll get(ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) return 0;
	if (L <= l && r <= R) return st[id];
	ll mid = (l + r) / 2;
	return get(id * 2, l, mid, L, R) + get(id * 2 + 1, mid + 1, r, L, R);
}

ll dp[2005][2005];

void sub1() {
	ll ans = 0;
	for (int id = 1; id <= m; id ++) {
		for (int i = 1; i <= m; i ++) {
			ll jtoi = 0;
			for (int j = 0; j < i; j ++) {
				dp[id][i] = max(dp[id][i], dp[id - 1][j] + cost[j][i]);
				ans = max(ans, dp[id][i]);
				if (dp[id][i] == dp[id - 1][j] + cost[j][i]) {
					jtoi = j;
				}
			}
			//cout << i << " jtoi " << jtoi << endl;
		}
		cout << ans << endl;
	}
}

ll res = 0;

void dnc(ll id, ll l, ll r, ll L, ll R) {
	if (l > r) return;
	if (L > R) return;
	ll mid = (l + r) / 2;
	ll bd = max(0, L);
	ll en = min(R, mid - 1);
	ll i = mid, jtoi = 0;;
	for (int j = bd; j <= en; j ++) {
		dp[id][i] = max(dp[id][i], dp[id - 1][j] + cost[j][i]);
		//cout << dp[id - 1][j] + cost[j][i] << " j " << j << endl;
		if (dp[id][i] == dp[id - 1][j] + cost[j][i]) {
			jtoi = j;
		}
		res = max(res, dp[id][i]);
	}
	//cout << "id " << i << " " << jtoi << " " << dp[id][mid] << " " << cost[0][mid] << endl;
	dnc(id, l, mid - 1, L, jtoi);
	dnc(id, mid + 1, r, jtoi, R);
}

void sub2() {
	for (int id = 1; id <= m; id ++) {
		dnc(id, 1, m, 0, m - 1);
		cout << res << endl;
	}
}

void pre() {
	map<ll, ll> mp;
	for (int i = 1; i <= cur; i ++) {
		ll r = find(i);
		if (mp[r] == 0) {
			mp[r] = ++ cur2;
			sum[mp[r]] = 0;
			L[mp[r]] = inf;
			R[mp[r]] = -inf;
		}
		sum[mp[r]] += b[i];
		L[mp[r]] = min(L[mp[r]], p[i].se);
		R[mp[r]] = max(R[mp[r]], p[i].se);
	}
	vector<piii> vt;
	for (int i = 1; i <= cur2; i ++) {
		vt.push_back({L[i], R[i], sum[i]});
	}
	sort(vt.begin(), vt.end(), cmp);
	/*for (auto it : vt) {
		cout << it.l << " " << it.r << " " << it.val << endl;
	}*/
	ll pt = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 1; i <= m; i ++) {
		//cout << "den " << i << endl;
		while (pt < vt.size() && vt[pt].l <= i) {
			update(1, 1, m, vt[pt].l, vt[pt].val);
			//cout << "add " << vt[pt].l << " " << vt[pt].r << " " << vt[pt].val << endl;
			pq.push({vt[pt].r, pt});
			pt ++ ;
		}
		while (pq.size() && pq.top().fi < i) {
			ll id = pq.top().se;
			update(1, 1, m, vt[id].l, -vt[id].val);
			pq.pop();
		}
		for (int j = i - 1; j >= 0; j --) {
			cost[j][i] = get(1, 1, m, j + 1, i);
			//cout << j << " " << i << " " << cost[j][i] << endl;
		}
	}
	
}

bool klinh;

signed main() {
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(par, -1, sizeof(par));
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> a[i][j];
			if ('0' <= a[i][j] && a[i][j] <= '9') {
				b[++ cur] = a[i][j] - '0';
				p[cur] = {i, j};
				ax[i][j] = cur;
			}
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if ('0' <= a[i][j] && a[i][j] <= '9') {
				for (int z = 0; z < 4; z ++) {
					ll dx = i + hx[z];
					ll dy = j + hy[z];
					if (dx < 1 || dy < 1 || dx > n || dy > m || !('0' <= a[dx][dy] && a[dx][dy] <= '9')) {
						continue;
					}
					join(ax[i][j], ax[dx][dy]);
				}
			}
		}
	}
	
	pre();
	sub2();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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