QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#391935 | #1170. Hotspot-2 | Diu | WA | 27ms | 239480kb | C++14 | 2.7kb | 2024-04-16 22:12:16 | 2024-04-16 22:12:16 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e6+10;
const ll inf=2e9;
inline char nc(){
static char buf[1000010],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000010,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register int s=0;
static char ch=nc();
for(;!isdigit(ch);)ch=nc();
for(;isdigit(ch);)s=(s<<1)+(s<<3)+(ch^48),ch=nc();
return s;
}
int n,a[N];
ll ans;
vector<ll> g[N],f[N];
//g存有用状态,f用于dp
signed main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
a[0]=-inf,a[n+1]=inf;
// bool flg=1;
// for(int i=2;i<n;i++)if((ll)a[i]*2!=(ll)a[i+1]+(ll)a[i-1]){flg=0;break;}
// if(flg)return printf("%lld\n",2ll*(a[2]-a[1])*(a[2]-a[1])*((n+1)/2)),0;
for(int i=1;i<=n;i++)g[i].push_back(0),g[i].push_back(min((ll)a[i]-(ll)a[i-1],(ll)a[i+1]-(ll)a[i]));
//不选和顶满的状态必须考虑
//贪心:考虑><<<<<<<>和<>>>>>>><的情况(我也不会证
//等号在两端带上
for(int l=1;l<=n;l++){
if((ll)a[l]-(ll)a[l-1]>(ll)a[l+1]-(ll)a[l])continue;
int r=l+1;
while((ll)a[r]-(ll)a[r-1]>(ll)a[r+1]-(ll)a[r])++r;
ll lst=0;//上一个半径(会影响到下一个圆的决策)
for(int i=l;i<=r;i++){
ll t;
if(i!=l)t=min((ll)a[i+1]-(ll)a[i],(ll)a[i]-(ll)a[i-1]-lst);//表示当前半径
else t=(ll)a[i]-(ll)a[i-1];
if(t<0)break;
g[i].push_back(t);
lst=t;
}
l=r-1;
}
for(int l=1;l<=n;l++){//和他一样
if((ll)a[l]-(ll)a[l-1]<(ll)a[l+1]-(ll)a[l])continue;
int r=l+1;
while((ll)a[r]-(ll)a[r-1]<(ll)a[r+1]-(ll)a[r])++r;
ll lst=0;
for(int i=r;i>=l;i--){
ll t;
if(i!=r)t=min((ll)a[i]-(ll)a[i-1],(ll)a[i+1]-(ll)a[i]-lst);
else t=(ll)a[i+1]-a[i];
if(t<0)break;
g[i].push_back(t);
lst=t;
}
l=r-1;
}
for(int i=1;i<=n;i++){//dp
if(i>2)g[i-2].clear(),f[i-2].clear();//i的转移只和i-1有关
sort(g[i].begin(),g[i].end());
// printf("DP:%lld\n",i);
for(int j=0;j<g[i].size();j++){
ll x=2ll*g[i][j]*g[i][j];
if(g[i-1].size()){
int t=upper_bound(g[i-1].begin(),g[i-1].end(),(ll)a[i]-(ll)a[i-1]-g[i][j])-g[i-1].begin()-1;
if(t>=0)x+=f[i-1][t];
}
f[i].push_back(x);
// printf("%lld %lld\n",g[i][j],f[i][j]);
if(j)f[i][j]=max(f[i][j],f[i][j-1]);
}
g[i].push_back(inf);
}
printf("%lld\n",f[n][f[n].size()-1]);
}
详细
Test #1:
score: 0
Wrong Answer
time: 27ms
memory: 239480kb
input:
3 0 2 5
output:
26
result:
wrong answer expected '13', found '26'