제출 #657082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657082		perchuts	Cloud Computing (CEOI18_clo)	C++17	72 / 100	435 ms	1844 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;
    ll bound = 0, cur = 0;
    for(int i=1;i<=n;++i)cin>>v[i].c>>v[i].f>>v[i].v, v[i].type = 0, cur += v[i].c;
    bound = cur, cur = 0;
    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, cur += v[i].c;
    sort(v+1, v+1+n+m, [&](operation x,operation y){return x.f>y.f;});

    for(int i=0;i<=bound+200;++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+50;++j){
            if(v[i].type==1){
                dp[i&1][j] = max(dp[(i-1)&1][j], dp[(i-1)&1][j+v[i].c]+v[i].v);
            }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+50;++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: 0 / 18
• Subtask 5: 18 / 18
• Subtask 6: 0 / 10