Submission #148297

#	Time	Username	Problem	Language	Result	Execution time	Memory
148297		youssefbou62	Ideal city (IOI12_city)	C++14	0 / 100	7 ms	764 KiB

city

#include  <bits/stdc++.h>
// #include "city.h"
using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }

ll ans ;
int root ; 
const int N = 2e5+5; 
// int visited[N] ; 
const ll mod = 1e9 ; 
int x[N],y[N]; 
// void bfs(int root ){
// 	int u = root; 
// 	queue<int> q; 
// 	q.push(u); 
// 	visited[u]=0; 
// 	int dx [][2] ={{0,-1},{0,1},{1,0},{-1,0}};
// 	while(!q.empty()){
// 		u = q.front(); 
// 		q.pop(); 
// 		// cout << visited[u]<<" " << ans <<endl; 
// 		if( u >= root )ans += visited[u] , ans %= mod; 
// 		for(int i = 0 ; i < 4 ; i++ ){
// 			int xx = x[u]+dx[i][0] ; 
// 			int yy = y[u]+dx[i][1] ; 

// 			if( xx >= 0 && yy >= 0 &&notE[xx][yy]!=-1&& visited[notE[xx][yy]]==-1 ){
// 				visited[notE[xx][yy]] = visited[u]+1; 
// 				q.push(notE[xx][yy]); 
// 			}
// 		}
// 	}
// }

int DistanceSum(int N, int *X, int *Y){
	ll sum = 0 ; 
	for(int i = 0 ; i < N ; i++ ){
		x[i] = X[i] ; 
		y[i] = Y[i] ; 
		sum += (1LL*x[i])+(1LL*y[i]) ; 
	}

	for(int i = 0 ; i <  N ; i++ ){
		ans += sum - ((1LL*x[i])+(1LL*y[i]))*1LL*(N-i-1) ; 
		ans %= mod ; 	
		sum -= (1LL*x[i])+(1LL*y[i]) ; 
	} 

	return ans; 
}
// int main(){
// 	int n ; cin >> n ; for(int i = 0 ; i < n ; i++ )cin >> x[i]>>y[i] ; cout << DistanceSum(n,x,y)<<endl; 
// }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45