oj.uz

Submission #141105

# Submission time Handle Problem Language Result Execution time Memory
141105 2019-08-06T18:17:05 Z abacaba Lightning Conductor (POI11_pio) C++14
100 / 100
 344 ms 16120 KB 
#include <bits/stdc++.h>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int inf = 2e9;
const int N = 1e6 + 15;
int n, s[N], a[N], dp[N];

void rec(int l, int r, int l2, int r2) {
    if(l > r)
        return;
    int mid = l + r >> 1, opt = l2;
    for(int i = l2; i <= min(mid, r2); ++i)
        if(a[opt] + sqrt(abs(mid - opt)) < a[i] + sqrt(abs(mid - i)))
            opt = i;
    dp[mid] = max(dp[mid], a[opt] + (int)ceil(sqrt(abs(mid - opt))) - a[mid]);
    rec(l, mid - 1, l2, opt);
    rec(mid + 1, r, opt, r2);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i * i < N; ++i)
        s[i * i] = i;
    for(int i = 1; i < N; ++i)
        s[i] = (s[i] ? s[i] : s[i-1]);
    rec(1, n, 1, n);
    reverse(a + 1, a + 1 + n);
    reverse(dp + 1, dp + 1 + n);
    rec(1, n, 1, n);
    for(int i = n; i; --i)
        printf("%d\n", dp[i]);
    return 0;
}

Compilation message

pio.cpp: In function 'void rec(int, int, int, int)':
pio.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1, opt = l2;
               ~~^~~
pio.cpp: In function 'int main()':
pio.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
pio.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5112 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5472 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5424 KB Output is correct
2 Correct 40 ms 5084 KB Output is correct
3 Correct 44 ms 5468 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5880 KB Output is correct
2 Correct 63 ms 5692 KB Output is correct
3 Correct 65 ms 6264 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 7416 KB Output is correct
2 Correct 139 ms 7544 KB Output is correct
3 Correct 143 ms 7992 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 10744 KB Output is correct
2 Correct 219 ms 8700 KB Output is correct
3 Correct 223 ms 10744 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 13528 KB Output is correct
2 Correct 308 ms 10336 KB Output is correct
3 Correct 316 ms 13560 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 11012 KB Output is correct
2 Correct 312 ms 14968 KB Output is correct
3 Correct 315 ms 16120 KB Output is correct