akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define reg register
	#define Rint register int
	#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
	#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
	#define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)+1;++i)
	#define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a);i!=(arr)+(b)-1;--i)
	#define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
	#define MEM(x,v) memset(x,v,sizeof(x))
	#define fir first
	#define sec second
	#define pq priority_queue
	#define PII pair<int,int>
	#define MP make_pair
	typedef long long LL;
	typedef double DB;
	#define Templ(T) template<typename T>
	inline int read(){
		int ans=0,f=1;char c=getchar();
		while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
		for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48); return f?ans:-ans;
	}
	Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
	Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
	#define using_mod
	const int mod = 998244353 , N = 17;
	#ifdef using_mod
	inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
	inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
	#endif
	Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
	#define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
}
using namespace my_std;
#define inf (1145141919)
int n,a[N][N],m,f[60010][N],G[60010],U;
//发现最后一定是几个连通块串起来(即相邻连通块只有一条边且某一连通块连向两边连通块的边都出自同一点) 
//f[sta][i] : 做到的集合为 sta , 最后连上的点为 i 此时保留的边的最大权值和 
//G[sta] : 连通块 sta 只保留内部的边的权值和 

inline int Count_(int sta,vector<int> &vec) {
	Rint t = 0,res = 0;
	while(sta) {
		if(sta & 1) ++res , vec.push_back(t);
		++t , sta >>= 1;
	}
	return res;
}

