Submission #993885

#TimeUsernameProblemLanguageResultExecution timeMemory
993885Savu_Stefan_CatalinSafety (NOI18_safety)C++14
71 / 100
65 ms10080 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #define int long long using namespace std; const int NMAX=2e5+505; int n,h,a[NMAX+5]; priority_queue <int> q1; priority_queue <int,vector<int>,greater<int> > q2; vector <int> v; signed main() { ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); cin>>n>>h; for (int i=1;i<=n;++i) { cin>>a[i]; } q1.push(a[1]); q2.push(a[1]); int sum1=0,sum2=0; for (int i=2;i<=n;++i) { sum1+=h; sum2+=h; int x=q1.top(),y=q2.top(); x-=sum1; y+=sum2; int val=a[i]; if (val<=x) { q1.pop(); q1.push(val+sum1); q1.push(val+sum1); q2.push(x-sum2); } else if (val>y) { q2.pop(); q2.push(val-sum2); q2.push(val-sum2); q1.push(y+sum1); } else { q1.push(val+sum1); q2.push(val-sum2); } } int ss=0; for (int i=1;i<=n;++i) { ss+=a[i]; } while (!q1.empty()) {v.push_back(q1.top()); q1.pop();} reverse(v.begin(),v.end()); int ras=ss+(((-h*(n-1)))+(-(v[0]-sum1))*2)*n/2; for (int i=1;i<v.size();++i) { ras-=(v[i]-v[i-1])*(n-i); } cout<<ras; return 0; }

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i=1;i<v.size();++i)
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...