제출 #1105018

#제출 시각아이디문제언어결과실행 시간메모리
1105018salmonSalesman (IOI09_salesman)C++14
2 / 100
495 ms35304 KiB
#include <bits/stdc++.h> using namespace std; int N; int D,U; int S; vector<pair<int,int>> f[500100]; int best[500100]; map<int,int> sat; const int inf = 2.1e9; int retrieve(int p){ int num = -inf; if(sat.find(p) != sat.end()){ auto it = sat.find(p); num = it -> second; } else{ auto it = sat.lower_bound(p); if(it != sat.end()){ num = max(num, it -> second - U * (it -> first - p) ); } if(it != sat.begin()){ advance(it,-1); num = max(num, it -> second - D * (p - it -> first) ); } } return num; } int main(){ scanf(" %d",&N); scanf(" %d",&U); scanf(" %d",&D); scanf(" %d",&S); for(int i = 0; i < N; i++){ int T,L,M; scanf(" %d",&T); scanf(" %d",&L); scanf(" %d",&M); f[T].push_back({L,M}); } sat.insert({S,0}); for(int i = 1; i < 500100; i++){ sort(f[i].begin(),f[i].end()); if(f[i].empty()) continue; int past = -inf; for(int j = 0; j < f[i].size(); j++){ int num = retrieve(f[i][j].first) + f[i][j].first * D; if(j == 0) best[j] = num + f[i][j].second; else{ best[j] = max(best[j - 1], num) + f[i][j].second; } } for(int j = 0; j < f[i].size(); j++){ best[j] -= f[i][j].first * D; } for(int j = f[i].size() - 1; j >= 0; j--){ past = max(past, retrieve(f[i][j].first) - f[i][j].first * U) + f[i][j].second; best[j] = max(best[j], past + f[i][j].first * U); } for(int j = 0; j < f[i].size(); j++){ pair<int,int> ii = f[i][j]; int num = best[j]; sat.erase(ii.first); if(retrieve(ii.first) >= ii.second){ continue; } while(true){ auto it = sat.lower_bound(ii.first); if(it == sat.end()) break; if(it -> second <= num - (it -> first - ii.first) * D ){ sat.erase(it); } else break; } while(true){ auto it = sat.lower_bound(ii.first); if(it == sat.begin()) break; advance(it,-1); if(it -> second <= num - (ii.first - it -> first) * U ){ sat.erase(it); } else break; } sat.insert({ii.first, num}); } } auto it = sat.lower_bound(S); int ans = -inf; if(it != sat.end()){ ans = max(ans, it -> second - U * (it -> first - S) ); } if(it != sat.begin()){ advance(it,-1); ans = max(ans, it -> second - D * (S - it -> first)); } printf("%d",ans); }

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

salesman.cpp: In function 'int main()':
salesman.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j = 0; j < f[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
salesman.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j = 0; j < f[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
salesman.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j = 0; j < f[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
salesman.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf(" %d",&U);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf(" %d",&D);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf(" %d",&T);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf(" %d",&L);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...