이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define int ll
using namespace std;
struct obj {
int c, f, p;
bool type;
};
int N, M;
vector<obj> v;
int memo[2][100010];
int sol(int pos, int cpu) {
if (cpu < 0) return -1e18;
if (pos == v.size()) return 0;
if (v[pos].type)
return max(sol(pos + 1, cpu), sol(pos + 1, cpu + v[pos].c) - v[pos].p);
else
return max(sol(pos + 1, cpu), sol(pos + 1, cpu - v[pos].c) + v[pos].p);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int a, b, c;
cin >> a >> b >> c;
v.pb({a, b, c, 1});
}
cin >> M;
for (int i = 0; i < M; i++) {
int a, b, c;
cin >> a >> b >> c;
v.pb({a, b, c, 0});
}
sort(v.begin(), v.end(), [](const obj &a, const obj &b) {
if (a.f != b.f) return a.f > b.f;
if (a.type != b.type) return a.type > b.type;
return a.p < b.p;
});
for (int i = 0; i < 100010; i++) memo[1][i] = 0;
for (int i = v.size() - 1; i >= 0; i--) {
for (int j = 0; j < 100010; j++) {
if (v[i].type)
memo[0][j] = max(memo[1][j], j + v[i].c < 100010 ? memo[1][j + v[i].c] - v[i].p : -1000000000000000);
else
memo[0][j] = max(memo[1][j], j - v[i].c >= 0 ? memo[1][j - v[i].c] + v[i].p : -1000000000000000);
}
for (int j = 0; j < 100010; j++) {
memo[1][j] = memo[0][j];
}
}
cout << memo[0][0] << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
clo.cpp: In function 'long long int sol(long long int, long long int)':
clo.cpp:18:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | if (pos == v.size()) 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... |