結果
問題 | No.1163 I want to be a high achiever |
ユーザー |
![]() |
提出日時 | 2020-08-12 01:16:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,106 bytes |
コンパイル時間 | 1,558 ms |
コンパイル使用メモリ | 120,968 KB |
最終ジャッジ日時 | 2025-01-12 20:49:09 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 2 WA * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, const char**)’: main.cpp:27:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | re(i, n) scanf("%lld", &a[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:28:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 28 | re(i, n) scanf("%lld", &b[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <string> #include <vector> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <iomanip> #define vll vector<ll> #define vvvl vector<vvl> #define vvl vector<vector<ll>> #define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c)) #define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; using namespace std; int main(int argc, char const *argv[]) { ll n, x;std::cin >> n >> x; vll a(n), b(n); re(i, n) scanf("%lld", &a[i]); re(i, n) scanf("%lld", &b[i]); vvl minus, plus; for(int i=0;i<n;i++){ a[i]-=x; if(a[i]<=0) minus.push_back({abs(a[i]), b[i]}); else plus.push_back({a[i], b[i]}); } //kを作るのに必要なお金 ll m = minus.size(); ll p = plus.size(); ll INF = 10000000000; vvl dp = VV(m+1, 50001, INF, ll); vvl dp2 = VV(p+1, 50001, INF, ll); if(m==0){ std::cout << 0 << '\n'; return 0; } dp[0][0] = 0; if(p!=0)dp2[0][0] = 0; for(int i=0;i<m;i++){ ll val = minus[i][0], w = minus[i][1]; for(int j=0;j<50001;j++){ //スルー dp[i+1][j] = min(dp[i+1][j], dp[i][j] + w); //取る if(j+val<=50000) dp[i+1][j+val] = min(dp[i+1][j+val], dp[i][j]); } } for(int i=0;i<p;i++){ ll val = plus[i][0], w = plus[i][1]; for(int j=0;j<50001;j++){ //スルー dp2[i+1][j] = min(dp2[i+1][j], dp2[i][j] + w); //取る if(j+val<=50000) dp2[i+1][j+val] = min(dp2[i+1][j+val], dp2[i][j]); } } for(int i=1;i<=50000;i++) dp[m][i] = min(dp[m][i], dp[m][i-1]); for(int i=50000-1;i>=0;i--) dp2[p][i] = min(dp2[p][i], dp2[p][i+1]); for(int i=0;i<=10;i++) std::cout << dp2[p][i] << (i==10?"\n":" "); for(int i=0;i<=10;i++) std::cout << dp[m][i] << (i==10?"\n":" "); ll ans = INF; for(int i=0;i<=50000;i++){ ans = min(ans, dp2[p][i] + dp[m][i]); } std::cout << (ans==INF?-1:ans) << '\n'; return 0; }