Submission #1193864

#TimeUsernameProblemLanguageResultExecution timeMemory
1193864MkswllFeast (NOI19_feast)C++20
41 / 100
1096 ms35268 KiB
// I will become better someday. #include <bits/stdc++.h> using namespace std; typedef unsigned int uint; typedef unsigned long long ull; typedef long long ll; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, int> pli; typedef pair <int, ll> pil; typedef pair <ll, ll> pll; typedef pair <ld, ld> pdd; #define debug(x) cout << '[' << #x << ": " << x << "] " #define cio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define cases int _; cin >> _; while(_--) #define pb push_back #define eb emplace_back #define space << " " << #define lb lower_bound #define ub upper_bound #define F first #define S second #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define Unique(v) v.erase(unique(all(v)), v.end()) #define mset(x) memset(x, 0, sizeof(x)) #define sflush fflush(stdout) #define cflush cout.flush() #define yes cout << "YES\n" #define no cout << "NO\n" #define lyes cout << "Yes\n" #define lno cout << "No\n" #define nl cout << "\n"; #define vt vector #define ar array #define uid uniform_int_distribution template <typename T> istream& operator >> (istream& in, vector<T>& a){ for(auto &x : a) in >> x; return in; } template <typename T> ostream& operator << (ostream& out, vector<T>& a){ for(auto &x : a) out << x << ' '; return out; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); ll read(){ int w = 1, c; ll ret; while((c = getchar()) > '9' || c < '0'){ w = (c == '-' ? -1 : 1); } ret = c - '0'; while((c = getchar()) >= '0' && c <= '9'){ ret = ret * 10 + c - '0'; } return ret * w; } ll rd(){ ll in; cin >> in; return in; } void write(ll x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9){ write(x / 10); } putchar(x % 10 + '0'); } #define int long long const int MAXN = 3e5 + 5, MAXM = 2e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7; const ll LMOD = (ll) 1e18 + 9; const ll LINF = 1e18 + 5; const ld ep = 1e-8, Pi = acos(-1.0); int n, m, k, x; int a[MAXN]; string s; pli solve(ll pen){ vt dp(n + 1, vt <ll> (2, 0)); vt cdp(n + 1, vt <int> (2, 0)); dp[0][1] = -LINF; cdp[0][1] = 1; for(int i = 1; i <= n; ++i){ dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); if(dp[i][0] == dp[i - 1][0]) cdp[i][0] = max(cdp[i][0], cdp[i - 1][0]); if(dp[i][0] == dp[i - 1][1]) cdp[i][0] = max(cdp[i][1], cdp[i - 1][1]); dp[i][1] = max(dp[i - 1][0] + a[i] - pen, dp[i - 1][1] + a[i]); if(dp[i][1] == dp[i - 1][0] + a[i] - pen) cdp[i][1] = max(cdp[i][1], cdp[i - 1][0] + 1); if(dp[i][1] == dp[i - 1][1] + a[i]) cdp[i][1] = max(cdp[i][1], cdp[i - 1][1]); } return max((pli) {dp[n][0], cdp[n][0]}, (pli) {dp[n][1], cdp[n][1]}); } void clear(){ } signed main(){ cio; cin >> n >> k; int cnt = 0; ll sm = 0; for(int i = 1; i <= n; ++i){ cin >> a[i]; // if(a[i] >= 0){ // ++cnt; // sm += a[i]; // } } // if(cnt <= k){ // cout << sm << "\n"; // return 0; // } ll l = 0, r = 1e18, ans = 0; while(l <= r){ ll mid = (l + r) >> 1; auto res = solve(mid); if(res.S >= k){ ans = mid; l = mid + 1; } else r = mid - 1; } auto res = solve(ans); cout << res.F + ans * k << "\n"; return 0; }
#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...