Submission #1076411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076411		cpdreamer	Split the sequence (APIO14_sequence)	C++17	50 / 100	2060 ms	24152 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
#define V vector
#define S second
#define F first
#define P pair
#define pb push_back
#define all(v) v.begin(),v.end()
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;
static int called = 0;const long long MOD = 1e9+7; // 1e9 + 7

void file(){
    freopen("input.txt.txt","r",stdin);
    freopen("output.txt.txt","w",stdout);
}
ll sum(int n){
    ll a=n;
    ll b=n+1;
    ll c=a*b;
    c=c/2;
    return c;
}
P<int,int>mex(V<int>a){
    int cnt=0;
    sort(all(a));
    P<int,int>ans;
    for(int i=0;i<a.size();i++){
        if(a[i]>cnt)
            break;
        if(a[i]==cnt)
            cnt++;
    }
    ans.F=cnt;
    cnt=0;
    a.pb(ans.F);
    sort(all(a));
    for(int i=0;i<a.size();i++){
        if(a[i]>cnt)
            break;
        if(a[i]==cnt)
            cnt++;
    }
    ans.S=cnt;
    return ans;
}
void solve() {
    int n;
    cin>>n;
    int k;
    cin>>k;
    int A[n];
    for(int i=0;i<n;i++)
        cin>>A[i];
    ll dp[n][k+1];
    ll pref[n];
    pref[0]=A[0];
    for(int i=1;i<n;i++){
        pref[i]=pref[i-1]+A[i];
    }
    int best_ind[n][k+1];
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    ll sum=A[0];
    for(int i=1;i<n;i++){
        sum+=A[i];
        for(int a=0;a<=k;a++){
            if(a==0){
                dp[i][0]=0;
                continue;
            }
            ll cur_sum=A[i];
            for(int j=i-1;j>=0;j--){
                if(dp[j][a-1]!=-1){
                    if(dp[j][a-1]+cur_sum*pref[j]>dp[i][a]) {
                        dp[i][a] = max(dp[i][a], dp[j][a - 1] + cur_sum * pref[j]);
                        best_ind[i][a]=j;
                    }
                }
                cur_sum+=A[j];
            }
        }
    }
    cout<<dp[n-1][k]<<endl;
    int curr=n-1;
    V<int>ans;
    for(int j=k;j>0;j--){
        curr=best_ind[curr][j];
       ans.pb(curr+1);
    }
    reverse(all(ans));
    for(auto u:ans)
        cout<<u<<" ";
    cout<<endl;

}
int main(){
    //file();
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<int, int> mex(std::vector<int>)':
sequence.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
sequence.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
sequence.cpp: In function 'void file()':
sequence.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("input.txt.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("output.txt.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:15:12: warning: 'called' defined but not used [-Wunused-variable]
   15 | static int called = 0;const long long MOD = 1e9+7; // 1e9 + 7
      |            ^~~~~~

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