Submission #91888

#	Time	Username	Problem	Language	Result	Execution time	Memory
91888		jufreire	Split the sequence (APIO14_sequence)	C++11	33 / 100	2045 ms	58716 KiB

sequence

#include <stdio.h>
#include <stdlib.h>

typedef struct solution
{
  int lastcut;
  int ncuts;
  int cuts[200];
  long long value;
} solution;

int k;

int compar(const void* p1, const void* p2)
{
  solution * m1 = (solution *)p1;
  solution * m2 = (solution *)p2;
  int c = m1->ncuts - m2->ncuts;
  int p = m1-> lastcut - m2->lastcut;
  long long v = m2->value - m1->value;
  if (c==0) 
  {
    if (p==0 || m1->ncuts==k)
    {
      if (v>0) return 1;
      if (v<0) return -1;
      return 0;
    }
    return p;
  }
  return c;
}

int tamanho[201];
solution  **s;
void tam(int vv)
{
  tamanho[vv] *= 2;
  s[vv] = (solution*) realloc(s[vv],tamanho[vv]*sizeof(solution));
}
void copysol(int vv, int to, int from)
{
  s[vv][to].lastcut = s[vv][from].lastcut;
  s[vv][to].ncuts = s[vv][from].ncuts;
  s[vv][to].value = s[vv][from].value;
  int i;
  for (i=0;i<s[vv][to].ncuts;i++)
    s[vv][to].cuts[i] = s[vv][from].cuts[i];
}


int main()
{
  int n,i,j,jj,jjj,p;
  long long * a;
  long long * b;
  scanf("%d", &n);
  scanf("%d", &k);
  a = (long long *) malloc(n*sizeof (long long));
  for (i=0;i<n;i++) scanf("%lld",&a[i]);
  b = (long long *) malloc(n * sizeof(long long));
  b[n-1]=a[n-1];
  for (i=n-2;i>=0;i--) b[i] = b[i+1]+a[i]; 
  //b[i] guarda a soma de i ate o fim
  
  s = (solution**) malloc ((k+1)*sizeof(solution*));
  for (i=0;i<=k;i++)
  {
    s[i] = 0;
    tamanho[i] = 200;
    tam(i);
  }

  
  int nsols[201];
  nsols[0]=1;
  for(i=1;i<=k;i++) nsols[i]=0;

  s[0][0].lastcut = 0;
  s[0][0].value = 0;
  s[0][0].ncuts = 0;
  int ss;

  for (i=0;i<n-1;i++)
  {
    //tentar cortar entre i e i+1
    for (jjj=k-1;jjj>=0;jjj--) //tamanho do ncuts anterior
    {
      ss = nsols[jjj];
      if (ss==0) continue; 
      for (j=0;j<ss;j++)
      {
        //if (s[j].ncuts==k) continue; //nao posso mais cortar
        s[jjj + 1][nsols[jjj + 1]].lastcut = i+1;
        s[jjj + 1][nsols[jjj + 1]].ncuts = s[jjj][j].ncuts+1;
        s[jjj + 1][nsols[jjj + 1]].value = s[jjj][j].value + b[i+1]*(b[s[jjj][j].lastcut] - b[i+1]);
        for (jj=0;jj<s[jjj][j].ncuts;jj++) s[jjj+1][nsols[jjj+1]].cuts[jj] = s[jjj][j].cuts[jj];
        s[jjj + 1][nsols[jjj + 1]].cuts[jj] = i+1;
        nsols[jjj + 1]++; if (nsols[jjj + 1]==tamanho[jjj + 1]) tam(jjj + 1);
      }
      //aqui seria uma boa hora para descartar solucoes.
      qsort(s[jjj+1], nsols[jjj+1], sizeof(solution), compar);

      /*
      for (j = 0; j<nsols; j++)
      {
        printf("sol %d: %d %d %lld\n", j, s[j].ncuts, s[j].lastcut, s[j].value);
      }
      printf("\n");
      */

      j=0;
      p=0;
      do
      {
        copysol(jjj+1,j,p);
        p++;
        //while( p<nsols && s[p].ncuts == s[j].ncuts &&  s[p].value <= s[j].value ) p++;
        while (p<nsols[jjj+1] && s[jjj+1][p].value <= s[jjj+1][j].value) p++;
        j++;
      } while(p<nsols[jjj+1]); // && s[p].ncuts!=k);
      /*
      if (p<nsols)
      {
        copysol(j,p);
        j++;
      }
      */ //essa parte nao precisa mais porque cada um eh seu vetor e k foi tratado igual
      nsols[jjj+1]=j;
    }
  }
  //nao guardei dados o suficiente pra imprimir a repsosta, 
  //mas vamos ver se pelo menos o valor total sai certo.
  
  /*
  for(j=0;j<nsols;j++)
  {
    printf("sol %d: %d %d %lld - %d %d %d\n",j,s[j].ncuts,s[j].lastcut,s[j].value,
      s[j].cuts[0], s[j].cuts[1], s[j].cuts[2]);
  }*/
  
  //procurar a atual maior valor solucao e imprimir
  qsort(s[k], nsols[k], sizeof(solution), compar);
  //vai ser a ultima que eh a unica com k cuts
  //printf("%lld\n",s[nsols-1].value);
  printf("%lld\n", s[k][0].value);
  for (i=0;i<k;i++) printf("%d ",s[k][0].cuts[i]);
  printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
sequence.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
sequence.cpp:60:26: 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",&a[i]);
                     ~~~~~^~~~~~~~~~~~~~

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