Submission #855271

#	Time	Username	Problem	Language	Result	Execution time	Memory
855271		vjudge1	Split the sequence (APIO14_sequence)	C++17	11 / 100	921 ms	2272 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
const int N = 1e5 + 7, mod = 1e9 + 7;
int a[N];
long long dp[N];
void solve() {
    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
        dp[i] = dp[i - 1] + a[i];
    }
    vector<int> v;
    for(int i = 1; i < n; i++)v.push_back(i);
    vector<int> ans;
    long long maxx = -1;
    for(int i = 1; i <= 1000; i++) {
        random_shuffle(v.begin(), v.end());
        // for(auto to : v) {
        //     cout << to << ' ';
        // }
        // cout << '\n';
        vector<int> vec;
        for(int j = 0; j < k; j++) {
            vec.push_back(v[j]);
        }
        sort(vec.begin(), vec.end());
        int last = 0;
        long long s = 0;
        for(int j = 0; j < k; j++) {
            s = (s + (dp[n] - dp[vec[j]]) * 1ll * (dp[vec[j]] - dp[last]));
            last = vec[j];
        }
        if(maxx < s) {
            maxx = s;
            ans = vec;
        }
    }
    cout << maxx << '\n';
    for(auto to : ans)cout << to << ' ';
}
signed main() {
    // freopen ("sequence.in", "r", stdin);
    // freopen ("sequence.out", "w", stdout);
    ios_base::sync_with_stdio(NULL);    
    cin.tie(NULL);
    int t = 1;
    // cin>>t;
    // int cases = 0;
    while(t -- ) {
        // cases ++;
        // cout << "Case " << cases << ": ";
        solve();
    }    
}
/*

*/

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