Submission #612712

#	Time	Username	Problem	Language	Result	Execution time	Memory
612712		Apiram	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	212 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	 vector<vector<long long>>arr(m + 1);
    for (long long i = 0;i<n;++i){
		 r[i]--;
		 c[i]--;
		 if (c[i] > r[i])swap(r[i],c[i]);
		 long long temp = (r[i] - c[i]);
		 if (temp % 2 == 1){
			 long long row = temp;
			 long long col = m - temp;
			 long long dist = max(abs(r[i] - row),abs(c[i] - col));
			 arr[temp].push_back(dist - 1); 
		 }
		 else{
			 long long row = temp - 1;
			 long long col = m - row;
			 long long dist = max(abs(r[i] - row),abs(c[i] - col));
			 if (dist - 1 <= temp - 1)
				arr[temp - 1].push_back(dist - 1);
			 row = temp + 1;
			 col = m - row;
			 dist = max(abs(r[i] - row),abs(c[i] - col));
			 if (dist - 1 <= temp + 1){
				arr[temp + 1].push_back(dist - 1);
			 }
		 }
	 }
	 for (long long i = 0;i<=m;++i)sort(arr[i].begin(),arr[i].end());
	 vector<pair<long long,long long>>dp(m + 1,{0,0}); 
	 for (long long i = 0;i<m;++i){
		long long dist = 0;
		if (!arr[i].empty()){
			dist = arr[i].back();
		}
		auto temp = dp[i - dist];
		long long p = (long long)arr[i].size();
		long long total = dist * dist * 4;
		if (dp[i + dist].first < p + temp.first){
			dp[i + dist].first = p + temp.first;
			dp[i + dist].second = total + temp.second;
		}
		else if (dp[i + dist].first == p + temp.first && dp[i + dist].second > temp.second + total){
			dp[i + dist].first = p + temp.first;
			dp[i + dist].second = total + temp.second;
		}
	 }
	 long long ans = m * m;
	 for (long long i = 0;i<=m;++i){
		if (dp[i].first == n){
			ans = min(ans,dp[i].second);
		}
	 }
	 return ans;
}

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