oj.uz

답안 #93597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93597 2019-01-10T00:45:26 Z jasony123123 Nafta (COI15_nafta) C++11
100 / 100
 357 ms 31220 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 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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 2 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 8 ms 2552 KB Output is correct
9 Correct 7 ms 2424 KB Output is correct
10 Correct 8 ms 2680 KB Output is correct
11 Correct 7 ms 2524 KB Output is correct
12 Correct 6 ms 2424 KB Output is correct

Subtask #3
66.0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 8 ms 2552 KB Output is correct
9 Correct 7 ms 2424 KB Output is correct
10 Correct 8 ms 2680 KB Output is correct
11 Correct 7 ms 2524 KB Output is correct
12 Correct 6 ms 2424 KB Output is correct
13 Correct 357 ms 31220 KB Output is correct
14 Correct 307 ms 25304 KB Output is correct
15 Correct 289 ms 19188 KB Output is correct
16 Correct 285 ms 24480 KB Output is correct
17 Correct 186 ms 18768 KB Output is correct
18 Correct 193 ms 18520 KB Output is correct