제출 #138455

#제출 시각아이디문제언어결과실행 시간메모리
138455baluteshihSalesman (IOI09_salesman)C++14
62 / 100
596 ms25564 KiB
#include <bits/stdc++.h> #define pb push_back #define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ET cout << "\n" #define F first #define S second #define MP make_pair #define ALL(v) v.begin(),v.end() #define MEM memset(i,j,sizeof i) #define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;} using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; struct mode { int ti,pl,earn; bool operator<(const mode &a)const{ if(ti==a.ti) return pl<a.pl; return ti<a.ti; } }arr[500005]; const int INF=2e9,MAXC=500001; pii seg[2000005]; int dp[500005]; void build(int l,int r,int rt) { seg[rt]=MP(-INF,-INF); if(l==r) return; int m=l+r>>1; build(l,m,rt<<1),build(m+1,r,rt<<1|1); } void modify(int x,int l,int r,int rt,pii v) { if(l==r) return seg[rt].F=max(seg[rt].F,v.F),seg[rt].S=max(seg[rt].S,v.S),void(); int m=l+r>>1; if(x<=m) modify(x,l,m,rt<<1,v); else modify(x,m+1,r,rt<<1|1,v); seg[rt]=MP(max(seg[rt<<1].F,seg[rt<<1|1].F),max(seg[rt<<1].S,seg[rt<<1|1].S)); } pii query(int L,int R,int l,int r,int rt) { if(L<=l&&R>=r) return seg[rt]; int m=l+r>>1; if(R<=m) return query(L,R,l,m,rt<<1); if(L>m) return query(L,R,m+1,r,rt<<1|1); auto a=query(L,R,l,m,rt<<1),b=query(L,R,m+1,r,rt<<1|1); return MP(max(a.F,b.F),max(a.S,b.S)); } int main() {jizz int n,u,d,s; cin >> n >> u >> d >> arr[0].pl; for(int i=1;i<=n;++i) cin >> arr[i].ti >> arr[i].pl >> arr[i].earn; build(1,MAXC,1),sort(arr+1,arr+n+1),modify(arr[0].pl,1,MAXC,1,MP(arr[0].pl*d,-arr[0].pl*u)); for(int i=1;i<=n;++i) { dp[i]=max(query(1,arr[i].pl,1,MAXC,1).F-arr[i].pl*d,query(arr[i].pl,MAXC,1,MAXC,1).S+arr[i].pl*u)+arr[i].earn; modify(arr[i].pl,1,MAXC,1,MP(dp[i]+arr[i].pl*d,dp[i]-arr[i].pl*u)); } cout << max(query(1,arr[0].pl,1,MAXC,1).F-arr[0].pl*d,query(arr[0].pl,MAXC,1,MAXC,1).S+arr[0].pl*u) << "\n"; }

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

salesman.cpp: In function 'void build(int, int, int)':
salesman.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'void modify(int, int, int, int, pii)':
salesman.cpp:41:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'pii query(int, int, int, int, int)':
salesman.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'int main()':
salesman.cpp:60:12: warning: unused variable 's' [-Wunused-variable]
  int n,u,d,s;
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...