제출 #56934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56934		Plurm	Split the sequence (APIO14_sequence)	C++11	0 / 100	153 ms	105568 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
int a[100005];
long long dp[100005][2]; // End with i, having j parts;
int qs[100005];
int par[100005][256];
vector<pair<long long,long long> > lines;
vector<int> idx;
inline long long M(int x){
	return lines[x].first;
}
inline long long C(int x){
	return lines[x].second;
}
inline bool bad(int x, int y, int z){
	return (C(y)-C(x))*(M(x)-M(z)) > (C(z)-C(x))*(M(x)-M(y));
}
void add(int i,long long m, long long c){
	lines.emplace_back(m,c);
	idx.push_back(i);
	while(lines.size() >= 3 && bad(lines.size()-3, lines.size()-2, lines.size()-1)){
		lines.pop_back();
		lines.pop_back();
		lines.emplace_back(m,c);
		idx.pop_back();
		idx.pop_back();
		idx.push_back(i);
	}
}
int ptr;
pair<int,long long> query(long long x){
	if(ptr >= lines.size()) ptr = lines.size()-1;
	while(ptr < lines.size()-1 && M(ptr+1)*x + C(ptr+1) > M(ptr)*x + C(ptr)) ptr++;
	return make_pair(idx[ptr],M(ptr)*x + C(ptr));
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	k++;
	add(0,0,0);
	for(int i = 1; i <= n; i++){
		scanf("%d",a+i);
		qs[i] = qs[i-1] + a[i];
		dp[i][0] = -1e10;
	}
	for(int j = 1; j <= k; j++){
		for(int i = 1; i <= n; i++){
			if(!lines.empty())
				tie(par[i][j],dp[i][j % 2]) = query(qs[i]);
			else
				tie(par[i][j],dp[i][j % 2]) = make_pair(-1,-1e10);
			add(i,(long long)qs[i], dp[i][(j+1) % 2] - (long long)qs[i]*(long long)qs[i]);
		}
		lines.clear();
		idx.clear();
		ptr = 0;
	}
	printf("%lld\n",dp[n][k % 2]);
	int x = n;
	stack<int> stk;
	for(int j = k; j > 1; j--){
		x = par[x][j];
		stk.push(x);
	}
	while(!stk.empty()){
		printf("%d ",stk.top());
		stk.pop();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'std::pair<int, long long int> query(long long int)':
sequence.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ptr >= lines.size()) ptr = lines.size()-1;
     ~~~~^~~~~~~~~~~~~~~
sequence.cpp:33:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr < lines.size()-1 && M(ptr+1)*x + C(ptr+1) > M(ptr)*x + C(ptr)) ptr++;
        ~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+i);
   ~~~~~^~~~~~~~~~

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