| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998432 |
2024-06-14T01:41:46 Z |
HUECTRUM |
Feast (NOI19_feast) |
C++14 |
|
1000 ms |
35156 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) {
vvll dp(n, vll(2)), cnt(n, vll(2));
dp[0][0] = 0, cnt[0][0] = 0;
dp[0][1] = v[0] - lambda, cnt[0][1] = 1;
reps(i, 1, n) {
if (dp[i - 1][1] > dp[i - 1][0]) dp[i][0] = dp[i - 1][1], cnt[i][0] = cnt[i - 1][1];
else dp[i][0] = dp[i - 1][0], cnt[i][0] = cnt[i - 1][0];
ll cut = dp[i - 1][0] + v[i] - lambda, fill = dp[i - 1][1] + v[i];
if (cut > fill) dp[i][1] = cut, cnt[i][1] = cnt[i - 1][0] + 1;
else dp[i][1] = fill, cnt[i][1] = cnt[i - 1][1];
}
if (dp[n - 1][1] > dp[n - 1][0]) return {dp[n - 1][1], cnt[n - 1][1]};
else return {dp[n - 1][0], cnt[n - 1][0]};
}
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) >> 1;
pll sol = solve(mid);
if (sol.second >= k) l = mid;
else r = mid - 1;
}
pll lSol = solve(l), rSol = solve(r);
pll fSol = lSol.second == k ? lSol : rSol;
cout << fSol.first + fSol.second * l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
34532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1034 ms |
34796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1055 ms |
35156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
34532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
