Submission #51854

#	Time	Username	Problem	Language	Result	Execution time	Memory
51854		zetapi	Aliens (IOI16_aliens)	C++14	0 / 100	2 ms	472 KiB

aliens

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

#define pb  push_back
#define mp  make_pair
//#define int long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;
const int INF=1e12;

vector<pii> vec;

bool cmp(pii X,pii Y)
{
	return X.second<Y.second;
}

int cost(int X,int Y)
{
	return (vec[Y-1].second-vec[X-1].first)*(vec[Y-1].second-vec[X-1].first);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) 
{
	int N=n,M=m,K=k,dp[n+99][k+99];
	for(int A=0;A<n;A++)
		vec.pb(mp(r[A],r[A]+abs(r[A]-c[A])));
	sort(vec.begin(),vec.end(),cmp);
	for(int A=0;A<=N;A++)
		for(int B=0;B<=K;B++)
			dp[A][B]=INF;
	dp[0][0]=0;
	for(int A=1;A<=N;A++)
	{
		dp[A][0]=0;
		for(int B=0;B<A;B++)
			for(int C=1;C<=K;C++)
				dp[A][C]=min(dp[A][C],dp[B][C-1]+cost(B+1,A));
	}
    return dp[N][K];
}

Compilation message (stderr)

aliens.cpp:13:15: warning: overflow in implicit constant conversion [-Woverflow]
 const int INF=1e12;
               ^~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:29:10: warning: unused variable 'M' [-Wunused-variable]
  int N=n,M=m,K=k,dp[n+99][k+99];
          ^

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