Submission #540901

#	Time	Username	Problem	Language	Result	Execution time	Memory
540901		keta_tsimakuridze	Aliens (IOI16_aliens)	C++14	25 / 100	2078 ms	78160 KiB

aliens

#include "aliens.h"
 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
using namespace std;
const ll N = 1e6 + 5;
int n, m, cntL[N], cntR[N], R[N];
pii dp[N];
vector<int> st[N], g[N];
ll check(ll c) {
	vector<int> v;
	for(ll x = 1; x <= n; x++) {
		dp[x] = {n * n + 5, 0};
		if(cntL[x - 1] + cntR[x + 1] == m) dp[x] = dp[x - 1];
		for(int i = 0; i < g[x].size(); i++) {
			v.push_back(g[x][i]);
		}
		for(ll i = 0; i < v.size(); i++) {
			int l = v[i];
			ll r = R[l - 1];
			if(r >= x) continue;
			ll y = dp[r].f + (ll)(x - l + 1) * (x - l + 1) - (ll)(r - l + 1) * (r - l + 1) + c;
			dp[x] = min(dp[x], {y, dp[r].s - 1});
		}
	}
	
	return -dp[n].s;
}
long long take_photos(int N, int M, int k, std::vector<int> r1, std::vector<int> c) {
	swap(N, M); 
	m = M; n = N;
//	vector<ll> l(m + 5);
	int mnl = n, mxr = 0;
    for(int i = 0; i < m; i++) {
    	if(c[i] > r1[i]) swap(c[i], r1[i]);
    	int l = min(r1[i], c[i]); r1[i] = max(r1[i], c[i]);
    	l++; r1[i]++;
    	cntL[r1[i]]++; cntR[l]++;
    	st[l].push_back(r1[i]);
    	mnl = min(l, mnl); mxr = max(mxr, r1[i]);
	}
	if(k == 1) {
		return (ll)(mxr - mnl + 1) * (mxr - mnl + 1);
	}
	for(int i = 1; i <= n; i++) cntL[i] += cntL[i - 1];
	for(int i = n; i >= 1; i--) cntR[i] += cntR[i + 1];
	int C = 0;
	for(int i = 1; i <= n; i++) {
		C = max(C, i);
		for(ll j = 0; j < st[i].size(); j++) {
			C = max(C, st[i][j]);
		}
		R[i] = C;
		g[R[i - 1] + 1].push_back(i);
	}
	ll l = 0, r = 2e9, p = 0;
	while(l <= r) {
		ll mid = (l + r) / 2;
		if(check(mid) >= k) {
			p = mid;
			l = mid + 1;
			
		} else r = mid - 1;
	}
	check(p); 
	return dp[n].f - (ll)p * k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int check(long long int)':
aliens.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i < g[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
aliens.cpp:21:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(ll i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:53:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(ll j = 0; j < st[i].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~

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