oj.uz

답안 #31122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31122 2017-08-10T09:31:08 Z tatatan 수열 (APIO14_sequence) C++11
0 / 100
 0 ms 1844 KB 
#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,dp[MAXN][MAXK],sum[MAXN],t,pnt[MAXK],used[MAXN][MAXK];
vector<pair<pii,int> > line[MAXK];

double inter(pii a,pii b) {
	
	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) {
		add(0,mp(sum[i],-sum[i]*sum[i]),i);
		for(int j=1;j<i;++j){
			upd(j-1,sum[i]);
			dp[i][j]=line[j-1][pnt[j-1]].st.st*sum[i]+line[j-1][pnt[j-1]].st.nd;
			used[i][j]=line[j-1][pnt[j-1]].nd;
			add(j,mp(sum[i],-sum[i]*sum[i]+dp[i][j]),i);
		}
	}
	cout<<dp[n][k]<< endl;
	int cur=n;
	for(int i=k;i>=1;--i) {
		cur=used[cur][i];
		cout<<cur<<" ";
	}
	cout<<endl;

}

Compilation message

sequence.cpp: In function 'void upd(int, long long int)':
sequence.cpp:23: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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -