oj.uz

Submission #101153

# Submission time Handle Problem Language Result Execution time Memory
101153 2019-03-17T06:45:57 Z TuGSGeReL Aliens (IOI16_aliens) C++14
0 / 100
 52 ms 768 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Incorrect 2 ms 384 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 1
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 256 KB Correct answer: answer = 1
4 Correct 2 ms 256 KB Correct answer: answer = 5
5 Correct 2 ms 384 KB Correct answer: answer = 41
6 Correct 4 ms 384 KB Correct answer: answer = 71923
7 Correct 3 ms 512 KB Correct answer: answer = 77137
8 Incorrect 52 ms 768 KB Wrong answer: output = 753, expected = 764
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Incorrect 2 ms 384 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Incorrect 2 ms 384 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Incorrect 2 ms 384 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct answer: answer = 4
2 Correct 2 ms 384 KB Correct answer: answer = 4
3 Correct 2 ms 384 KB Correct answer: answer = 4
4 Incorrect 2 ms 384 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -