Submission #619491

#	Time	Username	Problem	Language	Result	Execution time	Memory
619491		sofapuden	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	304 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;


ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	for(int i = 0; i < n; ++i)if(r[i] > c[i])swap(r[i],c[i]);
	vector<pair<int,int>> v, _v;
	for(int i = 0; i < n; ++i)_v.emplace_back(r[i],c[i]);
	sort(_v.begin(),_v.end());
	v.push_back(_v[0]);
	for(int i = 0; i < n; ++i){while(v.size()&& _v[i].first == v.back().first)v.pop_back();if(_v[i].second > v.back().second)v.push_back(_v[i]);}
	n = v.size();
	if(k >= n){
		ll ans = (v[0].second-v[0].first+1)*(v[0].second-v[0].first+1);
		for(int i = 1; i < n; ++i){
			ans+=(v[i].second-v[i].first+1)*(v[i].second-v[i].first+1);
			if(v[i].first <= v[i-1].second)ans-=(v[i-1].second-v[i].first+1)*(v[i-1].second-v[i].first+1);
		}
		return ans;
	}
	return 0;

}

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