oj.uz

Submission #950486

# Submission time Handle Problem Language Result Execution time Memory
950486 2024-03-20T11:05:19 Z koukirocks Lightning Conductor (POI11_pio) C++17
100 / 100
 187 ms 22984 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6872 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9184 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9052 KB Output is correct
2 Correct 21 ms 8920 KB Output is correct
3 Correct 19 ms 9180 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9076 KB Output is correct
2 Correct 34 ms 9112 KB Output is correct
3 Correct 24 ms 9816 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 14000 KB Output is correct
2 Correct 82 ms 13792 KB Output is correct
3 Correct 62 ms 14548 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 20940 KB Output is correct
2 Correct 135 ms 18836 KB Output is correct
3 Correct 98 ms 20768 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 22972 KB Output is correct
2 Correct 186 ms 20208 KB Output is correct
3 Correct 137 ms 22888 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 20440 KB Output is correct
2 Correct 187 ms 19888 KB Output is correct
3 Correct 127 ms 22984 KB Output is correct