oj.uz

Submission #950474

# Submission time Handle Problem Language Result Execution time Memory
950474 2024-03-20T10:48:13 Z koukirocks Lightning Conductor (POI11_pio) C++17
27 / 100
 115 ms 19796 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<<(int)ceil(dp[i])<<"\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 2396 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 1 ms 2396 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 8 ms 5212 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5580 KB Output is correct
2 Correct 14 ms 4952 KB Output is correct
3 Incorrect 12 ms 5468 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 6036 KB Output is correct
2 Correct 25 ms 5972 KB Output is correct
3 Incorrect 18 ms 6208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10324 KB Output is correct
2 Correct 43 ms 9812 KB Output is correct
3 Incorrect 49 ms 9808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16468 KB Output is correct
2 Correct 69 ms 14508 KB Output is correct
3 Incorrect 66 ms 15184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 19796 KB Output is correct
2 Correct 111 ms 17112 KB Output is correct
3 Incorrect 104 ms 17932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 17480 KB Output is correct
2 Correct 97 ms 16964 KB Output is correct
3 Incorrect 96 ms 18004 KB Output isn't correct
4 Halted 0 ms 0 KB -