結果
問題 | No.974 最後の日までに |
ユーザー |
|
提出日時 | 2020-02-16 00:11:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 2,035 bytes |
コンパイル時間 | 653 ms |
コンパイル使用メモリ | 59,376 KB |
最終ジャッジ日時 | 2025-01-09 00:50:29 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:16:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 16 | scanf("%d", &w); | ~~~~~^~~~~~~~~~ main.cpp:17:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | for(int i = 0; i < w; i++) scanf("%lld%lld%lld", A+i, B+i, C+i); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <vector> #include <algorithm> int w; long long int A[100], B[100], C[100]; struct S { long long int money; long long int love; }; std::vector<S> states0[3], states1[3], tmp; int main(){ scanf("%d", &w); for(int i = 0; i < w; i++) scanf("%lld%lld%lld", A+i, B+i, C+i); for(int t = 0; t < 3; t++){ if(t==2) states1[t].emplace_back(S({0, 0})); else states0[t].emplace_back(S({0, 0})); for(int i = t ? (w+1)/2: 0; i < (t ? w : (w+1) / 2); i++){ for(auto it0 = states0[t].begin(), it1 = states1[t].begin(); ;){ if(it0 == states0[t].end()){ for(; it1 != states1[t].end(); ++it1){ tmp.emplace_back(S({it1->money - C[i], it1->love + B[i]})); } break;} else if(it1 == states1[t].end()){ for(; it0 != states0[t].end(); ++it0){ tmp.emplace_back(S({it0->money + A[i], it0->love})); } break;} else if(it0->money + A[i] >= it1->money - C[i] && it0->love >= it1->love + B[i]) ++it1; else if(it0->money + A[i] <= it1->money - C[i] && it0->love <= it1->love + B[i]) ++it0; else if(it0->money + A[i] <= it1->money - C[i]) tmp.emplace_back(S({it0->money + A[i], it0->love})), ++it0; else tmp.emplace_back(S({it1->money - C[i], it1->love + B[i]})), ++it1; } states0[t].swap(states1[t]); states0[t].swap(tmp); tmp.clear(); } } // printf("%ld %ld %ld %ld\n", states0[0].size(), states1[0].size(), states0[1].size(), states0[2].size()); long long int ans = 0; for(auto it0 = states0[0].begin(), it1 = states0[1].end(); it0 != states0[0].end(); ++it0){ while(it1 != states0[1].begin() && it0->money + (it1-1)->money >= 0) --it1; if(it1 != states0[1].end()) ans = std::max(ans, it0->love + it1->love); } for(auto it0 = states1[0].begin(), it1 = states0[2].end(); it0 != states1[0].end(); ++it0){ while(it1 != states0[2].begin() && it0->money + (it1-1)->money >= 0) --it1; if(it1 != states0[2].end()) ans = std::max(ans, it0->love + it1->love); } printf("%lld\n", ans); return 0; }