제출 #555393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555393		status_coding	Cloud Computing (CEOI18_clo)	C++14	54 / 100	3087 ms	2376 KiB

clo

#include <bits/stdc++.h>

using namespace std;

struct pos
{
    long long nr, val, cost;

    pos() {}
    pos(long long nr, long long val, long long cost)
    {
        this->nr = nr;
        this->val = val;
        this->cost = cost;
    }

    bool operator<(pos b) const
    {
        return val < b.val;
    }
};

long long n,m,ans;

pos v[2005];
vector<pos> q[2005];

long long prof[100055];
long long dp[2][100055];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1; i<=n; i++)
        cin>> v[i].nr >> v[i].val >> v[i].cost;
    sort(v+1, v+n+1);

    cin>>m;
    for(int i=1; i<=m; i++)
    {
        int nr, val, cost;

        cin>>nr>>val>>cost;

        for(int j=1; j<=n; j++)
            if(v[j].val >= val)
            {
                q[j].push_back(pos(nr, val, cost));
                break;
            }
    }


    for(int i=0; i<=1; i++)
        for(int nr=0; nr<= 50 * n; nr++)
            dp[i][nr] = -1e18;

    dp[(n+1)%2][0] = 0;

    for(int i=n; i>=1; i--)
    {
        int sum = 0;
        for(auto it : q[i])
            sum += it.nr;

        for(int j=0; j<= sum; j++)
            prof[j] = 0;

        for(auto it : q[i])
            for(int j=sum; j>=it.nr; j--)
                prof[j] = max(prof[j], prof[j - it.nr] + it.cost);

        for(int nr=0; nr<= 50*n; nr++)
            dp[i%2][nr] = -1e18;

        for(int last=0; last <= 50*n; last++)
        {
            if(dp[(i+1)%2][last] == -1e18)
                continue;

            for(int cur=0; cur<=sum; cur++)
            {
                if(last - cur >= 0)
                    dp[i%2][last - cur] = max(dp[i%2][last - cur], dp[(i+1)%2][last] + prof[cur]);

                if(last + v[i].nr - cur >= 0)
                    dp[i%2][last + v[i].nr - cur] = max(dp[i%2][last + v[i].nr - cur],
                                                      dp[(i+1)%2][last] + prof[cur] - v[i].cost);
            }
        }
    }

    for(int nr=0; nr<= 50*n; nr++)
        ans = max(ans, dp[1][nr]);

    cout<<ans;
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10