int main() {
	n = read() , m = read() , U = (1 << n) - 1;
	FOR(i,0,n) FOR(j,0,n) a[i][j] = -inf;
	Rint u,v;
	FOR(i,1,m) u = read() - 1 , v = read() - 1 , a[u][v] = a[v][u] = read();
	FOR(i,1,U) FOR(j,0,n - 1) f[i][j] = -inf;
	FOR(S,1,U){
		Rint t = 0 , SS;
		while(!(S & (1 << t))) ++t;
		SS = S ^ (1 << t);
		G[S] = G[SS];
		FOR(i,0,n - 1) if((SS & (1 << i)) && (a[t][i] != -inf)) G[S] += a[t][i];
	}
	FOR(S,1,U) if(S & 1) f[S][0] = G[S];
	FOR(S,1,U){
		vector<int> vec;
		Count_(S,vec);
		for(reg auto i : vec) if(f[S][i] != -inf){//刷表更新
			Rint &Now = f[S][i] , C = (U ^ S)/*补集*/;
			FOR(j,0,n - 1) if(!(S & (1 << j)) && a[i][j] != -inf){//新挂一个点 
				chkmax(f[S ^ (1 << j)][j] , Now + a[i][j]);
			}
			for(Rint T = C;T;T = (T - 1) & C){//在最后一个点上新挂一个块 
				chkmax(f[S ^ T][i] , Now + G[T ^ (1 << i)]);
			}
		}
	}
	printf("%d\n",G[U] - f[U][n - 1]);
	return 0;
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;

v1 move_h{1, 1, -1, -1};
v1 move_w{1, -1, 1, -1};
ll t = 0;
ll H, W;

/*void kaku(ll h, ll w, v2& b){
	if(h < 0 || w < 0 || h >= H || w >= W) return;
	if(b.at(h).at(w) == 1) return;
	t++;
	b.at(h).at(w) = 1;
	rep(i, 4){
		ll n_h = h + move_h.at(i);
		ll n_w = w + move_w.at(i);
		kaku(n_h, n_w, b);
	}
}*/

int main(){
	/*cin >> H >> W;
	v2 b(H, vector<int>(W, 0));
	kaku(0, 0, b);
	cout << t << endl;*/
	cin >> H >> W;
	int a = H%2;
	if(H == 1 || W == 1){
		cout << 1 << endl;
		return 0;
	}
	if(W%2 == 0) cout << W/2*H << endl;
	if(W%2 == 1) cout << W/2*H + H/2 + H%2 << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = ((B)-1); I >= (A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define pri(a) cout << (a) << endl


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll N,p=0,n=0;
	cin >> N;
	vector<ll> A(100001,0);
	FOR(i,0,N){
		ll x;
		cin>>x;
		if(A[x]==0){
			A[x]++;
			n++;
		}else{
			p++;
		} 
	}
	if(p%2){
		cout << n - 1 << endl;
	}else{
		cout << n << endl;
	}
}


Measured memory_bytes: 1024
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dp[3010][3010] = {};
ll a[3010];
ll N;
ll calc(ll lv, ll rv){
    ll &res = dp[lv][rv];
    if(~res) return res;
    res = 0;
    ll cnt = N - (rv - lv);
    if(cnt % 2 == 0){
        res = max(a[lv] + calc(lv+1, rv), a[rv-1] + calc(lv, rv-1));
        return res;
    }else{
        res = min(-a[lv] + calc(lv+1, rv), -a[rv-1] + calc(lv, rv-1));
        return res;
    }


    return res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    rep(i,0,N) cin >> a[i];
    rep(i,0,N+1){
        rep(j,0,N+1){
            dp[i][j] = -1;
        }
    }
    rep(i,0,N+1) dp[i][i] = 0;
    ll ans = calc(0, N);
    print(ans);
    

}

Measured memory_bytes: 71040
#include<iostream>
using namespace std;



int main(){
	int h, m, s, n,l;



	cin >> n;

	s = n % 60;
	l = n / 60;
	h = n / 3600;
	m = l - h * 60;

	





	cout << h << ":" << m << ":" << s << endl;




	return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
 
using namespace std;

void solve(int TestCase) {
    long long n, a, b;
    cin >> n >> a >> b;
    
    long long ret = n / (a + b) * a;
    n %= (a+b);
    ret += min(n, a);
    cout << ret << endl;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    //cin >> t;
    for(auto i = 1; i <= t; ++i) {
    //    cout << "Case #"<< i << ": ";
        solve(i);
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//関数
const long INF=1000000000000000;

int main(void){
    long N,M;
    cin>>N>>M;
    
    vector<long> A(M);
    for(int i=0;i<M;i++){
        cin>>A.at(i);
    }
    vector<long> cost={INF,2,5,5,4,5,6,3,7,6};
    
    vector<string> dp(N+1,"impossible");
    dp.at(0)="";
    for(int n=1;n<=N;n++){
        //cout<<n<<"本の時"<<endl;　
        for(int i=0;i<M;i++){
            long j=n-cost.at(A.at(i));
            //cout<<j<<endl;
            if(0<=j && dp.at(j)!="impossible"){
                //cout<<A.at(i)<<":cost="<<cost.at(A.at(i))<<"を["<<dp.at(j)<<"]に付け加えようとします。　";
                if(dp.at(n) =="impossible" || dp.at(j).size()+1>dp.at(n).size() ||( dp.at(j).size()+1==dp.at(n).size() &&dp.at(j)+to_string(A.at(i))> dp.at(n))){
                    dp.at(n)=dp.at(j)+to_string(A.at(i));
                    //cout<<"["<<dp.at(n)<<"]に更新されました";
                }else{
                    //cout<<"["<<dp.at(j)+to_string(A.at(i))<<"]は["<<dp.at(n)<<"]より小さいので却下されました。";
                }
                //cout<<endl;
            }
        }
        //cout<< "dp.at("<<n<<")=["<<dp.at(n)<<"]に決定しました。"<<endl<<endl;
    }
    cout<<dp.at(N)<<endl;
}

Measured memory_bytes: 31872
#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 10;
int a[N],b[N],mark[N],p[N],n,S;
vector<int> v[N];
char s[N];
void push(int i){
    if(mark[i]^S){
        mark[i] ^= 1;
        swap(v[i][1],v[i][2]);
    }
}
int main(){
    scanf("%d%s",&n,s);
    p[0] = 1; for(int i=1;i<13;i++) p[i] = p[i-1] * 3;
    for(int i=0;i<n;i++){
        for(int j=0;j<p[i];j++) v[j] = {0,1,2};
        S = 0;
        for(int j=0;s[j];j++){
            push(b[j]);
            int nxt = b[j] + p[i] * v[b[j]][2];
            if(s[j]=='S') S ^= 1;
            else{
                swap(v[b[j]][1],v[b[j]][2]), swap(v[b[j]][0],v[b[j]][1]);
            }
            b[j] = nxt;
        }
        for(int j=0;j<p[i];j++) push(j), mark[j] = 0;
        for(int j=0;j<p[i];j++){
            int tmp = a[j];
            for(int k=0;k<3;k++) a[j+p[i]*v[j][k]] = tmp+p[i]*k;
        }
    }
    for(int i=0;i<p[n];i++) printf("%d%c",a[i]," \n"[i==p[n]-1]);
}


Measured memory_bytes: 60284
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define dump(x)  cout << #x << " = " << (x) << endl;

#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
//             0123456789 - digits. check the limits, int vs long
const int MX = 100001;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(0);
    cout << std::fixed;
    // freopen("ex.in","r",stdin);
    // freopen("ex.out","w",stdout);
    int n;
    cin >> n;
    map<string, int> m;
    string x;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        sort(x.begin(), x.end());
        m[x]++;
    }
    ll ans = 0;
    ll temp;
    for(auto u : m) {
        temp = u.second;
        ans += temp * (temp - 1) / 2;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
  int n,k;
  cin >> n >> k;
  VI a(n);
  rep(i,n)cin >> a.at(i);
  rep(i,n-k){
     if(a.at(i)<a.at(i+k))cout << "Yes" << endl;
     else if(a.at(i)>=a.at(i+k))cout << "No" << endl;
  }  

}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define mat vector<vec>

using namespace std;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

  ll n,m,x,y;
  cin >> n >> m >> x >> y;

  ll a[n],b[m];
  for(ll i=0;i<n;i++)cin >> a[i];
  for(ll i=0;i<m;i++)cin >> b[i];

  sort(a,a+n);
  sort(b,b+m);

  for(ll i=-100;i<101;i++){
    if(x<i && i<=y && a[n-1]<i && i<=b[0]){
      cout << "No War" << endl;
      return 0;
    }
  }
  cout << "War" << endl;

}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
  int n, k;
  cin >> n >> k;
  COMinit();
  vector<long long> a(n);
  for(int i=0;i<n;i++) cin >> a[i];
  sort(a.begin(), a.end());
  long long ans = 0;
  for(int i=0;i<n;i++) {
    ans += a[i] * COM(i, k-1);
    ans -= a[i] * COM(n-i-1, k-1);
    ans %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 12928
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    int a[n];
    bool dp[k+1];   // dp[i]=1 if it is possible to win in 1 move for i no. of stones
    memset(dp,false,sizeof dp);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<=k;i++){
        for(int j=0;j<n;j++){   //i-a[j]<0 means move is not possible
            if(i-a[j]>=0 && dp[i-a[j]]==0){ //dp[i-a[j]]==0 implies that it is not possible to win in one move for i-a[j] number of stones
                dp[i]=1;break;
            }
        }
    }
    if(dp[k])   cout<<"First";
    else    cout<<"Second";
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;

int arr[100 + 5];
bool dp[100000 + 5];

int main(){
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int stones = 0; stones <= k; stones++) {
		for (int x : arr) {
			if (x > 0 and stones >= x and !dp[stones - x]) {
				dp[stones] = true;
			}
		}
	}


	cout << (dp[k] ? "First" : "Second") << endl;
	return 0;
}

Measured memory_bytes: 384
p=lambda x:print(x,end=' ')
n=input();p(n+':')
n=int(n);s=n**.5
while n%2==0 and n>3:p(2);n//=2
d=3
while s>d and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)


Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int main(){
  string s;
  cin>>s;
  bool f=1;
  if(s[0]!='A')f=0;
  ll cnt=0,x=-1;
  for(int i=2;i<s.size()-1;i++){
    if(s[i]=='C'){
      cnt++;
      x=i;
    }
  }
  if(cnt!=1)f=0;
  if(f)for(int i=1;i<s.size();i++)if(i!=x&&s[i]<='Z')f=0;
  cout<<(f?"AC":"WA")<<endl;
  return 0;
}


Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

struct UnionFind {
    parent: Vec<i64>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let parent = vec![-1; n];
        UnionFind { parent: parent }
    }

    fn root(&mut self, a: i64) -> i64 {
        if self.parent[a as usize] < 0 {
            a
        } else {
            let p = self.parent[a as usize];
            self.parent[a as usize] = self.root(p);
            self.parent[a as usize]
        }
    }

    fn size(&mut self, a: i64) -> i64 {
        let r = self.root(a);
        -self.parent[r as usize]
    }

    fn connect(&mut self, a: i64, b: i64) -> bool {
        let mut a = self.root(a);
        let mut b = self.root(b);

        if a == b {
            return false;
        }

        if self.size(a) < self.size(b) {
            std::mem::swap(&mut a, &mut b);
        }

        self.parent[a as usize] += self.parent[b as usize];
        self.parent[b as usize] = a;

        true
    }
}

