oj.uz

Submission #98219

# Submission time Handle Problem Language Result Execution time Memory
98219 2019-02-21T15:04:52 Z luciocf Ideal city (IOI12_city) C++14
23 / 100
 52 ms 3704 KB 
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

const int maxn = 1e5+10;
const long long mod = 1e9;

typedef long long ll;
typedef pair<int, int> pii;

int n;

ll soma[maxn];

pii pt[maxn];

bool comp(pii a, pii b) {return a.y < b.y;}

int DistanceSum(int N, int *X, int *Y)
{
	n = N;
	for (int i = 0; i < n; i++)
		pt[i+1] = {X[i], Y[i]};

	sort(pt+1, pt+n+1);

	for (int i = 1; i <= n; i++)
		soma[i] = (soma[i-1]+(ll)pt[i].x)%mod;

	ll ans = 0LL;

	for (int i = 1; i <= n; i++)
	{
		ll v = (soma[n]-soma[i]+mod)%mod;

		ans = (ans+v)%mod;
		ans = (ans-((n-i)*(ll)pt[i].x)%mod+mod)%mod;
	}

	sort(pt+1, pt+n+1, comp);

	for (int i = 1; i <= n; i++)
		soma[i] = (soma[i-1]+(ll)pt[i].y)%mod;

	for (int i = 1; i <= n; i++)
	{
		ll v = (soma[n]-soma[i]+mod)%mod;

		ans = (ans+v)%mod;
		ans = (ans-(((ll)n-(ll)i)*(ll)pt[i].y)%mod+mod)%mod;
	}

	return ans;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 896 KB Output is correct
2 Correct 11 ms 1024 KB Output is correct
3 Correct 21 ms 1892 KB Output is correct
4 Correct 23 ms 1920 KB Output is correct
5 Correct 51 ms 3448 KB Output is correct
6 Correct 42 ms 3448 KB Output is correct
7 Correct 45 ms 3704 KB Output is correct
8 Correct 45 ms 3448 KB Output is correct
9 Correct 52 ms 3448 KB Output is correct
10 Correct 51 ms 3576 KB Output is correct

Subtask #4
0 / 45.0

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