Submission #91869

#	Time	Username	Problem	Language	Result	Execution time	Memory
91869		jufreire	Split the sequence (APIO14_sequence)	C++11	33 / 100	2074 ms	41872 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;
solution  *s;
void tam()
{
  tamanho *= 2;
  s = (solution*) realloc(s,tamanho*sizeof(solution));
}
void copysol(int to, int from)
{
  s[to].lastcut = s[from].lastcut;
  s[to].ncuts = s[from].ncuts;
  s[to].value = s[from].value;
  int i;
  for (i=0;i<s[to].ncuts;i++)
    s[to].cuts[i] = s[from].cuts[i];
}


int main()
{
  int n,i,j,jj,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 = 0;
  tamanho = 200;
  tam();
  
  int nsols=1;
  s[0].lastcut = 0;
  s[0].value = 0;
  s[0].ncuts = 0;
  int ss;

  for (i=0;i<n-1;i++)
  {
    //tentar cortar entre i e i+1
    ss = nsols;
    for (j=0;j<ss;j++)
    {
      if (s[j].ncuts==k) continue; //nao posso mais cortar
      s[nsols].lastcut = i+1;
      s[nsols].ncuts = s[j].ncuts+1;
      s[nsols].value = s[j].value + b[i+1]*(b[s[j].lastcut] - b[i+1]);
      for (jj=0;jj<s[j].ncuts;jj++) s[nsols].cuts[jj] = s[j].cuts[jj];
      s[nsols].cuts[jj] = i+1;
      nsols++; if (nsols==tamanho) tam();
    }
    //aqui seria uma boa hora para descartar solucoes.
    qsort(s, nsols, 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(j,p);
      p++;
      while( p<nsols && s[p].ncuts == s[j].ncuts &&  s[p].value <= s[j].value ) p++;
      j++;
    } while(p<nsols && s[p].ncuts!=k);
    if (p<nsols)
    {
      copysol(j,p);
      j++;
    }
    nsols=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, nsols, sizeof(solution), compar);
  //vai ser a ultima que eh a unica com k cuts
  printf("%lld\n",s[nsols-1].value);
  for (i=0;i<k;i++) printf("%d ",s[nsols-1].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