Submission #88068

#	Time	Username	Problem	Language	Result	Execution time	Memory
88068		Mercenary	Split the sequence (APIO14_sequence)	C++11	71 / 100	2045 ms	83216 KiB

sequence

#include<bits/stdc++.h>
#define pb push_back
#define brokenheart "TEST"
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 5;

struct TVector{
    int x;
    ll y;
    TVector operator - (const TVector & other)
    {
        return {other.x - x , other.y - y};
    }
    bool operator % (const TVector & other)
    {
        return (ld)x * other.y <= (ld)other.x * y;
    }
    ll operator * (const ll & other)
    {
        return x * other + y;
    }
    bool operator < (const TVector & other)
    {
        if(x != other.x)return x < other.x;
        return y < other.y;
    }
};
int n , m , k , trace[maxn][201] , b[maxn] , sum[maxn];
ll dp[maxn][2];
TVector a[maxn];

void add(TVector now , int j)
{
    while(m >= 2 && (a[m] - a[m - 1]) % (a[m] - now))--m;
    a[++m] = now;
    b[m] = j;
}

ll ans(TVector now , ll k)
{
    return now.x * k + now.y;
}

void enter()
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    bool bit = 0;
    for(int i = 1 ; i <= k ; ++i)
    {
        bit ^= 1;
        m = 0;
        int p = 1;
        for(int j = i + 1 ; j <= n ; ++j)
        {
            add({sum[j - 1] , dp[j - 1][bit ^ 1] - (ll)sum[j - 1] * sum[j - 1]} , j - 1);
            p = min(p , m);
            while(p < m && ans(a[p] , sum[j]) < ans(a[p + 1] , sum[j]))
                ++p;
            dp[j][bit] = ans(a[p] , sum[j]);
            trace[j][i] = b[p];
        }
    }

    cout << dp[n][bit] << '\n';
    int best = n;
    for(int i = k ; i >= 1 ; --i)
    {
        assert(best);
        best = trace[best][i];
        cout << best << " ";
    }
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    if(fopen(brokenheart".INP","r"))
        freopen(brokenheart".INP","r",stdin) ,
        freopen(brokenheart".OUT","w",stdout);
    enter();
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:86:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(brokenheart".INP","r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(brokenheart".OUT","w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
sequence.cpp:86:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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