Submission #25556

#	Time	Username	Problem	Language	Result	Execution time	Memory
25556		tlwpdus	스트랩 (JOI14_straps)	C++98	100 / 100	46 ms	85708 KiB

straps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll knap[2100][5100], INF = 1LL<<50;
int n, bia = 2010;
int a[2100], b[2100];

int main() {
    int i, j, k;

    //freopen("input","r",stdin);

    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for (i=1;i<=n;i++) a[i]--;
    for (j=0;j<5100;j++) knap[0][j] = -INF;
    knap[0][bia] = 0;
    ll res = 0;
    for (i=1;i<=n;i++) {
        for (j=0;j<=n+bia+1;j++) {
            knap[i][j] = knap[i-1][j];
            if (j==n+bia+1) {
                knap[i][j] = max(knap[i][j],knap[i-1][j]+b[i]);
                for (k=j-a[i];k<=n+bia;k++) knap[i][j] = max(knap[i][j],knap[i-1][k]+b[i]);
            }
            else if (j-a[i]>=0&&j-a[i]<=n+bia) knap[i][j] = max(knap[i][j],knap[i-1][j-a[i]]+b[i]);
            if (i==n&&j-bia>=-1) res = max(res,knap[i][j]);
        }
    }
    printf("%lld\n",res);

    return 0;
}

Compilation message (stderr)

straps.cpp: In function 'int main()':
straps.cpp:16:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
straps.cpp:17:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
                                                 ^

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