oj.uz

Submission #103812

# Submission time Handle Problem Language Result Execution time Memory
103812 2019-04-02T18:48:12 Z Shtef Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 7796 KB 
#include <iostream>
#include <utility>
#include <cmath>
#include <iomanip>
#include <vector>

using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair <ll, ll> pll;
#define x first
#define y second
#define mp make_pair

int n, q, dosad[200005];
vector <pll> a, b;

ld duljina(pll x, pll y){
	ld ret = sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
	return ret;
}

ll crossprod(pll px1, pll py1, pll px2, pll py2){
	ll x1 = py1.x - px1.x;
	ll y1 = py1.y - px1.y;
	ll x2 = py2.x - px2.x;
	ll y2 = py2.y - px2.y;
	ll ret = x1 * y2 - x2 * y1;
	return ret;
}

void solve(){
	n = (int)a.size();
	b = a;
	for(int i = 0 ; i < n ; ++i){
		a.push_back(a[i]);
	}
	int j = 1;
	ld sad = duljina(a[0], a[1]), sol = 0;
	for(int i = 0 ; i < n ; ++i){
		//cout << i << ": ";
		while(crossprod(a[i], a[i + 1], a[j], a[j + 1]) > 0 && j < 2 * n){
			//cout << j << "-";
			sad += duljina(a[j], a[j + 1]);
			j++;
		}
		//cout << j << endl;
		sol = max(sol, sad);
		sad -= duljina(a[i], a[i + 1]);
	}
	cout << fixed << setprecision(10) << sol << endl;
	a = b;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
int m = n;
for(int i = 0 ; i < n ; ++i){
	int x, y;
	cin >> x >> y;
	a.push_back(mp(x, y));
}
cin >> q;
solve();
for(int i = 0 ; i < q ; ++i){
	int x;
	cin >> x;
	--x;
	a.erase(a.begin() + x - dosad[x]);
	for(int j = x ; j <= m ; ++j){
		dosad[j]++;
	}
	solve();
}

return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB 11 numbers
2 Correct 2 ms 384 KB 41 numbers
3 Correct 2 ms 384 KB 11 numbers
4 Correct 3 ms 384 KB 93 numbers
5 Correct 5 ms 484 KB 101 numbers
6 Correct 28 ms 512 KB 1201 numbers
7 Correct 54 ms 620 KB 1556 numbers
8 Correct 67 ms 620 KB 1996 numbers
9 Correct 58 ms 632 KB 1960 numbers
10 Correct 74 ms 640 KB 1991 numbers
11 Correct 58 ms 512 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 3 ms 640 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 9 ms 1408 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 9 ms 2300 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 38 ms 7796 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 33 ms 7784 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 684 KB 1001 numbers
2 Execution timed out 3035 ms 2780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB 11 numbers
2 Correct 2 ms 384 KB 41 numbers
3 Correct 2 ms 384 KB 11 numbers
4 Correct 3 ms 384 KB 93 numbers
5 Correct 5 ms 484 KB 101 numbers
6 Correct 28 ms 512 KB 1201 numbers
7 Correct 54 ms 620 KB 1556 numbers
8 Correct 67 ms 620 KB 1996 numbers
9 Correct 58 ms 632 KB 1960 numbers
10 Correct 74 ms 640 KB 1991 numbers
11 Correct 58 ms 512 KB 1963 numbers
12 Correct 2 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 3 ms 640 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 9 ms 1408 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 9 ms 2300 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 38 ms 7796 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 33 ms 7784 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 62 ms 684 KB 1001 numbers
19 Execution timed out 3035 ms 2780 KB Time limit exceeded
20 Halted 0 ms 0 KB -