Submission #950486

#	Time	Username	Problem	Language	Result	Execution time	Memory
950486		koukirocks	Lightning Conductor (POI11_pio)	C++17	100 / 100	187 ms	22984 KiB

pio

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=5e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n;
int h[MAX];
ldb dp[MAX],dp2[MAX];

void cal(int l,int r,int il,int ir) {
	int m=l+r>>1;
	dp[m]=-INF;
	int id=0;
	for (int i=il;i<=min(ir,m);i++) {
		if (dp[m]<h[i]+sqrt(abs(i-m))) {
			dp[m]=h[i]+sqrt(abs(i-m));
			id=i;
		}
	}
	dp[m]-=h[m];
	if (m+1<=r) cal(m+1,r,id,ir);
	if (l<=m-1) cal(l,m-1,il,id);
}

void cal2(int l,int r,int il,int ir) {
	int m=l+r>>1;
	dp2[m]=-INF;
	int id=0;
	for (int i=max(m,il);i<=ir;i++) {
		if (dp2[m]<h[i]+sqrt(abs(i-m))) {
			dp2[m]=h[i]+sqrt(abs(i-m));
			id=i;
		}
	}
	dp2[m]-=h[m];
	if (m+1<=r) cal2(m+1,r,id,ir);
	if (l<=m-1) cal2(l,m-1,il,id);
}

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>h[i];
	}
//	for (int i=1;i<=n;i++) {
//		for (int j=1;j<=n;j++) {
//			cout<<fixed<<setprecision(6)<<h[j]+sqrt(abs(i-j))<<" ";
//		}
//		cout<<"\n";
//	}
	cal(1,n,1,n);
	cal2(1,n,1,n);
	for (int i=1;i<=n;i++) {
		dp[i]=max(dp[i],dp2[i]);
		cout<<max(0,(int)ceil(dp[i]-1e-8))<<"\n";
	}
	return 0;
}

Compilation message (stderr)

pio.cpp: In function 'void cal(int, int, int, int)':
pio.cpp:22:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |  int m=l+r>>1;
      |        ~^~
pio.cpp: In function 'void cal2(int, int, int, int)':
pio.cpp:37:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int m=l+r>>1;
      |        ~^~

• 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