Submission #272928

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
272928	2020-08-18T20:08:35 Z	Haunted_Cpp	Discharging (NOI20_discharging)	C++17	38 / 100	354 ms	19960 KB

Discharging

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

class CHT {
private:
  typedef long long i64;
  struct Node {
    Node *l, *r;
    pair<i64, i64> line;
    Node() {
      l = r = nullptr;
      line = {1e9, 1e9};
    }
  };
  Node *root;
  const int LO, HI;
  long long f(const pair<i64, i64> line, int x) {
    return 1LL * x * line.first + line.second;
  }
  void add_line(pair<i64, i64> line, int l, int r, Node *seg) {
    const int mid = l + (r - l) / 2;
    bool esq = f(seg -> line, l) > f(line, l);
    bool middle = f(seg -> line, mid) > f(line, mid);
    if (middle) {
      swap(line, seg -> line);
    }
    if (l == r) return;
    if (esq == middle) {
      if (!seg -> r) seg -> r = new Node;
      add_line(line, mid + 1, r, seg -> r);
    } else {
      if (!seg -> l) seg -> l = new Node;
      add_line(line, l, mid, seg -> l);
    }
  }
  long long query(int l, int r, int where, Node *seg) {
    if (!seg) return 1e18;
    if (l == r) return f(seg -> line, where);
    const int mid = l + (r - l) / 2;
    if (where > mid) {
      return min(query(mid + 1, r, where, seg -> r), f(seg -> line, where));
    }
    return min(query(l, mid, where, seg -> l), f(seg -> line, where));
  }
public:
  CHT() : LO(0), HI(1e9 + 7) {
    root = new Node;
  }
  void add_line(pair<i64, i64> line) {
    add_line(line, LO, HI, root);
  }
  long long get_best(int where) {
    return query(LO, HI, where, root);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n;
  cin >> n;
  vector<int> arr(n + 1);
  for (int i = 1; i <= n; i++) cin >> arr[i];
  CHT seg;
  vector<long long> dp(n + 1);
  seg.add_line({0, 0});
  for (int i = 1; i <= n; i++) {
    dp[i] = 1LL * arr[i] * n + seg.get_best(arr[i]);
    seg.add_line({1LL * -i, dp[i]});
  }
  cout << dp[n] << '\n';
  return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	1 ms	512 KB	Output is correct
15	Correct	1 ms	532 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	1 ms	512 KB	Output is correct
15	Correct	1 ms	532 KB	Output is correct
16	Correct	313 ms	18264 KB	Output is correct
17	Correct	326 ms	19320 KB	Output is correct
18	Correct	318 ms	17528 KB	Output is correct
19	Correct	315 ms	18936 KB	Output is correct
20	Correct	316 ms	18884 KB	Output is correct
21	Correct	319 ms	19216 KB	Output is correct
22	Correct	326 ms	18552 KB	Output is correct
23	Correct	316 ms	19832 KB	Output is correct
24	Correct	354 ms	19192 KB	Output is correct
25	Correct	316 ms	19576 KB	Output is correct
26	Correct	323 ms	19960 KB	Output is correct
27	Correct	322 ms	18296 KB	Output is correct
28	Correct	312 ms	19192 KB	Output is correct
29	Correct	322 ms	19320 KB	Output is correct
30	Correct	325 ms	19896 KB	Output is correct