Submission #950476

#	Time	Username	Problem	Language	Result	Execution time	Memory
950476		koukirocks	Lightning Conductor (POI11_pio)	C++17	27 / 100	139 ms	15240 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];

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<=ir;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,il,id);
	if (l<=m-1) cal(l,m-1,id,ir);
}

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]-h[i]+sqrt(abs(i-j))<<" ";
//		}
//		cout<<"\n";
//	}
	cal(1,n,1,n);
	for (int i=1;i<=n;i++) {
		cout<<max(0,(int)ceil(dp[i]-1e-6))<<"\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;
      |        ~^~

• Subtask 1: 0 / 9
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10