oj.uz

Submission #923804

# Submission time Handle Problem Language Result Execution time Memory
923804 2024-02-07T19:35:40 Z aykhn Restore Array (RMI19_restore) C++17
7 / 100
 600 ms 1512 KB 
#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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 1480 KB Output is correct
2 Correct 325 ms 1504 KB Output is correct
3 Correct 335 ms 1508 KB Output is correct
4 Correct 328 ms 1512 KB Output is correct
5 Execution timed out 719 ms 1508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 1480 KB Output is correct
2 Correct 325 ms 1504 KB Output is correct
3 Correct 335 ms 1508 KB Output is correct
4 Correct 328 ms 1512 KB Output is correct
5 Execution timed out 719 ms 1508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 315 ms 1480 KB Output is correct
12 Correct 325 ms 1504 KB Output is correct
13 Correct 335 ms 1508 KB Output is correct
14 Correct 328 ms 1512 KB Output is correct
15 Execution timed out 719 ms 1508 KB Time limit exceeded
16 Halted 0 ms 0 KB -