oj.uz

Submission #817714

# Submission time Handle Problem Language Result Execution time Memory
817714 2023-08-09T15:14:14 Z TB_ Measures (CEOI22_measures) C++17
59 / 100
 150 ms 7144 KB 
#include <bits/stdc++.h>
using namespace std;
 
// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")
 
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD
 
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(ll i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;
 
 
 
int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
 
    ll n, m, d, val;
    cin >> n >> m >> d;
    vl v(n);
    fo(i, n){
        cin >> v[i];
    }
    ll extra = 0;
  	pl maxMove = {-1e18, 1e18}; // max, -max
    fo(x, m){
        cin >> val;
        v.pb(val);
      	if(m>10){
          ll toMove = v[0]+x*d-v[x]+extra;
          if(toMove < maxMove.S){
            extra -= toMove;
            toMove = 0;
          }
          maxMove.F = max(toMove, maxMove.F);
          maxMove.S = min(toMove, maxMove.S);

          ll ans = maxMove.F-maxMove.S;
          if(ans%2 == 1) cout << fixed << setprecision(1) << ans/2.0 << " ";
          else cout << ans/2 << " ";
        }else{
          sort(all(v));

          maxMove = {-1e18, 1e18}; // max, -max
          fo(i, v.size()){
              ll toMove = v[0]+d*i-v[i]+extra;
              if(toMove < maxMove.S){
                  extra -= toMove;
                  toMove = 0;
              }
              maxMove.F = max(toMove, maxMove.F);
              maxMove.S = min(toMove, maxMove.S);
          }
          ll ans = maxMove.F-maxMove.S;
          if(ans%2 == 1) cout << fixed << setprecision(1) << ans/2.0 << " ";
          else cout << ans/2 << " ";
        }
    }
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 98 ms 4076 KB Output is correct
10 Correct 142 ms 4072 KB Output is correct
11 Correct 54 ms 4044 KB Output is correct
12 Correct 150 ms 4052 KB Output is correct
13 Correct 46 ms 4024 KB Output is correct
14 Correct 96 ms 4044 KB Output is correct
15 Correct 92 ms 4064 KB Output is correct
16 Correct 44 ms 4032 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4964 KB Output is correct
2 Correct 86 ms 6808 KB Output is correct
3 Correct 87 ms 6844 KB Output is correct
4 Correct 31 ms 4712 KB Output is correct
5 Correct 58 ms 5948 KB Output is correct
6 Correct 66 ms 5060 KB Output is correct
7 Correct 104 ms 6056 KB Output is correct
8 Correct 70 ms 4776 KB Output is correct
9 Correct 73 ms 4600 KB Output is correct
10 Correct 105 ms 7144 KB Output is correct
11 Correct 107 ms 5468 KB Output is correct
12 Correct 85 ms 6508 KB Output is correct
13 Correct 79 ms 4744 KB Output is correct
14 Correct 60 ms 6576 KB Output is correct
15 Correct 84 ms 6412 KB Output is correct
16 Correct 77 ms 4284 KB Output is correct
17 Correct 56 ms 5936 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4964 KB Output is correct
2 Correct 86 ms 6808 KB Output is correct
3 Correct 87 ms 6844 KB Output is correct
4 Correct 31 ms 4712 KB Output is correct
5 Correct 58 ms 5948 KB Output is correct
6 Correct 66 ms 5060 KB Output is correct
7 Correct 104 ms 6056 KB Output is correct
8 Correct 70 ms 4776 KB Output is correct
9 Correct 73 ms 4600 KB Output is correct
10 Correct 105 ms 7144 KB Output is correct
11 Correct 107 ms 5468 KB Output is correct
12 Correct 85 ms 6508 KB Output is correct
13 Correct 79 ms 4744 KB Output is correct
14 Correct 60 ms 6576 KB Output is correct
15 Correct 84 ms 6412 KB Output is correct
16 Correct 77 ms 4284 KB Output is correct
17 Correct 56 ms 5936 KB Output is correct
18 Incorrect 85 ms 6112 KB Output isn't correct
19 Halted 0 ms 0 KB -