oj.uz

답안 #254547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254547 2020-07-30T08:43:36 Z babo 수열 (APIO14_sequence) C++14
0 / 100
 11 ms 2844 KB 
#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,k;
L a[1000010],nu[1000010];
L cut[1000010];

bool ok(L now){
	return cut[now]+1!=cut[now+1]&&
	(nu[cut[now]]-nu[cut[now-1]])*(nu[cut[now+1]]-nu[cut[now]])
	<(nu[cut[now]+1]-nu[cut[now-1]])*(nu[cut[now+1]]-nu[cut[now]+1]);
}

void dfs(L now){
	if(now==k) return;
	dfs(now+1);
	while(ok(now))
	{
		cut[now]++;
		dfs(now+1);
	}
}

int main()
{
	scanf("%lld %lld",&n,&k);
	k++;
	L i;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		nu[i]=a[i]+nu[i-1];
		cut[i]=i;
	}
	cut[k]=n;
	dfs(1);
	L ans=nu[n]*nu[n];
	for(i=1;i<=k;i++)
		ans-=(nu[cut[i]]-nu[cut[i-1]])*(nu[cut[i]]-nu[cut[i-1]]);
	ans/=2;
	printf("%lld\n",ans);
	for(i=1;i<k;i++)
		printf("%lld ",cut[i]);
}

Compilation message

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

Subtask #1
0 / 11.0

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

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 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 0 ms 384 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 0 ms 384 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 2 ms 640 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 11 ms 2844 KB contestant didn't find the optimal answer: 5054344 < 19795776960
2 Halted 0 ms 0 KB -