제출 #886761

#제출 시각아이디문제언어결과실행 시간메모리
886761byakko로봇 (IOI13_robots)C++17
14 / 100
133 ms4952 KiB
#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]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...