Submission #791855

#TimeUsernameProblemLanguageResultExecution timeMemory
791855anhduc2701Feast (NOI19_feast)C++17
100 / 100
107 ms11784 KiB
/* #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("unroll-loops") */ #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define eb emplace_back #define PI acos(-1.0) #define fi first #define se second #define mp make_pair #define pb push_back #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define BIT(x, i) (1 & ((x) >> (i))) #define MASK(x) (1LL << (x)) #define task "tnc" #define rep(i, n) for (int i = 0; i < (n); i++) #define rep1(i, n) for (int i = 1; i <= (n); i++) typedef long long ll; typedef long double ld; const ll INF = 1e14; const int maxn = 1e6 + 5; const int mod = 1e9 + 7; const int mo = 998244353; using pi = pair<ll, ll>; using vi = vector<ll>; using pii = pair<pair<ll, ll>, ll>; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll n, k; ll a[maxn]; ll dp[maxn]; ll trace[maxn]; ll pre[maxn]; ll f(ll mid) { // dp[i] = max(dp[i-1],dp[j]+dp[i]-pre[j]+pre[i]-mid); dp[0] = 0; ll ma = 0; ll vt = 0; trace[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = 0; trace[i] = 0; } for (int i = 1; i <= n; i++) { if (dp[i - 1] <= ma + pre[i] - mid) { dp[i] = ma + pre[i] - mid; trace[i] = trace[vt] + 1; } else { dp[i] = dp[i - 1]; trace[i] = trace[i - 1]; } if (ma <= dp[i] - pre[i]) { ma = dp[i] - pre[i]; vt = i; } } return trace[n]; } void solve() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } ll l = -INF; ll r = INF; ll ans; ll ans1; while (l <= r) { ll mid = (l + r) / 2; if (f(mid) >= k) { ans = dp[n]; ans1 = mid; l = mid + 1; } else { r = mid - 1; } } if (ans1 <= 0) { f(0); cout << dp[n]; } else { cout << ans + ans1 * k; } } signed main() { cin.tie(0), cout.tie(0)->sync_with_stdio(0); solve(); }

Compilation message (stderr)

feast.cpp: In function 'void solve()':
feast.cpp:108:28: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |         cout << ans + ans1 * k;
      |                       ~~~~~^~~
feast.cpp:108:30: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |         cout << ans + ans1 * k;
      |                              ^
#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...