이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2003;
const ll inf = 1e18;
int n, m;
struct Edge{
int c;
ll f, v;
};
Edge st[2 * maxn + 7];
bool cmp(Edge a, Edge b)
{
if(a.f == b.f) return a.c > b.c;
return a.f > b.f;
}
int main()
{
//freopen("CLOUDCOMPUTING.INP", "r", stdin);
// freopen("CLOUDCOMPUTING.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++)
{
int c;
ll f, v;
cin >> c >> f >> v;
st[i].c = c;
st[i].f = f;
st[i].v = -v;
}
cin >> m;
for(int i = 1 + n; i <= n + m; i++)
{
int c;
ll f, v;
cin >> c >> f >> v;
st[i].c = -c;
st[i].f = f;
st[i].v = v;
}
sort(st + 1, st + n + m + 1, cmp);
/*for(int i = 1; i <= n + m; i++)
{
cout << st[i].c << ' ' << st[i].f << ' ' << st[i].v << '\n';
}*/
vector<vector<ll>>dp(n + m + 3, vector<ll>(101, -inf));
dp[0][0] = 0;
ll ans = 0;
for(int i = 1; i <= n + m; i++)
{
for(int j = 0; j <= 50; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j]);
if(st[i].c >= 0)
{
dp[i][j + st[i].c] = max(dp[i][j + st[i].c], dp[i - 1][j] + st[i].v);
ans = max(ans, dp[i][j + st[i].c]);
}
else{
if(j + st[i].c >= 0)
{
dp[i][j + st[i].c] = max(dp[i][j + st[i].c], dp[i - 1][j] + st[i].v);
ans = max(ans, dp[i][j + st[i].c]);
}
}
}
}
cout << ans;
}
# | 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... |