Submission #565017

#	Time	Username	Problem	Language	Result	Execution time	Memory
565017		Karuk	Cloud Computing (CEOI18_clo)	C++14	100 / 100	508 ms	1524 KiB

clo

#include<bits/stdc++.h>
#define min(A,B) (A<B?A:B)
#define max(A,B) (A>B?A:B)
using namespace std;
long long dp[150000];
void solve() {
    int n;
    cin>>n;
    vector<vector<long long> >a;
    for(int i=0;i<n;i++) {
        long long f,v,c;
        cin>>c>>f>>v;
        a.push_back({f,c,-v});
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++) {
        long long f,v,c;
        cin>>c>>f>>v;
        a.push_back({f,-c,v});
    }
    sort(a.begin(),a.end());
    for(int i=1;i<=n+m;i++) {
        int maxs=min(100000,100+50*min(i,n+m-i));
        if(a[i-1][1]<0) {
            for(int negcores=maxs;negcores>=-a[i-1][1];negcores--) {
                dp[negcores]=max(dp[negcores],dp[negcores+a[i-1][1]]+a[i-1][2]);
            }
        }
        else {
            for(int negcoresfrom=0;negcoresfrom-a[i-1][1]<=maxs;negcoresfrom++) {
                dp[max(0,negcoresfrom-a[i-1][1])]=max(dp[max(0,negcoresfrom-a[i-1][1])],dp[negcoresfrom]+a[i-1][2]);
            }
        }
    }
    cout<<dp[0]<<endl;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    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