oj.uz

Submission #923812

# Submission time Handle Problem Language Result Execution time Memory
923812 2024-02-07T19:45:41 Z aykhn Restore Array (RMI19_restore) C++17
7 / 100
 600 ms 1620 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 1 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 318 ms 1368 KB Output is correct
2 Correct 314 ms 1376 KB Output is correct
3 Correct 307 ms 1620 KB Output is correct
4 Correct 318 ms 1372 KB Output is correct
5 Execution timed out 702 ms 1392 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 1368 KB Output is correct
2 Correct 314 ms 1376 KB Output is correct
3 Correct 307 ms 1620 KB Output is correct
4 Correct 318 ms 1372 KB Output is correct
5 Execution timed out 702 ms 1392 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 318 ms 1368 KB Output is correct
12 Correct 314 ms 1376 KB Output is correct
13 Correct 307 ms 1620 KB Output is correct
14 Correct 318 ms 1372 KB Output is correct
15 Execution timed out 702 ms 1392 KB Time limit exceeded
16 Halted 0 ms 0 KB -