Submission #1285679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285679		bartimaeus28	Cloud Computing (CEOI18_clo)	C++20	18 / 100	733 ms	3424 KiB

clo

#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;
    }
    int ans=0;
    for (int i:new_dp){
        ans=max(ans,i);
    }
    cout<<ans;
    
}

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