Submission #29745

#TimeUsernameProblemLanguageResultExecution timeMemory
29745cki86201Lightning Conductor (POI11_pio)C++11
100 / 100
243 ms17656 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <iostream> #include <functional> #include <unordered_map> #include <unordered_set> #include <list> #include <bitset> using namespace std; typedef pair<int, int> Pi; typedef long long ll; #define pii Pi #define pll PL #define Fi first #define Se second #define pb(x) push_back(x) #define sz(x) ((int)(x).size()) #define rep(i, n) for(int i=0;i<n;i++) #define all(x) (x).begin(), (x).end() typedef tuple<int, int, int> t3; typedef pair<ll, ll> PL; typedef long double ldouble; int sq[1000020]; int n, h[500050]; int ans[500050]; double sqf[1000020]; void Do1(int l, int r, int s, int d) { int m = (l + r) >> 1; double mxf = -1; int mi = -1; for(int i=s;i<=d&&i<=m;i++) { double tf = h[i] + sqf[m-i]; if(mxf < tf) mxf = tf, mi = i; } ans[m] = max(ans[m], h[mi] + sq[m-mi]); if(l<m) Do1(l, m-1, s, mi); if(m<r) Do1(m+1, r, mi, d); } void Do2(int l, int r, int s, int d) { int m = (l + r) >> 1; int mi = -1; double mxf = -1; for(int i=max(m,s);i<=d;i++) { double tf = h[i] + sqf[i-m]; if(mxf < tf) mxf = tf, mi = i; } ans[m] = max(ans[m], h[mi] + sq[mi-m]); if(l<m) Do2(l, m-1, s, mi); if(m<r) Do2(m+1, r, mi, d); } int main(){ for(int i=1, j=1;i<=1000000;i++) { while(j*j<i)++j; sq[i] = j; sqf[i] = sqrt(i); } scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d", h+i); Do1(1, n, 1, n); Do2(1, n, 1, n); for(int i=1;i<=n;i++) printf("%d\n", ans[i] - h[i]); return 0; }

Compilation message (stderr)

pio.cpp: In function 'int main()':
pio.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
pio.cpp:72:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d", h+i);
                                        ^
#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...