QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#266020 | #2338. Beautiful Bridges | InfinityNS# | WA | 1ms | 3624kb | C++14 | 2.2kb | 2023-11-26 01:10:56 | 2023-11-26 01:10:57 |
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;
long 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);
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++){
if(x[j]>2*y[i])break;
/*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(p.f<N&&next[p.f]!=INT_MAX){
c[next[p.f]]++;
}
if(p.s<N&&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]);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
5 60 18 2 0 0 20 20 30 10 50 30 70 20
output:
6460
result:
ok single line: '6460'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
4 10 1 1 0 0 1 9 9 9 10 0
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 1 1 1 0 0 2 0
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
2 1 1 1 0 0 3 0
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
4 5 100 1 0 0 1 3 9 3 10 0
output:
1100
result:
ok single line: '1100'
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3616kb
input:
4 5 1 100 0 0 1 3 9 3 10 0
output:
8212
result:
wrong answer 1st lines differ - expected: '10010', found: '8212'