Submission #610555

#	Time	Username	Problem	Language	Result	Execution time	Memory
610555		neki	Robots (IOI13_robots)	C++14	100 / 100	2990 ms	20604 KiB

robots

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

using namespace std;

int putaway(int A,int B,int T, int X[], int Y[],int W[],int S[]){
    int l=1, r=T+1;
    
    vc<int> ind(T);for(int i=0;i<T;++i) ind[i]=i;
    sort(ind.begin(), ind.end(), [&](int a, int b){return W[a]<W[b];});
    sort(X, X+A);
    
    function<bool (int)> check=[&](int k){
        map<int, int> prosti;
        for(int i=0;i<B;++i) prosti[Y[i]]+=k;
        
        int j=A-1;
        for(int i=T-1;i>=0;--i){
            while(j>=0 and X[j]>W[ind[i]]) prosti[INT_MAX]+=k, --j;
            
            auto poi=prosti.upper_bound(S[ind[i]]);
            if(poi==prosti.end()) return false;
            
            if(--poi->second ==0) prosti.erase(poi);
        }
        return true;
    };
    if(check(T)){
        while(l<r){
            int mid=(l+r)/2;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        return l;
    }
    else return -1;
}

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