Submission #1208999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208999		ansori	Aliens (IOI16_aliens)	C++20	60 / 100	1896 ms	1114112 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll inf = 1e16;
using namespace std;

long long take_photos(int n, int m, int k, std::vector<int> rec , std::vector<int> col) {
	vector<pair<int , int>> p(n);
	for(int i = 0;i < n; ++ i){
		if(rec[i] > col[i]) swap(rec[i] , col[i]);
		p[i] = {rec[i] , col[i]};
	}
	sort(p.begin() , p.end());
	vector<pair<int , int>> q;
	for(int i = 0;i < n; ++ i){
		if(q.size() and q.back().fi == p[i].fi) q.pop_back();
		if((q.size() == 0) or (q.back().se < p[i].se)) q.push_back({p[i].fi , p[i].se});
	}
	n = q.size();
	vector<ll> l(n) , r(n);
	for(int i = 0;i < n; ++ i){
		l[i] = q[i].fi;
		r[i] = q[i].se;
		//cout << l[i] << ' ' << r[i] << '\n';
	}
	vector<vector<ll>> f(k + 1 , vector<ll> (n + 1 , inf));
	f[0][0] = 0;
	for(int i = 1;i <= k; ++ i){
		vector<pair<pair<ll , ll> , int>> con;
		vector<ll> co(n + 1) , k(n + 1);
		for(int j = 1;j <= n; ++ j){
			co[j] = f[i - 1][j - 1] + ((l[j - 1] - 1) * (l[j - 1] - 1));
			if(j > 1) co[j] -= max(0ll , r[j - 2] - l[j - 1] + 1) * max(0ll , r[j - 2] - l[j - 1] + 1);
			k[j] = -2 * (l[j - 1] - 1);
		}
		f[i][0] = f[i - 1][0];
		//cout << -1 << ' ';
		for(int j = 1;j <= n; ++ j){
			while(con.size()){
				ll p = con.back().se;
				ll xc = (co[j] - co[p] + (k[p] - k[j] - 1)) / (k[p] - k[j]);
				if(xc <= con.back().fi.fi) con.pop_back();
				else{
					int nc = con.back().fi.fi;
					con.pop_back();
					con.push_back({{nc , xc - 1} , p});
					con.push_back({{xc , inf} , j});
					break;
				}
			}
			if(con.size() == 0) con.push_back({{-inf , inf} , j});
			int l1 = 0;
			int r1 = con.size();
			while(l1 + 1 < r1){
				int mid = (l1 + r1) / 2;
				if(con[mid].fi.fi <= r[j - 1]) l1 = mid;
				else r1 = mid;
			}
			f[i][j] = co[con[l1].se] + r[j - 1] * r[j - 1] + k[con[l1].se] * r[j - 1];
			// cout << f[i][j] << ' ';
		}
		// cout << '\n';
	}
    return f[k][n];
    //return 0;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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