Submission #428540

#	Time	Username	Problem	Language	Result	Execution time	Memory
428540		Kevin_Zhang_TW	Aliens (IOI16_aliens)	C++17	25 / 100	2039 ms	126664 KiB

aliens

#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 = 300010;
const ll inf = 1ll << 55;

#include "aliens.h"

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

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	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) {
			DE(x, y);
			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();
	}

	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)), osz(g, vector<ll>(k + 1, 0));

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

	vector<vector<ll>> segmn(g, vector<ll>(g, inf));

	vector<ll> omn(g, inf);

	for (int i = 0;i < n;++i) {
		int j = get_pos(c[i]); 
		chmin(omn[j], (ll)r[i]);
	}
		
	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));
	for (int i = 1;i < g;++i) {
		for (int j = 1;j <= k;++j) {
			for (int l = 0;l < i;++l) {
				ll mnc = segmn[l+1][i];
				ll wid = allc[i] - mnc + 1;
				ll rep = max<ll>(0, allc[l] - mnc + 1);
				//if (rep > osz[l][j-1]) continue;
				if (chmin(dp[i][j], dp[l][j-1] + sq(wid) - sq(rep)))
					osz[i][j] = wid;
			}
		}
	}

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

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
aliens.cpp:37:4: note: in expansion of macro 'DE'
   37 |    DE(x, y);
      |    ^~
aliens.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
aliens.cpp:80:2: note: in expansion of macro 'debug'
   80 |  debug(AI(allc));
      |  ^~~~~
aliens.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
aliens.cpp:94:2: note: in expansion of macro 'debug'
   94 |  debug(AI(dp[g-1]));
      |  ^~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40