제출 #520563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520563		krit3379	Divide and conquer (IZhO14_divide)	C++17	100 / 100	40 ms	6500 KiB

divide

#include<bits/stdc++.h>
using namespace std;
#define N 100005
using pii = pair<long long,long long>;

long long x[N],g[N],p[N],ans;
deque<pii> dq;

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld %lld %lld",&x[i],&g[i],&p[i]);
        ans=max(ans,g[i]);
        g[i]+=g[i-1];
        p[i]+=p[i-1];
    }
    for(i=n;i>0;i--){
        auto it=lower_bound(dq.begin(),dq.end(),(pii){p[i-1]-x[i],-1});
        if(it!=dq.end())ans=max(ans,(*it).second-g[i-1]);
        if(dq.empty()||p[i]-x[i]>dq.back().first)dq.push_back({p[i]-x[i],g[i]});
    }
    printf("%lld",ans);
    return 0;
}

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

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

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52