Submission #823485

#	Time	Username	Problem	Language	Result	Execution time	Memory
823485		tolbi	Aliens (IOI16_aliens)	C++17	25 / 100	42 ms	3460 KiB

aliens

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//ahmet23 orz...
//FatihSultanMehmedHan(ortanca da orz)
//AbdulhamidHan
//YavuzSultanSelimHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it;return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" ";return os;}
template<typename T, size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it;return is;}
template<typename T, size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" ";return os;}
template<typename T> void coutarr(T __arr){for (auto &it : __arr){cout<<it<<" ";}cout<<endl;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define endl '\n'
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define vint(x) vector<int> x
#define tol(bi) (1LL<<((int64_t)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "aliens.h"

ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	vector<bool> gerekli(n,true);
	for (int i = 0; i < n; i++){
		if (r[i]>c[i]) swap(r[i],c[i]);
		for (int j = 0; j < i; j++){
			if (r[i]>=r[j] && c[i]<=c[j]){
				gerekli[i]=false;
			}
			else if (r[j]>=r[i] && c[j]<=c[i]){
				gerekli[j]=false;
			}
		}
	}
	vector<pair<int,int>> arr;
	for (int i = 0; i < n; ++i)
	{
		if (gerekli[i]) arr.push_back({r[i],c[i]});
	}
	n=arr.size();
	sortarr(arr);
	vector<vector<ll>> dp(n,vector<ll>(k+1,-1));
	vector<vector<int>> opt(n,vector<int>(k+1,-1));
	function<ll(int,int)> f;
	f = [&](int node, int kal)->ll{
		if (dp[node][kal]!=-1) return dp[node][kal];
		dp[node][kal]=dp[node][kal]=((ll)arr.back().second-(ll)arr[node].first+1LL)*((ll)arr.back().second-(ll)arr[node].first+1LL);
		opt[node][kal]=n-1;
		if (node==n-1){
			opt[node][kal]=node;
			return dp[node][kal];
		}
		if (kal>1){
			f(node,kal-1);
			f(node+1,kal);
			int i = node;
			ll curdir = ((ll)arr[i].second-(ll)arr[node].first+1)*((ll)arr[i].second-(ll)arr[node].first+1);
			ll azaldir = ((ll)arr[i].second-(ll)arr[i+1].first+1)*((ll)arr[i].second-(ll)arr[i+1].first+1);
			if (((ll)arr[i].second-(ll)arr[i+1].first+1)<0){
				azaldir=0;
			}
			ll crr = curdir-azaldir+f(i+1,kal-1);
			if (crr<dp[node][kal]){
				opt[node][kal]=i;
				dp[node][kal]=crr;
			}
			for (int i = max(node,opt[node][kal-1]-1000); i <= min(opt[node+1][kal],n-2); i++){
				ll curdir = ((ll)arr[i].second-(ll)arr[node].first+1)*((ll)arr[i].second-(ll)arr[node].first+1);
				ll azaldir = ((ll)arr[i].second-(ll)arr[i+1].first+1)*((ll)arr[i].second-(ll)arr[i+1].first+1);
				if (((ll)arr[i].second-(ll)arr[i+1].first+1)<0){
					azaldir=0;
				}
				ll crr = curdir-azaldir+f(i+1,kal-1);
				if (crr<dp[node][kal]){
					opt[node][kal]=i;
					dp[node][kal]=crr;
				}
			}
		}
		return dp[node][kal];
	};
	return f(0,k);
}

Compilation message (stderr)

aliens.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

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