Submission #258311

#	Time	Username	Problem	Language	Result	Execution time	Memory
258311		eohomegrownapps	Robots (IOI13_robots)	C++14	76 / 100	301 ms	20940 KiB

robots

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

int w,h;

vector<vector<int>> grid;

bool success(int mid){
	vector<vector<int>> dp(w+1,vector<int>(h+1,0));
	for (int i = w-1; i>=0; i--){
		dp[i][h]=mid*(w-1-i);
	}
	for (int i = h-1; i>=0; i--){
		dp[w][i]=mid*(h-1-i);
	}
	for (int y = h-1; y>=0; y--){
		for (int x = w-1; x>=0; x--){
			dp[x][y]=dp[x+1][y]+dp[x][y+1]-dp[x+1][y+1]-grid[x][y];
			if (dp[x][y]<0){
				return false;
			}
		}
	}
	return true;
}

int putaway(int lx, int ly, int n, int xpos[], int ypos[], int xtoys[], int ytoys[]) {
	sort(xpos,xpos+lx);
	sort(ypos,ypos+ly);
	for (int i = 0; i<n; i++){
		xtoys[i]=upper_bound(xpos,xpos+lx,xtoys[i])-xpos;
		ytoys[i]=upper_bound(ypos,ypos+ly,ytoys[i])-ypos;
	}
	w=lx+1;
	h=ly+1;
	grid.resize(w,vector<int>(h,0));
	for (int i = 0; i<n; i++){
		grid[xtoys[i]][ytoys[i]]++;
	}
	if (grid[w-1][h-1]>0){
		return -1;
	}
    int l = 0, r = n;
    while (l<=r){
    	int mid = (l+r)/2;;
    	if (success(mid)){
    		r=mid-1;
    	} else {
    		l=mid+1;
    	}
    }
    return l;
}

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