Submission #907239

#	Time	Username	Problem	Language	Result	Execution time	Memory
907239		heeheeheehaaw	Cloud Computing (CEOI18_clo)	C++17	100 / 100	383 ms	2176 KiB

clo

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
 
using namespace std;
 
struct event
{
    int tip, a, b, cost;
};
 
vector<event> events;
const long long INF = 1e13;
 
bool cmp(event a, event b)
{
     if(a.b != b.b)
        return a.b > b.b;
     else
        return a.tip < b.tip;
}
 
long long dp[100005], newdp[100005];
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, q;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        events.push_back({1, a, b, c});
    }
 
    cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        events.push_back({2, a, b, c});
    }
 
    sort(events.begin(), events.end(), cmp);
 
    int sum = 0;
    for(auto it : events)
    {
 
        if(it.tip == 1)
        {
            sum += it.a;
            for(int i = 0; i <= sum; i++)
            {
                newdp[i] = -INF;
                if(i<=sum-it.a) newdp[i] = dp[i];
                int last = i - it.a;
                if(last >= 0)
                    newdp[i] = max(newdp[i], dp[last] - it.cost);
            }
        }
        else
        {
            for(int i = 0; i <= sum; i++)
            {
                newdp[i] = dp[i];
                int nx = i + it.a;
                if(nx <= sum) newdp[i] = max(newdp[i], dp[nx] + it.cost);
            }
        }
 
        for(int i = 0; i <= sum; i++)
            dp[i] = newdp[i];
    }
 
    long long maxx = 0;
    for(int i = 0; i <= sum; i++)
        maxx = max(maxx, dp[i]);
    cout<<maxx<<'\n';
    return 0;
}

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