제출 #169898

#제출 시각아이디문제언어결과실행 시간메모리
169898Retro3014Salesman (IOI09_salesman)C++17
40 / 100
1085 ms59056 KiB
#include <bits/stdc++.h> #define all(v) (v).begin(), (v).end() #define sortv(v) sort(all(v)) #define uniqv(v) (v).erase(unique(all(v)), (v).end()) #define pb push_back #define FI first #define SE second #define lb lower_bound #define ub upper_bound #define mp make_pair #define test 1 #define TEST if(test) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; const int MOD = 1000000007; // 998244353 const int INF = 2e9; const ll INFLL = 1000000000LL; const int MAX_N = 500001; int N; ll U, D, S; struct ST{ ll t, l, m; bool operator <(const ST &a)const{ if(t==a.t){ return l<a.l; } return t<a.t; } }; vector<ST> v; struct SEG{ struct NODE{ int l, r; ll mx; }; vector<NODE> seg; int SZ; void add(){seg.pb({-1, -1, -INFLL});} void Init(int x){ add(); SZ = x; } void Update(int x, int y, ll z){ update(0, 1, SZ, x, y, z); } void update(int idx, int s, int e, int x, int y, ll z){ if(x<=s && e<=y) { seg[idx].mx = max(seg[idx].mx, z); return; } if(x>e || y<s) return; if(seg[idx].l==-1){ seg[idx].l = seg.size(); add(); } if(seg[idx].r == -1){ seg[idx].r = seg.size(); add(); } update(seg[idx].l, s, (s+e)/2, x, y, z); update(seg[idx].r, (s+e)/2+1, e, x, y, z); } ll Mx(int x){ return mx(0, 1, SZ, x); } ll mx(int idx, int s, int e, int k){ if(idx==-1) return -INFLL; if(s==e) return seg[idx].mx; if(k<=(s+e)/2){ return max(seg[idx].mx, mx(seg[idx].l, s, (s+e)/2, k)); }else{ return max(seg[idx].mx, mx(seg[idx].r, (s+e)/2+1, e, k)); } } }Seg1, Seg2; vector<pair<ll, int> > vt; ll get(ll idx){ return max(Seg1.Mx((int)idx)+idx*U, Seg2.Mx((int)idx)-idx*D); } void Upd(ll idx, ll x){ Seg1.Update(1, (int)idx, x-idx*U); Seg2.Update((int)idx, MAX_N, x+idx*D); } int main(){ scanf("%d%lld%lld%lld", &N, &U, &D, &S); Seg1.Init(MAX_N); Seg2.Init(MAX_N); Upd(S, 0); for(int i=0; i<N; i++){ ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c); v.pb({a, b, c}); } sort(v.begin(), v.end()); int s = 0, e = 0; while(s<v.size()){ while(e+1<v.size() && v[e+1].t==v[s].t) e++; if(s==e){ Upd(v[s].l, get(v[s].l)+v[s].m); }else{ for(int i=s; i<=e; i++){ vt.pb({get(v[i].l), i}); } sort(vt.begin(), vt.end()); while(!vt.empty()){ int n = vt.back().second; vt.pop_back(); Upd(v[n].l, get(v[n].l)+v[n].m); } } s = e+1; e++; } cout<<get(S); return 0; }

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

salesman.cpp: In function 'int main()':
salesman.cpp:104:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(s<v.size()){
        ~^~~~~~~~~
salesman.cpp:105:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e+1<v.size() && v[e+1].t==v[s].t) e++;
         ~~~^~~~~~~~~
salesman.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld%lld", &N, &U, &D, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:99:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...