Submission #855309

#	Time	Username	Problem	Language	Result	Execution time	Memory
855309		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	4 ms	5208 KiB

sequence

#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define Youarestupid ios_base::sync_with_stdio(0);cin.tie(0);
#define all(x) x.begin() , x.end()
#define	pofik continue
#define int long long
#define pb push_back
#define ins insert
#define sz size()
#define F first
#define S second
const int N = 100 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-11;
using namespace std;
int T = 1 , sum;
int binpow(int a , int b){
    if (!b) return 1;
    if (b % 2){
        return (a * binpow(a , b - 1)) % MOD;
    }
    else{
        int val = binpow(a , b / 2);
        return (val * val) % MOD;
    }
}

int pref[N];

void solve(){
	int n , k;
	cin >> n >> k;
	int a[n + 5];
	int l[n + 5] , r[n + 5];
	int ans = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		l[i] = 1;
		r[i] = n;
		pref[i] = pref[i - 1] + a[i];
	}
	vector < int > v;
	for(int ti = 1; ti <= k; ti++){
		int mx = -inf;
		int ind = 0;
		for(int i = 1; i <= n; i++){
			int x = pref[i] - pref[l[i] - 1] , y = pref[r[i]] - pref[i];
// 			cout << x << ' ' << y << ' ' << i << ' ' << ti << '\n' << '\n';
			if(mx < x * y){
				ind = i;
				mx = x * y;
			}
		}
		ans += mx;
		int x = r[ind];
		for(int i = l[ind]; i <= ind; i++){
			r[i] = ind;
		}
		for(int i = ind + 1; i <= x; i++){
			l[i] = ind + 1;
		}
		v.pb(ind);
	}
	cout << ans << '\n';
	for(int it : v){
		cout << it << ' ';
	}
}

signed main(){
    Youarestupid
//	cin >> T;
    while(T--){
    	solve();
    }
}
/*
  ___      __                      _
 |   \    | |          _____      | |  _
 | |\ \   | |  __  __ |  __ \     | | (_)
 | | \ \  | | | |  | || |  \_\__ _| |  _
 | |  \ \ | | | |  | || |    / _` | | | |
 | |   \ \| | | |__| || |   / (_| | | | |
 |_|    \___| |______||_|    \_,__|_| |_|

*/

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