Submission #1205951

#TimeUsernameProblemLanguageResultExecution timeMemory
1205951repmannRestore Array (RMI19_restore)C++20
13 / 100
104 ms844 KiB
#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)}); } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...