Submission #964745

#	Time	Username	Problem	Language	Result	Execution time	Memory
964745		hirayuu_oj	Robots (IOI13_robots)	C++17	14 / 100	3047 ms	36024 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector<int> x(A);
    rep(i,A){
        x[i]=X[i];
    }
    sort(all(x));
    vector<int> y(B);
    rep(i,B){
        y[i]=Y[i];
    }
    vector<pair<int,int>> toy(T);
    rep(i,T){
        toy[i]={W[i],S[i]};
    }
    sort(all(toy));
    int ng=0,ok=T+1;
    while(ok-ng>1){
        int mid=(ok+ng)/2;
        multiset<int> size;
        int cnt=0;
        rep(i,A){
            while(cnt<T&&toy[cnt].first<x[i]){
                size.insert(toy[cnt].second);
                cnt++;
            }
            rep(j,mid){
                if(size.empty())break;
                size.erase(size.find(*size.rbegin()));
            }
        }
        while(cnt<T){
            size.insert(toy[cnt].second);
            cnt++;
        }
        rep(i,B){
            rep(j,mid){
                if(size.empty())break;
                if(*size.begin()>=y[i])break;
                size.erase(size.find(*size.begin()));
            }
        }
        if(size.empty())ok=mid;
        else ng=mid;
    }
    if(ok==T+1)return -1;
    return ok;
}

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