oj.uz

Submission #998440

# Submission time Handle Problem Language Result Execution time Memory
998440 2024-06-14T01:52:49 Z HUECTRUM Feast (NOI19_feast) C++14
18 / 100
 161 ms 12368 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() {
    ll 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 sL = solve(l), sR = solve(r);
    if (sL.second == k && sR.second == k) cout << max(sL.first, sR.first) + k * l;
    else if (sL.second == k) cout << sL.first + k * l;
    else cout << sR.first + k * l;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11860 KB Output is correct
2 Correct 86 ms 12368 KB Output is correct
3 Correct 81 ms 11604 KB Output is correct
4 Incorrect 84 ms 11856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 11860 KB Output is correct
2 Correct 147 ms 11688 KB Output is correct
3 Correct 151 ms 11856 KB Output is correct
4 Correct 161 ms 11856 KB Output is correct
5 Correct 143 ms 11856 KB Output is correct
6 Correct 146 ms 11856 KB Output is correct
7 Correct 148 ms 11860 KB Output is correct
8 Correct 152 ms 11956 KB Output is correct
9 Correct 148 ms 11996 KB Output is correct
10 Correct 147 ms 11856 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -