Submission #87965

#	Time	Username	Problem	Language	Result	Execution time	Memory
87965		Mercenary	Split the sequence (APIO14_sequence)	C++11	0 / 100	2060 ms	91752 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;
}

char ch;
inline void fastio(int & x)
{
    x = 0;
    for(ch = getchar() ; ch < '0' || ch > '9' ; ch = getchar());
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())
        x = x * 10 + ch - '0';
}

void enter()
{
    fastio(n);fastio(k);
    for(int i = 1 ; i <= n ; ++i)
    {
        fastio(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 = 1 ; j <= n ; ++j)
        {
            if(j != 1)add({sum[j - 1] , dp[j - 1][bit ^ 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][bit] = ans(a[p] , sum[j] - sum[n]) + (ll)sum[n] * sum[j] - (ll)sum[j] * sum[j];
            trace[j][i] = b[p];
        }
    }
    int best = 1;
    for(int i = 1 ; i <= n ; ++i)
        if(dp[i][bit] > dp[best][bit])best = i;
    cout << dp[best][bit] << '\n';
    for(int i = k ; i >= 1 ; --i)
    {
        assert(best > 0);
        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:96: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:96: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