Submission #87944

#	Time	Username	Problem	Language	Result	Execution time	Memory
87944		Mercenary	Split the sequence (APIO14_sequence)	C++11	0 / 100	118 ms	132096 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{
    ll x , y;
    TVector operator - (const TVector & other)
    {
        return {other.x - x , other.y - y};
    }
    ll Div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
    bool operator % (const TVector & other)
    {
        if(other.x == 0 || other.y == 0)return x * other.y <= other.x * y;
        return (ld)x / other.x <= (ld)y / other.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 , b[maxn] , c[maxn] , trace[maxn][201];
ll sum[maxn] , dp[maxn][201];
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 >> c[i];
        sum[i] = sum[i - 1] + c[i];
    }
    for(int i = 1 ; i <= k ; ++i)
    {
        m = 0;
        int p = 1;
        for(int j = 1 ; j <= n ; ++j)
        {
            add({sum[j - 1] , dp[j - 1][i - 1]} , j - 1);
            p = min(p , m);
            while(p < m && ans(a[p] , sum[j] - sum[n]) < ans(a[p + 1] , sum[j] - sum[n]))
                ++p;
            dp[j][i] = ans(a[p] , sum[j] - sum[n]) + sum[n] * sum[j] - sum[j] * sum[j];
            trace[j][i] = b[p];
        }
    }
    int best = 1;
    for(int i = 1 ; i <= n ; ++i)
        if(dp[i][k] > dp[best][k])best = i;
    cout << dp[best][k] << '\n';
    for(int i = k ; i >= 1 ; --i)
    {
        cout << best << ' ';
        best = trace[best][i];
    }
}

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:85: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:85:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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