제출 #47371

#제출 시각아이디문제언어결과실행 시간메모리
47371nickyrio새로운 문제 (POI11_pio)C++17
0 / 100
2 ms452 KiB
//https://oj.uz/problem/view/POI11_pio #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define FORD(i, a, b) for (int i = (a); i >= (b); --i) #define REP(i, a) for (int i = 0; i < (a); ++i) #define DEBUG(x) { cerr << #x << '=' << x << endl; } #define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; } #define N 500100 #define pp pair<int, int> #define endl '\n' #define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define taskname "" #define bit(S, i) (((S) >> (i)) & 1) using namespace std; int n, lg[N]; long long h[N], MAX[N][20]; void Build() { FOR(i, 1, n) MAX[i][0] = h[i]; FOR(i, 1, n) lg[i] = log2(i); FOR(j, 1, lg[n]) FOR(i, 1, n) if (i + (1 << j) - 1 <= n) { MAX[i][j] = max(MAX[i][j - 1], MAX[i + (1 << (j - 1))][j - 1]); } } long long Get(int l, int r) { int d = lg[r - l + 1]; return max(MAX[l][d], MAX[r - (1 << d) + 1][d]); } int main() { #ifdef NERO freopen("test.inp","r",stdin); freopen("test.out","w",stdout); double stime = clock(); #else //freopen(taskname".inp","r",stdin); //freopen(taskname".out","w",stdout); #endif //NERO IO; cin >> n; FOR(i, 1, n) cin >> h[i]; Build(); FOR(i, 1, n) { int bef = i; long long need = 0; FOR(j, 1, n) { long long LEFT = max(1ll, 1ll * i - 1ll * j * j); if (LEFT >= bef) break; need = max(need, - h[i] + Get(LEFT, bef - 1) + j); if (LEFT == 1) break; bef = LEFT; } bef = i; FOR(j, 1, n) { long long RIGHT = min(1ll * n, 1ll * i + 1ll * j * j); if (RIGHT <= bef) break; need = max(need, - h[i] + Get(bef + 1, RIGHT) + j); if (RIGHT == n) break; bef = RIGHT; } cout << need << '\n'; } #ifdef NERO double etime = clock(); cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n"; #endif // NERO }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...