oj.uz

Submission #256937

# Submission time Handle Problem Language Result Execution time Memory
256937 2020-08-03T12:14:34 Z Bruteforceman Discharging (NOI20_discharging) C++11
72 / 100
 615 ms 245216 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const long long inf = 1e16;
long long dp[maxn];
int a[maxn];
int n;

struct hull {
  vector <long long> M, C;
  int pt;
  hull() {
    pt = 0;
  }
  bool bad(int i, int j, int k) {
    return (C[k] - C[j]) * (M[i] - M[k]) <= (C[k] - C[i]) * (M[j] - M[k]);
  }
  void add(long long m, long long c) {
    M.push_back(m);
    C.push_back(c);
    while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
      M.erase(M.end() - 2);
      C.erase(C.end() - 2);
    }
    pt = min(pt, int(M.size()) - 1);
  }
  long long eval(long long x) {
    if(M.size() == 0) return inf;
    while(pt + 1 < M.size() && 
        M[pt] * x + C[pt] >= M[pt + 1] * x + C[pt + 1]) {
      ++pt;
    }
    return M[pt] * x + C[pt];
  }
} t[maxn * 4];
void update(int x, int c = 1, int b = 0, int e = n) {
  if(c == 1) t[c].add(n - x, dp[x]);
  if(b == e) {
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) update(x, l, b, m);
  else update(x, r, m + 1, e);
}
long long query(int x, int y, int val, int c = 1, int b = 0, int e = n) {
  if(x <= b && e <= y) {
    return t[c].eval(val);
  }
  if(y < b || e < x) return inf;
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return min(query(x, y, val, l, b, m), query(x, y, val, r, m + 1, e));
}
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
  vector <int> v ({0});
  a[0] = INT_MAX;
  update(0);
  dp[0] = inf;
  for(int i = 1; i <= n; i++) {
    while(a[v.back()] <= a[i]) {
      v.pop_back();
    }
    dp[i] = min(dp[v.back()], query(v.back(), n, a[i]));
    update(i);
    v.push_back(i);
  }
  printf("%lld\n", dp[n]);
  return 0;
}

Compilation message

Discharging.cpp: In member function 'long long int hull::eval(long long int)':
Discharging.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pt + 1 < M.size() && 
           ~~~~~~~^~~~~~~~~~
Discharging.cpp: In function 'int main()':
Discharging.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
Discharging.cpp:59:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
                               ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 219512 KB Output is correct
