Submission #171641

#	Time	Username	Problem	Language	Result	Execution time	Memory
171641		Ruxandra985	Split the sequence (APIO14_sequence)	C++14	100 / 100	1403 ms	81928 KiB

sequence

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
long long dp[2][DIMN] , sp[DIMN] ;
int opt[210][DIMN] , poz[DIMN];
int v[DIMN] , n;
void solve (int p , int st , int dr , int optst , int optdr){
    int mid = (st + dr)/2 , optc , i;
    long long maxi;
    if (st > dr)
        return;
    /// calcul brut pt mid
    //if (st == 1 && dr == 1)
      //  printf ("a");
    //printf ("%d %d\n",st , dr);
    maxi = 0;
    optc = 0;
    for (i = optst ; i <= optdr && i<=mid ; i++){
 
        /// aici o sa faci chestia cu bestcut intre i + 1 si mid
 
        /// dp[p][mid] il faci in fct de dp[1-p][i] + cut la poz mid din sufix
 
        if (maxi < (sp[mid] - sp[i]) * (sp[n] - sp[mid]) + dp[1 - p%2][i]){
            maxi = (sp[mid] - sp[i]) * (sp[n] - sp[mid]) + dp[1 - p%2][i];
            optc = i;
        }
    }
    dp[p%2][mid] = maxi;
    opt[p][mid] = optc;
    solve (p , st , mid-1 , optst , optc);
    solve (p , mid+1 , dr , optc , optdr);
 
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int k , i;
    long long sol;
    fscanf (fin,"%d%d",&n,&k);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d",&v[i]);
        sp[i] = sp[i-1] + v[i];
    }
    /// dp[j][i] = max daca i e pozitia la care s a fcaut a j - a taietura
    /// mai umbli doar la sufix
    for (i=1;i<=k;i++){
        solve (i , i , n , i - 1 , n);
       // if (i == 1)
       // printf ("%lld" , dp[1][1]);
    }
    sol = -1;
    int p = 0;
    for (i=k;i<=n;i++){
        if (sol < dp[k % 2][i]){
            sol = dp[k%2][i];
            p = i;
        }
    }
    fprintf (fout,"%lld\n",sol);
    int elem = 0;
    for (i = k ; i ; i--){
        poz[++elem] = p;
        p = opt[i][p];
    }
    for (i=elem;i;i--)
        fprintf (fout,"%d ",poz[i]);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:43:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~

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