제출 #1253800

#제출 시각아이디문제언어결과실행 시간메모리
1253800abdullah_Feast (NOI19_feast)C++20
0 / 100
629 ms192420 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> pp; #define all(a) (a).begin(), (a).end() #define what_is(x) cerr << #x << " is " << x << '\n'; #define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n'; const int N = 2e5 + 7; const int MOD = 1e9 + 7; const int INF = 1e15; void solve() { int n, k; cin >> n >> k; vector<int> a(n + 1); vector<int> pre(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } // The maximum sum when taking 3 segments and some segments may be big // we will add some random value into the auto check = [&] (int val)->pp { vector<int> dp(n + 1), g(n + 1); int mxDp = 0, mxG = 0; for (int i = 1; i <= n; ++i) { int sum = pre[i] + mxDp - val; dp[i] = dp[i - 1]; g[i] = g[i - 1]; if (sum > dp[i]) { dp[i] = sum; g[i] = mxG + 1; } if (dp[i] - pre[i - 1] > mxDp) { mxDp = dp[i] - pre[i - 1]; mxG = g[i]; } else if (dp[i] - pre[i - 1] == mxDp) { mxG = min(mxG, g[i]); } } // print(dp); // print(g); // cout << "val: " << val << endl; return {dp[n], g[n]}; }; int l = 1, r = 1000, pos = -1; int res = 0; while (l <= r) { int mid = (l + r) / 2; auto [ans, count] = check(mid); // cout << ans << ' ' << count << '\n'; if (count <= k) { res = max(res, ans + mid * count); r = mid - 1; } else { l = mid + 1; } } cout << res << endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int tt = 1; // cin >> tt; while (tt--) { solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'int32_t main()':
feast.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...