Submission #1035413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035413		nishkarsh	Aliens (IOI16_aliens)	C++14	100 / 100	131 ms	11516 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vt vector
#define pb push_back

const int INF = 2e9;
const ll INFLL = 4e18;
const int N = 1e5+1;
const int mod = 998244353;

struct convex_hull_point{
	int m;
	int64_t c;

	convex_hull_point () {}

	convex_hull_point(const int &_m, const int64_t &_c) : m(_m), c(_c) {}

	convex_hull_point operator - (const convex_hull_point nw){
		return convex_hull_point(m-nw.m,c-nw.c);
	}
};

int64_t cross(convex_hull_point a, convex_hull_point b){
	return(a.m*b.c - a.c*b.m);
}

int64_t eval(convex_hull_point &a, int x){
	return (1ll*a.m*x + a.c);
}

struct convex_hull_with_ind : convex_hull_point{
	int ind;
	
	convex_hull_with_ind() : convex_hull_point() {}

	convex_hull_with_ind(int _m, ll _c, int _ind) : convex_hull_point(_m, _c), ind(_ind) {}

};

struct convex_hull{
	vector<convex_hull_with_ind> hull;
	int ind = 0;
	void add(convex_hull_with_ind x){
		int n = hull.size();
		while(n > 1 && cross(x-hull[n-1], hull[n-1] - hull[n-2]) < 0){
			--n;
			hull.pop_back();
		}
		hull.push_back(x);
		if(ind > n) ind = n;
	}

	convex_hull_with_ind query(int x){
		while(ind < hull.size() - 1 && eval(hull[ind],x) <= eval(hull[ind + 1],x)) ind++;
		return hull[ind];
	}
};


struct point{
	int x,y;

	point() {}
	
	point(const int &_x, const int &_y) : x(_x), y(_y) {}
	
	int64_t square_size(){
		int64_t ans = max(y+1-x,0);
		return ans*ans;
	}
};

point unite(const point &a, const point &b){
	int nwx = min(a.x,b.x);
	int nwy = max(a.y,b.y);
	return point(nwx,nwy);
}

point intersection(const point &a, const point &b){
	int nwx = max(a.x,b.x);
	int nwy = min(a.y,b.y);
	return point(nwx,nwy);
}

bool cmp(const point &a, const point &b){
	if(a.x == b.x) return a.y > b.y;
	else return a.x < b.x;
}

pair<int64_t,int> get_cost_and_partitions(vector<point> &p, int64_t cost){
	int n = p.size();
	int64_t dp[n+1];
	int cnt[n+1];
	dp[0] = cnt[0] = 0;

	convex_hull my_hull;
	for(int i = 1; i <= n; i++){
		int xi = p[i-1].x;
		int yi = p[i-1].y + 1;
		ll common_area;
		if(i == 1) common_area = 0;
		else common_area = intersection(p[i-1],p[i-2]).square_size();
		my_hull.add(convex_hull_with_ind(2*xi, common_area - 1ll*xi*xi - dp[i-1], i-1));

		convex_hull_with_ind temp = my_hull.query(yi);

		dp[i] = 1ll*yi*yi + cost - 1ll*temp.m*yi - temp.c;
		cnt[i] = cnt[temp.ind] + 1;
	}

	return make_pair(dp[n],cnt[n]);
}

int64_t take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	point temp[n];
	for(int i = 0; i < n; i++){
		if(r[i] <= c[i]) temp[i] = point(r[i],c[i]);
		else temp[i] = point(c[i],r[i]);
	}
	sort(temp,temp+n,cmp);

	vector<point> p;

	int threshold = -1;
	for(int i = 0; i < n; i++){
		if(temp[i].y > threshold){
			// cout << temp[i].x << " " << temp[i].y << "\n";
			p.pb(temp[i]);
			threshold = temp[i].y;
		}
	}
	n = p.size();

	int64_t lt = 0, rt = 1ll*m*m + 1;
	while(rt-lt > 1){
		int64_t mid = (lt+rt)/2;
		auto it = get_cost_and_partitions(p, mid);
		if(it.second >= k) lt = mid;
		else rt = mid;

		// cout << mid << " " << it.first << " " << it.second << "\n";
	}
	auto it = get_cost_and_partitions(p,lt);
	return it.first - 1ll*k*lt;
}

void solve(){
	int n,m,k;
	cin >> n >> m >> k;
	vector<int> r(n),c(n);
	for(int i = 0; i < n; i++) cin >> r[i];
	for(int i = 0; i < n; i++) cin >> c[i];
	cout << take_photos(n,m,k,r,c) << "\n";
}

// int main() {

// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
// 	cout.tie(0);

// 	int t = 1;
// 	// cin >> t;

// 	while(t--) solve();
// }

Compilation message (stderr)

aliens.cpp: In member function 'convex_hull_with_ind convex_hull::query(int)':
aliens.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<convex_hull_with_ind>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   while(ind < hull.size() - 1 && eval(hull[ind],x) <= eval(hull[ind + 1],x)) ind++;
      |         ~~~~^~~~~~~~~~~~~~~~~

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