oj.uz

Submission #629576

# Submission time Handle Problem Language Result Execution time Memory
629576 2022-08-14T16:16:39 Z somethingnew Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 3216 KB 
#include "towers.h"

#include <cassert>
#include <cstdio>

#include <vector>
using namespace std;
vector<int> h;
struct segtree{
    int sz;
    vector<int> tree;
    void init(int n, vector<int> a) {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.assign(sz * 2, 0);
        for (int i = 0; i < n; ++i) {
            tree[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }
    int get(int l, int r) {
        int res = 0;
        while (l <= r) {
            if (l & 1) {
                res += tree[l];
                l++;
            }
            if ((r & 1) == 0) {
                res += tree[r];
                r--;
            }
            l /= 2;r /= 2;
        }
        return res;
    }
};
segtree sg;

void init(int n, vector<int> hh) {
    h = hh;
    vector<int> bebra(n);
    for (int i = 1; i + 1 < n; ++i) {
        if (hh[i-1] > hh[i] and hh[i] < hh[i + 1])
            bebra[i] = 1;
    }
    sg.init(n, bebra);
}
int max_towers(int L, int R, int D) {
    if (D == 1) {
        int val = sg.get(L + 1, R - 1);
        if (L + 1 <= R and h[L] < h[L + 1])
            val++;
        if (L + 1 <= R and h[R-1] > h[R])
            val++;
        return max(val, 1);
    }
    vector<int> dp(h.size(), 1);
    int res = 0;
    for (int i = L; i < R; ++i) {
        int mx = h[i];
        res = max(res, dp[i]);
        for (int j = i + 1; j <= R; ++j) {
            mx = max(mx, h[j]);
            if (mx - D >= max(h[i], h[j]) and h[j - 1] > h[j] and (j == R or h[j + 1] > h[j])) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }
    res = max(res, dp[R]);
    return res;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '79', found: '532'
16 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '79', found: '532'
16 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 720 ms 3216 KB 1st lines differ - on the 1st token, expected: '11903', found: '58979'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '79', found: '532'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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