Submission #976630

#	Time	Username	Problem	Language	Result	Execution time	Memory
976630		leanchec	Aliens (IOI16_aliens)	C++17	0 / 100	5 ms	21236 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[110][50100];
vector<pair<int,int>> aux;

ll sq(ll a){return a*a;}

void solve(int qtd,int l, int r, int p, int q){
	int mid=(l+r)>>1, opt=-1;
	for(int i=p; i<=min(q, mid-1); i++){
		if(dp[qtd][mid]>dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-max((ll)0, sq(aux[i].second-aux[i+1].first+1))){
			dp[qtd][mid]=dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-max((ll)0, sq(aux[i].second-aux[i+1].first+1));
			opt=i;
		}
	}
	if(l<mid)solve(qtd, l, mid-1, p, opt);
	if(mid<r)solve(qtd, mid+1, r, opt, q);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	aux.clear();
	for(int i=0; i<n; i++){
		aux.push_back({min(r[i], c[i]), -max(r[i], c[i])});
	}

	sort(aux.begin(), aux.end());

	vector<pair<int,int>> temp;
	temp.push_back({-1, -1});
	for(auto cur:aux){
		if(-cur.second>temp.back().second)temp.push_back({cur.first, -cur.second});
	}
	aux=temp;

	for(int i=1; i<=k; i++){
		for(int j=1; j<=aux.size(); j++){
			dp[i][j]=1e18;
		}
	}

	for(int i=1; i<aux.size(); i++)
		dp[1][i]=sq(aux[i].second-aux[1].first+1);

	for(int i=2; i<=min((int)aux.size()-1, k); i++)
		solve(i, 1, aux.size()-1, 1, aux.size()-1);

    return dp[min((int)aux.size()-1, k)][aux.size()-1];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j=1; j<=aux.size(); j++){
      |                ~^~~~~~~~~~~~
aliens.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=1; i<aux.size(); i++)
      |               ~^~~~~~~~~~~

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