結果
| 問題 |
No.974 最後の日までに
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,716 bytes |
| コンパイル時間 | 855 ms |
| コンパイル使用メモリ | 90,436 KB |
| 実行使用メモリ | 232,016 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:54 |
| 合計ジャッジ時間 | 7,345 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 48 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility> // For std::move
using namespace std;
// Define long long type for large numbers often needed in competitive programming
typedef long long ll;
/**
* @brief Updates a map representing states (Favorability -> Max Money).
* For a given favorability F, ensures that the map stores the maximum possible money M achieved.
* If F is already a key in the map, it updates the associated money M if the new M is greater.
* If F is not in the map, it inserts the new pair (F, M).
*
* @param m Reference to the map to be updated.
* @param F The favorability value.
* @param M The money value associated with F.
*/
void update_map(map<ll, ll>& m, ll F, ll M) {
// Find if F already exists as a key in the map
auto it = m.find(F);
if (it != m.end()) {
// If F exists, update the associated money M only if the new M is greater
it->second = max(it->second, M);
} else {
// If F does not exist, insert the new pair (F, M) into the map
m.insert({F, M});
}
// Note: This function implements the "max M per F" filtering strategy.
// A full Pareto optimality check could be more complex and potentially store more states.
// Based on problem structure and examples, "max M per F" seems appropriate.
}
int main() {
// Use faster I/O operations by disabling synchronization with C stdio and unlinking cin/cout.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int W; // Number of weeks until graduation
cin >> W;
// Vectors to store the parameters for each week. Using 1-based indexing for convenience.
// a[i]: money earned fromアルバイト in week i
// b[i]: favorability points gained from dating in week i
// c[i]: money spent for dating in week i
vector<ll> a(W + 1), b(W + 1), c(W + 1);
for (int i = 1; i <= W; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
// DP state representation: Use two maps.
// dp[0]: Stores states (Favorability -> Max Money) achievable at the end of a week,
// such that NO appointment is made for the NEXT week.
// dp[1]: Stores states (Favorability -> Max Money) achievable at the end of a week,
// such that an appointment IS made for the NEXT week.
map<ll, ll> dp[2];
// Base case: At the end of week 0 (which is the start of week 1).
// Initial favorability F=0, initial money M=0.
// The problem states she does not have an appointment for week 1.
// This corresponds to a state in dp[0].
dp[0][0] = 0;
// Iterate through each week from 1 to W
for (int i = 1; i <= W; ++i) {
// Temporary maps to store the DP states computed for the end of week i.
// These will replace dp[0] and dp[1] after processing week i.
map<ll, ll> next_dp[2];
// Process transitions originating from states that ended week i-1 WITH an appointment FOR week i.
// These states are currently stored in dp[1].
// Rule: If she has an appointment for week i, she MUST go on a date.
if (!dp[1].empty()) { // Check if there are any such states
for (auto const& [F, M] : dp[1]) { // Iterate through each state (F, M)
ll next_F = F + b[i]; // Favorability increases by b[i]
ll next_M = M - c[i]; // Money decreases by c[i]
// After dating, no appointment is made for the following week (i+1).
// Therefore, this resulting state contributes to next_dp[0].
update_map(next_dp[0], next_F, next_M);
}
}
// Process transitions originating from states that ended week i-1 with NO appointment FOR week i.
// These states are currently stored in dp[0].
// Rule: If she has no appointment, she can choose either 'Go to school' or 'Do アルバイト'.
if (!dp[0].empty()) { // Check if there are any such states
for (auto const& [F, M] : dp[0]) { // Iterate through each state (F, M)
// Option 1: Choose 'Go to school'
if (i < W) { // If it's not the last week
// This action makes an appointment for week i+1.
// State (F, M) transitions to a state contributing to next_dp[1].
update_map(next_dp[1], F, M);
} else { // If i == W (the last week)
// The problem states "if i=W, nothing happens".
// This means the state (F, M) remains, and no appointment is relevant after week W.
// The resulting state effectively has no appointment for 'next week', contributing to next_dp[0].
update_map(next_dp[0], F, M);
}
// Option 2: Choose 'Do アルバイト'
ll next_M = M + a[i]; // Money increases by a[i]. Favorability F remains unchanged.
// This action does not make an appointment for week i+1.
// The resulting state (F, next_M) contributes to next_dp[0].
update_map(next_dp[0], F, next_M);
}
}
// After processing all transitions for week i, update the main DP state maps.
// Using std::move can be more efficient for large maps as it avoids copying.
dp[0] = move(next_dp[0]);
dp[1] = move(next_dp[1]);
}
// After iterating through all W weeks, the final possible states are in dp[0] and dp[1].
// We need to find the maximum favorability F among all final states where the money M is non-negative.
ll max_F = 0; // Initialize maximum Favorability found so far to 0.
// The initial state (0, 0) is always reachable and satisfies M >= 0, so 0 is a possible result.
// Check states in dp[0] (ended week W without an appointment for W+1)
for (auto const& [F, M] : dp[0]) {
if (M >= 0) { // Check the final money constraint
max_F = max(max_F, F); // Update max_F if this state has higher F
}
}
// Check states in dp[1] (ended week W having made an appointment for W+1).
// Based on the rules for week W actions, this map should theoretically be empty.
// Checking it provides robustness in case of interpretation differences.
for (auto const& [F, M] : dp[1]) {
if (M >= 0) { // Check the final money constraint
max_F = max(max_F, F); // Update max_F if this state has higher F
}
}
// Output the final result: the maximum favorability achievable with non-negative money.
cout << max_F << endl;
return 0;
}