oj.uz

답안 #162528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162528 2019-11-08T16:06:17 Z combi1k1 수열 (APIO14_sequence) C++14
0 / 100
 2000 ms 3832 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

const int   N   = 1e5 + 1;

typedef pair<ll,ll>     ii;

struct  ConvexHull  {
    int tot = 0;
    int ptr = 0;

    ii  line[N];
    int name[N];

    int bad(ii a,ii b,ii c) {
        return  1.0 * (c.Y - a.Y) / (a.X - c.X) <= 1.0 * (b.Y - a.Y) / (a.X - b.X);
    }
    int add(ll s,ll c,int i){
        while (tot > 1) {
            if (bad(line[tot - 1],line[tot],ii(s,c)))   {
                tot--;
                continue;
            }
            break;
        }
        ++tot;
        line[tot] = ii(s,c);
        name[tot] = i;
    }
    ll  get(int i,int x)    {
        return  line[i].X * x + line[i].Y;
    }
    ii  get(int x)  {
        for(ptr = min(ptr,tot) ; ptr < tot && get(ptr,x) <= get(ptr + 1,x) ; ++ptr);
        return ii(get(ptr,x),name[ptr]);
    }
}   Combi;

int a[N], c[N];
ll  f[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;

    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i],
        a[i] += a[i - 1];

    auto trial = [&](ll  D) {
        Combi.tot = 0;
        Combi.ptr = 1;
        Combi.add(0,0,0);
        for(int i = 1 ; i <= n ; ++i)   {
            int j = Combi.get(a[i] * 2).Y;

            f[i] = f[j] + 1ll * (a[i] - a[j]) * (a[i] - a[j]) - D;
            c[i] = c[j] + 1;

            Combi.add(a[i], -f[i] - 1ll * a[i] * a[i],i);
        }

        return  c[n] > k;
    };

    ll  L = -1e13;
    ll  R =  1e13;

    for(; L < R ;)  {
        ll  M = (L + R) / 2;
        if (trial(M))
            R = M;
        else
            L = M + 1;
    }

    trial(L);

    ll  ans = (1ll * a[n] * a[n] - f[n] - L * (k + 1)) / 2;

    cout << ans << "\n";

    stack<int>  res;

    while (n)   {
        for(int i = n - 1 ; i >= 0 ; --i)
            if (f[i] + 1ll * (a[n] - a[i]) * (a[n] - a[i]) - L == f[n]) {
                res.push(n);
                n = i;
                break;
            }
    }
    while (res.size() > 1)
        cout << res.top() << " ",
        res.pop();
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message

sequence.cpp: In member function 'int ConvexHull::add(long long int, long long int, int)':
sequence.cpp:34:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1912 KB contestant found the optimal answer: 108 == 108
2 Execution timed out 2051 ms 1912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2068 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2060 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2040 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 12 ms 2300 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Execution timed out 2056 ms 2140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2049 ms 3832 KB Time limit exceeded
2 Halted 0 ms 0 KB -