Submission #557951

#	Time	Username	Problem	Language	Result	Execution time	Memory
557951		n0sk1ll	Split the sequence (APIO14_sequence)	C++14	11 / 100	2092 ms	78772 KiB

sequence

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;

/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/







//Note to self: Check for overflow

int a[100005];
li dp[100005][202];
int gde[100005][202];
int pre[100005];

li cost(int l, int r)
{
    return pre[l-1]*(pre[r]-pre[l-1]);
}

void rekurz(int n, int k)
{
    if (k==0) return;
    rekurz(gde[n][k],k-1),cout<<gde[n][k]<<" ";
}

int main()
{
    FAST;

    int n,k; cin>>n>>k;
    fff(i,1,n) cin>>a[i];

    if (k==n-1)
    {
        li ans=0;
        fff(i,1,n) ff(j,1,i) ans+=a[i]*a[j];
        cout<<ans<<"\n";
        ff(i,1,n) cout<<i<<" ";
        return 0;
    }

    fff(i,1,n) pre[i]=pre[i-1]+a[i];
    fff(j,1,k)
    {
        fff(i,2,n) ff(g,1,i)
        {
            li sta=dp[g][j-1]+cost(g+1,i);
            if (sta>dp[i][j]) dp[i][j]=sta,gde[i][j]=g;
        }
    }

    /*fff(j,0,k)
    {
        cout<<j<<": "<<endl;
        fff(i,1,n) cout<<dp[i][j]<<" "; cout<<endl;
        fff(i,1,n) cout<<gde[i][j]<<" "; cout<<endl<<endl;
    }*/

    cout<<dp[n][k]<<"\n";
    rekurz(n,k);
}

//Note to self: Check for overflow

/*

7 3
4 1 3 4 0 2 3

7 6
4 1 3 4 0 2 3

*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:68:5: note: in expansion of macro 'fff'
   68 |     fff(i,1,n) cin>>a[i];
      |     ^~~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:73:9: note: in expansion of macro 'fff'
   73 |         fff(i,1,n) ff(j,1,i) ans+=a[i]*a[j];
      |         ^~~
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:73:20: note: in expansion of macro 'ff'
   73 |         fff(i,1,n) ff(j,1,i) ans+=a[i]*a[j];
      |                    ^~
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:75:9: note: in expansion of macro 'ff'
   75 |         ff(i,1,n) cout<<i<<" ";
      |         ^~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:79:5: note: in expansion of macro 'fff'
   79 |     fff(i,1,n) pre[i]=pre[i-1]+a[i];
      |     ^~~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:80:5: note: in expansion of macro 'fff'
   80 |     fff(j,1,k)
      |     ^~~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:82:9: note: in expansion of macro 'fff'
   82 |         fff(i,2,n) ff(g,1,i)
      |         ^~~
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'g' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:82:20: note: in expansion of macro 'ff'
   82 |         fff(i,2,n) ff(g,1,i)
      |                    ^~

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