제출 #1205952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205952		repmann	Restore Array (RMI19_restore)	C++20	20 / 100	155 ms	988 KiB

restore

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M;
struct EDGE
{
  int u, v;
  ll w;
};
vector <EDGE> E;
ll DP[5096];
inline bool BellmanFord()
{
  DP[0] = 0;
  for(int i = 1; i <= N; i++) DP[i] = 1e18;
  for(int i = 1; i <= N; i++) {for(EDGE e : E) DP[e.v] = min(DP[e.u] + e.w, DP[e.v]);}
  for(EDGE e : E) if((DP[e.u] + e.w) < DP[e.v]) return true;
  return false;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> M;
  int L, R, K, X;
  for(int i = 1; i <= M; i++)
  {
    cin >> L >> R >> K >> X;
    L++;
    R++;
    if(X) E.push_back({R, L - 1, -(R - L - K + 2)});
    else
    {
      E.push_back({L - 1, R, +(R - L - K + 1)});
      E.push_back({R, L - 1, +0});
    }
  }
  for(int i = 1; i <= N; i++) E.push_back({i - 1, i, +1});
  if(BellmanFord()) {cout << "-1\n"; return 0;}
  for(int i = 1; i <= N; i++) cout << (DP[i] - DP[i - 1]) << " \n"[i == N];

  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55