제출 #998446

#제출 시각아이디문제언어결과실행 시간메모리
998446HUECTRUMFeast (NOI19_feast)C++14
100 / 100
972 ms27036 KiB
#include <iostream> #include <utility> #include <vector> #include <algorithm> #include <numeric> #include <map> #include <unordered_set> #include <iostream> #include <utility> #include <vector> #include <algorithm> #include <numeric> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <set> #include <stack> #include <fstream> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <bitset> #include <sstream> #include <ext/rope> #include <ctime> #include <random> #include <cstdlib> #include <complex> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; /* clang-format off */ /* TYPES */ #define ll long long #define pii pair<int, int> #define pll pair<long long, long long> #define vi vector<int> #define vll vector<long long> #define vpii vector<pair<int, int>> #define vpii vector<pair<int, int>> #define vvpii vector<vector<pair<int, int>>> #define vpll vector<pair<long long, long long>> #define vvpll vector<vector<pair<long long, long long>>> #define vvi vector<vector<int>> #define vvll vector<vector<long long>> #define mii map<int, int> #define si set<int> #define sc set<char> /* FUNCTIONS */ #define feach(el, v) for(auto &el: v) #define rep(i, n) for(int i=0;i<n;i++) #define reprv(i, n) for(int i=n-1;i>=0;i--) #define reps(i, s, e) for(int i=s;i<e;i++) #define reprve(i, e, s) for(int i=e-1;i>=s;i--) #define repe(x, y) for (auto &x: y) #define repe2(x, a, y) for (auto &[x,a]: y) typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> oSet; const ll mod = 1e9 + 7; template<ll mod = 1000000007> struct ModInt { ll p; ModInt() : p(0) {} ModInt(ll x) { p = x >= 0 ? x % mod : x + (-x + mod - 1) / mod * mod; } ModInt &operator+=(const ModInt &y) { p = p + *y - ((p + *y) >= mod ? mod : 0); return *this; } ModInt &operator-=(const ModInt &y) { p = p - *y + (p - *y < 0 ? mod : 0); return *this; } ModInt &operator*=(const ModInt &y) { p = (p * *y) % mod; return *this; } ModInt &operator%=(const ModInt &y) { if (y)p %= *y; return *this; } ModInt operator+(const ModInt &y) const { ModInt x = *this; return x += y; } ModInt operator-(const ModInt &y) const { ModInt x = *this; return x -= y; } ModInt operator*(const ModInt &y) const { ModInt x = *this; return x *= y; } ModInt operator%(const ModInt &y) const { ModInt x = *this; return x %= y; } ModInt binpow(const ModInt &y, ll pow) const { pow %= mod - 1; ModInt res = 1, a = y; while (pow) { if (pow & 1) res *= a; a *= a, pow >>= 1; } return res; } ModInt inv() const { return binpow(*this, mod - 2); } ModInt &operator/=(const ModInt &y) { p = (p * y.inv().p) % mod; return *this; } ModInt operator/(const ModInt &y) const { ModInt x = *this; return x /= y; } friend istream &operator>>(istream &is, ModInt &a) { int v; is >> v; a = ModInt(v); return is; } friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.p; } ModInt &operator++() { p = (p + 1) % mod; return *this; } ModInt &operator--() { p = (p - 1 + mod) % mod; return *this; } bool operator==(const ModInt &y) const { return p == *y; } bool operator!=(const ModInt &y) const { return p != *y; } const ll &operator*() const { return p; } ll &operator*() { return p; } }; using Mint = ModInt<>; #define vmint vector<Mint> #pragma GCC target("popcnt") ////////////////////////////////////////////////////////////////////////// int n; vll v; pll solve(ll lambda) { vvpll dp(n, vpll(2)); dp[0][0] = {0, 0}, dp[0][1] = {v[0] - lambda, 1}; reps(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].first + v[i] - lambda, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + v[i], dp[i - 1][1].second) ); } return max(dp[n - 1][0], dp[n - 1][1]); } int main() { ll k; cin >> n >> k; v = vll(n); rep(i, n) cin >> v[i]; ll l = 0, r = 1e18; while (r > l) { ll mid = (l + r + 1) / 2; pll sol = solve(mid); if (sol.second >= k) l = mid; else r = mid - 1; } pll sL = solve(l); cout << sL.first + k * l; }
#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...