fn main() {
    let n = input::<i64>();
    let m = input::<i64>();
    let ab = (0..m)
        .map(|_| {
            let a = input();
            let b = input();
            (a, b)
        })
        .collect::<Vec<(i64, i64)>>();

    let mut ans = vec![0i64; m as usize];
    ans[m as usize - 1] = n * (n - 1) / 2;

    let mut uni = UnionFind::new(n as usize);
    for i in (1..m).rev() {
        let (a, b) = ab[i as usize];

        ans[i as usize - 1] = ans[i as usize];
        if uni.root(a - 1) != uni.root(b - 1) {
            ans[i as usize - 1] -= uni.size(a - 1) * uni.size(b - 1);
            uni.connect(a - 1, b - 1);
        }
    }

    let stdout = std::io::stdout();
    let mut writer = std::io::BufWriter::new(stdout.lock());
    for an in ans {
        writeln!(writer, "{}", an).unwrap();
    }
}


Measured memory_bytes: 9468
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,d;
    cin >> n >> d;
    vector<vector<int>> x(n,vector<int>(d));

    for (int i = 0;i < n;i++){
        for (int j = 0;j < d;j++){
            cin >> x.at(i).at(j);
        }
    }
    int count = 0;
    double s;
    for (int i = 0;i < n;i++){
        for (int j = i + 1;j < n;j++){
            double sq = 0;
            for (int k = 0;k < d;k++){
                s = x.at(i).at(k) - x.at(j).at(k);
                sq += s * s;            
            }
            sq = sqrt(sq);
            if (ceil(sq) == floor(sq)){
                count++;
            }
        }
    }
    cout << count << endl;
}    

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;
 
const int N=2005; 

int n,f[N][N],a[N+N],typ[N+N],pos[2][N]; 
char col[N+N]; 

struct BinaryIndexedTree{
	int res,c[N+N]; 
	void update(int p,int x){
		for(;p<=n+n;p+=p&-p)c[p]+=x;
	}
	int query(int p){
		for(res=0;p>=1;p-=p&-p)res+=c[p]; 
		return res;
	}
	void clear(){
		memset(c,0,sizeof(c)); 
	}
} bit;

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin); 
	//freopen("my.out","w",stdout); 
#endif
	scanf("%d",&n); 
	rep(i,1,n+n){
		scanf(" %c%d",col+i,a+i); 
		typ[i]=col[i]=='W'?0:1;
		pos[typ[i]][a[i]]=i;
	}

	memset(f,0x3f,sizeof(f)); 
	f[0][0]=0; 
	rep(i,0,n){
		bit.clear();
		rep(k,i+1,n){
			bit.update(pos[0][k],1);
		}
		rep(j,1,n){
			bit.update(pos[1][j],1); 
		}
		rep(j,0,n){
			if(i!=n){
				int w=bit.query(pos[0][i+1])-1;
				cmin(f[i+1][j],f[i][j]+w); 
			}
			if(j!=n){
				int w=bit.query(pos[1][j+1])-1;
				cmin(f[i][j+1],f[i][j]+w); 
			}
			if(j!=n)bit.update(pos[1][j+1],-1); 
		}
	}
	printf("%d\n", f[n][n]);
	return 0; 
}

