제출 #31124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31124		tatatan	수열 (APIO14_sequence)	C++11	50 / 100	109 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<LL,LL>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=100005,MAXK=201;
LL n,k,sum[MAXN],t,pnt[MAXK],val[MAXK];
int used[MAXN][MAXK];
vector<pair<pii,int> > line[MAXK];

double inter(pii a,pii b) {
	
	if(a.st==b.st)
		return -1e9;
	return 1.0*(b.nd-a.nd)/(a.st-b.st);

}

void upd(int x,LL val) {

	while(pnt[x]+1<line[x].size()&&inter(line[x][pnt[x]].st,line[x][pnt[x]+1].st)<=1.0*val)
		++pnt[x];

}

void add(int x,pii ll,int y) {

	while(line[x].size()>=2&&inter(line[x].back().st,line[x][line[x].size()-2].st)>=inter(ll,line[x].back().st)) 
		line[x].pop_back();
	line[x].pb(mp(ll,y));
	pnt[x]=min(pnt[x],(LL)line[x].size()-1);

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;++i) {
		cin>>t;
		sum[i]=sum[i-1]+t;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<min((LL)i,k+1);++j){
			upd(j-1,sum[i]);
			val[j]=line[j-1][pnt[j-1]].st.st*sum[i]+line[j-1][pnt[j-1]].st.nd;
			//cout<<i<<" "<<j<<" "<<val[j]<<" "<<line[j-1][pnt[j-1]].nd<<" "<<sum[i]<<" "<<-sum[i]*sum[i]+val[j]<<endl;
			used[i][j]=line[j-1][pnt[j-1]].nd;
		}
		for(int j=1;j<min((LL)i,k+1);++j)
			add(j,mp(sum[i],-sum[i]*sum[i]+val[j]),i);
		add(0,mp(sum[i],-sum[i]*sum[i]),i);
	}
	cout<<val[k]<< endl;
	int cur=n;
	for(int i=k;i>=1;--i) {
		cur=used[cur][i];
		cout<<cur<<" ";
	}
	cout<<endl;

}

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

sequence.cpp: In function 'void upd(int, long long int)':
sequence.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pnt[x]+1<line[x].size()&&inter(line[x][pnt[x]].st,line[x][pnt[x]+1].st)<=1.0*val)
                ^

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