이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*raghav0307 - Raghav Gupta*/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll
struct Item{
int c, f, v, prod;
Item (int cc, int ff, int vv, int type) :
c(cc), f(ff), v(vv), prod(type) {}
};
bool custom(Item a, Item b){
if(a.f < b.f)
return false;
if(a.f > b.f)
return true;
if(a.prod == 1)
return true;
return false;
}
vector<Item> v;
const int MAXN = 2e3 + 5;
const int MAXC = 50;
const int inf = 1e15;
int dp[MAXN*MAXC], dp2[MAXN*MAXC];
// int memo[MAXN + 500][800];
// int dp(int pos, int left){
// if(pos == v.size()) return 0;
// if(memo[pos][left] != -1) return memo[pos][left];
// if(v[pos].prod == 1){
// if(left + v[pos].c >= 800) memo[pos][left] = dp(pos + 1, left);
// return memo[pos][left] = max( dp(pos+1, left + v[pos].c) - v[pos].v, dp(pos+1, left));
// }
// else if(v[pos].prod == 2){
// if(v[pos].c <= left) return memo[pos][left] = max(dp(pos + 1, left - v[pos].c) + v[pos].v, dp(pos +1 , left));
// return memo[pos][left] = dp(pos + 1, left);
// }
// }
signed main(){
fast_io();
// memset(memo, -1, sizeof(memo));
int n; cin >> n;
for(int i = 0; i < n; i++){
int c, f, vv;
cin >> c >> f >> vv;
v.push_back(Item(c, f, vv, 1));
}
int m; cin >> m;
for(int i = 0; i < m; i++){
int c, f, vv;
cin >> c >> f >> vv;
v.push_back(Item(c, f, vv, 2));
}
sort(v.begin(), v.end(), custom);
// for(auto x : v){
// cout << x.c << " " << x.f << " " << x.v << " " << x.prod << "\n";
// }
for(int i = 0; i < MAXN*MAXC; i++) dp[i] = dp2[i] = 0;
// if(v.back().prod == 2){
// for(int i = v.back().c; i < MAXN*MAXC; i++){
// dp[i] = v.back().v;
// }
// }
// for(int i = 0; i < 25; i++){
// cout << dp[i] << " ";
// }cout << "\n";
for(int i = n+m-1; i >= 0; i--){
for(int j = 0; j < MAXN*MAXC; j++){
if(v[i].prod == 1 and j + v[i].c < MAXN*MAXC){
dp2[j] = max(dp[j + v[i].c] - v[i].v, dp2[j]);
dp2[j] = max(dp2[j], dp[j]);
}
else if(v[i].prod == 2 and j >= v[i].c){
dp2[j] = max(dp[j - v[i].c] + v[i].v, dp2[j]);
dp2[j] = max(dp2[j], dp[j]);
}
}
// for(int j = 0; j < MAXC*MAXN; j++)
// dp[j] = dp2[j];
// for(int i = 0; i < 25; i++){
// cout << dp[i] << " ";
// }cout << "\n";
}
cout << max(dp[0], 0ll) << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |