oj.uz

Submission #950476

# Submission time Handle Problem Language Result Execution time Memory
950476 2024-03-20T10:49:56 Z koukirocks Lightning Conductor (POI11_pio) C++17
27 / 100
 139 ms 15240 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];

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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5028 KB Output is correct
2 Correct 12 ms 4952 KB Output is correct
3 Incorrect 18 ms 5172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5216 KB Output is correct
2 Correct 22 ms 4956 KB Output is correct
3 Incorrect 21 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8192 KB Output is correct
2 Correct 52 ms 7804 KB Output is correct
3 Incorrect 45 ms 8532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12992 KB Output is correct
2 Correct 69 ms 10832 KB Output is correct
3 Incorrect 68 ms 13044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 15040 KB Output is correct
2 Correct 103 ms 12120 KB Output is correct
3 Incorrect 95 ms 15184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12708 KB Output is correct
2 Correct 97 ms 12128 KB Output is correct
3 Incorrect 98 ms 15240 KB Output isn't correct
4 Halted 0 ms 0 KB -