제출 #92189

#제출 시각아이디문제언어결과실행 시간메모리
92189jufreire수열 (APIO14_sequence)C++11
71 / 100
1938 ms132096 KiB
#include <stdio.h> #include <stdlib.h> long long xf; class solution { public: int lastcut; //"this" cut int ncuts; //int cuts[200]; int prevcut; long long b; //valor anterior long long a; //soma do inicio ate o lastcut // long long preva; //soma do zero ate o lastcut anterior // long long melhor; //a partir de onde esta eh a melhor long long valueat(long long x) //valor no final se este fosse o ultimo corte { if (x < a) return -1; return a * (x - a) + b; } long long acima(solution nova) // retorna A PARTIR DE ONDE a nova esta acima desta. Pode ser xf se nunca. { long long x0 = a; if (nova.a > x0) x0 = nova.a; //nao adianta comparar antes de comecar long long x1 = xf; long long m; if (valueat(xf)>nova.valueat(xf)) return xf+1; if (valueat(x0)<nova.valueat(x0)) return x0; //solucao nova ja surge acima da antiga. o que retornar? do { m = (x0 + x1)/2; if (valueat(m) > nova.valueat(m)) x0=m; else x1=m; } while(x1>x0+1); return x1; } }; int k; /* int compar(const void* p1, const void* p2) //dessa vez vou querer em ordem da menos para mais inclinada { solution * m1 = (solution *)p1; solution * m2 = (solution *)p2; long long a = m1->a - m2->a; if (a>0) return 1; if (a<0) return -1; return 0; } */ 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].a = s[vv][from].a; s[vv][to].b = s[vv][from].b; // s[vv][to].preva = s[vv][from].preva; //s[vv][to].melhor = s[vv][from].melhor; // int i; // for (i=0;i<s[vv][to].ncuts;i++) // s[vv][to].cuts[i] = s[vv][from].cuts[i]; s[vv][to].prevcut = s[vv][from].prevcut; } int main() { int n,i; long long * a; long long * b; // freopen("33","r",stdin); 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 xf = b[0]; s = (solution**) malloc ((k+1)*sizeof(solution*)); for (i=0;i<=k;i++) { s[i] = 0; tamanho[i] = 100; 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].ncuts = 0; s[0][0].a = 0; s[0][0].b = 0; s[0][0].prevcut = -1; int ki,si,ss,ci; long long x,t1,t2; for (ki=1;ki<=k;ki++) //fazer o proximo corte { // printf("debug k=%d\n",ki); si = 0; //primeira solucao anterior ss = nsols[ki - 1]; //quantidade delas for (ci=ki;ci<n;ci++) //tem que ter espaco no inicio para pelo menos ki-1 cortes { x = b[0] - b[ci]; //ponto onde tenho que analisar as solucoes anteriores while (si<ss-1 && s[ki-1][si+1].lastcut < ci && s[ki-1][si].valueat(x) <= s[ki-1][si+1].valueat(x)) si++; //se tudo der certo bastava um if, mas por via das duvidas s[ki][nsols[ki]].lastcut = ci; s[ki][nsols[ki]].ncuts = ki; s[ki][nsols[ki]].a = x; s[ki][nsols[ki]].b = s[ki-1][si].valueat(x); //for (i=0;i<ki-1;i++) s[ki][nsols[ki]].cuts[i] = s[ki - 1][si].cuts[i]; //s[ki][nsols[ki]].cuts[i] = ci; s[ki][nsols[ki]].prevcut = si; //na verdade nao eh o cut, eh a solucao que tem o cut, pra ler recursivamente. //esta eh a nova solucao proposta. agora tenho que decidir se ela sera incluida ou nao. // printf("debug: %lld x + %lld - ", s[ki][nsols[ki]].a, s[ki][nsols[ki]].b); /* for (i=0;i<nsols[ki];i++) { if (s[ki][i].acima(s[ki][nsols[ki]]) > xf) //if (nsols[ki] >=1 && s[ki][nsols[ki]-1].acima(s[ki][nsols[ki]]) > xf) { // printf("rejected\n"); break; //nunca ficara acima, nao incluo //i = nsols[ki] - 1; } } */ //if (i==nsols[ki]) //nao deu break. esta acima de alguem. if (nsols[ki] == 0 || s[ki][nsols[ki] - 1].acima(s[ki][nsols[ki]]) <= xf) //ta errado { // printf("accepted\n"); nsols[ki]++; if (nsols[ki]==tamanho[ki]) tam(ki); //foi inserida na ordem certa de coeficiente angular, nem preciso ordenar. //so preciso ver se tem alguem antes dela que foi toda coberta. //e elas nao estao espalhadas. se alguem foi coberto, foram as ultimas. i = nsols[ki]-1; do { if (i<2) break; t1 = s[ki][i - 1].acima(s[ki][i]); //i passa de i-1 t2 = s[ki][i - 2].acima(s[ki][i - 1]); //i-1 passa de i-2 if (t1>t2) break; //porque esse eh o certo, cruzar em ordem. // printf(" removing old solution %lld %lld\n", s[ki][i - 1].a, s[ki][i - 1].b); copysol(ki, i - 1, i); i--; nsols[ki]--; } while(1); } else { // printf("rejected\n"); } } } //a que ganha eh a mais inclinada com k cortes no valor de xf printf("%lld\n", s[k][nsols[k]-1].valueat(xf)); //for (i=0;i<k;i++) printf("%d ",s[k][nsols[k] - 1].cuts[i]); int pr[201]; int p = nsols[k]-1; for (i=k;i>=1;i--) { pr[i] = s[i][p].lastcut; p = s[i][p].prevcut; } for (i=1;i<=k;i++) printf("%d ",pr[i]); printf("\n"); }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
sequence.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
sequence.cpp:87: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]);
                     ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...