Submission #955337

#	Time	Username	Problem	Language	Result	Execution time	Memory
955337		sleepntsheep	Knapsack (NOI18_knapsack)	C11	100 / 100	61 ms	2416 KiB

knapsack

unsigned rng=12345; int rand_(){return (rng*=3)>>1;}
int(*compar)(int,int);
void sort_(int*a,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r,t,p=a[l+rand_()%(r-l)];
        while(j<k)
            switch(compar(a[j],p))
            {
                case 0:++j;break;
                case -1:t=a[i],a[i]=a[j],a[j]=t,++i,++j;break;
                case 1:t=a[--k],a[k]=a[j],a[j]=t;break;
            }

        sort_(a,l,i);
        l=k;
    }
}

int min_(int a,int b){return a<b?a:b;}
long long max_(long long a,long long b){return a>b?a:b;}

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

#define S 2005
#define N 100005

int s,n,v[N],w[N],k[N];
int *eh[N],eo[N];


void append(int i,int j)
{
    int o=eo[i]++;
    if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
    eh[i][o]=j;
}

int c0(int i,int j){return v[i]<v[j]?1:v[i]>v[j]?-1:0;}

#define SlgS (S*13)

int vv[SlgS],ww[SlgS],oo;

long long dp[S];

int main()
{
    scanf("%d%d",&s,&n);

    for(int i=1;i<=s;++i)eh[i]=(int*)realloc(0,sizeof**eh*2);
    for(int i=1;i<=n;++i)
        scanf("%d%d%d",v+i,w+i,k+i),
        append(w[i],i);

    compar=c0;
    for(int i=1;i<=s;++i) sort_(eh[i],0,eo[i]);

    for(int i=1;i<=s;++i)
    {
        int left=(s+i-1)/i;
        for(int j=0;left&&j<eo[i];++j)
        {
            int take=min_(left,k[eh[i][j]]);
            for(int k=0;k<take;++k)
            {
                vv[oo]=v[eh[i][j]];
                ww[oo]=w[eh[i][j]];
                ++oo;
            }
            left-=take;
        }
        dp[i]=-1e18;
    }


    for(int i=0;i<oo;++i)
    {
        for(int j=s;j>=ww[i];--j)
        {
            dp[j]=max_(dp[j],dp[j-ww[i]]+vv[i]);
            dp[s+1]=max_(dp[s+1],dp[j]);
        }
    }

    printf("%lld",dp[s+1]);


}

Compilation message (stderr)

knapsack.c: In function 'append':
knapsack.c:37:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   37 |     if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
knapsack.c: In function 'main':
knapsack.c:51:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d",&s,&n);
      |     ^~~~~~~~~~~~~~~~~~~
knapsack.c:55:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d%d%d",v+i,w+i,k+i),
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27