QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#266004 | #2338. Beautiful Bridges | InfinityNS# | WA | 1ms | 3792kb | C++14 | 2.2kb | 2023-11-26 00:37:33 | 2023-11-26 00:37:34 |
Judging History
answer
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
using namespace std;
const ll oo=LLONG_MAX/2;
vector<pair<int,int>> sols(int x,int y){
ll k=2*(ll)x*y;
double a=sqrtl(k);
ll sq=-1;
for(ll x=a-2;x<=a+2;x++){
if(x*x==k){
sq=x;
}
}
int badL=-1,badR=-1;
if(sq!=-1){
badL=2*(x+y-sq)-1;
badR=2*(x+y+sq)+1;
}
else{
badL=floor(2*(x+y-a));
badR=ceil(2*(x+y+a));
}
badL=max(badL,0);
if(y%2){
y=y/2;
}
else{
y=y/2;
}
y=max(y,x-1);
if(badL>y){
return {{y+1,badL},{badR,INT_MAX}};
}
else{
if(badR>y){
return {{badR,INT_MAX}};
}
else{
return {{y+1,INT_MAX}};
}
}
}
int main(){
int n,h,a,b;
cin>>n>>h>>a>>b;
vector<ll> dp(n,oo);
vector<int> x(n),y(n);
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
y[i]=h-y[i];
}
const int N=1e5+5;
vector<int> next(N,INT_MAX);
for(int i=0;i<n;i++){
next[x[i]]=i;
}
for(int i=N-2;i>=0;i--){
next[i]=min(next[i],next[i+1]);
}
dp[n-1]=(ll)a*y[n-1];
vector<int> c(n);
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++)x[j]-=x[i],c[j]=0;
int cntBad=0;
for(int j=i+1;j<n;j++){
/*cout << i << " " << j << endl;
for(auto p:sols(x[j],y[j])){
cout << "bad " << p.f << " " << p.s << endl;
}*/
for(auto p:sols(x[j],y[j])){
p.f+=x[i];
if(p.s!=INT_MAX)
p.s+=x[i]+1;
if(next[p.f]!=INT_MAX){
c[next[p.f]]++;
}
if(p.s!=INT_MAX&&next[p.s]!=INT_MAX){
c[next[p.f]]--;
}
}
cntBad+=c[j];
if(cntBad==0){
dp[i]=min(dp[i],dp[j]+(ll)x[j]*x[j]*b+(ll)y[i]*a);
}
}
for(int j=i+1;j<n;j++)x[j]+=x[i];
}
if(dp[0]>=oo){
printf("impossible\n");
}
else
printf("%lld\n",dp[0]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3792kb
input:
5 60 18 2 0 0 20 20 30 10 50 30 70 20
output:
6560
result:
wrong answer 1st lines differ - expected: '6460', found: '6560'