Submission #93595

#	Time	Username	Problem	Language	Result	Execution time	Memory
93595		jasony123123	Nafta (COI15_nafta)	C++11	34 / 100	1067 ms	35208 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 Bit {
	T bit[L + 1];
	Bit() {}
	void clr() { memset(bit, 0, sizeof bit); }
	void upd(int k, T val) { for (k++; k <= L; k += (k&-k)) bit[k] += val; }
	T query(int k) { T temp = 0; for (k++; k > 0; k -= (k&-k)) temp += bit[k]; return temp; }
	T query(int l, int r) { return query(r) - query(l - 1); }
};
Bit<int, MX> cnt;
void add(int x, int y, int val) {
	cnt.upd(x, val);
	cnt.upd(y + 1, -val);
	//FORE(i, x, y)
	//	cnt[i] += val;
}
int query(int x) {
	return cnt.query(x);
	//return cnt[x];
}
void clear() {
	cnt.clr();
	//memset(cnt, 0, sizeof 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<ll, int> best = { LLONG_MAX, -1 };
	//if (mid == 0)
	//	best = { 0,0 };

	//// [0, mid-1]
	//// [optl, optr]
	//for (int j = max(0, optl); j <= min(mid - 1, optr); j++) {
	//	best = min(best, { dp_before[j] + cost(j + 1,mid), 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]) add(alls[j].LL, alls[j].RR, alls[j].PP);
		dp_cur[i] = query(i);
		FORE(j, 0, i) W[i][j] = dp_cur[i] - query(j);
		for (auto j : delE[i]) 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: 0 / 66