Submission #995000

#	Time	Username	Problem	Language	Result	Execution time	Memory
995000		Baytoro	Split the sequence (APIO14_sequence)	C++17	100 / 100	706 ms	88668 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
//#define int long long 
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
#define ll long long
const int N=2e5+5;
int n;
struct line{
    ll m, b;
    ll operator *(int x){
        return m*x+b;
    }
    int operator ^(line x){
        return ceil((b-x.b)/(x.m-m));
    }
};
struct CHT{
	 deque<ll> a, b;
    deque<int> c;
 
    void init() {
        a.clear();
        b.clear();
        c.clear();
    }
 
    void push(ll n, ll m, int v) {
        while (a.size() > 1 &&
               (b[b.size() - 2] - b.back()) * (n - a.back()) >= (b.back() - m) * (a.back() - a[a.size() - 2])) {
            a.pop_back();
            b.pop_back();
            c.pop_back();
        }
        a.push_back(n);
        b.push_back(m);
        c.push_back(v);
    }
 
    pair<ll, int> query(ll x) {
        while (a.size() > 1 && (a[1] - a[0]) * x > (b[0] - b[1])) {
            a.pop_front();
            b.pop_front();
            c.pop_front();
        }
        return make_pair(a[0] * x + b[0], c[0]);
    }
};
vector<ll> dp_cur(N),dp_prev(N);
int p[N][205];
void solve(){
	int n,k;cin>>n>>k;
	vector<ll> a(n+1),pref(n+1);
	for(int i=0;i<n;i++){
		cin>>a[i];
		pref[i+1]=a[i]+pref[i];
	}
	for(int i=0;i<n-1;i++){
		dp_prev[i]=pref[i+1]*(pref[n]-pref[i+1]);
		p[i][1]=-1;
	}
	for(int j=2;j<=k;j++){
		CHT cht;
		dp_cur[0]=0;
		for(int i=1;i<n-1;i++){
			cht.push(pref[i],dp_prev[i-1],i);
			auto it=cht.query(pref[i+1]-pref[n]);
			dp_cur[i]=it.fr+pref[i+1]*pref[n]-pref[i+1]*pref[i+1];
			p[i][j]=it.sc-1;
		}
		dp_prev=dp_cur;
	}
	ll ans=0,c=0;
	for(int i=0;i<n-1;i++){
		if(ans<dp_prev[i]){
			ans=dp_prev[i];
			c=i;
		}
	}
	cout<<ans<<endl;
	for(int i=0;i<k;i++){
		cout<<c+1<<' ';
		c=p[c][k-i];
	}
}
signed main(){
	//fopn("paint");
	int t=1;//cin>>t;
	while(t--) solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void fopn(std::string)':
sequence.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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