Measured memory_bytes: 16000
import static java.lang.Math.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			long[] p = in.nextLongArray(n);

			long[] a = new long[n];
			long[] b = new long[n];

			for (int i = 0; i < n; i++) {
				b[(int)(p[i]-1)] = (i+1);
			}

			for (int i = n-1; i > 0; i--) {
				b[i-1] = b[i-1] + b[i];
				a[i-1] -= b[i];
			}

			long min = Long.MAX_VALUE/10;
			for (long i : a) {
				min = min(min, i);
			}

			for (int i = 0; i < n; i++) {
				a[i] += abs(min) + 1;
			}

			for (int i = 0; i < n; i++) {
				if (i == 0) {
					out.print(a[i]);
				} else {
					out.print(" " + a[i]);
				}
			}
			out.print("\n");

			for (int i = 0; i < n; i++) {
				if (i == 0) {
					out.print(b[i]);
				} else {
					out.print(" " + b[i]);
				}
			}
			out.print("\n");

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}


Measured memory_bytes: 32112
import sys
import math

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inl():
    return list(map(int, input().split()))


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')



N = inp()
V = inl()
C = inl()

ans = 0
for v, c in zip(V, C):
    ans += max(0, v-c)
print(ans)


Measured memory_bytes: 3064
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Aizu Online Judge Algorithm and Data Structure, counting sort

import sys

def count_sort(A, n, k):
    C = [0 for i in range(k+1)]
    B = [None for i in range(n)]

    for val in A:
        C[val] += 1
    C[0] -= 1
    for i in range(1, k+1):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        val = A[i]
        B[C[val]] = val
        C[val] -= 1

    print(' '.join(map(str,B)))


MAX_NUM = 10000
n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
count_sort(A, n, MAX_NUM)



Measured memory_bytes: 242180
#include <bits/stdc++.h>

#define fi first
#define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<char,int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

const ll INF = LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MAXN = 1e5+20;
const double EPS= 1e-10;
const int nax= 300;

int main(){
    int n;
    cin>>n ;
    int arr[n];
    forn(i,n) cin>> arr[i];
    ll dp[n][n];
    for(int l= n-1; l>=0 ; l--){
        for(int r= l; r<n; r++){
            if(l==r){
                dp[l][r]= arr[l];
                continue;
            }
            dp[l][r]= max(arr[l]- dp[l+1][r], arr[r]- dp[l][r-1]);
        }
    }
    cout<< dp[0][n-1]<<el;
}



Measured memory_bytes: 46464
#include <iostream>
using namespace std;
long n,a,i,x,y,z;
int main() {
    cin >> n;
    cin >> a;
    x = y = z = a;
    while (++i < n) {
        cin >> a;
        if (x > a) x = a;
        if (y < a) y = a;
        z += a;
    }
    cout << x << " " << y << " " << z << endl;
    return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <limits>
#include <functional>
#include <cassert>
#include <numeric>
#include <bitset>

#define FOR(x,n) for(int x = 0; x < n; x++)
#define PUT(x) cout << x << endl
#define DPUT(x) printf("%.15lf\n",x)
#define GET(x,y) std::get<x>(y)
#define CHMAX(x,y) x = std::max(x,y)
#define CHMIN(x,y) x = std::min(x,y)
#define SP_END (i != n - 1 ? ' ' : '\n') ;

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;
using vch = std::vector<char>;
using vvch = std::vector<vch>;
using tiii = std::tuple<int, int, int>;

const ll mod197 = 1000000007LL;
const ll INF = 10000000000LL;

const double PI11 = 3.14159265359;

const int dis[5] = { 0,1,0,-1,0 };

const int disD[4] = { 0,1,1,0 };

int main(void)
{

	int a, b, c, x;
	cin >> a >> b >> c >> x;

	int answer = 0;

	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if(500 * i + 100 * j + 50 * k == x)
					answer++;
			}
		}
	}

	cout << answer << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n;
    cin >> n;

    vector<ll> a(n);

    ll atmp;

    for (int i=0; i<n; i++) {
        cin >> atmp;
        a.at(i) = -atmp;
    }

    ll ans = 0;

    sort(a.begin(), a.end());

    ll ind = n/2;

    for (int i=0; i<ind; i++) {
        ans -= 2*a.at(i);
    }

    if (n%2) {
        ans -= a.at(ind);
    }

    ans += a.at(0);

    cout << ans << endl;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
using namespace std;

