| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1106050 | RKHTM | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define yasuho ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
typedef long long ll;
const ll MOD = 1e9+7;
int putaway(int a, int b, int t, int x[], int y[], int weight[], int size[]){
int mxa=INT_MIN, mxb=INT_MIN;
for(int i=0; i<a; i++) mxa = max(mxa, x[i]);
for(int i=0; i<b; i++) mxb = max(mxb, y[i]);
for(int i=0; i<t; i++){
if(weight[i]<mxa or size[i]<mxb) continue;
return -1;
}
ll l=1, r=t, m/*time*/;
while(l<=r){
m = (l+r)/2;
// cout << l << ' ' << r << ' ' << m << endl;
priority_queue<pair<ll, ll>> all; // {-weight, size}
for(int i=0; i<t; i++) all.push({-1*weight[i], size[i]});
priority_queue<pair<ll, ll>> in; // {size, weight}
for(int i=0; i<a; i++){
while(not all.empty() and all.top().first*-1<x[a]){
in.push({all.top().second, all.top().first*-1});
all.pop();
}
for(int j=1; j<=m and not in.empty(); j++) in.pop();
}
priority_queue<pair<ll, ll>> jackpot; // {-size, weight}
while(not all.empty()){
jackpot.push({all.top().second*-1, all.top().first*-1});
all.pop();
}
while(not in.empty()){
jackpot.push({in.top().first*-1, in.top().second});
in.pop();
}
for(int i=0; i<b; i++){
for(int j=1; j<=m and not jackpot.empty(); j++){
if(jackpot.top().first*-1>=size[i]) break;
jackpot.pop();
}
}
if(jackpot.empty()) r=m-1;
else l=m+1;
}
return l;
}
void solve(){
int a, b, t; cin >> a >> b >> t;
int x[a], y[b], weight[t], size[t];
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 >> weight[i];
for(int i=0; i<t; i++) cin >> size[i];
cout << putaway(a, b, t, x, y, weight, size);
return;
}
int main(){
yasuho // remove for interactive problem
ll t;
t = 0;
//cin >> t;
while(t--) solve();
}