oj.uz

Submission #568331

# Submission time Handle Problem Language Result Execution time Memory
568331 2022-05-25T08:37:39 Z gs15120 Safety (NOI18_safety) C++17
0 / 100
 23 ms 6564 KB 
#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;
ll ans;

int main()
{
  scanf("%d %d",&a,&b);
  for(int t=1;t<=a;t++)
    scanf("%lld",&o[t]);
  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);
      //ll z=l.top();
      r.push(x-(ll)(t-1)*b);
      l.top();
    }
    else
    {
      ans+=o[t]-y;
      
      r.push(o[t]-(ll)(t-1)*b);
      r.push(o[t]-(ll)(t-1)*b);
      //ll z=r.top();
      l.push(y+(ll)(t-1)*b);
      r.top();
    }
  }
  printf("%lld\n",ans);
}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 6564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -