이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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";
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |