Submission #659371

#	Time	Username	Problem	Language	Result	Execution time	Memory
659371		angelo_torres	Robots (IOI13_robots)	C++17	76 / 100	136 ms	20360 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define sz(v) (int) v.size() 

using namespace std;
typedef pair<int,int> ii;
typedef vector<pair<int,int>> vii;

vector<int> a,b;
int g[1005][1005],pr[1005][1005];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    // A -> X -> W[i] < X[i]
    // B -> Y -> S[i] < Y[i]
    for(int i = 0; i < A; ++i) a.push_back(X[i]);
    for(int i = 0; i < B; ++i) b.push_back(Y[i]);
    sort(a.begin(),a.end()), sort(b.begin(),b.end());
    // g[i][j] : number of toys that can be carry for
    // i-th weak robot but not for i+1-th weak robot,
    // and for j-th small robot but not for j+1-th small
    // robot
    for(int i = 0; i < T; ++i){
        // 0 1 2 
        // 4 7 9
        // W[i] < a[] -> w[i] >= a[]
        int id = (int) (lower_bound(a.begin(),a.end(),W[i]+1)-a.begin());
        int jd = (int) (lower_bound(b.begin(),b.end(),S[i]+1)-b.begin());
        g[id][jd]++;
    }
    for(int i = 0; i <= sz(a); ++i){
        for(int j = 0; j <= sz(b); ++j){
            pr[i][j] = g[i][j];
            if(j > 0) pr[i][j] += pr[i][j-1];
            if(i > 0) pr[i][j] += pr[i-1][j];
            if(i > 0 && j > 0) pr[i][j] -= pr[i-1][j-1];
        }
    }
    int ans = 0;
    for(int i = 0; i < sz(a)+1; ++i){
        for(int j = 0; j < sz(b)+1; ++j){
            // i sz(a) j sz(b)
            int kp = pr[sz(a)][sz(b)];
            if(j > 0) kp -= pr[sz(a)][j-1];
            if(i > 0) kp -= pr[i-1][sz(b)];
            if(i > 0 && j > 0) kp += pr[i-1][j-1];
            int nr = A+B-i-j;
            if(nr == 0){
                if(kp != 0) return -1;
                break;
            }
            ans = max(ans,(kp+nr-1)/nr);
        }
    }
    return ans;
}

// int main(){
//     int A,B,T;
//     cin >> A >> B >> T;
//     int X[A+10],Y[B+10],W[T+10],S[T+10];
//     for(int i = 0; i < A; ++i) cin >> X[i];
//     for(int i = 0; i < B; ++i) cin >> Y[i];
//     for(int i = 0; i < T; ++i) cin >> W[i] >> S[i];
//     cout << putaway(A,B,T,X,Y,W,S) << "\n";
// }

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