oj.uz

Submission #976637

# Submission time Handle Problem Language Result Execution time Memory
976637 2024-05-06T23:41:02 Z leanchec Aliens (IOI16_aliens) C++17
0 / 100
 1 ms 348 KB 
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<vector<ll>> dp;
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)-sq(aux[i].second-aux[i+1].first+1)*(aux[i].second>=aux[i+1].first)){
			dp[qtd][mid]=dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-sq(aux[i].second-aux[i+1].first+1)*(aux[i].second>=aux[i+1].first);
			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();
	dp.resize(k+1);
	for(int i=i; i<=k; i++)
		dp.resize(n+1);

	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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:43: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]
   43 |   for(int j=1; j<=aux.size(); j++){
      |                ~^~~~~~~~~~~~
aliens.cpp:48: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]
   48 |  for(int i=1; i<aux.size(); i++){
      |               ~^~~~~~~~~~~
aliens.cpp:26:2: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  for(int i=i; i<=k; i++)
      |  ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -