Submission #464848

#	Time	Username	Problem	Language	Result	Execution time	Memory
464848		snoop	Split the sequence (APIO14_sequence)	C++14	0 / 100	140 ms	131072 KiB

sequence

#include<bits/stdc++.h>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip> 
#include <stdio.h>
#include <assert.h>
#include <cstring>
#define f first
#define s second

#define MAXV 200007
#define MAXE 100007
#define f first
#define s second
#define pii pair<int,int>
#define rep(i,n) for(int i = 0 ; i < n ; i++) 
#define drep(i,n) for(int i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(int i = x ; i < n ; i++)
#define lnf 3999999999999999999
#define inf 999999999
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())

#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5,K = 200, mod = 1e9 + 7; // !
int t,n,k,a[N],s[N],ans,bef[N][K + 5],last,L[K + 5];
vector<pair<pii,int> > st[K + 5];
int f(int x,pii y) {
	return y.f * x + y.s;
}
long double x_(pii x1,pii x2) {
	return (x2.s - x1.s) / (x1.f - x2.f);
} 
void add(int j,pii x,int i) {
	while(st[j].size() > 1) {
		pii cur = st[j].back().f;
		pii prev = st[j][(int)st[j].size() - 2].f;
		if(cur.f == x.f) {
			st[j].pop_back();
			continue;
		}
		if(x_(cur,x) >= x_(cur,prev)) st[j].pop_back();
		else break;
	}
	st[j].push_back({x,i});
}
void query(int j,int c,int i) {
	while((int)st[j].size() - L[j] >= 2) {
		
		pii cur = st[j][L[j]].f;
		pii prev = st[j][L[j] + 1].f;
		if(f(c,cur) > f(c,prev)) break;
		L[j]++;
	}
	
	if(L[j] >= st[j].size()) return;
	pii cur_ans;
	cur_ans.s = f(c,st[j][L[j]].f) - c * c;
	cur_ans.f = c;
	bef[i][j] = st[j][L[j]].s;
	add(j + 1,cur_ans,i);
	if(j == k - 1) {
		if(cur_ans.s > ans) {
			ans = cur_ans.s;
			last = i;
		}
	}
}
main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
	}
	for(int i=n;i>=1;i--) {
		s[i] = s[i+1] + a[i];
	}
	st[0].push_back({{s[1],0},1});
	for(int i=2;i<=n;i++){
		for(int j=k - 1;j>=0;j--) {
			query(j,s[i],i);
		}
	}
	cout<<ans<<"\n";
	int cur = k-1;
	vector<int> ans;
	while(cur >= 0) {
		ans.push_back(last-1);
		
		last = bef[last][cur];
		cur--;
	}
	while(ans.size()) {
	cout<<ans.back()<<" ",ans.pop_back();
 }
}

Compilation message (stderr)

sequence.cpp: In function 'void query(long long int, long long int, long long int)':
sequence.cpp:82:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  if(L[j] >= st[j].size()) return;
      |     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main(){
      | ^~~~

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