long long int dp[200005][3];
int main(){
int N;
cin >> N;
long long int a[N];
int i,j;
for(i=0;i<N;i++)cin >> a[i];
if(N%2==0){
    dp[0][0]=a[0];
    dp[1][1]=a[1];
    for(i=2;i<N;i+=2){
        for(j=0;j<2;j++){
            dp[i][j]=dp[i-2][j]+a[i];
            dp[i+1][j]=dp[i-1][j]+a[i+1];
        }
        dp[i+1][1]=max(dp[i-2][0]+a[i+1],dp[i+1][1]);
    }
    long long int ans=max(dp[N-2][0],dp[N-1][1]);
    cout << ans << endl;
}
else{
    dp[0][0]=a[0];
    dp[1][1]=a[1];
    for(i=2;i<N;i+=2){
        for(j=0;j<3;j++){
            dp[i][j]=dp[i-2][j]+a[i];
            dp[i+1][j]=dp[i-1][j]+a[i+1];
        }
        dp[i+1][1]=max(dp[i-2][0]+a[i+1],dp[i+1][1]);
        if(i>=4){
            dp[i][2]=max(max(dp[i-4][0]+a[i],dp[i-3][1]+a[i]),dp[i][2]);
    }}
    long long int ans=max(max(dp[N-3][0],dp[N-2][1]),dp[N-1][2]);
    cout << ans << endl;    
}
}

Measured memory_bytes: 9864
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] h = new int[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
            if (k <= h[i]) count++;
        }
       
        System.out.println(count);
        
    }
}

Measured memory_bytes: 58224
#include <iostream>
#include <string>

using namespace std;