2 Correct 118 ms 219516 KB Output is correct
3 Correct 119 ms 219512 KB Output is correct
4 Correct 123 ms 219512 KB Output is correct
5 Correct 116 ms 219512 KB Output is correct
6 Correct 124 ms 219512 KB Output is correct
7 Correct 124 ms 219512 KB Output is correct
8 Correct 126 ms 219512 KB Output is correct
9 Correct 130 ms 219640 KB Output is correct
10 Correct 120 ms 219512 KB Output is correct
11 Correct 127 ms 219512 KB Output is correct
12 Correct 121 ms 219512 KB Output is correct
13 Correct 127 ms 219640 KB Output is correct
14 Correct 129 ms 219512 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 219676 KB Output is correct
2 Correct 130 ms 219512 KB Output is correct
3 Correct 132 ms 219496 KB Output is correct
4 Correct 124 ms 219512 KB Output is correct
5 Correct 144 ms 219552 KB Output is correct
6 Correct 126 ms 219512 KB Output is correct
7 Correct 130 ms 219512 KB Output is correct
8 Correct 138 ms 219512 KB Output is correct
9 Correct 140 ms 219476 KB Output is correct
10 Correct 128 ms 219512 KB Output is correct
11 Correct 123 ms 219544 KB Output is correct
12 Correct 134 ms 219512 KB Output is correct
13 Correct 124 ms 219516 KB Output is correct
14 Correct 133 ms 219512 KB Output is correct
15 Correct 139 ms 219508 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 219676 KB Output is correct
2 Correct 130 ms 219512 KB Output is correct
3 Correct 132 ms 219496 KB Output is correct
4 Correct 124 ms 219512 KB Output is correct
5 Correct 144 ms 219552 KB Output is correct
6 Correct 126 ms 219512 KB Output is correct
7 Correct 130 ms 219512 KB Output is correct
8 Correct 138 ms 219512 KB Output is correct
9 Correct 140 ms 219476 KB Output is correct
10 Correct 128 ms 219512 KB Output is correct
11 Correct 123 ms 219544 KB Output is correct
12 Correct 134 ms 219512 KB Output is correct
13 Correct 124 ms 219516 KB Output is correct
14 Correct 133 ms 219512 KB Output is correct
15 Correct 139 ms 219508 KB Output is correct
16 Correct 366 ms 231928 KB Output is correct
17 Correct 358 ms 237176 KB Output is correct
18 Correct 351 ms 235620 KB Output is correct
19 Correct 362 ms 237052 KB Output is correct
20 Correct 356 ms 236920 KB Output is correct
21 Correct 370 ms 237048 KB Output is correct
22 Correct 361 ms 236664 KB Output is correct
23 Correct 367 ms 237688 KB Output is correct
24 Correct 360 ms 237176 KB Output is correct
25 Correct 369 ms 237592 KB Output is correct
26 Correct 377 ms 237816 KB Output is correct
27 Correct 354 ms 236408 KB Output is correct
28 Correct 367 ms 237176 KB Output is correct
29 Correct 363 ms 237432 KB Output is correct
30 Correct 375 ms 237688 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 236260 KB Output is correct
2 Correct 591 ms 244920 KB Output is correct
3 Correct 555 ms 245036 KB Output is correct
4 Correct 574 ms 245216 KB Output is correct
5 Correct 565 ms 244956 KB Output is correct
6 Correct 559 ms 244956 KB Output is correct
7 Correct 554 ms 244956 KB Output is correct
8 Correct 562 ms 244964 KB Output is correct
9 Correct 561 ms 244956 KB Output is correct
10 Correct 557 ms 244956 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 219512 KB Output is correct
2 Correct 118 ms 219516 KB Output is correct
3 Correct 119 ms 219512 KB Output is correct
4 Correct 123 ms 219512 KB Output is correct
5 Correct 116 ms 219512 KB Output is correct
6 Correct 124 ms 219512 KB Output is correct
7 Correct 124 ms 219512 KB Output is correct
8 Correct 126 ms 219512 KB Output is correct
9 Correct 130 ms 219640 KB Output is correct
10 Correct 120 ms 219512 KB Output is correct
11 Correct 127 ms 219512 KB Output is correct
12 Correct 121 ms 219512 KB Output is correct
13 Correct 127 ms 219640 KB Output is correct
14 Correct 129 ms 219512 KB Output is correct
15 Correct 128 ms 219676 KB Output is correct
16 Correct 130 ms 219512 KB Output is correct
17 Correct 132 ms 219496 KB Output is correct
18 Correct 124 ms 219512 KB Output is correct
19 Correct 144 ms 219552 KB Output is correct
20 Correct 126 ms 219512 KB Output is correct
21 Correct 130 ms 219512 KB Output is correct
22 Correct 138 ms 219512 KB Output is correct
23 Correct 140 ms 219476 KB Output is correct
24 Correct 128 ms 219512 KB Output is correct
25 Correct 123 ms 219544 KB Output is correct
26 Correct 134 ms 219512 KB Output is correct
27 Correct 124 ms 219516 KB Output is correct
28 Correct 133 ms 219512 KB Output is correct
29 Correct 139 ms 219508 KB Output is correct
30 Correct 126 ms 219588 KB Output is correct
31 Correct 132 ms 219536 KB Output is correct
32 Correct 125 ms 219488 KB Output is correct
33 Correct 124 ms 219516 KB Output is correct
34 Correct 123 ms 219512 KB Output is correct
35 Correct 128 ms 219512 KB Output is correct
36 Correct 123 ms 219512 KB Output is correct
37 Correct 123 ms 219512 KB Output is correct
38 Correct 121 ms 219640 KB Output is correct
39 Correct 124 ms 219640 KB Output is correct
40 Correct 127 ms 219592 KB Output is correct
41 Correct 129 ms 219512 KB Output is correct
42 Correct 124 ms 219512 KB Output is correct
43 Correct 124 ms 219516 KB Output is correct
44 Correct 137 ms 219472 KB Output is correct
45 Correct 135 ms 219512 KB Output is correct
46 Correct 131 ms 219512 KB Output is correct
47 Correct 132 ms 219512 KB Output is correct
48 Correct 131 ms 219512 KB Output is correct
49 Correct 123 ms 219512 KB Output is correct
50 Correct 122 ms 219512 KB Output is correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 219512 KB Output is correct
2 Correct 118 ms 219516 KB Output is correct
3 Correct 119 ms 219512 KB Output is correct
4 Correct 123 ms 219512 KB Output is correct
5 Correct 116 ms 219512 KB Output is correct
6 Correct 124 ms 219512 KB Output is correct
7 Correct 124 ms 219512 KB Output is correct
8 Correct 126 ms 219512 KB Output is correct
9 Correct 130 ms 219640 KB Output is correct
10 Correct 120 ms 219512 KB Output is correct
11 Correct 127 ms 219512 KB Output is correct
12 Correct 121 ms 219512 KB Output is correct
13 Correct 127 ms 219640 KB Output is correct
14 Correct 129 ms 219512 KB Output is correct
15 Correct 128 ms 219676 KB Output is correct
16 Correct 130 ms 219512 KB Output is correct
17 Correct 132 ms 219496 KB Output is correct
18 Correct 124 ms 219512 KB Output is correct
19 Correct 144 ms 219552 KB Output is correct
20 Correct 126 ms 219512 KB Output is correct
21 Correct 130 ms 219512 KB Output is correct
22 Correct 138 ms 219512 KB Output is correct
23 Correct 140 ms 219476 KB Output is correct
24 Correct 128 ms 219512 KB Output is correct
25 Correct 123 ms 219544 KB Output is correct
26 Correct 134 ms 219512 KB Output is correct
27 Correct 124 ms 219516 KB Output is correct
28 Correct 133 ms 219512 KB Output is correct
29 Correct 139 ms 219508 KB Output is correct
30 Correct 366 ms 231928 KB Output is correct
31 Correct 358 ms 237176 KB Output is correct
32 Correct 351 ms 235620 KB Output is correct
33 Correct 362 ms 237052 KB Output is correct
34 Correct 356 ms 236920 KB Output is correct
35 Correct 370 ms 237048 KB Output is correct
36 Correct 361 ms 236664 KB Output is correct
37 Correct 367 ms 237688 KB Output is correct
38 Correct 360 ms 237176 KB Output is correct
39 Correct 369 ms 237592 KB Output is correct
40 Correct 377 ms 237816 KB Output is correct
41 Correct 354 ms 236408 KB Output is correct
42 Correct 367 ms 237176 KB Output is correct
43 Correct 363 ms 237432 KB Output is correct
44 Correct 375 ms 237688 KB Output is correct
45 Correct 615 ms 236260 KB Output is correct
46 Correct 591 ms 244920 KB Output is correct
47 Correct 555 ms 245036 KB Output is correct
48 Correct 574 ms 245216 KB Output is correct
49 Correct 565 ms 244956 KB Output is correct
50 Correct 559 ms 244956 KB Output is correct
51 Correct 554 ms 244956 KB Output is correct
52 Correct 562 ms 244964 KB Output is correct
53 Correct 561 ms 244956 KB Output is correct
54 Correct 557 ms 244956 KB Output is correct
55 Correct 126 ms 219588 KB Output is correct
56 Correct 132 ms 219536 KB Output is correct
57 Correct 125 ms 219488 KB Output is correct
58 Correct 124 ms 219516 KB Output is correct
59 Correct 123 ms 219512 KB Output is correct
60 Correct 128 ms 219512 KB Output is correct
61 Correct 123 ms 219512 KB Output is correct
62 Correct 123 ms 219512 KB Output is correct
63 Correct 121 ms 219640 KB Output is correct
64 Correct 124 ms 219640 KB Output is correct
65 Correct 127 ms 219592 KB Output is correct
66 Correct 129 ms 219512 KB Output is correct
67 Correct 124 ms 219512 KB Output is correct
68 Correct 124 ms 219516 KB Output is correct
69 Correct 137 ms 219472 KB Output is correct
70 Correct 135 ms 219512 KB Output is correct
71 Correct 131 ms 219512 KB Output is correct
72 Correct 132 ms 219512 KB Output is correct
73 Correct 131 ms 219512 KB Output is correct
74 Correct 123 ms 219512 KB Output is correct
75 Correct 122 ms 219512 KB Output is correct
76 Correct 575 ms 237256 KB Output is correct
77 Incorrect 576 ms 237316 KB Output isn't correct
78 Halted 0 ms 0 KB -