結果

問題 No.489 株に挑戦
ユーザー vjudge1
提出日時 2025-01-26 11:05:25
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 56 ms / 1,000 ms
コード長 1,684 bytes
コンパイル時間 1,818 ms
コンパイル使用メモリ 87,024 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2025-01-26 11:05:29
合計ジャッジ時間 3,960 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream> 
#include<cstdio>
using namespace std;
const int MAXN=100010;
int x[MAXN],w[MAXN<<1],ls[MAXN<<1],rs[MAXN<<1];
int tot,rt;
int newNode(){return ++tot;}
void pushup(int u)
{
    w[u]=max(w[ls[u]],w[rs[u]]);
}
void upd(int &u,int l,int r,int ul,int ur,int x)
{
    if(ur<l||r<ul)return;
    if(!u)u=newNode();
    if(ul<=l&&r<=ur)
    {
        w[u]=x;
        return;
    }
    int mid=l+r>>1;
    if(ul<=mid)upd(ls[u],l,mid,ul,ur,x);
    if(ur>mid)upd(rs[u],mid+1,r,ul,ur,x);
    pushup(u);
}
int qry(int &u,int l,int r,int ql,int qr)
{
    if(qr<l||r<ql)return 0;
    if(!u)u=newNode();
    if(ql<=l&&r<=qr)return w[u];
    int mid=l+r>>1;
    int res=-1;
    if(ql<=mid)res=max(res,qry(ls[u],l,mid,ql,qr));
    if(qr>mid)res=max(res,qry(rs[u],mid+1,r,ql,qr));
    return res;
}
int main()
{
    int N,D,K;scanf("%d%d%d",&N,&D,&K);
    for(int i=1;i<=N;++i)scanf("%d",&x[i]);
    int f=1;
    for(int i=1;i<N;++i)
    {
        if(x[i]>=x[i+1])continue;
        else
        {
            f=0;
            break;
        }
    }
    if(f==1)printf("0");
    else
    {
        int ansb=0,anse=0,ans=0;
        for(int i=1;i<=N;++i)upd(rt,1,N,i,i,x[i]);
        for(int i=1;i<=N;++i)
        {
            int b=i+1,e=i+D>N?N:i+D;
            int k=qry(rt,1,N,b,e);
            int curans=k-x[i];
            if((curans>ans)||(curans==ans&&b<ansb)){ansb=i;anse=k;ans=curans;}
        }
        printf("%lld\n",(long long)ans*K);
        int anss=0;
        for(int i=ansb+1;i<=N;++i)
        {
            if(x[i]==anse)
            {
                anss=i;
                break;
            }
        }
        printf("%d %d",ansb-1,anss-1);
    }
    return 0;
}
0