제출 #580402

#제출 시각아이디문제언어결과실행 시간메모리
580402amunduzbaevCloud Computing (CEOI18_clo)C++17
100 / 100
2629 ms3640 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef int64_t ll; #define int ll const int inf = -1e18; const int N = 2005; const int M = 51; const int H = 103; int dp[2][N][H]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<ar<int, 3>> a(n); for(int i=0;i<n;i++){ cin>>a[i][0]>>a[i][1]>>a[i][2]; } sort(a.begin(), a.end(), [&](auto& a, auto& b){ return a[1] < b[1]; }); int m; cin>>m; vector<ar<int, 3>> b(m); for(int i=0;i<m;i++){ cin>>b[i][0]>>b[i][1]>>b[i][2]; } sort(b.begin(), b.end(), [&](auto& a, auto& b){ return a[1] < b[1]; }); memset(dp, -63, sizeof dp); dp[0][0][M] = 0; for(int i=0;i<=n;i++){ int cur = i & 1, nxt = !cur; memset(dp[nxt], -63, sizeof dp[nxt]); for(int j=0;j<=m;j++){ if(dp[cur][j][M] > inf){ //~ cout<<i<<" "<<j<<" "<<0<<" "<<dp[cur][j][M]<<endl; if(i < n) dp[nxt][j][M] = max(dp[nxt][j][M], dp[cur][j][M]); if(j < m) dp[cur][j + 1][M] = max(dp[cur][j + 1][M], dp[cur][j][M]); if(i < n){ //~ cout<<dp[cur][j][M + a[i][0]]<<endl; dp[cur][j][M + a[i][0]] = max(dp[cur][j][M + a[i][0]], dp[cur][j][M] - a[i][2]); //~ cout<<dp[cur][j][M + a[i][0]]<<endl; } if(j < m){ assert(j < m); dp[cur][j][M - b[j][0]] = max(dp[cur][j][M - b[j][0]], dp[cur][j][M] + b[j][2]); } } for(int k=-M;k<=M;k++){ if(dp[cur][j][k + M] <= inf || !k) continue; //~ cout<<i<<" "<<j<<" "<<k<<" "<<dp[cur][j][k + M]<<endl; if(k < 0 && i < n){ assert(j < m); dp[nxt][j][k + M] = max(dp[nxt][j][k + M], dp[cur][j][k + M]); if(b[j][1] <= a[i][1]){ if(k + a[i][0] < 0){ dp[nxt][j][k + a[i][0] + M] = max(dp[nxt][j][k + a[i][0] + M], dp[cur][j][k + M] - a[i][2]); } else if(k + a[i][0] == 0){ dp[nxt][j + 1][M] = max(dp[nxt][j + 1][M], dp[cur][j][k + M] - a[i][2]); } else { dp[cur][j + 1][k + a[i][0] + M] = max(dp[cur][j + 1][k + a[i][0] + M], dp[cur][j][k + M] - a[i][2]); } } } if(k > 0){ assert(i < n); if(j < m) dp[cur][j + 1][k + M] = max(dp[cur][j + 1][k + M], dp[cur][j][k + M]); dp[nxt][j][M] = max(dp[nxt][j][M], dp[cur][j][k + M]); if(j < m && b[j][1] <= a[i][1]){ if(k - b[j][0] < 0){ //~ cout<<i + 1<<" "<<j<<" "<<k - b[j][0]<<endl; dp[nxt][j][k - b[j][0] + M] = max(dp[nxt][j][k - b[j][0] + M], dp[cur][j][k + M] + b[j][2]); } else if(k - b[j][0] == 0){ dp[nxt][j + 1][M] = max(dp[nxt][j + 1][M], dp[cur][j][k + M] + b[j][2]); } else { dp[cur][j + 1][k - b[j][0] + M] = max(dp[cur][j + 1][k - b[j][0] + M], dp[cur][j][k + M] + b[j][2]); } } } } } } int res = inf; for(int i=M;i<H;i++){ res = max(res, dp[n&1][m][i]); } cout<<res<<"\n"; } /* 5 6 1 6 4 1 12 5 1 5 4 1 9 6 1 12 4 6 1 9 5 1 12 6 1 6 5 1 7 3 6 1 8 6 1 5 6 1 11 3 6 1 9 6 1 4 4 1 12 */
#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...