Submission #51871

#	Time	Username	Problem	Language	Result	Execution time	Memory
51871		zetapi	Aliens (IOI16_aliens)	C++14	12 / 100	192 ms	3124 KiB

aliens

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

#define pb  push_back
#define mp  make_pair
#define ll 	long long
#define itr ::iterator

typedef pair<int,int>  pii;

const ll INF=1e12;

vector<int> vec,lol;

ll cost(int X,int Y)
{
//	cout<<X<<" "<<Y<<" "<<vec[X-1]<<" "<<vec[Y-1]<<" "<<(-vec[X-1]+vec[Y-1]+1)*(-vec[X-1]+vec[Y-1]+1)<<"\n";
	return (-vec[X-1]+vec[Y-1]+1)*(-vec[X-1]+vec[Y-1]+1);
}

ll take_photos(int n=4, int m=6, int k=2, std::vector<int> r={1,1,4,5}, std::vector<int> c={0,0,0,0}) 
{
	ll N=n,M=m,K=k,dp[n+99][k+99];
	for(int A=0;A<N;A++)
		lol.pb(r[A]);
	sort(lol.begin(),lol.end());
	vec.pb(lol[0]);
	for(int A=1;A<lol.size();A++)
	{
		if(lol[A]==vec.back())
			continue;
		vec.pb(lol[A]);
	}
	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<=vec.size();A++)
	{
		for(int B=1;B<=K;B++)
		{
			for(int C=0;C<A;C++)
				dp[A][B]=min(dp[A][B],dp[C][B-1]+cost(C+1,A));
		}
	}
	ll res=INF;
	for(int B=1;B<=K;B++)
		res=min(res,dp[vec.size()][B]);
    return res;
}

/*int main()
{
	ios_base::sync_with_stdio(false);
	cout<<take_photos();
	return 0;
}*/

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=1;A<lol.size();A++)
              ~^~~~~~~~~~~
aliens.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=1;A<=vec.size();A++)
              ~^~~~~~~~~~~~
aliens.cpp:24:9: warning: unused variable 'M' [-Wunused-variable]
  ll N=n,M=m,K=k,dp[n+99][k+99];
         ^

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