Submission #93597

#	Time	Username	Problem	Language	Result	Execution time	Memory
93597		jasony123123	Nafta (COI15_nafta)	C++11	100 / 100	357 ms	31220 KiB

nafta

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/************************COI TST2 2015 P2****************************************/
typedef pair<pii, int> seg;
const int MX = 2000;
#define LL first.first 
#define	RR first.second
#define PP second

int R, C;
char oil[MX][MX];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
seg findseg(int i, int j) {
	int total = oil[i][j] - '0', l = j, r = j;
	queue<pii> q;
	q.push({ i,j });
	oil[i][j] = '.';
	while (!q.empty()) {
		i = q.front().first, j = q.front().second;
		q.pop();
		FOR(d, 0, 4) {
			int ni = i + dx[d], nj = j + dy[d];
			if (0 <= ni && ni<R && 0 <= nj && nj<C && oil[ni][nj] != '.') {
				total += oil[ni][nj] - '0';
				minn(l, nj), maxx(r, nj);
				q.push({ ni,nj });
				oil[ni][nj] = '.';
			}
		}
	}
	return{ { l,r }, total };
}

template<class T, int L> struct IBit{
	T bit[L + 1];
	IBit() {}
	void upd(int k, T val) { for (k++; k <= L; k += (k&-k)) bit[k] += val; }
	T qu(int k) { T temp = 0; for (k++; k > 0; k -= (k&-k)) temp += bit[k]; return temp; }
	
	void clear() { memset(bit, 0, sizeof bit); } // reset to 0
	void add(int x, int y, T val) { upd(x, val), upd(y + 1, -val); }// add val to arr[x...y]
	T query(int x) { return qu(x); } // get arr[x]
};
IBit<int, MX> cnt;

int getMax(v<int> &dp) {
	int ret = dp[0];
	for (auto x : dp) maxx(ret, x);
	return ret;
}
v<int> dp_before, dp_cur;
int W[MX][MX]; // W[i][j]: --j---i- new points

void compute(int l, int r, int optl, int optr) {
	///* Brute Force: N^2 */
	//FOR(i, 0, optr) {
	//	// calculate dp_cur[i];
	//	dp_cur[i] = 0;
	//	FORE(j, 0, i) maxx(dp_cur[i], dp_before[j] + W[i][j]);
	//}

	/* NlogN Optimized*/
	if (l > r) return;

	// compute dp[mid]
	int mid = (l + r) >> 1;
	pair<int, int> best = { 0,-1 };

	// [0, mid-1]
	// [optl, optr]
	for (int j = max(0, optl); j <= min(mid, optr); j++)
		maxx(best, { dp_before[j] + W[mid][j],j });
	
	dp_cur[mid] = best.first;
	int opt = best.second;

	compute(l, mid - 1, optl, opt);
	compute(mid + 1, r, opt, optr);
}

void process(v<seg> &alls, int N) { // [0,N-1]
	dp_before.resize(N), dp_cur.resize(N);
	// setup W[i][j];
	v<int> addE[MX], delE[MX];
	FOR(i, 0, alls.size())
		addE[alls[i].LL].push_back(i), delE[alls[i].RR].push_back(i);
	FOR(i, 0, N) {
		for (auto j : addE[i]) cnt.add(alls[j].LL, alls[j].RR, alls[j].PP);
		dp_cur[i] = cnt.query(i);
		FORE(j, 0, i) W[i][j] = dp_cur[i] - cnt.query(j);
		for (auto j : delE[i]) cnt.add(alls[j].LL, alls[j].RR, -alls[j].PP);
	}

	cout << getMax(dp_cur) << "\n";

	FORE(k, 2, N) {
		swap(dp_cur, dp_before);
		compute(0, N - 1, 0, N);
		cout << getMax(dp_cur) << "\n";
	}
}

int main() {
	io();
	cin >> R >> C;
	FOR(i, 0, R) FOR(j, 0, C) cin >> oil[i][j];

	v<seg> alls;
	FOR(i, 0, R) FOR(j, 0, C) if (oil[i][j] != '.') alls.push_back(findseg(i, j));

	//for (auto s : alls) {
	//	cout << s.LL << " " << s.RR << " " << s.PP << "\n";
	//}

	process(alls, C);
	return 0;
}

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