oj.uz

Submission #672888

# Submission time Handle Problem Language Result Execution time Memory
672888 2022-12-18T20:41:07 Z MilosMilutinovic Restore Array (RMI19_restore) C++14
0 / 100
 142 ms 916 KB 
/**
 *    author:  wxhtzdy
 *    created: 18.12.2022 21:11:23
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> q;
  for (int i = 0; i < m; i++) {
    int l, r, k, v;
    cin >> l >> r >> k >> v;
    int len = r - l + 1;
    if (v == 0) {
      q.emplace_back(l, r, len - k);
    }
    if (v == 1) {
      q.emplace_back(r, l, -(len - k + 1));
    }
  }
  for (int i = 0; i < n - 1; i++) {
    q.emplace_back(i, i + 1, 1);
    q.emplace_back(i + 1, i, 0);
  }
  const long long inf = (long long) 1e18;
  vector<long long> d(n, inf);
  d[0] = 0;
  for (int iter = 0; iter < n + 1; iter++) {
    bool any = false;
    for (auto& p : q) {
      int i = get<0>(p);
      int j = get<1>(p);
      int w = get<2>(p);
      if (d[i] < inf && d[j] > d[i] + w) {
        d[j] = max(-inf, d[i] + w);          
        any = true;
      }
    }
    if (iter == n && any) {
      cout << -1 << '\n';
      return 0;
    }
  }
  int prv = 0;
  for (int i = 0; i < n; i++) {
    cout << d[i] - prv << " ";
    prv = d[i];
  }
  cout << '\n';
  return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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