oj.uz

Submission #31123

# Submission time Handle Problem Language Result Execution time Memory
31123 2017-08-10T09:38:24 Z tatatan Split the sequence (APIO14_sequence) C++11
0 / 100
 33 ms 95360 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,sum[MAXN],t,pnt[MAXK];
int 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<min((LL)i,k+1);++j){
			upd(j-1,sum[i]);
			t=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]+t),i);
		}
	}
	cout<<t<< 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:24: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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 81484 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 81484 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 81484 KB Integer 2 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 81484 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 81484 KB contestant didn't find the optimal answer: 484133 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 81620 KB contestant didn't find the optimal answer: 395622 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 83264 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 95360 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -