Submission #895276

#	Time	Username	Problem	Language	Result	Execution time	Memory
895276		AgentPengin	Split the sequence (APIO14_sequence)	C++17	100 / 100	1026 ms	87764 KiB

sequence

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define pb push_back

using namespace std;

const ll mod = 1e9 + 7;
const ll inf = 5e18;
const int MAXN = 1e5 + 5;

int n,k,a[MAXN];
ll pr[MAXN],dp[MAXN];
int trace[MAXN][205];

struct line {
	ll m,b;
	int id;
};

vector<line> vec;

ll val(const ll&x,const line& a) {
	return x * a.m + a.b;
}

bool bad(const line& a,const line& b,const line& c) {
	return (b.b - a.b) * (a.m - c.m) >= (c.b - a.b) * (a.m - b.m);
}

void add(const line& a) {
	while(sz(vec) >= 2 && bad(vec[sz(vec) - 2],vec.back(),a)) {
		vec.pop_back();
	}
	vec.push_back(a);
}

pair<ll,int> get(ll x) {
	if (sz(vec) == 1) return {val(x,vec[0]),vec[0].id};
	int l = 0,r = sz(vec) - 2;
	while(l <= r) {
		int mid = l + r >> 1;
		if (val(x,vec[mid]) <= val(x,vec[mid + 1])) l = mid + 1;
		else r = mid - 1;
	}
	return {val(x,vec[l]),vec[l].id};
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (ifstream(NAME".inp")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
    	cin >> a[i];
    	pr[i] = pr[i - 1] + a[i];
    }
    for (int i = 1;i <= n;i++) dp[i] = -inf;
    dp[0] = 0;
    for (int j = 1;j <= k;j++) {
    	add({0,0,0});
    	for (int i = 1;i <= n;i++) {
    		auto got = get(pr[i]);
    		if (dp[i] != -inf) add({pr[i],dp[i],i});
    		dp[i] = got.fi - pr[i] * pr[i];
    		trace[i][j] = got.se;
    	}
		vec.clear();
    }
    ll pos = 0;
    dp[0] = -1;
    for (int i = k;i <= n;i++) {
    	if (dp[i] + pr[n] * pr[i] > dp[pos] + pr[n] * pr[pos]) {
    		pos = i;
    	}
    }
    cout << dp[pos] + pr[n] * pr[pos] << EL;
    vector<int> ans;
    while(pos) {
    	ans.push_back(pos);
    	pos = trace[pos][k--];
    }
    reverse(bend(ans));
    for (auto x : ans) cout << x << " ";
    
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> get(long long int)':
sequence.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int main()':
sequence.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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