This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 ? other.deltaProfit < deltaProfit : 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;
}
Compilation message (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... |