#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- LLI pre[100001]; LLI dp[201][100001]; int parent[201][100001]; int main() { int i; int n,k; scanf("%d %d",&n,&k); for (i = 0; i < n; i++) scanf("%lld",&pre[i+1]),pre[i+1] += pre[i]; int j,l; for (i = 0; i <= n; i++) dp[0][i] = pre[i]*pre[i]; for (i = 1; i <= k; i++) { for (j = 0; j < n; j++) { dp[i][j+1] = pre[j+1]*pre[j+1]; parent[i][j+1] = 0; for (l = j; l >= 0; l--) { if (((pre[j+1]-pre[l])*(pre[j+1]-pre[l])+dp[i-1][l]) < dp[i][j+1]) { dp[i][j+1] = (pre[j+1]-pre[l])*(pre[j+1]-pre[l])+dp[i-1][l]; parent[i][j+1] = l; } } } } printf("%lld\n",(pre[n]*pre[n]-dp[k][n])/2); int u = n; for (i = k; i >= 1; i--) printf("%d ",parent[i][u]),u = parent[i][u]; printf("\n"); return 0; }

sequence.cpp: In function 'int main()':
sequence.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:65:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%lld",&pre[i+1]),pre[i+1] += pre[i];
                             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~