제출 #331876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331876		zggf	로봇 (IOI13_robots)	C++14	76 / 100	3098 ms	35668 KiB

robots

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

using namespace std;


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	vector<pair<int, int>> R;
	for(int i = 0; i < T; i++){
		R.push_back(make_pair(W[i], S[i]));	
	}
	sort(R.begin(), R.end());

	sort(X, X+A);
	sort(Y, Y+B, greater<int>());
	
	int pocz = 0, kon = T+1;
	while(pocz<kon){
		int mid = (pocz+kon)/2;
		int pt = -1;
		multiset<int> mp;
		for(int i = 0; i < A; i++){
			int x = X[i];
			while((pt<T-1)&&R[pt+1].first<x){
				pt++;	
				mp.insert(R[pt].second);	
			}	
			int tmp = mid;
			while(tmp&&mp.size()){
				auto nwm = mp.end();
				nwm--;
				mp.erase(nwm);
				tmp--;	
			}	
		}
		for(int i = pt+1; i < T; i++) mp.insert(R[i].second);

		bool pos = true;
		for(int i = 0; i < B; i++){
			int tmp = mid;
			while(tmp&&mp.size()){
				auto nwm = mp.end();
				nwm--;
				if(*nwm>=Y[i]) {pos = false; break;}
				mp.erase(nwm);
				tmp--;	
			}	
			if(!pos) break;
		}	
		if(mp.size()) pos = false;
		if(pos) kon = mid;
		else pocz = mid+1;
	}
	if(pocz==T+1) return -1;
	return pocz;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10