oj.uz

Submission #1022880

# Submission time Handle Problem Language Result Execution time Memory
1022880 2024-07-14T07:05:10 Z mansur Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 1604 KB 
#include "towers.h"
#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second 
#define f first 

using ll = long long;
using pii = pair<int, int>; 
using pll = pair<ll, ll>;

vector<int> h;
int n, k, ok = 1;
const int inf = 1e9;

void init(int N, vector<int> H) {
    n = N, h = H;
    k = n - 1;
    for (int i = 1; i < n; i++) {
        if (h[i] < h[i - 1]) {
            k = i - 1;
            break;
        }
    }
    for (int i = 1; i < k; i++) {
        if (h[i - 1] > h[i]) ok = 0;
    }
    for (int i = k + 1; i < n; i++) {
        if (h[i - 1] < h[i]) ok = 0;
    }
}

int f(int l, int r, int d, int mx) {
    if (r < l) return 0;
    if (l == r) return (h[l] <= mx);
    int pos = l;
    for (int i = l; i <= r; i++) if (h[i] > h[pos]) pos = i;
    if (pos == l) return f(l + 1, r, d, mx);
    if (pos == r) return f(l, r - 1, d, mx);
    return f(l, pos - 1, d, min(mx, h[pos] - d)) + f(pos + 1, r, d, min(mx, h[pos] - d));
}

int max_towers(int l, int r, int d) {
    if (ok) {
        if (k == -1) return 1;
        if (k <= l || r <= k) return 1;
        if (h[l] >  h[k] - d || h[k] - h[r] > d) return 1;
        return 2;
    }
    return f(l, r, d, inf);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 310 ms 1112 KB 5th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '292', found: '284'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '292', found: '284'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4011 ms 600 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 344 KB Output is correct
2 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '292', found: '284'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 310 ms 1112 KB 5th lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -