Submission #248350

#	Time	Username	Problem	Language	Result	Execution time	Memory
248350		Gurban	Split the sequence (APIO14_sequence)	C++17	0 / 100	58 ms	1656 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define pii pair<int,int>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll mod = 1e9+7; //998244353;
ll modpow(ll a, ll e) {
	if (e == 0) return 1;
	ll x = modpow(a * a % mod, e >> 1);
	return e & 1 ? x * a % mod : x;
}

int n,k,p[N],a[N],pos,g;
ll ans,mx,sum,jog;

int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	p[n] = 1;
	for(int i = 1;i <= k;i++){
		pos = 1,mx = 0;
		for(int j = 1;j <= n;j++){
			sum += a[j];
			if(p[j] == 1){
				jog = 0;
				for(int l = pos;l <= j;l++){
					jog += a[l];
					if(mx < jog*(sum-jog)){
						mx = (sum-jog)*jog;
						g = l;
					}
				}
				pos = j + 1,sum = 0;
			}
		}
		p[g] = 1,ans += mx;
	}
	printf("%lld\n",ans);
	for(int i = 1;i < n;i++){
		if(p[i]) printf("%d ",i);
	}
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

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

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29