| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998438 |
2024-06-14T01:50:46 Z |
HUECTRUM |
Feast (NOI19_feast) |
C++14 |
|
171 ms |
12116 KB |
#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) {
pair<ll, ll> dp[n][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() {
int k; cin >> n >> k;
v = vll(n); rep(i, n) cin >> v[i];
ll l = 0, r = 1e18;
while (r - l > 1) {
ll mid = (l + r) / 2;
pll sol = solve(mid);
if (sol.second >= k) l = mid;
else r = mid - 1;
}
pll solveL = solve(l);
if (solveL.second == k) cout << solveL.first + k * l;
else cout << solve(r).first + k * l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
11600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
11832 KB |
Output is correct |
| 2 |
Correct |
85 ms |
12112 KB |
Output is correct |
| 3 |
Correct |
91 ms |
11860 KB |
Output is correct |
| 4 |
Incorrect |
86 ms |
11704 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
11860 KB |
Output is correct |
| 2 |
Correct |
146 ms |
11688 KB |
Output is correct |
| 3 |
Correct |
150 ms |
11952 KB |
Output is correct |
| 4 |
Correct |
144 ms |
11860 KB |
Output is correct |
| 5 |
Correct |
148 ms |
11952 KB |
Output is correct |
| 6 |
Correct |
154 ms |
11856 KB |
Output is correct |
| 7 |
Correct |
169 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
147 ms |
11860 KB |
Output is correct |
| 9 |
Correct |
149 ms |
12116 KB |
Output is correct |
| 10 |
Correct |
171 ms |
12000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
11600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
