17216
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
#include <stdio.h>
int how_big(int *D, int index, int value);
int main(void) {
int N;
int A[1000];
int D[1000];
int sum=0;
int index=0;
int check;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d", &A[i]);
}
/* test input
printf("input N=%d, input: ", N);
for(int i=0; i<N; i++){
printf("%d ", A[i]);
}
printf("\n");
*/
for(int next=1; next<N; next++){
if(A[next] < D[index]){
index++;
D[index] = A[next];
}else if(A[next] > D[index]){
check = how_big(D, index, A[next]);
if(check==0){
//no change
continue;
}else {
//change
index-=check-1;
D[index] = A[next];
}
}
}
/* test calc
printf("final D index=%d, input: ", index);
for(int i=0; i<=index; i++){
printf("%d ", D[i]);
}
printf("\n");
*/
for(int i=0; i<=index; i++){
sum+=D[i];
}
printf("%d", sum);
return 0;
}
int how_big(int *D, int index, int value){
int sum=D[index];
int nth=1;
for(int i=index-1; i>=0; i--){
if(value > D[i]){
sum+=D[i];
if(value >= sum){
nth++;
}else {
return 0;
}
}else if(value < D[i]){
return nth;
}else if(value == D[i]){
return 0;
}
}
return nth;
}
C
INFO