Submission #611263

#	Time	Username	Problem	Language	Result	Execution time	Memory
611263		Do_you_copy	Split the sequence (APIO14_sequence)	C++17	0 / 100	73 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;

int n, k;
int a[maxN];
ll dp[maxN][201];
int trace[maxN][201];
ll pre[maxN];

struct TLine{
    int fi, se, idx;
};

inline ld intersect(const TLine &i, const TLine &j){
    return ld(i.se - j.se) / ld(j.fi - i.fi);
}

inline ll cal(const TLine &i, int x){
    return i.fi * x + i.se;
}

deque <TLine> S[201];

void Init(){
    cin >> n >> k;
    ++k;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    S[0].pb({0, 0, 0});
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= k; ++j){
            if (S[j - 1].empty()) break;
            int x = pre[n] - pre[i];
            while (S[j - 1].size() > 1 && cal(S[j - 1][0], x) <= cal(S[j - 1][1], x)) S[j - 1].pop_front();
            TLine f = S[j - 1][0];
            dp[i][j] = cal(f, x) + pre[i] * x;
            trace[i][j] = f.idx;
            TLine newline = {-pre[i], dp[i][j], i};
            while (S[j].size() > 1 && S[j].back().fi != newline.fi && intersect(S[j].back(), S[j][S[j].size() - 2]) <= intersect(S[j].back(), newline)) S[j].pop_back();
            S[j].pb(newline);
        }
    }
    cout << dp[n][k] << "\n";
    int idx = n;
    vector <int> ans;
    for (int i = k; i && trace[idx][i]; --i){
        idx = trace[idx][i];
        ans.pb(idx);
    }
    reverse(ans.begin(), ans.end());
    for (int i: ans) cout << i << " ";
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void Init()':
sequence.cpp:66:30: warning: narrowing conversion of '- pre[i]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |             TLine newline = {-pre[i], dp[i][j], i};
      |                              ^~~~~~~
sequence.cpp:66:46: warning: narrowing conversion of 'dp[i][j]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |             TLine newline = {-pre[i], dp[i][j], i};
      |                                       ~~~~~~~^
sequence.cpp: In function 'int main()':
sequence.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29