Submission #568387

#	Time	Username	Problem	Language	Result	Execution time	Memory
568387		gs15120	Safety (NOI18_safety)	C++14	100 / 100	60 ms	7028 KiB

safety

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <cassert>
#include <thread>
#include <tuple>
#include <typeindex>
  

using namespace std;
#define ll long long
#define lll long long//__int128
#define pii pair<int,int>
#define pdi pair<double,int>
#define f first
#define s second
# define pi 3.14159265358979323846

const ll inf=1987654321987654321;
int a,b;
ll o[222222];
priority_queue<ll> l;
priority_queue<ll,vector<ll>,greater<ll>> r;

int main()
{
  scanf("%d %d",&a,&b);
  for(int t=1;t<=a;t++)
    scanf("%lld",&o[t]);
    
  ll ans=0;
  l.push(o[1]);
  r.push(o[1]);
  
  for(int t=2;t<=a;t++)
  {
    ll x=l.top()-(ll)(t-1)*b,y=r.top()+(ll)(t-1)*b;
    if(x<=o[t]&&o[t]<=y)
    {
      l.push(o[t]+(ll)(t-1)*b);
      r.push(o[t]-(ll)(t-1)*b);
    }
    else if(o[t]<x)
    {
      ans+=x-o[t];
      l.push(o[t]+(ll)(t-1)*b);
      l.push(o[t]+(ll)(t-1)*b);
      
      r.push(x-(ll)(t-1)*b);
      l.pop();
    }
    else
    {
      ans+=o[t]-y;
      
      r.push(o[t]-(ll)(t-1)*b);
      r.push(o[t]-(ll)(t-1)*b);
      
      l.push(y+(ll)(t-1)*b);
      r.pop();
    }
  }
  printf("%lld",ans);
}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d %d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~
safety.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%lld",&o[t]);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29