Submission #923804

#	Time	Username	Problem	Language	Result	Execution time	Memory
923804		aykhn	Restore Array (RMI19_restore)	C++17	7 / 100	719 ms	1512 KiB

restore

#include <bits/stdc++.h>
// author: aykhn
using namespace std;
#define int long long
#define inf 0x3F3F3F3F

const int MXN = 5e3 + 5;

int n, m;
vector<array<int, 2>> adj[MXN];
int dist[MXN];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        adj[i].push_back({i + 1, 1});
        adj[i + 1].push_back({i, 0});
    }
    for (int i = 1; i <= n; i++) dist[i] = inf;
    while (m--)
    {
        int l, r, k, v;
        cin >> l >> r >> k >> v;
        r++;
        int sz = r - l;
        if (v == 1)
        {
            int mx = sz;
            int mn = sz - k + 1;
            adj[l].push_back({r, sz});
            adj[r].push_back({l, -mn});
        }
        else
        {
            int mn = 0;
            int mx = sz - k;
            adj[l].push_back({r, mx});
            adj[r].push_back({l, -mn});
        }
    }
    int f = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        f = 0;
        for (int j = 0; j <= n; j++)
        {
            for (const array<int, 2> &x : adj[j])
            {
                if (dist[j] + x[1] < dist[x[0]]) f = 1;
                dist[x[0]] = min(dist[x[0]], dist[j] + x[1]);
            }
        }
    }
    if (f)
    {
        cout << -1 << '\n';
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << dist[i] - dist[i - 1] << ' ';
    }
    cout << '\n';
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:32:17: warning: unused variable 'mx' [-Wunused-variable]
   32 |             int mx = sz;
      |                 ^~

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