제출 #53582

#제출 시각아이디문제언어결과실행 시간메모리
53582ho94949Salesman (IOI09_salesman)C++17
100 / 100
962 ms36836 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 524288; const int INF = 0x3f3f3f3f; //day, place, price vector<pair<int, int> > market[MAXN]; struct Tree { int idx[2*MAXN]; void init() { memset(idx, 0xc0, sizeof idx); } void setv(int a, int v) { a += MAXN; idx[a]=max(idx[a], v); while((a=a/2)) idx[a] = max(idx[2*a], idx[2*a+1]); } int getv(int a, int b) { a += MAXN; b += MAXN; int res = -INF; while(a<=b) { if(a%2==1) res = max(res, idx[a++]); if(b%2==0) res = max(res, idx[b--]); a /= 2; b /= 2; } return res; } }UTree, DTree; int N, U, D, S; void setv(int a, int v) { DTree.setv(a, v+D*a); UTree.setv(a, v-U*a); } int getv(int a) { int ans = max(DTree.getv(0, a) - D*a, UTree.getv(a, MAXN-1) + U*a); return ans; } void solve(vector<pair<int, int> >& market) { if(market.size() == 0) return; sort(market.begin(), market.end()); vector<int> Uv(market.size()); vector<int> Dv(market.size()); for(int i=0; i<market.size(); ++i) Uv[i] = Dv[i] = getv(market[i].first); for(int i=0; i<market.size(); ++i) { if(i != 0) Dv[i] = max(Dv[i], Dv[i-1] - D*(market[i].first-market[i-1].first)); Dv[i] += market[i].second; } for(int i=market.size()-1; i>=0; --i) { if(i != market.size()-1) Uv[i] = max(Uv[i], Uv[i+1] - U*(market[i+1].first-market[i].first)); Uv[i] += market[i].second; } for(int i=0; i<market.size(); ++i) setv(market[i].first, max(Dv[i], Uv[i])); } int main() { int St; scanf("%d%d%d%d", &N, &U, &D, &S); for(int i=0; i<N; ++i) { int t, l, m; scanf("%d%d%d", &t, &l, &m); market[t].emplace_back(l, m); } UTree.init(); DTree.init(); setv(S, 0); for(int i=1; i<=500001; ++i) solve(market[i]); printf("%d\n", getv(S)); }

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

salesman.cpp: In function 'void solve(std::vector<std::pair<int, int> >&)':
salesman.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<market.size(); ++i)
               ~^~~~~~~~~~~~~~
salesman.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<market.size(); ++i)
               ~^~~~~~~~~~~~~~
salesman.cpp:64:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i != market.size()-1)
      ~~^~~~~~~~~~~~~~~~~~
salesman.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<market.size(); ++i)
               ~^~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:74:6: warning: unused variable 'St' [-Wunused-variable]
  int St;
      ^~
salesman.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &U, &D, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:78:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t, l, m; scanf("%d%d%d", &t, &l, &m);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...