oj.uz

답안 #93596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93596 2019-01-10T00:37:22 Z jasony123123 Nafta (COI15_nafta) C++11
100 / 100
 371 ms 31240 KB 
#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<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]) 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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 9 ms 2744 KB Output is correct
8 Correct 9 ms 2680 KB Output is correct
9 Correct 17 ms 2424 KB Output is correct
10 Correct 8 ms 2680 KB Output is correct
11 Correct 6 ms 2552 KB Output is correct
12 Correct 6 ms 2424 KB Output is correct

Subtask #3
66.0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 9 ms 2744 KB Output is correct
8 Correct 9 ms 2680 KB Output is correct
9 Correct 17 ms 2424 KB Output is correct
10 Correct 8 ms 2680 KB Output is correct
11 Correct 6 ms 2552 KB Output is correct
12 Correct 6 ms 2424 KB Output is correct
13 Correct 371 ms 31240 KB Output is correct
14 Correct 323 ms 29220 KB Output is correct
15 Correct 285 ms 22964 KB Output is correct
16 Correct 277 ms 28388 KB Output is correct
17 Correct 200 ms 22504 KB Output is correct
18 Correct 187 ms 22328 KB Output is correct