oj.uz

Submission #209423

# Submission time Handle Problem Language Result Execution time Memory
209423 2020-03-14T07:32:55 Z model_code Solar Storm (NOI20_solarstorm) C++17
100 / 100
 435 ms 120880 KB 
#include <bits/stdc++.h>
using namespace std;

const int LOGN = 21, N = 1e6 + 5;
#define ll long long

ll A[N], prefix[N];
int V[N];
int nxt[N], before[N], parent[LOGN][N];

int n, s, ans_start;
ll ans = 0;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int diff;
  ll k;
  cin>>n>>s>>k;
  A[0] = 0;
  for(int i = 1; i < n; i++) {
    cin>>diff;
    A[i] = A[i - 1] + diff;
  }
  for(int i = 0; i < n; i++) {
    cin>>V[i];
    prefix[i] = (i == 0 ? 0 : prefix[i - 1]) + V[i];
  }
  prefix[n] = prefix[n - 1];
  A[n] = A[n - 1] + 2*k;
  int current_ptr = 0;
  nxt[n] = n;
  for(int i = 0; i < n; i++) {
    for(int j = current_ptr; j <= n; j++) {
      if(A[j] - A[i] > k) {
        current_ptr = j;
        nxt[i] = j;
        break;
      }
    }
  }
  current_ptr = n;
  for(int i = n; i >= 0; i--) {
    for(int j = current_ptr; j >= -1; j--) {
      if(j == -1 or A[i] - A[j] > k) {
        current_ptr = j;
        before[i] = j;
        break;
      }
    }
  }
  parent[0][n] = n;
  for(int i = 0; i < n; i++) {
    int jump_to = nxt[i];
    if(jump_to != n) {
      jump_to = nxt[jump_to] - 1;
    }
    parent[0][i] = jump_to;
  }
  for(int i = 1; i < LOGN; i++) {
    for(int j = 0; j <= n; j++) {
      parent[i][j] = parent[i - 1][parent[i - 1][j]];
    }
  }

  for(int i = 0; i < n; i++) {
    int l = before[i];
    int r = i;
    for(int j = LOGN - 1; j >= 0; j--) {
      if(((1 << j) & (s - 1)) != 0) {
        r = parent[j][r];
      }
    }
    ll candidate = prefix[nxt[r] - 1] - (l == -1 ? 0 : prefix[l]);
    if(candidate > ans) {
      ans = candidate;
      ans_start = i;
    }
  }

  vector<int> Q;
  for(int i = 0; i < s; i++) {
    Q.push_back(ans_start);
    ans_start = parent[0][ans_start];
    if(ans_start == n)  break;
  }
  cout<<Q.size()<<endl;
  for(auto v : Q) cout<<v + 1<<" ";
  cout<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 9 ms 1632 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 8 ms 1528 KB Output is correct
