oj.uz

Submission #106450

# Submission time Handle Problem Language Result Execution time Memory
106450 2019-04-18T14:17:33 Z nxteru Split the sequence (APIO14_sequence) C++14
11 / 100
 53 ms 41108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct t{
	ll x,y,q;
};
bool check(t a,t b,t c){
	return D(c.y-b.y)/D(b.x-c.x)<=D(b.y-a.y)/D(a.x-b.x);
}
ll n,m,s[100005],dp[25][100005],b[20][100005],l,r;
t dq[100005];
vector<int>ans;
int main(void){
	scanf("%lld%lld",&n,&m);
	m++;
	for(int i=1;i<=n;i++){
		ll a;
		scanf("%lld",&a);
		s[i]=s[i-1]+a;
	}
	for(int i=0;i<=m;i++)for(int j=0;j<=n;j++)dp[i][j]=INF;
	dp[0][0]=0;
	for(int i=1;i<=m;i++){
		l=0,r=0;
		for(int j=1;j<=n;j++){
			t p=t{-2LL*s[j-1],s[j-1]*s[j-1]+dp[i-1][j-1],j-1};
			while(r-2>=l&&check(dq[r-2],dq[r-1],p))r--;
			dq[r++]=p;
			while(l+1<r&&dq[l].x*s[j]+dq[l].y>=dq[l+1].x*s[j]+dq[l+1].y)l++;
			b[i][j]=dq[l].q;
			dp[i][j]=dq[l].x*s[j]+dq[l].y+s[j]*s[j];
		}
	}
	printf("%lld\n",(s[n]*s[n]-dp[m][n])/2LL);
	int x=n;
	for(int i=m;i>1;i--){
		ans.PB(b[i][x]);
		x=b[i][x];
	}
	for(int i=ans.size()-1;i>=0;i--){
		printf("%d",ans[i]);
		if(i==0)printf("\n");
		else printf(" ");
	}
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a);
   ~~~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB contestant found the optimal answer: 108 == 108
2 Correct 3 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 3 ms 384 KB contestant found the optimal answer: 0 == 0
4 Correct 2 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 2 ms 384 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 2 ms 384 KB contestant found the optimal answer: 1 == 1
7 Correct 2 ms 384 KB contestant found the optimal answer: 1 == 1
8 Correct 3 ms 384 KB contestant found the optimal answer: 1 == 1
9 Correct 2 ms 384 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 2 ms 384 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 2 ms 384 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 2 ms 384 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 3 ms 384 KB contestant found the optimal answer: 140072 == 140072
14 Correct 2 ms 384 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 2 ms 384 KB contestant found the optimal answer: 805 == 805
16 Correct 2 ms 384 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 2 ms 384 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 3 ms 384 KB contestant found the optimal answer: 302460000 == 302460000
3 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 3 ms 384 KB contestant found the optimal answer: 311760000 == 311760000
3 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 3 ms 512 KB contestant found the optimal answer: 140412195 == 140412195
3 Runtime error 6 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 4 ms 1408 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Runtime error 11 ms 4736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10488 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 26 ms 10468 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Runtime error 53 ms 41108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -