Submission #70780052

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;
long long dat[250000];

int main()
{
    int n, w = 0;
    scanf("%d", &n);
    pair <int, pair <long long, long long>> arr[n + 100];
    long long val = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d %lld %lld", &arr[i].first, &arr[i].second.first, &arr[i].second.second);
        w += arr[i].first, val += arr[i].second.second;
        arr[i].second.first -= arr[i].second.second;
    }


    memset(dat,-1,sizeof(dat));
    dat[w] = val;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= w ; j++)
        {
            if(j - 2*arr[i].first < 0)
                continue;
            if(dat[j] == -1)
                continue;
            dat[j - 2*arr[i].first] = max(dat[j - 2*arr[i].first], dat[j] + arr[i].second.first);
        }
    }

    long long ans = val;
    for(int j = w ; j >= 0 ; j--)
    {
        //printf("j = %d -> %lld\n", j, dat[j]);
        ans = max(ans, dat[j]);
    }
    printf("%lld\n", ans);
    return 0;
}

Submission Info

Judge Result