#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;
auto tmp=i.eval(k);
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-1];
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;
}
Compilation message
shortcut.cpp: In function 'bool work(long long int, long long int)':
shortcut.cpp:36:8: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
auto tmp=i.eval(k);
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
372 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
3 ms |
372 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
3 ms |
508 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
532 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
532 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
3 ms |
532 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
3 ms |
532 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
532 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
4 ms |
532 KB |
n = 2, 2000000001 is a correct answer |
11 |
Incorrect |
3 ms |
532 KB |
n = 2, incorrect answer: jury 3000000000 vs contestant 0 |
12 |
Halted |
0 ms |
0 KB |
- |