제출 #347441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347441		tengiz05	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	384 KiB

aliens

#include "aliens.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	vector<vector<int>> v(m,vector<int>(m,0));
	for(int i=0;i<n;i++){
		if(r[i] > c[i])swap(r[i],c[i]);
	}
	vector<pair<int,int>> a;
	for(int i=0;i<n;i++){
		a.push_back({r[i],c[i]});
	}sort(a.begin(),a.end());
	//~ a.erase(unique(a.begin(),a.end()),a.end());
	for(int i=0;i<n;i++){
		int sc = r[i], sr = r[i], tc = c[i], tr = c[i];
		for(int I=sc;I<=tc;I++){
			for(int J=sr;J<=tr;J++){
				v[I][J] = 1;
			}
		}
	}n = a.size();
	k = n-k;
	vector<bool> used(n);
	while(k > 0){ k--;
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
		for(int i=1;i<n;i++){
			if(used[i])continue;
			int sc = a[i-1].ff, sr = a[i-1].ff, tc = a[i].ss, tr = a[i].ss;
			int res = 0;
			for(int I=sc;I<=tc;I++){
				for(int J=sr;J<=tr;J++){
					if(v[I][J] == 0)res++;
				}
			}q.push({res,i});
		}
		auto [res, i] = q.top();
		used[i] = true;
		int sc = a[i-1].ff, sr = a[i-1].ff, tc = a[i].ss, tr = a[i].ss;
		for(int I=sc;I<=tc;I++){
			for(int J=sr;J<=tr;J++){
				v[I][J] = 1;
			}
		}a.erase(a.begin()+i,a.begin()+i+1);
	}
	ll ans = 0;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			ans += v[i][j];
			//~ cout << v[i][j] << ' ';
		}
		//~ cout << '\n';
	}return ans;
}


/*

5 7 2
0 3
4 4
4 6
4 5
4 6

2 6 2
1 4
4 1



*/

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