제출 #87971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87971		Mercenary	Split the sequence (APIO14_sequence)	C++11	11 / 100	2103 ms	83320 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)
        {
            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();
}

컴파일 시 표준 에러 (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: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29