oj.uz

Submission #1113272

# Submission time Handle Problem Language Result Execution time Memory
1113272 2024-11-16T09:27:02 Z Master Line Town (CCO23_day1problem3) C++17
3 / 25
 2000 ms 9764 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int N = 500'000 + 10,
          MAX = 1'000'000'000'000'000;
int n;
int h[N];
 
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> h[i];
 
  int answer = MAX;
  for (int negNum = 0; negNum <= n; ++negNum) { 
    
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      if (i & 1) { 
        if (h[i] == 1) even.push_back(i);
        else odd.push_back(i);
      } else { 
        if (h[i] == 1) odd.push_back(i);
        else even.push_back(i);
      }
    }
 
    int total = 0;
    for (int i = 1; i <= negNum; ++i) { 
      auto& vt = (i & 1 ? odd : even);
      if (!vt.size()) { total = MAX; break; }
      
      total += max(0ll, vt.front() - i);
      vt.pop_front();
    }
    for (int i = negNum + 1; i <= n; ++i) { 
      auto& vt = ((i ^ 1) & 1 ? odd : even);
      if (!vt.size()) { total = MAX; break; }
      
      total += max(0ll, vt.front() - i);
      vt.pop_front();
    }
    
    answer = min(answer, total);
  }
 
  cout << (answer == MAX ? -1 : answer) << "\n";
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 22 ms 508 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 21 ms 592 KB Output is correct
9 Correct 20 ms 508 KB Output is correct
10 Correct 22 ms 516 KB Output is correct
11 Correct 18 ms 336 KB Output is correct
12 Correct 20 ms 512 KB Output is correct
13 Correct 22 ms 512 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 22 ms 508 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 21 ms 592 KB Output is correct
9 Correct 20 ms 508 KB Output is correct
10 Correct 22 ms 516 KB Output is correct
11 Correct 18 ms 336 KB Output is correct
12 Correct 20 ms 512 KB Output is correct
13 Correct 22 ms 512 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Execution timed out 2067 ms 9764 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 22 ms 508 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 21 ms 592 KB Output is correct
9 Correct 20 ms 508 KB Output is correct
10 Correct 22 ms 516 KB Output is correct
11 Correct 18 ms 336 KB Output is correct
12 Correct 20 ms 512 KB Output is correct
13 Correct 22 ms 512 KB Output is correct
14 Incorrect 1 ms 336 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 22 ms 508 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 21 ms 592 KB Output is correct
9 Correct 20 ms 508 KB Output is correct
10 Correct 22 ms 516 KB Output is correct
11 Correct 18 ms 336 KB Output is correct
12 Correct 20 ms 512 KB Output is correct
13 Correct 22 ms 512 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Execution timed out 2067 ms 9764 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

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

Subtask #6
0 / 3.0

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

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 22 ms 508 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 21 ms 592 KB Output is correct
9 Correct 20 ms 508 KB Output is correct
10 Correct 22 ms 516 KB Output is correct
11 Correct 18 ms 336 KB Output is correct
12 Correct 20 ms 512 KB Output is correct
13 Correct 22 ms 512 KB Output is correct
14 Incorrect 1 ms 336 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 22 ms 508 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 21 ms 592 KB Output is correct
9 Correct 20 ms 508 KB Output is correct
10 Correct 22 ms 516 KB Output is correct
11 Correct 18 ms 336 KB Output is correct
12 Correct 20 ms 512 KB Output is correct
13 Correct 22 ms 512 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Execution timed out 2067 ms 9764 KB Time limit exceeded
16 Halted 0 ms 0 KB -