제출 #1285684

#제출 시각아이디문제언어결과실행 시간메모리
1285684bartimaeus28Cloud Computing (CEOI18_clo)C++20
100 / 100
699 ms3436 KiB
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <cstdio>
#include <numeric>
#include <cstdio>

 
using namespace std;
 
int main(){
    int n;cin>>n; 
    vector<vector<int>> data1(n,vector<int>(3));
    for (int i=0;i<n;i++){
        cin>>data1[i][1]>>data1[i][0]>>data1[i][2];
        data1[i][2]=-data1[i][2];
    }
    int m;cin>>m;
    vector<vector<int>> data2(m,vector<int>(3));
    for (int i=0;i<m;i++){
        cin>>data2[i][1]>>data2[i][0]>>data2[i][2];
        data2[i][1]=-data2[i][1];
    }
    vector<vector<int>> data;
    for (auto i:data1){
        data.push_back(i);
    }
    for (auto i:data2){
        data.push_back(i);
    }
    
    sort(data.begin(),data.end());
    vector<vector<int>> arr(n+m,vector<int>(3));
    for (int i=0;i<n+m;i++){
        arr[i]=data[n+m-1-i];
    }
    
    vector<long long> prev_dp(100001);vector<long long> new_dp(100001);vector<int> prev_visited(100001);vector<int> next_visited(100001);
    prev_visited[0]=1;next_visited[0]=1;
    for (int i=0;i<n+m;i++){
        for (int j=0;j<100001;j++){
            if (prev_visited[j]==1 and j+arr[i][1]>=0 and j+arr[i][1]<100001){
                if (prev_visited[j+arr[i][1]]==1){
                    new_dp[j+arr[i][1]]=max(new_dp[j+arr[i][1]],1LL*prev_dp[j]+arr[i][2]);
                }
                else{
                    new_dp[j+arr[i][1]]=1LL*prev_dp[j]+arr[i][2];
                }
                next_visited[j+arr[i][1]]=1;
            }
        }
        prev_dp=new_dp;
        prev_visited=next_visited;
    }
    long long ans=0;
    for (int i=0;i<100001;i++){
        if (prev_visited[i]==1){
            ans=max(ans,new_dp[i]);
        }
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...