Submission #657084

#	Time	Username	Problem	Language	Result	Execution time	Memory
657084		perchuts	Cloud Computing (CEOI18_clo)	C++17	100 / 100	511 ms	2104 KiB

clo

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const ll inf = 1e18;
const int mod = 1e9+7;
const int maxn = 2010;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }



struct operation{
    ll c, f, v;
    bool type;
} v[2*maxn];

//dp[2*maxn][maxn*50] ->
//100*maxn^2 -> 4s! não funciona...

ll dp[2][55*maxn];

int main(){_
    int n;cin>>n;

    int bound = 0;

    for(int i=1;i<=n;++i)cin>>v[i].c>>v[i].f>>v[i].v, v[i].type = 0, bound += v[i].c;

    int m;cin>>m;
    
    for(int i=1+n;i<=n+m;++i)cin>>v[i].c>>v[i].f>>v[i].v, v[i].type = 1;

    sort(v+1, v+1+n+m, [&](operation x,operation y){
        if(x.f==y.f)return x.type < y.type;
        return x.f>y.f;
    });

    for(int i=0;i<=bound;++i)dp[0][i] = dp[1][i] = -inf;

    dp[0][0] = 0;
    
    for(int i=1;i<=n+m;++i){
        // cout<<v[i].c<<" "<<v[i].f<<" "<<v[i].v<<" "<<v[i].type<<endl;
        for(int j=0;j<=bound;++j){
            if(v[i].type==1){
                dp[i&1][j] = max(dp[(i-1)&1][j], (j+v[i].c<=bound?dp[(i-1)&1][j+v[i].c]+v[i].v:-inf));
            }else{
                dp[i&1][j] = max(dp[(i-1)&1][j], (j>=v[i].c?dp[(i-1)&1][j-v[i].c]-v[i].v:-inf));
            }
            // cout<<dp[i&1][j]<<endl;
        }
    }

    ll ans = 0;
    
    for(int i=0;i<=bound;++i)ckmax(ans, dp[(n+m)&1][i]);
    cout<<ans<<endl;
}

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