Submission #1290305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290305		Killer2501	Feast (NOI19_feast)	C++20	12 / 100	84 ms	11088 KiB

feast

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
using ll = long long;
using namespace std;
#define pll pair<ll, int>

const int N = 1e6+5;
const long long inf = 1e15;
const int base = 311;
const long long mod =  998244353;
struct BIT{
    vector<int> fe;
    int n;
    BIT(int _n){
        n = _n;
        fe.resize(n + 1, 0);
    }
    ~BIT(){
        fe.clear();
    }
    void reset(){
        fill(fe.begin(), fe.end(), 0);
    }
    void update(int id, int v){
        for(; id <= n; id += id & -id)
            fe[id] += v;
    }
    int get(int id){
        int res = 0;
        for(; id; id -= id & -id)
            res += fe[id];
        return res;
    }
    int get(int l, int r){
        if(r > n)r = n;
        if(l > r) return 0;
        return get(r) - get(l - 1);
    }
};
int n, m, k, a[N], b[N], d[N];
vector<ll> vi;
vector<int> adj[N], edge[N];
pll dp[N][2];
pll check(ll pen){
    dp[0][0] = {0, 0};
    dp[0][1] = {-inf, 0};
    for(int i = 1; i <= n; i ++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = {-inf, 0};
        if(dp[i-1][0].fi > -inf){
            dp[i][1] = max(dp[i][1], {dp[i-1][0].fi + a[i] - pen, dp[i-1][0].se + 1});
        }
        if(dp[i-1][1].fi > -inf){
            dp[i][1] = max(dp[i][1], {dp[i-1][1].fi + a[i], dp[i-1][1].se });
        }
    }
    return max(dp[n][0], dp[n][1]);
}
void sol(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    ll l = 0, r = 1e9, mid;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid).se <= k){
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    pll ans = check(l);
    cout << ans.fi + l * k;
    


}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen("test.in", "r")) {
        freopen("test.in", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    // for(ll x: sub)cout << x << "\n";
    int ntest = 1;
    // cin >> ntest;
    while(ntest -- > 0)sol();
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("test.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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