oj.uz

Submission #428669

# Submission time Handle Problem Language Result Execution time Memory
428669 2021-06-15T13:42:53 Z Kevin_Zhang_TW Aliens (IOI16_aliens) C++17
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 100010, MAX_K = 17;
const ll inf = 1ll << 55;

#include "aliens.h"

ll sq(ll v) { return v * v; }

void monolize(vector<int> &r, vector<int> &c, int &n) {
	for (int i = 0;i < n;++i) {
		if (r[i] > c[i]) swap(r[i], c[i]);
	}
	vector<pair<int,int>> loc;
	for (int i = 0;i < n;++i) loc.pb(c[i], r[i]);
	sort(AI(loc));
	int sz = 0;
	for (auto [x, y] : loc) {
		while (sz) {
			auto [xx, yy] = loc[sz-1];
			if (yy < y) break;
			--sz;
		}
		loc[sz++] = {x, y};
	}
	loc.resize(sz);

	r.clear(), c.clear();
	for (auto [x, y] : loc)
		r.pb(y), c.pb(x);
	n = r.size();
}

ll sp[MAX_K][MAX_N];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

	monolize(r, c, n);

	vector<int> allc(c); allc.pb(-1); sort(AI(allc)), allc.erase(unique(AI(allc)), end(allc));

	auto get_pos = [&](int c) -> int { 
		return lower_bound(AI(allc), c) - begin(allc);
	};

	int g = allc.size();

	vector<vector<ll>> dp(g, vector<ll>(k + 1, inf));

	fill(AI(dp[0]), 0);

	fill(sp[0], sp[0] + g, inf);

//	vector<vector<ll>> segmn(g, vector<ll>(g, inf));
//
//	vector<ll> omn(g, inf);
//
	for (int i = 0;i < g;++i) {
		int j = get_pos(c[i]); 
		chmin(sp[0][j], (ll)r[i]);
		//chmin(omn[j], (ll)r[i]);
	}
	for (int d = 1;d < MAX_K;++d)
		for (int i = 0;i < g;++i) 
			sp[d][i] = min(sp[d-1][i], sp[d-1][ min(n-1, i + (1<<(d-1))) ]);

	auto qry = [&](int l, int r) {
		int lg = __lg(r-l);
//		ll ret = inf;
//		for (int i = l;i < r;++i) chmin(ret, sp[0][i]);
//		return ret;
		return min(sp[lg][l], sp[lg][r - (1<<lg)]);
	};
//	for (int i = 0;i < g;++i) {
//		segmn[i][i] = omn[i];
//		for (int j = i+1;j < g;++j) 
//			segmn[i][j] = min(omn[j], segmn[i][j-1]);
//	}

	debug(AI(allc));

	auto cost = [&](int l, int i) {
		//ll mnc = segmn[l+1][i];
		//           [ , )
		ll mnc = qry(l+1, i+1);
		ll wid = allc[i] - mnc + 1;
		ll rep = max<ll>(0, allc[l] - mnc + 1);
		return sq(wid) - sq(rep);
	};
		
	for (int i = 1;i < g;++i)
		dp[i][1] = cost(0, i);

	for (int j = 2;j <= k;++j) {
		function<void(int,int,int,int)> dcop = [&](int l, int r, int sl, int sr) {
			if (l > r) return;
			int mid = l + r >> 1;
			int p = -1;
			for (int i = sl;i <= sr && i < mid;++i)
				if (chmin(dp[mid][j], dp[i][j-1] + cost(i, mid)))
					p = i;
			dcop(l, mid-1, sl, p);
			dcop(mid+1, r, p, sr);
		};
		dcop(1, g-1, 0, g-1);
	}
//	for (int i = 1;i < g;++i) {
//		for (int j = 1;j <= k;++j) {
//			auto trans = [&](int l, int i) {
//				return dp[l][j-1] + cost(l, i);
//			};
////			for (int l = 0;l < i;++l) {
////				chmin(dp[i][j], dp[l][j-1] + cost(l, i));
////			}
//		}
//	}

	debug(AI(dp[g-1]));
	return dp[g-1][k];
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
aliens.cpp:95:2: note: in expansion of macro 'debug'
   95 |  debug(AI(allc));
      |  ^~~~~
aliens.cpp: In lambda function:
aliens.cpp:112:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |    int mid = l + r >> 1;
      |              ~~^~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
aliens.cpp:133:2: note: in expansion of macro 'debug'
  133 |  debug(AI(dp[g-1]));
      |  ^~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 0 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Incorrect 1 ms 300 KB Wrong answer: output = -720575940379279179, expected = 88
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 1
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 1 ms 332 KB Correct answer: answer = 1
4 Correct 1 ms 332 KB Correct answer: answer = 5
5 Correct 1 ms 332 KB Correct answer: answer = 41
6 Incorrect 1 ms 332 KB Wrong answer: output = 75580, expected = 71923
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 0 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Incorrect 1 ms 300 KB Wrong answer: output = -720575940379279179, expected = 88
8 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 0 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Incorrect 1 ms 300 KB Wrong answer: output = -720575940379279179, expected = 88
8 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 0 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Incorrect 1 ms 300 KB Wrong answer: output = -720575940379279179, expected = 88
8 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 0 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Incorrect 1 ms 300 KB Wrong answer: output = -720575940379279179, expected = 88
8 Halted 0 ms 0 KB -