QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#391935#1170. Hotspot-2DiuWA 27ms239480kbC++142.7kb2024-04-16 22:12:162024-04-16 22:12:16

Judging History

你现在查看的是最新测评结果

  • [2024-04-16 22:12:16]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:239480kb
  • [2024-04-16 22:12:16]
  • 提交

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'