| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 659407 | angelo_torres | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// #include "robots.h"
#define sz(v) (int) v.size()
#define ff first
#define ss second
using namespace std;
typedef pair<int,int> ii;
vector<int> a,b;
vector<ii> t;
int g[1005][1005],pr[1005][1005];
bool go(int mn){
int mlx = mn, ix = sz(a)-1, mly = mn, iy = sz(b)-1;
for(int i = sz(t)-1; i >= 0; --i){
int wi = t[i].ff, si = t[i].ss;
if(ix >= 0 && a[ix] > wi){
mlx--;
if(mlx == 0) mlx = mn, ix--;
continue;
}
if(iy >= 0 && b[iy] > si){
mly--;
if(mly == 0) mly = mn, iy--;
continue;
}
return false;
}
return true;
}
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());
for(int i = 0; i < T; ++i) t.push_back({W[i],S[i]});
sort(t.begin(),t.end());
int l = 1, r = 1000001;
// [l,r>
while(r-l > 1){
int md = (l+r)>>1;
if(!go(md)) l = md;
else r = md;
}
if(r == 1000001) return -1;
return r;
}
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";
}