oj.uz

Submission #141103

# Submission time Handle Problem Language Result Execution time Memory
141103 2019-08-06T18:14:52 Z abacaba Lightning Conductor (POI11_pio) C++14
27 / 100
 196 ms 16040 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] + s[abs(mid - opt)] < a[i] + s[abs(mid - i)])
            opt = i;
    dp[mid] = max(dp[mid], a[opt] + s[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;
        int j = i * i + 1;
        while(j < N && j < (i + 1) * (i + 1))
            s[j++] = 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4216 KB Output isn't correct

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4216 KB Output isn't correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4984 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5368 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5240 KB Output is correct
2 Correct 22 ms 5112 KB Output is correct
3 Incorrect 26 ms 5624 KB Output isn't correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5752 KB Output is correct
2 Correct 36 ms 6364 KB Output is correct
3 Incorrect 38 ms 6536 KB Output isn't correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7344 KB Output is correct
2 Correct 75 ms 7276 KB Output is correct
3 Incorrect 79 ms 7928 KB Output isn't correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 10760 KB Output is correct
2 Correct 117 ms 11768 KB Output is correct
3 Incorrect 125 ms 12664 KB Output isn't correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 13404 KB Output is correct
2 Correct 166 ms 15072 KB Output is correct
3 Incorrect 174 ms 16040 KB Output isn't correct

Subtask #11
0 / 10.0

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