이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <bits/stdc++.h>
#ifdef N257
std::ifstream fin("input.in");
#define cin fin
#else
// std::ifstream fin (".in");
// std::ofstream fout (".out");
// #define cin fin
// #define cout fout
#endif
using namespace std;
#define VEC(T, N, V) vector<T>(N, V)
#define MAT(T, N, M, V) vector<vector<T>>(N, vector<T>(M, V))
#define CUBE(T, N, M, L, V) vector<vector<vector<T> > >(N, vector<vector<T> >(M, vector<T>(L, V)))
#define sz(a) (int)((a).size())
#define all(a) begin(a), end(a)
#define endl '\n'
#define int long long
#define dbg(x) cerr << "[DEBUG] " << #x << ": " << x << '\n'
const int inf = 1e18;
const int mod = 1e9 + 7;
struct Transaction {
int deltaCores = 0;
int freqRate = 0;
int deltaProfit = 0;
bool operator<(const Transaction &other) const {
return other.freqRate < freqRate;
}
};
signed main() {
int N, M, max_cores = 0;
vector<Transaction> transactions;
// reading computers
cin >> N;
for (int i = 0; i < N; ++i) {
int c, f, v; cin >> c >> f >> v;
max_cores += c;
transactions.push_back({c, f, -v});
}
// reading orders
cin >> M;
for (int i = 0; i < M; ++i) {
int c, f, v; cin >> c >> f >> v;
transactions.push_back({-c, f, v});
}
sort(all(transactions));
// for (auto &t : transactions) {
// cout << t.deltaCores << " " << t.freqRate << " " << t.deltaProfit << endl;
// }
// dp[t][c] = maximum profit gained if
// * we take into account the first ``t`` transactions
// * we have ``c`` cores left
auto dp = MAT(int, 2, max_cores + 1, -inf);
dp[0][0] = 0;
for (int t = 1; t <= transactions.size(); ++t) {
for (int c = 0; c <= max_cores; ++c) {
// do not take the transaction
dp[t % 2][c] = max(dp[t % 2][c],
dp[(t - 1) % 2][c]);
// take the transaction
if (0 <= c - transactions[t - 1].deltaCores and
c - transactions[t - 1].deltaCores <= max_cores and
dp[(t - 1) % 2][c - transactions[t - 1].deltaCores] != -inf)
dp[t % 2][c] = max(dp[t % 2][c],
dp[(t - 1) % 2][c - transactions[t - 1].deltaCores] + transactions[t - 1].deltaProfit);
}
}
cout << *max_element(dp[(N + M) % 2].begin(), dp[(N + M) % 2].end()) << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
clo.cpp: In function 'int main()':
clo.cpp:70:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Transaction>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int t = 1; t <= transactions.size(); ++t) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |