Submission #101153

#	Time	Username	Problem	Language	Result	Execution time	Memory
101153		TuGSGeReL	Aliens (IOI16_aliens)	C++14	0 / 100	52 ms	768 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

pair <ll, ll> dot[50001];
ll dp[50001][101], ans;

inline ll maaax(int lo, int ro)
{
	ll mx = 0, mn = 1e9;
	
	for (int o = lo; o <= ro; o++)
	{
		mx = max(mx, dot[o].ss);
		mn = min(mn, dot[o].ss);
		mx = max(mx, dot[o].ff);
		mn = min(mn, dot[o].ff);
	}
	
	return (mx - mn + 1) * (mx - mn + 1);
}

inline void hoho (int k, int l, int r, int optl, int optr)
{
	if ( l > r )
		return;
		
	int mid = (l + r) / 2, opt;
	dp[mid][k] = 1e18;
	
	for(int j = optl; j <= optr; j++)
	{
		ll now = dp[j - 1][k - 1] + maaax(j, mid);
		
		if ( now < dp[mid][k] )
		{
			dp[mid][k] = now;
			opt = j;
		}
	}
	
	hoho(k, l, mid - 1, optl, opt);
	hoho(k, mid + 1, r, opt, optr);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

	for (int i = 1; i <= n; i++)
	{
		dot[i].ff = r[i - 1];
		dot[i].ss = c[i - 1];
	}
	
	sort(dot + 1, dot + n + 1);
	
	ll mx = 0, mn = 1e9;
	
	for (int i = 1; i <= n; i++)
	{
		mx = max(mx, dot[i].ss);
		mn = min(mn, dot[i].ss);
		mx = max(mx, dot[i].ff);
		mn = min(mn, dot[i].ff);
		dp[i][1] = (mx - mn + 1) * (mx - mn + 1);
	}
	
	for (int i = 2; i <= k; i++)
		hoho(i, 1, n, 1, n);

	ll ans = 1e18;
	
	for (int i = 1; i <= k; i++)
	{
		ans = min(ans, dp[n][i]);
	}
	
	return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'void hoho(int, int, int, int, int)':
aliens.cpp:58:6: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  hoho(k, l, mid - 1, optl, opt);
  ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int mid = (l + r) / 2, opt;
                         ^~~
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:44:25: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:58:6: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  hoho(k, l, mid - 1, optl, opt);
  ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:44:25: note: 'opt' was declared here
  int mid = (l + r) / 2, opt;
                         ^~~

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