Submission #379418

#	Time	Username	Problem	Language	Result	Execution time	Memory
379418		blue	Robots (IOI13_robots)	C++17	0 / 100	1 ms	384 KiB

robots

#include "robots.h"
#include <algorithm>
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);

    int ct[A+1][B+1];
    for(int i = 0; i < A+1; i++)
        for(int j = 0; j < B+1; j++)
            ct[i][j] = 0;

    for(int k = 0; k < T; k++)
    {//if toy k goes in row a of res, it means that a is the smallest robot which can pick up k
        int a = 0, b = 0;

        if(A == 0 || W[k] > X[A-1]) a = A;
        else
        {
            for(int bit = 12; bit >= 0; bit--)
            {
                if(a + (1 << bit) > A-1) continue;
                if(X[a + (1 << bit)] <= W[k]) a += (1 << bit);
            }
            if(X[a] <= W[k]) a++;
        }

        if(B == 0 || S[k] > Y[B-1]) b = B;
        else
        {
            for(int bit = 12; bit >= 0; bit--)
            {
                if(b + (1 << bit) > B-1) continue;
                if(Y[b + (1 << bit)] <= S[k]) b += (1 << bit);
            }
            if(Y[b] <= S[k]) b++;
        }

        ct[a][b]++;
    }

    if(ct[A][B]) return -1;

    for(int i = A-1; i >= 0; i--) ct[i][B] += ct[i+1][B];
    for(int j = B-1; j >= 0; j--) ct[A][j] += ct[A][j+1];

    for(int i = A-1; i >= 0; i--)
    {
        for(int j = B-1; j >= 0; j--)
        {
            ct[i][j] += ct[i][j+1] + ct[i+1][j] - ct[i+1][j+1];
        }
    }

    int res = 0;

    for(int i = A; i >= 0; i--)
    {
        for(int j = B; j >= 0; j--)
        {
            if(i == A && j == B) continue;

            res = max(res, int(ct[i][j] / (A-i + B-j)) + int((ct[i][j] / (A-i + B-j)) != 0));
        }
    }

    return res;
}

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