P5665

不要在意最后几个点的输入没搞只是懒得搞

按照KSkun大佬的题解写的，但不知道为什么测试点1~9全对，10+全错。

#include <bits/stdc++.h>
using namespace std;

long long num[40000007];
int len;
int last[40000007];
int q[40000007] , ql , qr;
long long cost(int n){return 2 * num[n] - (last[n] == 0 ? 0 : num[last[n]]);}
class bigint
{
    public:
    #define base 1000000000
    vector <long long> num;
    // void assign(long long n){if(!n){num.clear();return;}num.clear();num.push_back(n);}
    void assign(long long n)
    {
        num.clear();
        for(;n > 0;n /= base)
            num.push_back(n % base);
    }
    void output()
    {
        if(num.empty()){putchar('0');return;}
        for(unsigned long long int i = num.size() - 1;
            i < num.size();i--)
            if(i != num.size() - 1)printf("%09lld" , num[i]);
            else printf("%lld" , num[i]);
    }
    void legal()
    {
        for(;!num.empty() && num.back() == 0;num.erase(num.end() - 1));
    }
};
bigint cplus(bigint a , bigint b)
{
    if(a.num.empty())return b;
    if(b.num.empty())return a;
    if(a.num.size() < b.num.size())swap(a , b);
    bool carry = false;
    for(unsigned long long int i = 0;
        i < b.num.size();i++)
    {
        a.num[i] += b.num[i];
        if(carry){a.num[i]++;carry = false;}
        if(a.num[i] >= base){a.num[i] -= base;carry = true;}
    }
    if(carry)
    {
        for(unsigned long long int i = b.num.size();
            i < a.num.size();i++)
            if(a.num[i] == base - 1){a.num[i] = 0;}
            else {carry = false;a.num[i]++;break;}
        if(carry)a.num.push_back(1);
    }
    return a;
}
bigint mul_single(bigint a , long long b)
{
    long long carry = 0;
    for(unsigned long long int i = 0;i < a.num.size();i++)
    {
        a.num[i] *= b;
        a.num[i] += carry;
        carry = a.num[i] / base;
        if(a.num[i] >= base)a.num[i] %= base;
    }
    a.legal();
    return a;
}
bigint mul10(bigint a , int b)
{
    bigint c;c.num.clear();
    while(b--)c.num.push_back(0);
    for(unsigned long long int i = 0;
        i < a.num.size();i++)
        c.num.push_back(a.num[i]);
    return c;
}
bigint mul(bigint a , bigint b)
{
    bigint c;c.num.clear();
    for(unsigned long long int i = 0;
        i < a.num.size();i++)
    {
        c = cplus(c , mul10(mul_single(b , a.num[i]) , i));
    }
    return c;
}
int main()
{
    cin >> len >> num[0];
    for(int i = 1;i <= len;i++)scanf("%lld" , num + i);
    for(int i = 2;i <= len;i++)num[i] += num[i - 1];
    for(int i = 1;i <= len;i++)
    {
        int l = 0;
        while(ql != qr && cost(q[ql]) <= num[i]){l = q[ql];ql++;}
        last[i] = l;q[--ql] = l;
        while(qr != ql && cost(q[qr - 1]) >= cost(i))qr--;
        q[qr++] = i;
    }
    bigint ans;ans.num.clear();
    for(int i = len;i != 0;)
    {
        bigint a;a.assign(num[i] - num[last[i]]);
        ans = cplus(ans , mul(a , a));
        i = last[i];
    }
    ans.output();
    return 0;
}