제출 #1062418

#제출 시각아이디문제언어결과실행 시간메모리
1062418CodeLakVNFeast (NOI19_feast)C++17
21 / 100
17 ms4424 KiB
#include <bits/stdc++.h> #define no "NO" #define yes "YES" #define F first #define S second #define vec vector #define task "FEAST" #define ll long long #define _mp make_pair #define ii pair<int, int> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define evoid(val) return void(std::cout << val) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FOD(i, b, a) for(int i = (b); i >= (a); --i) #define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin()) using namespace std; template<typename U, typename V> bool maximize(U &a, V b) { if (a < b) { a = b; return 1; } return 0; } template<typename U, typename V> bool minimize(U &a, V b) { if (a > b) { a = b; return 1; } return 0; } const int N = (int)2e5 + 9; const int INF = (int)1e9; const int MOD = (int)1e9 + 7; int n, k; int a[N]; namespace sub3 { bool valid() { return k == 1; } void solve() { ll sum = 0, minPre = 0, ans = 0; FOR(i, 1, n) { sum += a[i]; maximize(ans, sum - minPre); minimize(minPre, sum); } cout << ans << "\n"; } } namespace sub1 { bool valid() { return *min_element(a + 1, a + n + 1) >= 0; } void solve() { ll ans = 0; FOR(i, 1, n) ans += a[i]; cout << ans << "\n"; } } namespace sub2 { bool valid() { bool appeared = 0; FOR(i, 1, n) { if (a[i] < 0 && appeared) return false; if (a[i] < 0) appeared = 1; } return true; } void solve() { ll ans = 0; FOR(i, 1, n) ans += a[i]; ans -= *min_element(a + 1, a + n + 1); cout << ans << "\n"; } } namespace sub5 { const int N = 303; ll dp[N][N]; ll sum[N]; bool valid() { return n <= 300; } void solve() { FOR(i, 1, n) sum[i] = sum[i - 1] + a[i]; memset(dp, -0x3f, sizeof(dp)); dp[0][0] = 0; FOR(i, 1, n) FOR(j, 1, min(k, i)) { ll maxDP = dp[j - 1][j - 1]; FOR(x, j, i) { maximize(dp[i][j], maxDP + (sum[i] - sum[x - 1])); maximize(maxDP, dp[x][j - 1]); } //cout << i << " " << j << " " << dp[i][j] << "\n"; } ll ans = 0; FOR(i, 1, n) FOR(j, 1, min(k, i)) maximize(ans, dp[i][j]); cout << ans << "\n"; } } namespace sub6 { const int N = (int)2e3 + 3; ll dp[N][N], maxDP[N]; ll sum[N]; bool valid() { return n <= 2000; } void calc(int id, int l, int r, int optL, int optR) { if (l > r) return; int mid = (l + r) >> 1; int bestPos; FOR(i, optL, min(optR, r)) { ll newCost = maxDP[i - 1] + sum[mid] - sum[i - 1]; if (maximize(dp[id][mid], newCost)) bestPos = i; } calc(id, l, mid - 1, optL, bestPos); calc(id, mid + 1, r, bestPos, optR); } void solve() { FOR(i, 1, n) sum[i] = sum[i - 1] + 1LL * a[i]; memset(dp, -0x3f, sizeof(dp)); dp[0][0] = 0; ll minPre = 0; FOR(i, 1, n) dp[1][i] = sum[i] - minPre, minimize(minPre, sum[i]); FOR(id, 2, k) { FOR(i, 1, n) maxDP[i] = max(maxDP[i - 1], dp[id - 1][i]), cout << i << " " << id - 1 << " " << dp[id - 1][i] << "\n"; calc(id, id, n, id, n); } ll ans = 0; FOR(j, 1, k) FOR(i, j, n) maximize(ans, dp[j][i]); cout << ans << "\n"; } } void main_code() { cin >> n >> k; FOR(i, 1, n) cin >> a[i]; if (sub3::valid()) sub3::solve(); else if (sub1::valid()) sub1::solve(); else if (sub2::valid()) sub2::solve(); else if (sub5::valid()) sub5::solve(); //if (sub6::valid()) sub6::solve(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } const bool MULTITEST = 0; int num_test = 1; if (MULTITEST) cin >> num_test; while (num_test--) { main_code(); cout << "\n"; } } /* Lak lu theo dieu nhac */

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

feast.cpp: In function 'int main()':
feast.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp: In function 'void sub6::calc(int, int, int, int, int)':
feast.cpp:128:13: warning: 'bestPos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |         calc(id, l, mid - 1, optL, bestPos);
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...