Submission #69224

#	Time	Username	Problem	Language	Result	Execution time	Memory
69224		Navick	Aliens (IOI16_aliens)	C++17	60 / 100	514 ms	22244 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

const int maxN = 5e4 + 10, maxK = 510;
const ll oo = 2e15;

ll las[maxN], dp[maxN], f[maxN];
int l[maxN], r[maxN];

vector <pii> que;
pll lines[maxN];
int sz = 0;

bool cmp(pii a1, pii a2)
{
	if(a1.F != a2.F) return a1.F < a2.F;
	return a1.S > a2.S;
}

ll barkhord(pll A, pll B)
{
	return (B.F - A.F + A.S - B.S - 1) / (A.S - B.S);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    
	if(n > maxN) return cout << 1/0 << endl, -1;

	for (int i=0; i<n; i++)
	{
		if(r[i] <= c[i])
			c[i] ++;
		else r[i] ++;
		que.pb({min(r[i], c[i]), max(r[i], c[i])});
	}

	sort(que.begin(), que.end(), cmp);

	int mx = -1, cnt = 0;

	for (int i=0; i<n; i++)
	{
		if(mx >= que[i].S) continue ;
		else 
		{
			l[cnt] = que[i].F, r[cnt] = que[i].S;
			mx = max(mx, que[i].S);
			cnt ++;
		}
	}

	n = cnt;

	
	//for (int i=0; i<n; i++) cout << l[i] << ',' << r[i] << endl;

	for (int i=0; i<=n; i++) las[i] = oo;
	las[0] = 0;

	for (int i=0; i<n-1; i++)
		if(r[i] > l[i + 1]) f[i] = 1LL * (r[i] - l[i + 1]) * (r[i] - l[i + 1]);
	
	for (int j=1; j<=k; j++)
	{
		dp[0] = 0;

		sz = 0;
		int ptr = 0;
		//cout << j << " --> " << endl;

		for (int i=1; i<=n; i++)
		{

			ll c = 0;
			if(i - 1 > 0) c = f[i - 2];
			
			if(las[i - 1] < oo)
			{

				pll t = {las[i - 1] - c + (ll)l[i - 1] * l[i - 1], -2LL * l[i - 1]};
				while(sz >= 2 && barkhord(lines[sz - 2], lines[sz - 1]) >= barkhord(lines[sz - 1], t)) sz--;
				lines[sz ++] = t;
			}

			/*if(j == 2)
			{
				cout << sz << " lines " << endl;
				for (int c=0; c<sz; c++) cout << lines[c].F << ',' << lines[c].S << endl;
			}*/

			ptr = min(ptr, sz - 1);

			while(ptr < sz - 1 && barkhord(lines[ptr], lines[ptr + 1]) <= r[i - 1]) ptr ++;
			
	//		cout << ptr << endl;

			dp[i] = lines[ptr].F + (ll)r[i - 1] * r[i - 1] + (ll)r[i - 1] * lines[ptr].S;
			//cout << i << " : " << dp[i]; cout << endl << endl;
		}

		for (int i=1; i<=n; i++)
			las[i] = dp[i];

	}

	return dp[n];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:37:31: warning: division by zero [-Wdiv-by-zero]
  if(n > maxN) return cout << 1/0 << endl, -1;
                              ~^~

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