Submission #1290096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290096		sherwin	Feast (NOI19_feast)	C++20	100 / 100	86 ms	12160 KiB

feast

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> pa;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd __gcd
#define log __lg
#define upper upper_bound
#define lower lower_bound
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (((mask) >> (i)) & 1ll)
#define reset(a, val) memset(a, val, sizeof(a))
#define fu(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define int ll

constexpr int MOD = 1e9 + 7;
constexpr int mx = 3e5;
constexpr int maxn = 1 << 20;
constexpr int base = 311;
constexpr int box = 447;
constexpr int blockn = mx/box;
constexpr ld PI = acosl(-1);
constexpr int LOG = log(maxn);
constexpr ll inf = 1e18 + 173;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int Rand(int l, int r){
    return l + rd() % (r - l + 1);
}

template<typename T> inline bool maximize(T &res, const T &val){if (val > res){res = val; return true;} return false;}
template<typename T> inline bool minimize(T &res, const T &val){if (val < res){res = val; return true;} return false;}
template<typename T> inline T sqr(const T &val){return val * val;}

inline void add(int &a, int b){a += b; if (a >= MOD) a -= MOD;}
inline void sub(int &a, int b){a -= b; if (a < 0) a += MOD;}
inline int mul(const int &a, const int &b){return 1ll * (a%MOD) * (b%MOD) % MOD;}
inline int lcm(const int &a, const int &b){return 1ll * a * b / gcd(a, b) % MOD;}

//#define linear
//#define Ckn

#ifdef linear
    vector<int> prime;
    vector<int> lpf;

    void sieve(){
        prime.assign(1, 2);
        lpf.assign(maxn + 1, 2);
        lpf[0] = lpf[1] = 1;
        for (int i = 3; i <= maxn; i += 2){
            if (lpf[i] == 2) prime.pb(lpf[i] = i);
            for (int j = 0; j < (int)prime.size() && i * prime[j] <= maxn && prime[j] <= lpf[i]; ++j)
                lpf[prime[j] * i] = prime[j];
        }
    }
#endif

#ifdef Ckn
    int fact[mx + 5];
    int invm[mx + 5];
    int invf[mx + 5];

    void pre(){
        fact[1] = fact[0] = 1;
        invm[1] = invm[0] = 1;
        invf[1] = invf[0] = 1;
        fu(i, 2, mx){
            fact[i] = 1ll * fact[i - 1] * i % MOD;
            invm[i] = MOD - 1ll * MOD / i * invm[MOD % i] % MOD;
            invf[i] = 1ll * invf[i - 1] * invm[i] % MOD;
        }
    }

    int C(int k, int n){
        if (k > n || k < 0) return 0;
        return 1ll * fact[n] * invf[k] % MOD * invf[n - k] % MOD;
    }
#endif

int A[mx + 5];
pa dp[mx + 5][2];

void solve(){
    int n, k;
    cin >> n >> k;
    fu(i, 1, n) cin >> A[i];
    A[n + 1] = 0;
    int l = 0, r = inf;
    while (r != l){
        int mid = (l + r) >> 1;
        dp[0][0] = {0, 0};
        dp[0][1] = {-inf, -inf};
        fu(i, 1, n + 1){
            dp[i][1] = max(dp[i - 1][1], {dp[i - 1][0].fi - mid, dp[i - 1][0].se + 1});
            dp[i][1].fi += A[i];
            dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
        }
        if (dp[n + 1][0].se <= k) r = mid;
        else l = mid + 1;
    }   

    dp[0][0] = {0, 0};
    dp[0][1] = {-inf, -inf};
    fu(i, 1, n + 1){
        dp[i][1] = max(dp[i - 1][1], {dp[i - 1][0].fi - l, dp[i - 1][0].se + 1});
        dp[i][1].fi += A[i];
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
    }
    cout << dp[n + 1][0].fi + k * l;
}

signed main(){

    #define name "Sherwin"
    if (fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    #define name "graph"
    if (fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    #ifdef linear
        sieve();
    #endif

    #ifdef Ckn
        pre();
    #endif

    int testcase = 1;
    //cin >> testcase;
    while (testcase--){
        solve();
    }
}
/*

  /\__/\
 (=^.^= )
 (") (")_/

~~~-Sherwin-~~~

*/

Compilation message (stderr)

feast.cpp:130: warning: "name" redefined
  130 |     #define name "graph"
      | 
feast.cpp:124: note: this is the location of the previous definition
  124 |     #define name "Sherwin"
      | 
feast.cpp: In function 'int main()':
feast.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29