Submission #141105

#	Time	Username	Problem	Language	Result	Execution time	Memory
141105		abacaba	Lightning Conductor (POI11_pio)	C++14	100 / 100	344 ms	16120 KiB

pio

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10