oj.uz

Submission #1105666

# Submission time Handle Problem Language Result Execution time Memory
1105666 2024-10-27T09:07:45 Z cpptowin Safety (NOI18_safety) C++17
24 / 100
 2000 ms 86856 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 5010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if(x < 0) x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if(x < 0) x += mod;
}
struct SegmentTree
{
    vector<int> st;
    int n;
    /// real n
    SegmentTree(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10,0);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10,0);
    }
    void update(int id, int l, int r, int x, int val)
    {
        if (x > r or x < l)
            return;
        if (l == r)
        {
            st[id] += val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, x, val);
        update(id << 1 | 1, mid + 1, r, x, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }
    void assign(int id, int l, int r, int x, int val)
    {
        if (x > r or x < l)
            return;
        if (l == r)
        {
            st[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        assign(id << 1, l, mid, x, val);
        assign(id << 1 | 1, mid + 1, r, x, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return 1e9;
        if (u <= l && r <= v)
            return st[id];
        int mid = (l + r) >> 1;
        return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    int walkright(int id, int l, int r, int x, int val)
    {
        if (st[id] >= val)
            return -1;
        if (r < x)
            return -1;
        if (l == r)
            return l;
        int ans = -1;
        int mid = (l + r) >> 1;
        if (st[id << 1] < val)
            ans = walkright(id << 1, l, mid, x, val);
        if (ans == -1)
            ans = walkright(id << 1 | 1, mid + 1, r, x, val);
        return ans;
    }
    int walkleft(int id, int l, int r, int x, int val)
    {
        if (st[id] >= val)
            return -1;
        if (x < l)
            return -1;
        if (l == r)
            return l;
        int ans = -1;
        int mid = (l + r) >> 1;
        if (st[id << 1 | 1] < val)
            ans = walkleft(id << 1 | 1, mid + 1, r, x, val);
        if (ans == -1)
            ans = walkleft(id << 1, l, mid, x, val);
        return ans;
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int x, int val)
    {
        update(1, 1, n, x, val);
    }
    void assign(int x, int val)
    {
        assign(1, 1, n, x, val);
    }
    int walkleft(int x,int val)
    {
        return walkleft(1,1,n,x,val);
    }
    int walkright(int x,int val)
    {
        return walkright(1,1,n,x,val);
    }
};
int n,a[maxn],f[N][N],lim;
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> lim;
    fo(i,1,n) cin >> a[i];
    fo(i,1,n) 
    {
        SegmentTree st(5001);
        fo(j,1,5001) st.assign(j,f[i - 1][j - 1]);
        fo(j,1,5001) f[i][j - 1] = st.get(max(j - lim,0),min(5000,j + lim)) + abs(j - 1 - a[i]);
    }
    int ans = 1e9;
    fo(i,0,5000) minimize(ans,f[n][i]);
    cout << ans;
}

Compilation message

safety.cpp:161:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  161 | main()
      | ^~~~
safety.cpp: In function 'int main()':
safety.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4688 KB Output is correct
2 Correct 7 ms 4688 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 6 ms 4772 KB Output is correct
5 Correct 7 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4572 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4688 KB Output is correct
2 Correct 8 ms 4688 KB Output is correct
3 Correct 8 ms 4688 KB Output is correct
4 Correct 8 ms 4688 KB Output is correct
5 Correct 8 ms 4688 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 86856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4688 KB Output is correct
2 Correct 7 ms 4688 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 6 ms 4772 KB Output is correct
5 Correct 7 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4572 KB Output is correct
8 Correct 8 ms 4688 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 290 ms 12872 KB Output is correct
14 Correct 242 ms 12872 KB Output is correct
15 Correct 226 ms 12992 KB Output is correct
16 Correct 339 ms 12764 KB Output is correct
17 Correct 300 ms 12988 KB Output is correct
18 Correct 261 ms 10836 KB Output is correct
19 Correct 245 ms 12988 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4688 KB Output is correct
2 Correct 7 ms 4688 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 6 ms 4772 KB Output is correct
5 Correct 7 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4572 KB Output is correct
8 Correct 8 ms 4688 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 290 ms 12872 KB Output is correct
14 Correct 242 ms 12872 KB Output is correct
15 Correct 226 ms 12992 KB Output is correct
16 Correct 339 ms 12764 KB Output is correct
17 Correct 300 ms 12988 KB Output is correct
18 Correct 261 ms 10836 KB Output is correct
19 Correct 245 ms 12988 KB Output is correct
20 Correct 239 ms 12872 KB Output is correct
21 Correct 336 ms 12972 KB Output is correct
22 Correct 209 ms 10824 KB Output is correct
23 Correct 171 ms 10824 KB Output is correct
24 Correct 283 ms 12988 KB Output is correct
25 Correct 211 ms 10948 KB Output is correct
26 Correct 329 ms 12872 KB Output is correct
27 Correct 242 ms 12872 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4688 KB Output is correct
2 Correct 7 ms 4688 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 6 ms 4772 KB Output is correct
5 Correct 7 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4572 KB Output is correct
8 Correct 8 ms 4688 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 290 ms 12872 KB Output is correct
14 Correct 242 ms 12872 KB Output is correct
15 Correct 226 ms 12992 KB Output is correct
16 Correct 339 ms 12764 KB Output is correct
17 Correct 300 ms 12988 KB Output is correct
18 Correct 261 ms 10836 KB Output is correct
19 Correct 245 ms 12988 KB Output is correct
20 Correct 239 ms 12872 KB Output is correct
21 Correct 336 ms 12972 KB Output is correct
22 Correct 209 ms 10824 KB Output is correct
23 Correct 171 ms 10824 KB Output is correct
24 Correct 283 ms 12988 KB Output is correct
25 Correct 211 ms 10948 KB Output is correct
26 Correct 329 ms 12872 KB Output is correct
27 Correct 242 ms 12872 KB Output is correct
28 Execution timed out 2041 ms 84836 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4688 KB Output is correct
2 Correct 7 ms 4688 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 6 ms 4772 KB Output is correct
5 Correct 7 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4572 KB Output is correct
8 Correct 8 ms 4688 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Incorrect 6 ms 4688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4688 KB Output is correct
2 Correct 7 ms 4688 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 6 ms 4772 KB Output is correct
5 Correct 7 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4572 KB Output is correct
8 Correct 8 ms 4688 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4688 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Incorrect 6 ms 4688 KB Output isn't correct
14 Halted 0 ms 0 KB -