Submission #392712

#	Time	Username	Problem	Language	Result	Execution time	Memory
392712		Antekb	Robots (IOI13_robots)	C++14	100 / 100	2458 ms	22068 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    pair<int, int> tab[T];
    for(int i=0; i<T; i++){
    	tab[i]={upper_bound(X, X+A, W[i])-X, upper_bound(Y, Y+B, S[i])-Y};
    }
    sort(tab, tab+T);
    int l=1, r=T+1;
    while(l<r){
    	int m=(l+r)/2;
    	bool b=1;
    	int j=A-1;
        map<int, int> M;
        for(int i=0; i<B; i++){
            M[i]=m;
        }
    	long long a=0;
    	for(int i=T-1; i>=0; i--){
    		while(j>=0 && j>=tab[i].st)j--, a+=m;
            auto t=M.lower_bound(tab[i].nd);
            if(t==M.end())a--;
            else if(--(*t).nd==0)M.erase(t);
            if(a<0){
                b=0;
                break;
            }
    		
    	}
    	if(b)r=m;
    	else l=m+1;
    }
    if(l==T+1)return -1;
    return l;
}

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