Submission #989339

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

sequence

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define namein "inp.inp"
#define nameout "out.out"
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pb push_back
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpll vector<pll>
#define vpii vector<pii>
#define fr(i, j, n) for (ll i = j; i <= n; i++)
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX;
const ll maxn = 1e5 + 5;

void opt(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

void file(){
	if (fopen(namein, "r")){
		freopen(namein, "r", stdin);
		freopen(nameout, "w", stdout);
	}
}

ll n, k;
ll a[maxn];
ll p[maxn];
ll mcost = 0;
vector<vector<ll>> g(1);

void bt(ll j, vector<ll> sv){
    if (j == k && sv.back() != n){
        sv.push_back(n);
        bt(j + 1, sv);
    }
	else if (j == k + 1){
		ll sum[k + 1];
		ll psum[k + 1];
		fill_n(psum, j + 1, 0);
		for (ll i = 1; i < sv.size(); i++){
			//sv[i - 1] + 1 -> sv[i]
			sum[i] = p[sv[i]] - p[sv[i - 1]];
			psum[i] = psum[i - 1] + sum[i];
		}
		ll cost = 0;
		for (ll i = 1; i <= k; i++){
			cost += sum[i]*(psum[k] - psum[i]);
		}
		if (mcost < cost){
		    mcost = cost;
		    g[0] = sv;
		}
	}
	else {
		for (ll i = sv.back() + 1; i <= n; i++){
			sv.push_back(i);
			bt(j + 1, sv);
			sv.pop_back();
		}
	}
}

void ans(){
	cin >> n >> k;
	for (ll i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	bt(1, {0});
	cout << mcost << "\n";
	for (ll i = 1; i < g[0].size(); i++){
	    cout << g[0][i] << " ";
	}
}


int main(){
	opt();
	file();
	ans();
}

Compilation message (stderr)

sequence.cpp: In function 'void bt(long long int, std::vector<long long int>)':
sequence.cpp:49:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (ll i = 1; i < sv.size(); i++){
      |                  ~~^~~~~~~~~~~
sequence.cpp: In function 'void ans()':
sequence.cpp:80:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (ll i = 1; i < g[0].size(); i++){
      |                 ~~^~~~~~~~~~~~~
sequence.cpp: In function 'void file()':
sequence.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   freopen(namein, "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(nameout, "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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