Submission #886761

#	Time	Username	Problem	Language	Result	Execution time	Memory
886761		byakko	Robots (IOI13_robots)	C++17	14 / 100	133 ms	4952 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9 + 10;

bool check(int X[], int A, int W[], int T, int k) {
	int cur = 0;
	for(int i = 0; i < T; i += k) {
		int end = min(T, i + k);
		for(int j = i; j < end; j++)
			if(X[cur] <= W[j]) return false;
		cur++;
	}
	return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	if(A == 0) {
		swap(A, B);
		swap(X, Y);
		swap(W, S);
	}
	if(B == 0) {
		sort(X, X + A);
		reverse(X, X + A);
		sort(W, W + T);
		reverse(W, W + T);
		if(!check(X, A, W, T, T)) return -1;
		int lo = 0, hi = T;
		while(lo + 1 < hi) {
			int mid = (lo + hi) >> 1;
			if(check(X, A, W, T, mid)) hi = mid;
			else lo = mid;
		}
		return hi;
	} else {
		sort(X, X + A);
		sort(Y, Y + B);
		vector<vector<vector<int>>> dp(A + 1, vector<vector<int>>(B + 1, vector<int>(T + 1, INF)));
		for(int i = 0; i <= A; i++)
			for(int j = 0; j <= B; j++)
				dp[i][j][0] = 0;

		vector<vector<int>> acum(A + 1, vector<int>(B + 1, 0));
		for(int i = 0; i <= A; i++)
			for(int j = 0; j <= B; j++) {
				int best_a = 0, best_b = 0;
				if(i) best_a = X[i - 1];
				if(j) best_b = Y[j - 1];
				for(int k = 0; k < T; k++)
					if(W[k] < best_a and S[k] < best_b)
						acum[i][j]++;
			}

		if(acum[A][B] < T) return -1;

		for(int i = 1; i <= A; i++)
			for(int j = 1; j <= B; j++)
				for(int k = 1; k <= acum[A][B]; k++) {
					for(int s = 0; s < k; s++) {
						dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][j][s], k - s));
						dp[i][j][k] = min(dp[i][j][k], max(dp[i][j - 1][s], k - s));
					}
				}

		return dp[A][B][T];
	}
}

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