Submission #8241

#	Time	Username	Problem	Language	Result	Execution time	Memory
8241		dohyun0324	스트랩 (JOI14_straps)	C++98	100 / 100	28 ms	16884 KiB

straps

#include<stdio.h>
#include<algorithm>
using namespace std;
int dap,n,a[2010],b[2010],d[2010][2010];
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&a[i],&b[i]);
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            if(a[i]>a[j])
            {
                swap(a[i],a[j]); swap(b[i],b[j]);
            }
        }
    }
    for(i=0;i<=n;i++)
    {
        for(j=2;j<=2000;j++)
        {
            d[i][j]=-2147483647;
        }
        d[i][0]=-2147483647;
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=2000;j++)
        {
            if(d[i-1][j]!=-2147483647)
            {
                if(j!=0) d[i][min(2000,j+a[i]-1)]=max(d[i][min(2000,j+a[i]-1)],d[i-1][j]+b[i]);
                d[i][j]=max(d[i][j],d[i-1][j]);
            }
        }
    }
    for(i=0;i<=2000;i++)
    {
        if(dap<d[n][i]) dap=d[n][i];
    }
    printf("%d",dap);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 45 / 45