Submission #995281

#	Time	Username	Problem	Language	Result	Execution time	Memory
995281		vjudge1	Split the sequence (APIO14_sequence)	C++17	71 / 100	51 ms	131072 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define el '\n'
#define pb push_back
#define mp make_pair
#define niggers                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define file(name)                    \
    freopen(name ".inp", "r", stdin); \
    freopen(name ".out", "w", stdout);

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

const ll MOD = 1e9 + 7;
const int inf = 1e9;
const int mxN = 50 + 5;
const int mxM = 35000 + 5;
const int N = 1e5 + 5;

int hx[] = {-1, 0, 1, 0};
int hy[] = {0, 1, 0, -1};

ll n, k, a[N], dp[N][2], cnt[N], mo_l = 1, mo_r, cur1 = 0, cur2 = 0;
ll ps[N];
// void add(ll i){
//     cur1+=a[i];
//     cur2++;
// }
// void rmv(ll i){
//     cur1-=a[i];
//     cur2--;
// }
ll trace[N][208];
ll get(ll l, ll r)
{
    // while(mo_r < r) add(++mo_r);
    // while(mo_r > r) rmv(mo_r--);
    // while(mo_l < l) rmv(mo_l++);
    // while(mo_l > l) add(--mo_l);
    // return cur1*cur2;
    return (ps[r] - ps[l - 1]) * (ps[l-1]);
}
void calc(ll l, ll r, ll optl, ll optr, ll j)
{
    if (l > r)
        return;
    ll m = l + r >> 1;
    pll best = {-inf, -1};
    for (ll i = optl; i <= min(m, optr); ++i)
    {
            best = max(best, {dp[i - 1][j & 1 ^ 1] + get(i, m), i});
    }
    dp[m][j & 1] = best.fi;
    ll opt = best.se;
    trace[m][j] = opt-1;
    calc(l, m - 1, optl, opt, j);
    calc(m + 1, r, opt, optr, j);
}
void solve()
{
    cin >> n >> k;
    for (ll i = 1; i <= n; ++i)
    {
        cin >> a[i];
        ps[i] = ps[i - 1] + a[i];
    }
    for (ll i = 1; i <= k; ++i)
    {
        calc(i, n, 1, n, i);
    }
    cout << dp[n][k & 1] <<'\n';
    vi ans;
    for( ll i = k ; i >= 1 ; i--){
        n = trace[n][i];
        ans.pb(n);
    }
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout << x << ' ';
}

int main()
{
    // freopen("b.inp", "r", stdin);
    // freopen("b.out", "w", stdout);
    ll pinkkiu = 1;
    // cin >> pinkkiu;
    while (pinkkiu--)
    {
        solve();
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void calc(ll, ll, ll, ll, ll)':
sequence.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     ll m = l + r >> 1;
      |            ~~^~~
sequence.cpp:61:43: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   61 |             best = max(best, {dp[i - 1][j & 1 ^ 1] + get(i, m), i});
      |                                         ~~^~~

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