Submission #966903

#	Time	Username	Problem	Language	Result	Execution time	Memory
966903		AtabayRajabli	Restore Array (RMI19_restore)	C++17	100 / 100	330 ms	1620 KiB

restore

#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#define GCD(a, b)   __gcd(a, b)
#define LCM(a, b)   (a*b / (__gcd(a, b)))
#define int         ll

typedef long long           ll;
typedef long double         ld;
const int inf =             1e9 + 7;
const int inff =            (int)1e18 + 7;
const int sz =              5e3 + 5;
using namespace             std;

int n, m, l, r, k, v;
vector<array<int, 3>> e;
vector<int> d(sz, inf);

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        e.push_back({i, i + 1, 1});
        e.push_back({i + 1, i, 0});
    }
    while(m--)
    {
        cin >> l >> r >> k >> v;
        if(!v) e.push_back({l, r + 1, r - l + 1 - k});
        else e.push_back({r + 1, l, -(r - l + 1 - k + 1)});
    }
    d[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(auto p : e)
        {
            if(d[p[0]] + p[2] < d[p[1]])
            {
                d[p[1]] = d[p[0]] + p[2];
                if(i == n)
                {
                    cout << -1;
                    return 0;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) cout << d[i] - d[i - 1] << ' ';
}

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