int main(){
	string s;
	cin >> s;

	for(int i=0; i < (int)s.size()-2; i++){
		if( s[i] == s[i+2]){
			if(s[i] == s[i+1]){
				cout << "Yes" << endl;
				return 0;
			}
			i++;
		}	
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long int gcd(long long int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

long long int lcm(long long int a, int b)
{
   return a * b / gcd(a, b);
}

int main()
{
   long long int a, b;
   cin >> a >> b;


   cout << lcm(a, b) << endl;
   return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>

int main(void)
{
    int n,d1[101],d2[101],i;
    scanf("%d",&n);
    for(i = 0 ; i < n ; i++)
    {
        scanf("%d %d",&d1[i],&d2[i]);
    }
    for(i = 0 ; i <= n - 3 ; i++)
    {
        if(d1[i] == d2[i] && d1[i + 1] == d2[i + 1] && d1[i + 2] == d2[i + 2])
        {
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 1644
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<algorithm>
#include <cstring>
#include<set>
#include<cmath>
# define ll long long 
using namespace std;

int main()
{
	ll s,w;
	cin>>s>>w;
	if(w>=s)
		cout<<"unsafe\n";
	else
		cout<<"safe\n";
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>

int main(void)
{
	char str[1000];
	const char *apple = "apple";
	const char *peach = "peach";
	int i;

	gets(str);
	for (i = 0; str[i] != 0; i++){
		if (strncmp(&str[i], apple, 5) == 0){
			strncpy(str + i, peach, 5);
		}
		else if (strncmp(&str[i], peach, 5) == 0){
			strncpy(str + i, apple, 5);
		}
	}
	puts(str);

	return 0;
}

Measured memory_bytes: 524
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
primes = []

for i in range(2, n+1):
    ok = True
    for j in range(2, i):
        if i % j == 0:
            ok = False
            break
    if ok:
        primes.append(i)

es = []
for p in primes:
    k = n//p
    e = 0
    while k > 0:
        e += k
        k //= p
    es.append(e)
# print(es)

# 3*5*5
# 15*5
# 25*3
# 75

m = len(es)

ct = 0
for i in range(m):
    for j in range(i+1, m):
        for k in range(m):
            if i != k and j != k and es[i] >= 4 and es[j] >= 4 and es[k] >= 2:
                ct += 1

for i in range(m):
    for j in range(m):
        if i != j and es[i] >= 14 and es[j] >= 4:
            ct += 1

for i in range(m):
    for j in range(m):
        if i != j and es[i] >= 24 and es[j] >= 2:
            ct += 1

for i in range(m):
    if es[i] >= 74:
        ct += 1

print(ct)


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stdio.h>
#include<ctype.h>
using namespace std;
int main()
{
	int m, n;
	cin >> m >> n;
	vector<int> a(n);
	vector<int> c(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int f = 0;
	int ans = 0;

	for (int i = 0; i < n - 1; i++)
	{
		f++;
		if (a[i] != a[i + 1])
		{
			c.at(ans) = f;

			f = 0;
			ans++;

		}

	}
	int hh = 0;
	if (a[n - 1] == a[n - 2])
	{
		f++;
		c.at(ans) = f;
	}
	else
	{

		c.at(ans) = 1;
	}
	vector<int> bb(n);
	vector<int> aa(n);
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0)
		{
			aa.at(i) = 1;
			bb.at(i) = 2;
		}
		else
		{
			aa.at(i) = 2;
			bb.at(i) = 1;

		}
	}
	if (m == 2)
	{
		int s = 0;
		int ss = 0;
		for (int i = 0; i < n; i++)
		{
			if (a[i] == aa[i])
			{
				s++;
			}
			if (a[i] == bb[i])
			{
				ss++;
			}
		}
		cout << min(s, ss)<<endl;
	}
	else
	{
		for (int i = 0; i < ans + 1; i++)
		{

			
			
				int g = c.at(i) / 2;
				hh += g;
			
		}
		cout << hh << endl;
	}


}



Measured memory_bytes: 4416
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int N,A,B,C;
vector<int> L;

int dfs(int i,int a,int b,int c){
    if(i==N){
        if(a==0||b==0||c==0) return 1e8;
        return abs(a-A)+abs(b-B)+abs(c-C);
    }
    int res=dfs(i+1,a,b,c); //L[i]の竹を選択しない
    
    res=min(res,dfs(i+1,a+L[i],b,c)+(a?10:0)); //L[i]の竹を選択
    res=min(res,dfs(i+1,a,b+L[i],c)+(b?10:0));
    res=min(res,dfs(i+1,a,b,c+L[i])+(c?10:0));

    return res;
}

int main(){
    cin >> N >> A >> B >> C;
    L.resize(N);
    for(int i=0;i<N;i++){
        cin >> L[i];
    }
    cout << dfs(0,0,0,0) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void){
  char s[3][101];
  scanf("%s%s%s",s[0],s[1],s[2]);

  int cnt[3] = {0,0,0};
  int turn = 0;
  while(1){
    if(s[turn][cnt[turn]] == 0){
      printf("%c\n",'A'+turn);
      return 0;
    }
    turn = s[turn][cnt[turn]++]-'a';
  }
}

Measured memory_bytes: 128
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    if((a == 5 && b == 5 && c == 7) || (a == 5 && b == 7 && c == 5) || (a == 7 && b == 5 && c == 5)){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    return 0;
}


Measured memory_bytes: 256
A = list(map(int, input().split()))
cost = 0
dif_1to2 = abs(A[0]-A[1])
dif_1to3 = abs(A[0]-A[2])
dif_2to3 = abs(A[1]-A[2])
dif = [dif_1to2,dif_1to3,dif_2to3]
print(sum(dif)-max(dif))

Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //コード
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();

        String a = str.substring(2, 3);
        String b = str.substring(4, 5);
        String c = str.substring(3, 4);
        String d = str.substring(5, 6);

       if (a.equals(c) && (b.equals(d))) {
           System.out.println("Yes");
       } else{
           System.out.println("No");
       }
    }
}

Measured memory_bytes: 21716
#include<iostream>
using namespace std;

int main()
{
    char c1,c2,moji;
    int cup[3]={0};
    cup[0]=1;
    while(cin>>c1>>moji>>c2,!cin.eof()){
        int c;
        c=cup[(int)c1-(int)'A'];
        cup[(int)c1-(int)'A']=cup[(int)c2-(int)'A'];
        cup[(int)c2-(int)'A']=c;
    }
    for(int i=0;i<3;i++){
        if(cup[i]==1){
            cout<<(char)((int)'A'+i)<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1132
#include<bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x)  (long long)(x).size()
#define sqr(x) (x)*(x)
#define sof sizeof
#define ins insert
#define lowerB lower_bound
#define upperB upper_bound
#define mkp make_pair
#define mkt make_tuple
#define act(a,v) (get<(long long)a>(v))
#define mod 1000000007
#define mod1 998244353
#define N 1000003
#define inf 1e18
#define minf -1e18
#define min3(a,b,c) min(a,min(b,c));
#define max3(a,b,c) max(a,max(b,c));
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define sumall(v) accumulate(all(v),(ll)0)
#define sum accumulate
#define FastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PRECISION std::cout.unsetf ( std::ios::floatfield );std::cout.precision(15)
#define PI M_PI
#define fi first
#define se second
#define here cout<<"RSSB"<<endl
#define showzero cout<<std::showpoint
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define br "\n"
#define sp " "
#define zero (ll)0
using namespace  std ;
typedef double db;
typedef long long ll ;
typedef vector<int>vi ;
//typedef vector<l>vl ;
typedef vector<ll>vll ;
typedef vector<vector<ll> >vvl ;
typedef pair<int,int> pii ;
typedef pair<ll,ll> pll ;
typedef vector<pll>vpll;
typedef vector<string>vstr;
typedef vector<bool>vbool ;
void READ(vll &v, ll n)
{
    ll a ;
    for(ll i=0 ; i<n ; i=i+1)
    {
        cin>>a ;
        v.pb(a) ;
    }
}
void PRINT(vll &v , ll a = 0)
{
    //ll a ;
    for(ll i=a ; i<v.size() ; i=i+1)
    {
        v[i] = max((ll)0,v[i]);
        cout<<v[i]<<" " ;
    }
    cout<<"\n" ;
}
/*vbool isprime(N,true);
vll spf(N,0);
vll prime;
void sieve()
{
    isprime[0] = isprime[1] = false;
    for(ll i = 2 ; i<N ; i++)
    {
        if(isprime[i])
        {
            for(ll j=2*i ; j<N ; j+=i)
            {
                isprime[j] = false;
                if(spf[j]==0)
                {
                    spf[j] = i;
                }
            }
            prime.pb(i);
        }
    }
}*//*
ll nck(ll n , ll k ,ll m=1e18+7)
{
    ll i , j,b=1,c=1 ;
    if(n-k<k)
    {
        k = n-k ;
    }
    while(k)
    {
        b*=n ;
        c*=k ;
        ll g = __gcd(b,c) ;
        b/=g ;
        c/=g ;
        n--;
        k-- ;
    }
    return(b) ;
}*//*
long long power(long long k , long long n , long long m=mod)
{
    long long res = 1;
    while(n)
    {
        if(n%2!=0)
        {
            res = (res*k)%m ;
        }
        k = (k*k)%m ;
        n = n/2 ;
    }
    return(res) ;
}*/
ll n,m,k,l,r;
bool ok = false;
int main()
{
    FastIO ;
    PRECISION ;
    ll a,b,c,d,i,j,t,x,y,z;//,x1,y1,z1,e,f;
    ll p,q,r,u,w ;
    char ch,chr ;
    string str,st,str1,str2,str3,str4;
    //ll a1=0,a2=0,b1=0,b2=0,c1=0 ;
    //cin>>str>>str1;
    cin>>a>>b>>c>>d;
    x = (c+b-1)/b;
    y = (a+d-1)/d;
    if(x>y)
    {
        cout<<"No";
    }
    else
    {
        cout<<"Yes";
    }
}

Measured memory_bytes: 3644
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
s = gets.chomp
size = s.size

1.upto(size-1) do |i|
  next if (size-i).odd?
  t = s.slice(0,size-i)

  mid = (size-i)/2
  flg = true
  mid.times do |j|
    if t[j] != t[mid+j]
      flg = false
      break
    end
  end
  if flg
    puts size - i
    exit
  end
end

puts 0



Measured memory_bytes: 2172
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

template <typename T>
T gcd(T x, T y)
{
    T xy = x * y;
    if (x < y)
        swap(x, y);
    T r;
    r = x % y;
    while (r != 0)
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
};

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n)
    {
        cin >> a[i];
    }

    vector<int> l(n);
    vector<int> r(n);

    l[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        l[i] = gcd(a[i-1],l[i-1]);
    }

    r[n-2] = a[n-1];

    for (int i = 3; i < n+1; i++)
    {
        r[n-i] = gcd(a[n-i+1],r[n-i+1]);
    }

    int ans;
    int temp;

    rep(i,n)
    {
        if (i==0)
        {
            ans = r[0];
        }else if (i==n-1)
        {
            ans = max(ans,l[n-1]);
        }else
        {
            temp = gcd(l[i],r[i]);
            ans = max(ans,temp);
        }
    }
    
    cout << ans << endl;

    
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;

int H, W;
vector<string> S;
vector<vector<int>> C;
vector<int> dy = { 1, -1, 0, 0 };
vector<int> dx = { 0, 0, -1, 1 };

void dfs(int y, int x, int color) {
  C.at(y).at(x) = color;
  for (int d = 0; d < 4; d++) {
    int ny = y + dy.at(d);
    int nx = x + dx.at(d);
    if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
    if (C.at(ny).at(nx) != -1) continue;
    if (S.at(y).at(x) == '#') {
      if (S.at(ny).at(nx) == '.') dfs(ny, nx, color);
    }
    else {
      if (S.at(ny).at(nx) == '#') dfs(ny, nx, color);
    }
  }
}

int main() {
  cin >> H >> W;
  S.resize(H);
  for (int i = 0; i < H; i++) cin >> S.at(i);
  C = vector<vector<int>>(H, vector<int>(W, -1));
  int color = 0;
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      if (S.at(y).at(x) == '.') continue;
      if (C.at(y).at(x) != -1) continue;
      dfs(y, x, color);
      color++;
    }
  }
  map<long long, long long> black, white;
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      if (S.at(y).at(x) == '#') {
        if (black.count(C.at(y).at(x))) black[C.at(y).at(x)]++;
        else black[C.at(y).at(x)] = 1;
      }
      else {
        if (C.at(y).at(x) == -1) continue;
        if (white.count(C.at(y).at(x))) white[C.at(y).at(x)]++;
        else white[C.at(y).at(x)] = 1;
      }
    }
  }
  long long ans = 0;
  for (auto p : black) ans += p.second * white[p.first];
  cout << ans << endl;
}


Measured memory_bytes: 21120
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static AtCoderTemplate.MyLibrary;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main (string[] args)
        {
            long ans = long.MaxValue;

            string[] str1 = Console.ReadLine ().Split (' ');
            var N = int.Parse (str1[0]);
            var M = int.Parse (str1[1]);
            var X = int.Parse (str1[2]);

            var C = new int[N];
            var A = new int[12, 12];
            for (int i = 0; i < N; i++)
            {
                string[] str2 = Console.ReadLine ().Split (' ');
                C[i] = int.Parse (str2[0]);
                for (int j = 0; j < M; j++)
                {
                    A[i, j] = int.Parse (str2[j + 1]);
                }

            }

            long total = 0;
            for (int bit = 0; bit < (1 << N); bit++)
            {
                total = 0;
                int[] sum = new int[M];
                for (int i = 0; i < N; i++)
                {
                    if ((bit & (1 << i)) > 0)
                    {
                        total += C[i];
                        for (int j = 0; j < M; j++)
                        {
                            sum[j] += A[i, j];
                        }
                    }
                }
                for (int j = 0; j < M; j++)
                {
                    if (sum[j] < X) total = long.MaxValue;
                }
                if (total < ans) ans = total;

            }

            if (ans == long.MaxValue) Console.WriteLine (-1);
            else Console.WriteLine (ans);
        }

    }

    class MyLibrary
    {

        // 自作の関数
        public static int MyFunction (int n)
        {
            return 0;
        }
    }
}

Measured memory_bytes: 27788
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int A, B; cin >> A >> B;
	int ans = INF;
	REP(i, 1, 1001) {
		int a = (i * 8) / 100;
		int b = (i * 10) / 100;
		if (a == A && b == B)ans = min(ans, i);
	}
	if (ans == INF)ans = -1;
	cout << ans << "\n";

		
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

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

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  ll now = 7;

  ll K; cin >> K;
  int N = 1000000;
  map<ll,int> m;

  for(int i = 1; i < N; i++){
    now %= K;
    if(now == 0){
      cout << i << endl;
      return 0;
    }

    if(m.count(now) != 0){
      cout << -1 << endl;
      return 0;
    }
    now = now * 10 + 7;
  }

  cout << -1 << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;

int main() {
  int A, B, C;
  cin >> A >> B >> C ;

  int pattern_A = A * B;
  
  if ( pattern_A < C ){
  	cout << pattern_A << endl;
  }
  else {
    cout << C << endl;
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    double xn,xi,yn,yi;
    cin >> xn >> yn >> xi >> yi;
    double x = (xn-xi)*(xn-xi);
    double y = (yn-yi)*(yn-yi);
    cout << fixed << setprecision(15) << sqrt(x+y) << endl;
}


Measured memory_bytes: 3264
#include<bits/stdc++.h>
using namespace std;

main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long i,j,k,l,m,n,p,t;

while(cin>>m>>n){
    int x[m];
    for(i=0;i<m;i++)cin>>x[i];
    sort(x,x+m);
    j=0;
    for(i=0;i<n;i++)j+=x[i];
    cout<<j<<endl;
}
return 0;
}


Measured memory_bytes: 3620
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    if hp < 0:
        return 0
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)









