2015湖南省チーム合宿DAY 8-夢工場

夢工場(yume.cpp/c/pas)
Time Limit: 1 s Memory Limit: 128 M
問題の説明
「时には腐った名前でも意味がある」――EN语录よりこれはあなたがこの奇妙な場所に来て聞いた最初の言葉で、意外にも体長3メートルの熊が出てきたのです.最初に夢工場という看板を見たとき、あなたの心の中で思ったことは何ですか.本当に青くて純潔な夢があふれているなら、それは素晴らしいです.初めて来たので、熊さんはまず工場の運営過程を大まかに説明することにしました.「私たちの所は夢の工場で、子供たちのために楽しくて幸せな夢の工場を生産していることを知っておく必要があります!」クマさんは夢工場の定義を繰り返している.頭がぼんやりしていても、この工場は楽しくて幸せな気持ちを生産していることを最終的に知っています.退屈したり、挫折したりした子供に笑顔を見せるために使われています.「でも、私たちは問題にぶつかった...」と、クマさんの口調は低くなった.「最近、楽しくない子供が増えてきました.私たちが生産しなければならない楽しみも増えていますが、私たちの生産ラインはnつの工程で構成されています.単位時間当たりの工程は最大1つの楽しみしか収容できません.1つの楽しみが1つの工程で加工されると、すぐに次の工程に伝わります.」「それから、どうしたんですか.これはいいんじゃないですか」君は奇抜だ.「なんだ!快楽は次の工程に強制的に伝わり、次の工程にも快楽があれば爆発する!爆発わかるか!瞬間爆発!」クマさんは語気が高ぶった.「私たちは爆発を防ぐために、すべての工程を楽しく生産してから、もう一つの楽しみを生産し始めました.しかし、何百年も考えて、早く生産を始めることができると思います.同じ時点で同じ工程に現れないことを保証すればいいと思います」.クマさんは誇りに胸を張って、少し怖いです.「ついでに教えてあげましょう.各工程には複雑な指数Tiがあり、1つの快楽に快楽指数Fjがあり、j番目の快楽がi番目の工程で消費する時間はFj「私が何でも教えてあげた以上、へへへ」と、熊さんは凶暴な笑みを浮かべて、肉食の「どうやって生産するのが一番いいか手配してください.最短のすべての生産が終わった時間を教えてください.そうしないと、歯祭りをします!」これは夢工場ですか.夢でしょう?
入力フォーマット
1行目の2つの整数nとmは、工程の数、生産する必要がある楽しい数を表す.2行目のn個の整数は,それぞれ複雑な指数Tiを表す.3行目のm個の整数は、それぞれ快楽指数Fiを表す.
出力フォーマット
正の整数は最短時間です.Sample Input 3 3 2 1 1 2 1 1 Sample Output 11
問題解とツッコミ
南雅のこの問題面...人の話をするのはよくない
2時間近くかけてこの暴力を書いて、また2時間で愚かなバッグを調整しました.傾きの最適化が何なのかやっと分かったような気がします.
まずTiの接頭辞と求め,sumiとして記録し,前i−1個の物品をすべて処理した時間を維持する.そしてi番目の品物については,どうしても前の段階と同時に現れないようにするので,sumj∗fi−1−sumj−1∗fiの最大値を求め,この値から節約した時間を減算することができる.
上のそれは暴力で、それから私たちはその式を転化することができることを発見して、経典の傾きの最適化の問題になりました.(sumi−1,sumi)で形成されたオーバーフローパケットを維持し,問い合わせのたびに二分検索すればよい.
次のコード

#include 

using namespace std;

typedef long long ll;
typedef double db;

const int inf=0x3f3f3f3f;

int getint()
{
    char c=getchar();
    int f=1,g=0;
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c<='9' && c>='0')g=(g<<3)+(g<<1)+c-'0',c=getchar();
    return f*g;
}

const int maxn=2000005;

int top;
int sum[maxn];
int f[maxn];
int t[maxn];
int n,m;

db slp[maxn];
ll ans;
int q[maxn];

db slope(int j,int k)
{
    db temp1=(db)sum[j-1]-(db)sum[k-1];
    db temp2=(db)sum[j]-(db)sum[k];
    return temp1/temp2;
}

int findpos(db x)
{
    int l=1;
    int r=top-1;
    if(xreturn q[1];
    if(x>slp[r])return q[top];
    while(lint mid=(l+r)>>1;
        if(slp[mid]<x)
        {
            l=mid+1;
        }
        else r=mid;
    }
    return q[l];
}

int main()
{
    freopen("yume.in","r",stdin);
    freopen("yume.out","w",stdout);

    n=getint();
    m=getint();

    for(int i=1;i<=n;i++)
    {
        t[i]=getint();
        sum[i]=sum[i-1]+t[i];
    }

    for(int i=1;i<=m;i++)
    {
        f[i]=getint();
    }

    for(int i=1;i<=n;i++)
    {
        while(top>1 && slp[top-1]>=slope(q[top],i))
        {
            top--;
        }
        q[++top]=i;
        slp[top-1]=slope(q[top],q[top-1]);
    }
    for(int i=1;i<=m;i++)
    {
        db tem=(db)f[i-1]/(db)f[i];
        int temp=findpos(tem);

        ll mx=(ll)sum[temp]*(ll)f[i-1]-(ll)sum[temp-1]*(ll)f[i];

        mx-=(ll)sum[n]*((ll)f[i-1]-(ll)f[i]);
        mx=max(0ll,mx);

        ans+=mx;
    }
    printf("%lld
",ans);

    return 0;
}