8 Correct 8 ms 1656 KB Output is correct
9 Correct 7 ms 1272 KB Output is correct
10 Correct 8 ms 1632 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 94456 KB Output is correct
2 Correct 178 ms 60248 KB Output is correct
3 Correct 180 ms 64504 KB Output is correct
4 Correct 198 ms 70308 KB Output is correct
5 Correct 217 ms 82332 KB Output is correct
6 Correct 302 ms 109704 KB Output is correct
7 Correct 206 ms 72544 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 9 ms 1632 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 8 ms 1528 KB Output is correct
8 Correct 8 ms 1656 KB Output is correct
9 Correct 7 ms 1272 KB Output is correct
10 Correct 8 ms 1632 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 275 ms 94456 KB Output is correct
14 Correct 178 ms 60248 KB Output is correct
15 Correct 180 ms 64504 KB Output is correct
16 Correct 198 ms 70308 KB Output is correct
17 Correct 217 ms 82332 KB Output is correct
18 Correct 302 ms 109704 KB Output is correct
19 Correct 206 ms 72544 KB Output is correct
20 Correct 210 ms 60152 KB Output is correct
21 Correct 233 ms 73612 KB Output is correct
22 Correct 279 ms 87296 KB Output is correct
23 Correct 271 ms 89924 KB Output is correct
24 Correct 262 ms 81272 KB Output is correct
25 Correct 274 ms 81272 KB Output is correct
26 Correct 198 ms 60664 KB Output is correct
27 Correct 239 ms 77816 KB Output is correct
28 Correct 255 ms 76920 KB Output is correct
29 Correct 344 ms 99916 KB Output is correct
30 Correct 284 ms 81844 KB Output is correct
31 Correct 252 ms 71864 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 94860 KB Output is correct
2 Correct 151 ms 56160 KB Output is correct
3 Correct 161 ms 60156 KB Output is correct
4 Correct 228 ms 86724 KB Output is correct
5 Correct 231 ms 84088 KB Output is correct
6 Correct 235 ms 89080 KB Output is correct
7 Correct 369 ms 115792 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 9 ms 1632 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 8 ms 1528 KB Output is correct
8 Correct 8 ms 1656 KB Output is correct
9 Correct 7 ms 1272 KB Output is correct
10 Correct 8 ms 1632 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 8 ms 1656 KB Output is correct
14 Correct 8 ms 1400 KB Output is correct
15 Correct 8 ms 1400 KB Output is correct
16 Correct 7 ms 1144 KB Output is correct
17 Correct 8 ms 1400 KB Output is correct
18 Correct 8 ms 1528 KB Output is correct
19 Correct 8 ms 1376 KB Output is correct
20 Correct 7 ms 1272 KB Output is correct
21 Correct 9 ms 1784 KB Output is correct
22 Correct 10 ms 1656 KB Output is correct
23 Correct 9 ms 1656 KB Output is correct
24 Correct 10 ms 1536 KB Output is correct
25 Correct 8 ms 1528 KB Output is correct
26 Correct 8 ms 1528 KB Output is correct
27 Correct 7 ms 1400 KB Output is correct
28 Correct 7 ms 1400 KB Output is correct
29 Correct 8 ms 1400 KB Output is correct
30 Correct 9 ms 1528 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 9 ms 1632 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 8 ms 1528 KB Output is correct
8 Correct 8 ms 1656 KB Output is correct
9 Correct 7 ms 1272 KB Output is correct
10 Correct 8 ms 1632 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 275 ms 94456 KB Output is correct
14 Correct 178 ms 60248 KB Output is correct
15 Correct 180 ms 64504 KB Output is correct
16 Correct 198 ms 70308 KB Output is correct
17 Correct 217 ms 82332 KB Output is correct
18 Correct 302 ms 109704 KB Output is correct
19 Correct 206 ms 72544 KB Output is correct
20 Correct 210 ms 60152 KB Output is correct
21 Correct 233 ms 73612 KB Output is correct
22 Correct 279 ms 87296 KB Output is correct
23 Correct 271 ms 89924 KB Output is correct
24 Correct 262 ms 81272 KB Output is correct
25 Correct 274 ms 81272 KB Output is correct
26 Correct 198 ms 60664 KB Output is correct
27 Correct 239 ms 77816 KB Output is correct
28 Correct 255 ms 76920 KB Output is correct
29 Correct 344 ms 99916 KB Output is correct
30 Correct 284 ms 81844 KB Output is correct
31 Correct 252 ms 71864 KB Output is correct
32 Correct 302 ms 95864 KB Output is correct
33 Correct 245 ms 73568 KB Output is correct
34 Correct 321 ms 101088 KB Output is correct
35 Correct 233 ms 61016 KB Output is correct
36 Correct 210 ms 65272 KB Output is correct
37 Correct 231 ms 71904 KB Output is correct
38 Correct 389 ms 109192 KB Output is correct
39 Correct 258 ms 82016 KB Output is correct
40 Correct 347 ms 109944 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 9 ms 1632 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 8 ms 1528 KB Output is correct
8 Correct 8 ms 1656 KB Output is correct
9 Correct 7 ms 1272 KB Output is correct
10 Correct 8 ms 1632 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 275 ms 94456 KB Output is correct
14 Correct 178 ms 60248 KB Output is correct
15 Correct 180 ms 64504 KB Output is correct
16 Correct 198 ms 70308 KB Output is correct
17 Correct 217 ms 82332 KB Output is correct
18 Correct 302 ms 109704 KB Output is correct
19 Correct 206 ms 72544 KB Output is correct
20 Correct 210 ms 60152 KB Output is correct
21 Correct 233 ms 73612 KB Output is correct
22 Correct 279 ms 87296 KB Output is correct
23 Correct 271 ms 89924 KB Output is correct
24 Correct 262 ms 81272 KB Output is correct
25 Correct 274 ms 81272 KB Output is correct
26 Correct 198 ms 60664 KB Output is correct
27 Correct 239 ms 77816 KB Output is correct
28 Correct 255 ms 76920 KB Output is correct
29 Correct 344 ms 99916 KB Output is correct
30 Correct 284 ms 81844 KB Output is correct
31 Correct 252 ms 71864 KB Output is correct
32 Correct 329 ms 94860 KB Output is correct
33 Correct 151 ms 56160 KB Output is correct
34 Correct 161 ms 60156 KB Output is correct
35 Correct 228 ms 86724 KB Output is correct
36 Correct 231 ms 84088 KB Output is correct
37 Correct 235 ms 89080 KB Output is correct
38 Correct 369 ms 115792 KB Output is correct
39 Correct 8 ms 1656 KB Output is correct
40 Correct 8 ms 1400 KB Output is correct
41 Correct 8 ms 1400 KB Output is correct
42 Correct 7 ms 1144 KB Output is correct
43 Correct 8 ms 1400 KB Output is correct
44 Correct 8 ms 1528 KB Output is correct
45 Correct 8 ms 1376 KB Output is correct
46 Correct 7 ms 1272 KB Output is correct
47 Correct 9 ms 1784 KB Output is correct
48 Correct 10 ms 1656 KB Output is correct
49 Correct 9 ms 1656 KB Output is correct
50 Correct 10 ms 1536 KB Output is correct
51 Correct 8 ms 1528 KB Output is correct
52 Correct 8 ms 1528 KB Output is correct
53 Correct 7 ms 1400 KB Output is correct
54 Correct 7 ms 1400 KB Output is correct
55 Correct 8 ms 1400 KB Output is correct
56 Correct 9 ms 1528 KB Output is correct
57 Correct 302 ms 95864 KB Output is correct
58 Correct 245 ms 73568 KB Output is correct
59 Correct 321 ms 101088 KB Output is correct
60 Correct 233 ms 61016 KB Output is correct
61 Correct 210 ms 65272 KB Output is correct
62 Correct 231 ms 71904 KB Output is correct
63 Correct 389 ms 109192 KB Output is correct
64 Correct 258 ms 82016 KB Output is correct
65 Correct 347 ms 109944 KB Output is correct
66 Correct 218 ms 65968 KB Output is correct
67 Correct 344 ms 94804 KB Output is correct
68 Correct 264 ms 66336 KB Output is correct
69 Correct 304 ms 86864 KB Output is correct
70 Correct 210 ms 68572 KB Output is correct
71 Correct 356 ms 109284 KB Output is correct
72 Correct 234 ms 69108 KB Output is correct
73 Correct 298 ms 90444 KB Output is correct
74 Correct 247 ms 56440 KB Output is correct
75 Correct 284 ms 92716 KB Output is correct
76 Correct 199 ms 64664 KB Output is correct
77 Correct 293 ms 86520 KB Output is correct
78 Correct 191 ms 61632 KB Output is correct
79 Correct 259 ms 79868 KB Output is correct
80 Correct 317 ms 99872 KB Output is correct
81 Correct 237 ms 65876 KB Output is correct
82 Correct 398 ms 83428 KB Output is correct
83 Correct 185 ms 55672 KB Output is correct
84 Correct 216 ms 60352 KB Output is correct
85 Correct 193 ms 56416 KB Output is correct
86 Correct 323 ms 99404 KB Output is correct
87 Correct 215 ms 56684 KB Output is correct
88 Correct 321 ms 99576 KB Output is correct
89 Correct 253 ms 80636 KB Output is correct
90 Correct 223 ms 73116 KB Output is correct
91 Correct 435 ms 120880 KB Output is correct
92 Correct 346 ms 110812 KB Output is correct
93 Correct 385 ms 115816 KB Output is correct
94 Correct 417 ms 115816 KB Output is correct
95 Correct 321 ms 98144 KB Output is correct
96 Correct 280 ms 77188 KB Output is correct
97 Correct 349 ms 105204 KB Output is correct
98 Correct 259 ms 70640 KB Output is correct
99 Correct 336 ms 81240 KB Output is correct
100 Correct 277 ms 78628 KB Output is correct