제출 #347065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347065		inwbear	Candies (JOI18_candies)	C++14	0 / 100	1 ms	492 KiB

candies

#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,x,ps,nw,k,kk;
LL ans[100005],nn[200005][2],bs[200005],ss[200005][2],mx;
priority_queue<pii>pq;
bitset<200005>uu;
int F(int x)
{
    if(x==bs[x])return x;
    else return bs[x]=F(bs[x]);
}
void un(int x,int y)
{
    if(nn[x][0]==nn[x][1])
    {
        nn[x][0]+=nn[y][0];
        nn[x][1]+=nn[y][1];
        ss[x][0]+=ss[y][0];
        ss[x][1]+=ss[y][1];
    }
    else
    {
        nn[x][0]+=nn[y][1];
        nn[x][1]+=nn[y][0];
        ss[x][0]+=ss[y][1];
        ss[x][1]+=ss[y][0];
    }
    bs[y]=x;
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        bs[i]=i;
        scanf("%d",&x);
        pq.push({x,i});
    }
    while(!pq.empty())
    {
        x=pq.top().F;
        ps=pq.top().S;
        pq.pop();
        uu[ps]=true;
        nn[ps][0]=1;
        ss[ps][0]=x;
        mx+=x;
        nw++;
        if(uu[ps-1])
        {
            k=F(ps-1);
            kk=F(ps);
            if(nn[k][0]==nn[k][1])mx-=max(ss[k][0],ss[k][1]);
            else mx-=ss[k][0];
            if(nn[kk][0]==nn[kk][1])mx-=max(ss[kk][0],ss[kk][1]);
            else mx-=ss[kk][0];
            nw-=nn[k][0];
            nw-=nn[kk][0];
            un(k,kk);
            if(nn[k][0]==nn[k][1])mx+=max(ss[k][0],ss[k][1]);
            else mx+=ss[k][0];
            nw+=nn[k][0];
        }
        if(uu[ps+1])
        {
            k=F(ps);
            kk=F(ps+1);
            if(nn[k][0]==nn[k][1])mx-=max(ss[k][0],ss[k][1]);
            else mx-=ss[k][0];
            if(nn[kk][0]==nn[kk][1])mx-=max(ss[kk][0],ss[kk][1]);
            else mx-=ss[kk][0];
            nw-=nn[k][0];
            nw-=nn[kk][0];
            un(k,kk);
            if(nn[k][0]==nn[k][1])mx+=max(ss[k][0],ss[k][1]);
            else mx+=ss[k][0];
            nw+=nn[k][0];
        }
        ans[nw]=max(ans[nw],mx);
    }
    for(int i=1;i<=(n+1)/2;i++)
    {
        printf("%lld\n",ans[i]);
    }
}

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

candies.cpp: In function 'int main()':
candies.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
candies.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92