Submission #1264543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264543		thanhcodedao	Feast (NOI19_feast)	C++20	53 / 100	66 ms	12104 KiB

feast

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

#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 21
typedef long long ll;
const ll maxN = 3e5+3, modd = 1e9+7;
struct Point{
    ll x,y;
};
ll cross(Point p,Point q,Point r){ // vi tri r voi duong pq >0 la ben trai, =0 la thang hang
    ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
ll dot(Point vecA,Point vecB){ // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc
    ll val = vecA.x*vecB.x + vecA.y*vecB.y;
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
double triarea(Point p,Point q,Point r){ // cross(pq * pr) / 2
    double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    return fabs(cross)/2.0;
}
/* de cho
    cho n so nguyen, chon k day lien tiep sao cho tong lon nhat
*/
/* nhan xet nho
    ban dau khong quan tam can qtam chon k hay k+999 day
    su dung pair dp[i][0/1] = {sum,cnt} de chon dp lon nhat
    voi alien trick hay trick he so phat
    ta chat nhi phan 1 he so phat C, moi khi chuyen tu 0 sang 1 thi he so phat se duoc tinh 1 lan vao sum
    vi he so phat cang lon thi dp se cang chon it phan tu
    vi bai toan lay max nen he so phat se tru vao
    nen ta co the truy nguoc sum_real = sum - C*cnt
    neu dp[n].cnt <=k  => giam he so C
    nguoc => tang he so C
*/
/* nhan xet tu thuat trau
*/
int n,k;
ll a[maxN];
pair<ll,int> mxpa(pair<ll,int> p1,pair<ll,int> p2){
    if(p1.F == p2.F){
        if(p1.S < p2.S) return p1;
        return p2;
    }
    if(p1.F > p2.F) {
        return p1;
    }else{
        return p2;
    }

}
pair<ll,int> calc(ll c){
    pair<ll,int> f[n+3][2];
    f[1][0] = {0,0};
    f[1][1] = {a[1]-c,1};
    for(int i = 2;i<=n;i++){
        f[i][1] = mxpa({f[i-1][0].F + a[i] - c,f[i-1][0].S + 1}, {f[i-1][1].F + a[i],f[i-1][1].S});
        f[i][0] = mxpa(f[i-1][0],f[i-1][1]);
    }
    return mxpa(f[n][0],f[n][1]);
}
void solve() {
    cin >> n >> k;
    for(int i = 1;i<=n;i++) cin >> a[i];
    ll ans = 0;
    ll l = 0, r = 1e10;
    while(l<=r){
        ll cmid = (l+r)/2;
        pair<ll,int> dp = calc(cmid);
        if(dp.S <= k){
            ll sum = dp.F + cmid*dp.S;
            ans = max(ans,sum);
            r = cmid-1;
        }else{
            l = cmid+1;
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    //freopen("inp.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}

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