제출 #14038

#제출 시각아이디문제언어결과실행 시간메모리
14038kriiiBe Two Bees (OJUZ10_b2b)C++14
0 / 100
59 ms6840 KiB
#include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct rat{ rat(){a = 0; b = 1;} rat(long long a_, long long b_){ a = a_; b = b_; } long long a,b; bool operator <(const rat t) const{ return a * t.b < b * t.a; } }; vector<pair<int, int> > line[100010]; int N,H[100010],T[100010],V[100010],Z; long long S; int p=-1,q=-1; long long A[5],B[5]; void mul(long long *x, long long p) { for (int i=0;i<5;i++) x[i] *= p; for (int i=0;i<5;i++){ if (x[i] >= 10000000){ x[i+1] += x[i] / 10000000; x[i] %= 10000000; } } } void put(int i, int j) { if (i > j) swap(i,j); if (p == -1){ p = i; q = j; return; } for (int k=0;k<5;k++) A[k] = B[k] = 0; A[0] = B[0] = 1; mul(A,S-H[i]-H[j]); mul(A,T[i]); mul(A,T[j]); mul(B,T[i]+T[j]); mul(B,S-H[p]-H[q]); mul(B,T[p]); mul(B,T[q]); mul(A,T[p]+T[q]); bool good = false; for (int k=0;k<5;k++){ if (A[k] < B[k]){ good = true; break; } if (A[k] > B[k]) break; } if (good){ p = i; q = j; } } bool bad(long long t1, long long h1, long long t2, long long h2, long long t3, long long h3) { return t2 * t3 * (h2 - h3) + t3 * t1 * (h3 - h1) + t1 * t2 * (h1 - h2) >= t1 * t2 * t3; } int main() { scanf ("%d",&N); for (int i=0;i<N;i++) scanf ("%d",&H[i]), S += H[i]; for (int j=0;j<N;j++) scanf ("%d",&T[j]), line[T[j]].push_back(make_pair(H[j],j)); for (int i=100000;i>=1;i--) if (!line[i].empty()){ sort(line[i].rbegin(),line[i].rend()); if (line[i].size() >= 2){ put(line[i][0].second,line[i][1].second); } int x = line[i][0].second; while (Z >= 2){ if (bad(T[V[Z-2]],H[V[Z-2]],T[V[Z-1]],H[V[Z-1]],T[x],H[x])){ put(V[--Z],x); } else break; } V[Z++] = x; if (Z >= 2){ put(V[Z-2],V[Z-1]); } } printf ("%d %d\n",p+1,q+1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...