oj.uz

답안 #45576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45576 2018-04-15T13:34:31 Z Pajaraja 수열 (APIO14_sequence) C++17
0 / 100
 29 ms 4900 KB 
#include <bits/stdc++.h>
using namespace std;
long long dp[100007],dpl[100007],s[100007],a[100007];
int pre[207][100007];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	s[0]=a[0];
	for(int i=1;i<n;i++) s[i]=s[i-1]+a[i];
	for(int i=0;i<n;i++) dpl[i]=2*s[i]*s[i];
	for(int t=2;t<=k+1;t++)
	{
		int p=t-2;
		for(int i=t-1;i<n;i++)
		{
			while(dpl[p]-2*s[i]*s[p]>dpl[p+1]-2*s[i]*s[p+1] && p<i-1) p++;
			dp[i]=dpl[p]-2*s[i]*s[p]+2*s[i]*s[i];
			pre[t][i]=p;
		}
		for(int i=0;i<n;i++) {dpl[i]=dp[i];}
	}
	long long sol=(2*s[n-1]*s[n-1]-dpl[n-1])/2;
	printf("%lld\n",sol);
	int cur=pre[k+1][n-1];
	for(int i=k;i>0;i--)
	{
		printf("%d ",cur+1);
		cur=pre[i][cur];
	}
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:8: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:9:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%lld",&a[i]);
                       ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Correct 2 ms 496 KB contestant found the optimal answer: 999 == 999
3 Correct 2 ms 496 KB contestant found the optimal answer: 0 == 0
4 Correct 2 ms 524 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 2 ms 524 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Incorrect 2 ms 524 KB contestant didn't find the optimal answer: 0 < 1
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 524 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 676 KB contestant didn't find the optimal answer: 484133 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 676 KB contestant didn't find the optimal answer: 395622 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 972 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 4900 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -