제출 #401211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401211		Fidisk	Feast (NOI19_feast)	C++14	30 / 100	94 ms	13368 KiB

feast

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

#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;

struct comp{
    bool operator() (pll x,pll y) {
        return x.fi>y.fi;
    }
};

priority_queue<pll,vector<pll>,comp> heap;
ll n,k,i,a[400009],tmp,b[400009],m,l[400009],r[400009],res,cnt,cur;
bool ok[400009];

int main(){
    IO;
    cin>>n>>k;
    for (i=1;i<=n;i++) {
        cin>>a[i];
    }
    for (i=1;i<=n;i++) {
        if (a[i]*a[i-1]<0) {
            m++;
            b[m]=cur;
            cur=a[i];
        }
        else {
            cur+=a[i];
        }
    }
    m++;
    b[m]=cur;
    for (i=1;i<=m;i++) {
        l[i]=i+1;
        r[i]=i-1;
        if (b[i]>0) {
            cnt++;
        }
        heap.push({abs(b[i]),i});
    }
    while (cnt>k) {
        ll y=heap.top().fi;
        ll x=heap.top().se;
        heap.pop();
        if (ok[x]) continue;
        tmp=0;
        if (b[x]>0) {
            tmp++;
        }
        if (b[r[x]]>0) {
            tmp++;
        }
        if (b[l[x]]>0) {
            tmp++;
        }
        if (b[x]+b[l[x]]+b[r[x]]>0) {
            tmp--;
        }
        cnt-=tmp;
        ok[l[x]]=true;
        ok[r[x]]=true;
        b[x]=b[l[x]]+b[r[x]]+b[x];
        l[x]=l[l[x]];
        r[x]=r[r[x]];
        if (l[x]!=0) {
            r[l[x]]=x;
        }
        if (r[x]!=0) {
            l[r[x]]=x;
        }
        heap.push({abs(b[x]),x});
    }
    for (i=1;i<=m;i++) {
        if (!ok[i]&&b[i]>0) {
            res+=b[i];
        }
    }
    cout<<res<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'int main()':
feast.cpp:65:12: warning: unused variable 'y' [-Wunused-variable]
   65 |         ll y=heap.top().fi;
      |            ^

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