oj.uz

Submission #110854

# Submission time Handle Problem Language Result Execution time Memory
110854 2019-05-12T15:13:16 Z evpipis Split the sequence (APIO14_sequence) C++17
0 / 100
 127 ms 84040 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const ll inf = 1e18;
const int len = 1e5+5;
int arr[len], pos, pref[len], po[len][205];
ll dp[len];
vector<pll> vec;

ll func(pll line, ll x){
    return line.fi*x+line.se;
}

bool can(pll a, pll b, pll c){
    return (double)(a.se-b.se)/(double)(b.fi-a.fi) >= (double)(b.se-c.se)/(double)(c.fi-b.fi);
}

void add(pll cur){
    while (vec.size() >= 2 && can(vec[vec.size()-2], vec.back(), cur))
        vec.pop_back();
    vec.pb(cur);
}

pair<ll, int> query(ll x){
    if (pos >= vec.size())
        pos = vec.size()-1;

    while (pos+1 < vec.size() && func(vec[pos+1], x) > func(vec[pos], x))
        pos++;
    return mp(func(vec[pos], x), vec[pos].fi);
}

int main(){
    int n, k;
    scanf("%d %d", &n, &k), k++;
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);

    for (int i = 1; i <= n; i++)
        pref[i] = pref[i-1]+arr[i];

    for (int i = 1; i <= n; i++)
        dp[i] = -inf;
    for (int j = 1; j <= k; j++){
        vec.clear();
        pos = 0;
        add(mp(0, 0));
        for (int i = 1; i <= n; i++){
            pair<ll, int> ans = query(pref[i]);
            po[i][j] = ans.se;
            add(mp(pref[i], dp[i]-pref[i]*1LL*pref[i]));
            dp[i] = ans.fi;
        }
    }

    printf("%lld\n", dp[n]);

    int cur = n;
    for (int j = k, p = n; j > 1; j--){
        while (pref[p] > po[cur][j])
            p--;
        cur = p;
        printf("%d ", cur);
    }
    printf("\n");
    return 0;
}

Compilation message

sequence.cpp: In function 'std::pair<long long int, int> query(ll)':
sequence.cpp:33:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos >= vec.size())
         ~~~~^~~~~~~~~~~~~
sequence.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pos+1 < vec.size() && func(vec[pos+1], x) > func(vec[pos], x))
            ~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k), k++;
     ~~~~~~~~~~~~~~~~~~~~~~^~~~~
sequence.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 2 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 2 ms 384 KB contestant found the optimal answer: 0 == 0
4 Correct 3 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 2 ms 384 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Incorrect 2 ms 384 KB contestant didn't find the optimal answer: 0 < 1
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Integer 0 violates the range [1, 199]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1152 KB Integer 0 violates the range [1, 999]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 8828 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 84040 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -