#include "shortcut.h"
#include <vector>
#include <algorithm>
using namespace std;
struct rect {
long long lft,top,rgt,bot;
rect():lft(-1e18),top(1e18),rgt(1e18),bot(-1e18) {}
rect(long long _lft,long long _top,long long _rgt,long long _bot):lft(_lft),top(_top),rgt(_rgt),bot(_bot) {}
};
rect comb(const rect &a, const rect &b) {
return rect(max(a.lft,b.lft),min(a.top,b.top),min(a.rgt,b.rgt),max(a.bot,b.bot));
}
struct inter {
long long a,b,c;
rect eval(long long k) const {
long long z=k-c;
return rect(a-b-z,a+b+z,a-b+z,a+b-z);
}
};
vector<long long> qs;
vector<inter> inters;
bool work(long long k,long long cost) {
rect cur;
for (auto &i:inters) {
if (i.c-cost+i.b-i.a<=k) continue;
cur=comb(cur,i.eval(k));
}
if (cur.lft>cur.rgt||cur.bot>cur.top) return false;
int n=(int)qs.size();
long long x,y;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
x=qs[i]-qs[j];
y=qs[i]+qs[j];
if (cur.lft<=x&&x<=cur.rgt&&cur.bot<=y&&y<=cur.top) return true;
}
}
return false;
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
qs.resize(n,0);
for (int i=1;i<n;i++) {
qs[i]=l[i];
qs[i]+=qs[i-1];
}
inters.reserve(n*(n-1)/2);
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
inters.push_back(inter{qs[i],qs[j],d[i]+d[j]+c});
}
}
long long lo=0;
long long hi=1e15;
long long mid;
while (lo<hi) {
mid=(lo+hi)>>1;
if (work(mid,c)) {
hi=mid;
} else {
lo=mid+1;
}
}
return lo;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
492 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
492 KB |
n = 4, 21 is a correct answer |
4 |
Incorrect |
2 ms |
492 KB |
n = 3, incorrect answer: jury 4 vs contestant 3 |