Submission #636495

#	Time	Username	Problem	Language	Result	Execution time	Memory
636495		gromperen	Aliens (IOI16_aliens)	C++14	25 / 100	146 ms	2380 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
 
const int INF = 1e9+7;
 
#define ll long long
#define int long long

using namespace std;
 
int sqr(int x) {return x * x;}
 
long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
	/*
	vector<vector<int>> vis(m+1, vector<int>(m+1));
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (r[i] > c[i]) swap(r[i], c[i]);
		for (int x = r[i]; x <= c[i]; ++x) {
			for (int y = r[i]; y <= c[i]; ++y) {
				if (vis[x][y]) continue;
				ans++;
				vis[x][y] = 1;
			}
		}
	}
	*/
 
	vector<pair<int,int>> tmpcords;
	vector<pair<int,int>> cords;
	for (int i = 0; i < n; ++i) {
		tmpcords.push_back({min(r[i], c[i]), max(r[i], c[i])});
	}
	sort(tmpcords.begin(), tmpcords.end(), 
			[](pair<int,int>a,pair<int,int>b) 
			{return a.first<b.first || (a.first==b.first && a.second>b.second);});
 
	for (auto i : tmpcords) {
		if (cords.size() && cords.back().second >= i.second) continue;
		cords.push_back(i);
	}
 
	n = cords.size();
	//cout << "DBG" << endl;
	//for (int i =0 ;i < n; ++i) {
		//cout << cords[i].first << " " << cords[i].second << "\n";
	//}
	
	vector<vector<int>> dp(n+1, vector<int>(k+1, INF));
	dp[0][0] = 0;
	for (int i = 0;i <= k; ++i) dp[0][i] = 0;
 
	for (int i = 1; i <= n; ++i) {
		for (int j =1; j <= k; ++j) {
			for (int p = 0; p < i; ++p) {
				int cur = dp[p][j-1] + sqr(cords[i-1].second - cords[p].first + 1);
				//cout << cur << " ";
				if ((p -1 >= 0) && cords[p-1].second >= cords[p].first) 
					cur -= sqr(cords[p-1].second - cords[p].first + 1);
				//cout << cur << endl;
				dp[i][j] = min(dp[i][j], cur);
			}
 
		}
	}
 
	//for (int i =0; i<=n;++i) {
		//for (int j = 0; j<=k;++j) {
			//cout << dp[i][j] << " ";
		//}
		//cout << "\n";
	//}
 
	int ans = 1e9+7;
	for (int i = 0; i <= k; ++i) {
		ans = min(ans, dp[n][i]);
	}
 
 
    return ans;
}

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