답안 #47369 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47369	2018-05-01T16:57:22 Z	tieunhi	Lightning Conductor (POI11_pio)	C++14	45 / 100	39 ms	1780 KB

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define maxc 1000000007
#define N 50005
using namespace std;

int n, a[N], x2[N], res[N], delta[N], lef[N], rig[N];

void inline MAX(int &A, int B) {A = max(A, B);}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= sqrt(n) + 1; i++)
        x2[i] = i*i;
    for (int i = 1; i <= sqrt(n) + 1; i++)
        delta[i] = x2[i] - x2[i-1];

    for (int i = 1; i <= n; i++)
        lef[i] = max(a[i], lef[i-1]);
    for (int i = n; i >= 1; i--)
        rig[i] = max(a[i], rig[i+1]);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; i - x2[j-1] - 1 > 0; j++)
            MAX(res[i], lef[i - x2[j-1] - 1] + j);
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; i + x2[j-1] + 1 <= n; j++)
            MAX(res[i], rig[i + x2[j-1] + 1] + j);
    }
    for (int i = 1; i <= n; i++)
        if (res[i] <= a[i]) cout <<0<<'\n';
        else cout <<res[i] - a[i]<<'\n';

}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	436 KB	Output is correct

Subtask #4
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	1252 KB	Output is correct

Subtask #5
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	1780 KB	Output is correct

Subtask #6
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	9 ms	1780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	23 ms	1780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	9 ms	1780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	1780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	11 ms	1780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	1780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

답안 #47369

Compilation message