제출 #133799

#제출 시각아이디문제언어결과실행 시간메모리
133799figter001Salesman (IOI09_salesman)C++17
41 / 100
975 ms48248 KiB
#include <bits/stdc++.h> using namespace std; #define debug(x) '[' << #x << " is: " << x << "] " typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int nax = 5e5 + 100; vector<pair<int,int>> e[nax]; ll n,U,D,s,len; ll up[4*nax],dn[4*nax]; ll dp[nax]; void init(){ for(int i=1;i<=len;i++)dp[i] = -1e10; dp[s] = 0; } void build(int n,int s,int e){ if(s == e){ up[n] = dp[s] + s * U; dn[n] = dp[s] - s * D; return; } build(n*2,s,(s+e)/2); build(n*2+1,(s+e)/2+1,e); up[n] = max(up[n*2] , up[n*2+1]); dn[n] = max(dn[n*2] , dn[n*2+1]); } void update(int n,int s,int e,int at){ if(s > at || e < at)return; if(s == e){ up[n] = dp[s] - s * U; dn[n] = dp[s] + s * D; return; } update(n*2,s,(s+e)/2,at); update(n*2+1,(s+e)/2+1,e,at); up[n] = max(up[n*2] , up[n*2+1]); dn[n] = max(dn[n*2] , dn[n*2+1]); } ll get(int n,int s,int e,int l,int r,int t){ if(s > r || e < l)return -1e18; if(s >= l && e <= r){ if(t == 0)return up[n]; else if(t == 1)return dn[n]; } return max( get(n*2,s,(s+e)/2,l,r,t) , get(n*2+1,(s+e)/2+1,e,l,r,t) ); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout << fixed; cin>>n>>U>>D>>s; len = s; e[0].push_back({s,0}); int mxd=0; for(int i=1;i<n;i++){ int d,l,m; cin>>d>>l>>m; e[d].push_back({l,m}); len = max(len,1ll*l); mxd = max(mxd,d); } mxd++; e[mxd].push_back({s,0}); len++; init(); build(1,1,len); for(int day=0;day<=mxd;day++){ if(e[day].empty())continue; if(e[day].size() == 1){ int l = e[day][0].first; int m = e[day][0].second; ll cur = -1e18; if(day != 0){ cur = max(cur, get(1,1,len,1,l,1) + m - D*l); cur = max(cur, get(1,1,len,l,len,0) + m + U*l); } dp[l] = max(dp[l],cur); update(1,1,len,l); }else{ } } cout << dp[s] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...