Submission #1255148

#TimeUsernameProblemLanguageResultExecution timeMemory
1255148hungeazyFeast (NOI19_feast)C++20
100 / 100
110 ms12172 KiB
/* * @Author: hungeazy * @Date: 2025-08-08 22:07:03 * @Last Modified by: hungeazy * @Last Modified time: 2025-08-08 22:13:57 */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") using namespace std; using namespace __gnu_pbds; bool M1; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define ll long long #define ull unsigned long long #define sz(x) x.size() #define sqr(x) (1LL * (x) * (x)) #define all(x) x.begin(), x.end() #define fill(f,x) memset(f,x,sizeof(f)) #define FOR(i,l,r) for(int i=l;i<=r;i++) #define FOD(i,r,l) for(int i=r;i>=l;i--) #define debug(x) cout << #x << " = " << x << '\n' #define ii pair<int,int> #define iii pair<int,ii> #define di pair<ii,ii> #define vi vector<int> #define vii vector<ii> #define mii map<int,int> #define fi first #define se second #define pb push_back #define MOD 1000000007 #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define YES cout << "YES\n" #define NO cout << "NO\n" #define MASK(i) (1LL << (i)) #define c_bit(i) __builtin_popcountll(i) #define BIT(x,i) ((x) & MASK(i)) #define SET_ON(x,i) ((x) | MASK(i)) #define SET_OFF(x,i) ((x) & ~MASK(i)) #define oo 1e18 #define name "" #define endl '\n' #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>; const int N = (int)3e5+10; int n,k,a[N]; namespace hungeazy { ii dp[N][2]; ii calc(int lambda) { dp[0][1] = {-oo,-oo}; FOR(i,1,n) { dp[i][0] = max(dp[i-1][0],dp[i-1][1]); dp[i][1] = max(make_pair(dp[i-1][0].fi+a[i]-lambda,dp[i-1][0].se+1), make_pair(dp[i-1][1].fi+a[i],dp[i-1][1].se)); } return max(dp[n][0],dp[n][1]); } void solve(void) { int l = 1, r = 1e18, ans = 0; while (l <= r) { int mid = (l+r)>>1; if (calc(mid).se >= k) ans = mid, l = mid+1; else r = mid-1; } cout << calc(ans).fi+k*ans; } } bool M2; signed main() { fast; if (fopen(name".inp","r")) { freopen(name".inp","r",stdin); freopen(name".out","w",stdout); } cin >> n >> k; FOR(i,1,n) cin >> a[i]; hungeazy::solve(); time(); memory(); return 0; } // ██░ ██ █ ██ ███▄ █ ▄████ //▓██░ ██▒ ██ ▓██▒ ██ ▀█ █ ██▒ ▀█▒ //▒██▀▀██░▓██ ▒██░▓██ ▀█ ██▒▒██░▄▄▄░ //░▓█ ░██ ▓▓█ ░██░▓██▒ ▐▌██▒░▓█ ██▓ //░▓█▒░██▓▒▒█████▓ ▒██░ ▓██░░▒▓███▀▒ // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░ ▒ ▒ ░▒ ▒ // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░ ░ ▒░ ░ ░ // ░ ░░ ░ ░░░ ░ ░ ░ ░ ░ ░ ░ ░ // ░ ░ ░ ░ ░ ░

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name".out","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...