"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Measured memory_bytes: 111188
#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m; cin>>n>>m;
	vector<bool>s(n+1,false),g(n+1,false);
	for(int i=0;i<m;++i){
		int a,b; cin>>a>>b;
		if(a==1)s.at(b)=true;
		if(b==n)g.at(a)=true;
	}
	int i=1; while(i<=n&&!(s.at(i)&&g.at(i)))++i;
	cout<<(i>n?"IMPOSSIBLE"s:"POSSIBLE"s)<<"\n"s;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>

using namespace std;

constexpr int M = 3;

int b[M][M];

int main() {
	for(int i = 0; i < M; i++)
		for(int j = 0; j < M; j++)
			cin >> b[i][j];
	int N;
	cin >> N;
	for(int i = 0; i < N; i++) {
		int x;
		cin >> x;
		for(int j = 0; j < M; j++)
			for(int k = 0; k < M; k++)
				if(b[j][k] == x)
					b[j][k] = 0;
	}
	for(int i = 0; i < M; i++) {
		for(int j = 0; j < M; j++)
			if(b[i][j])
				goto no1;
		goto yes;
no1:;
	}
	for(int i = 0; i < M; i++) {
		for(int j = 0; j < M; j++)
			if(b[j][i])
				goto no2;
		goto yes;
no2:;
   	}
   	for(int i = 0; i < M; i++)
   		if(b[i][i])
   			goto no3;
   	goto yes;
no3:;
	for(int i = 0; i < M; i++)
		if(b[2 - i][i])
			goto no4;
yes:
	cout << "Yes" << '\n';
	return 0;
no4:;
	cout << "No" << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll a;
  cin>>a;
  cout<<a+a*a+a*a*a<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
 
int main(){
    int K;
    int N;
    cin >> K >> N;
    int A[N];
    for (int i = 0; i < N; ++i) cin >> A[i];
    int max=0;
    int dis;
    for (int i = 1; i < N; ++i){
        dis=A[i]-A[i-1];
        if (dis > max){
            max=dis;
        }
    }
    dis=A[0]+K-A[N-1];
    if (dis>max){
        max=dis;
    }
    cout << K-max << endl;
}

Measured memory_bytes: 1656
N,M = map(int,input().split(" "))
S = input()
T = input()
# gcd
def gcd (a,b):
    if a < b:
        a,b = b,a
    return a if b == 0 else gcd(b,a%b)


g = gcd(N,M)
l = N*(M//g)
dic = {}
for i in range(N):
    dic[i*(l//N)] = S[i]
for i in range(M):
    if (i*(l//M)) in dic:
        if dic[i*(l//M)] != T[i]:
            print(-1)
            exit(0)

print(l)


Measured memory_bytes: 49904
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  string s, t;
  cin >> n;
  cin >> s >> t;
  string ans = "";
  for (int i=0; i<n; i++) {
    ans += s[i];
    ans += t[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int x, y, z, k;
  cin >> x >> y >> z >> k;
  vector<ll> xlist(x);
  for (int i = 0; i < x; i++) {
    cin >> xlist[i];
  }
  vector<ll> ylist(y);
  for (int i = 0; i < y; i++) {
    cin >> ylist[i];
  }
  vector<ll> zlist(z);
  for (int i = 0; i < z; i++) {
    cin >> zlist[i];
  }

  vector<ll> xylist(x * y);
  for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
      xylist[y * i + j] = xlist[i] + ylist[j];
    }
  }
  sort(xylist.begin(), xylist.end(), greater<ll>());

  int cnt = min(k, x * y);
  vector<ll> xyzlist(cnt * z);
  for (int i = 0; i < cnt; i++) {
    for (int j = 0; j < z; j++) {
      xyzlist[z * i + j] = xylist[i] + zlist[j];
    }
  }

  sort(xyzlist.begin(), xyzlist.end(), greater<ll>());
  for (int i = 0; i < k; i++) {
    cout << xyzlist[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 31616