oj.uz

Submission #242904

# Submission time Handle Problem Language Result Execution time Memory
242904 2020-06-29T18:51:50 Z MatesV13 Svjetlost (COI18_svjetlost) C++11
40 / 100
 3000 ms 6136 KB 
#include <bits/stdc++.h>
using namespace std;
long long n, q, V, x[100005], y[100005], prijasnji[100005];
void update(int vrh){
	int minus=0;
	for (int i=1; i<vrh; i++){
		if (prijasnji[i]) minus++;
	} prijasnji[vrh]++; vrh-=minus;
	for (int i=vrh+1; i<=n; i++){
		x[i-1]=x[i]; y[i-1]=y[i];
	} return;
}
bool ok (int idx1, int idx2){
	idx1 = (idx1+n-1)%n+1; idx2 = (idx2+n-1)%n+1;
	long long dx1 = x[idx1] - x[idx1-1];
	long long dy1 = y[idx1] - y[idx1-1];
	long long dx2 = x[idx2] - x[idx2-1];
	long long dy2 = y[idx2] - y[idx2-1];
//	cout << dx1 << " " << dy1 << "   " << dx2 << " " << dy2 << endl;
//	cout << dx1*dy2 << " " << dx2*dy1 << endl;
	return (dx1*dy2 > dx2*dy1);
}
long double leng(int idx){
	idx = (idx+n-1)%n+1;
	long long dx = x[idx] - x[idx-1];
	long long dy = y[idx] - y[idx-1];
//	cout << "duljina izmedu " << idx << " i " << idx-1 << " iznosi: " << sqrtl(dx*dx + dy*dy) << endl;
	return sqrtl(dx*dx + dy*dy);
}
long double dp[200005];
void check(){
	long double ans=0.0000000000;
	x[0]=x[n]; y[0]=y[n];
	int cur=1; dp[1] = leng(1); ans=dp[1];
//	cout << "pomoc: 1 1" << endl << "udaljenost: " << dp[1] << endl << "ans: " << ans << endl << endl;
	for (int i=2; i<=2*n; i++){
		while (!ok(cur, i)) cur++;
//		cout << "pomoc: " << i << " " << cur << endl;
		dp[i] = dp[i-1] + leng(i);
//		cout << "udaljenost: " << dp[i] << endl;
		ans = max(ans, dp[i] - dp[cur-1]);
//		cout << "ans: " << ans << endl << endl;
	} cout << ans << endl; return;
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; 
for (int i=1; i<=n; i++){
	cin >> x[i] >> y[i];
}
cout << fixed << setprecision(10);
check(); cin >> q;
while (q--){
	cin >> V; update(V); n--; check();
}
return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 14 ms 384 KB 101 numbers
6 Correct 90 ms 512 KB 1201 numbers
7 Correct 123 ms 512 KB 1556 numbers
8 Correct 190 ms 760 KB 1996 numbers
9 Correct 173 ms 644 KB 1960 numbers
10 Correct 173 ms 632 KB 1991 numbers
11 Correct 169 ms 760 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 ms 384 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 9 ms 1152 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 14 ms 1636 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 40 ms 6136 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 39 ms 6136 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 760 KB 1001 numbers
2 Execution timed out 3031 ms 2312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 14 ms 384 KB 101 numbers
6 Correct 90 ms 512 KB 1201 numbers
7 Correct 123 ms 512 KB 1556 numbers
8 Correct 190 ms 760 KB 1996 numbers
9 Correct 173 ms 644 KB 1960 numbers
10 Correct 173 ms 632 KB 1991 numbers
11 Correct 169 ms 760 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 5 ms 384 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 9 ms 1152 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 14 ms 1636 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 40 ms 6136 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 39 ms 6136 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 185 ms 760 KB 1001 numbers
19 Execution timed out 3031 ms 2312 KB Time limit exceeded
20 Halted 0 ms 0 KB -