제출 #659371

#제출 시각아이디문제언어결과실행 시간메모리
659371angelo_torres로봇 (IOI13_robots)C++17
76 / 100
136 ms20360 KiB
#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 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...