akhauriyash/Code-Regression huggingface dataset:
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
// clang-format on

main {
  string s;
  cin >> s;
  s.pop_back();
  if (odd(s.size())) s.pop_back();
  for (;;) {
    if (s.substr(0, s.size() / 2) == s.substr(s.size() / 2, s.size() / 2)) {
      cout << s.size() << endl;
      return 0;
    }
    s.pop_back();
    s.pop_back();
  }
}


Measured memory_bytes: 256
import fractions
a, b, c, d = map(int, input().split())
lcm = (c*d) // fractions.gcd(c, d)
print(b - (a-1) - ((b // c + b // d - b // lcm) - ((a-1) // c + (a-1) // d - (a-1) // lcm)))

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

using namespace std;

typedef long long ll;

const int maxN = 1e5;

int cnt = 0;
vector<int> v[maxN];
vector<bool> visited(maxN, false);
vector<pair<int, int>> res;

void bfs(int node){
	cnt++;
	queue<int> q;
	q.push(node);
	visited[node] = true;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto x: v[u]){
			if(!visited[x]){
				res.push_back({x, u + 1});
				visited[x] = true;
				cnt++;
				q.push(x);
			}
		}
	}
}

int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	bfs(0);
	if(cnt < n){
		cout << "No" << '\n';
	}else{
		cout << "Yes" << '\n';
		sort(res.begin(), res.end());
		for(auto x: res) cout << x.second << '\n';
	}
}


Measured memory_bytes: 10940
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
 
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x first
#define y second
 
const int MOD = 1e9 + 7;
 
void setIO() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}
 
//ctrl q is comment
//ctrl b is run
//ctrl s is compile
//alt r is search & replace
//alt d is delete a line

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

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

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

const int mod = 1000000007;
class mint {
  long long x;

 public:
  mint(long long x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint& a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint& a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint& a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint& a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint& a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint& a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint& a) { return (*this) *= a.inv(); }
  mint operator/(const mint& a) const {
    mint res(*this);
    return res /= a;
  }

  friend ostream& operator<<(ostream& os, const mint& m) {
    os << m.x;
    return os;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
} comb(100005);

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  mint ans(1);

  for (int i = 1; i <= n; i++) {
    ans *= mint(i);
  }

  cout << ans << ln;

  return 0;
}

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

typedef long long ll;
const ll MOD = 1e9+7;
int n,d;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>d;
    cout<<(n+2*d)/(2*d+1);
    return 0;
}


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

using namespace std;

# define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;

# define S second
# define F first
# define kill(x) return(cout << x << endl, 0)
# define debug(x) cerr<< #x << " : " << x << endl
# define ddebug(x, y) cerr<< #x << " : " << x  << ", " << #y << " : " << y << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int a, b, c;
	cin >> a >> b >> c;
	for (int i = 0; i < 1000 * 1000; i ++)
	{
		if (a & 1 || b & 1 || c & 1)
			kill(i);
		int ap = a, bp = b, cp = c;
		a = (bp + cp) / 2, b = (ap + cp) / 2, c = (ap + bp) / 2;
	}
	cout << -1 << endl;


	return 0;
}


Measured memory_bytes: 256
m,d = map(int, input().split())
num_list = list(range(2,10))
count = 0
for i in range(2,m+1):
    for j in num_list:
        if i/j==int(i/j) and int(i/j)!=1:
            a = int(i/j)
            if int(str(a)+str(j))<=d:
                count +=1
print(count)

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define INF LONG_LONG_MAX
#define MOD 1000000007
#define yn(f) cout << (f ? "Yes" : "No") << endl;
#define YN(f) cout << (f ? "YES" : "NO") << endl;

int s,w;

signed main() {
    cin >> s >> w;
    if (s <= w) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}




Measured memory_bytes: 3624
#include<cstdio>
long long num[200050],n;
int main(){
	num[0]=-1;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&num[i]);
		if(num[i]-num[i-1]>1){puts("-1");return 0;}
	}
	long long ans=0;
	bool flag=false;
	for(int i=1;i<=n+1;i++)
		if(num[i]!=num[i-1]+1) ans+=num[i-1];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
n = int(input())
a = list(map(int,input().split()))
r = [0 for _ in range(100001)]
for i in range(n):
    r[a[i]] += 1
ans = 0
for i in range(len(r)-2):
    ans = max(ans,sum(r[i:i+3]))
print(ans)

Measured memory_bytes: 14008
# import copy
from sys import stdin
input = stdin.readline

n,m = map(int,input().split())
h = list(map(int,input().split()))
# p = copy.copy(h)
p = [0]*n
# path = list(list(map(int,input().split())) for x in range(m))
for i in range(m):
    x,y = map(int,input().split())
    if h[x-1] > h[y-1]:
        p[y-1] = 1
    elif h[x-1] < h[y-1]:
        p[x -1] = 1
    elif  h[x-1] == h[y-1]:
        p[y-1] = 1
        p[x-1] = 1


print(p.count(0))

Measured memory_bytes: 20212
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);

    ll a,b,c,d,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>str;
    if(str.length()==2&&str[0]==str[1]) {
      cout<<1<<" "<<2<<endl;
      return 0;
    }
    rep(i,str.length()-2){
      if(str[i]==str[i+1]){
        cout<<i+1<<" "<<i+3<<endl;
        return 0;
      }if(str[i]==str[i+2]){
        cout<<i+1<<" "<<i+3<<endl;
        return 0;
      }
    }
    if(str[str.length()-2]==str[str.length()-1]) {
      cout<<str.length()-2<<" "<<str.length()<<endl;
      return 0;
    }
    cout<<-1<<" "<<-1<<endl;
    
}


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

int main() {
	int s[31]={};
	int n;
	for (int i=0;i<28;i++){
		cin >> n;
		s[n]=1;
	}
	for (int i=1;i<31;i++){
		if(s[i]==0){
			cout << i << endl;
		}
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
int myctoi(char C) {return C - 48;}
char myitoc(int N) {return '0' + N;}
 
signed main()
{
  string A;
  cin >> A;
  int N = A.size();

  map<char, int> mp;
  for (int i = 0; i < N; i++)
  {
    mp[A.at(i)]++;
  }
  
  int ans = N * (N - 1) / 2 + 1;
  for (auto itr = mp.begin(); itr != mp.end(); itr++)
  {
    int M = itr->second;
    ans -= M * (M - 1) / 2;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 640
S=input()
m=0
count=0
for s in S:
  if s in "A":
    count+=1
  elif s in "C":
    count+=1
  elif s in "G":
    count+=1
  elif s in "T":
    count+=1
  else:
    count=0
  m=max(m,count)
print(m)

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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int N = 400 , _ = N + 3 , mo = 998244353;

template<typename T1,typename T2> inline T1 ad(T1 &a,T2 b){return a=a+b>=mo?a+b-mo:a+b;}
template<typename T1,typename T2> inline T1 dl(T1 &a,T2 b){return a=a>=b?a-b:a-b+mo;}

inline lint powa(lint a,lint t)
{
	lint b=1;
	while(t){if(t&1)b=b*a%mo;a=a*a%mo,t>>=1;}
	return b;
}

inline lint inva(lint a)
{
	return powa(a,mo-2);
}

lint jc[_],rjc[_];

inline void fuck(int n=_-1)
{
	jc[0]=jc[1]=rjc[0]=1;
	for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i%mo;
	rjc[n]=inva(jc[n]);
	for(int i=n-1;i>=1;i--)rjc[i]=rjc[i+1]*(1ll+i)%mo;
}

int n,lim[_];
lint f[_][_]={0},gai[_],sgai=0;

int main()
{
	n=ty();
	for(int i=1;i<=n;i++)gai[i]=ty(),lim[i]=ty(),sgai=(sgai+gai[i])%mo;
	
	fuck();
	f[0][0]=mo-1;
	for(int i=1;i<=n;i++)
		for(int j=sgai;j>=0;j--)
			for(int k=N;k>=0;k--)
				if(f[j][k])
					for(int a=0,x=1;a<lim[i];a++,x=1ll*x*gai[i]%mo)
						dl(f[j+gai[i]][k+a],f[j][k]*x%mo*rjc[a]%mo);
	lint ans=0;
	for(int i=1;i<=sgai;i++)
		for(int j=0,perx=inva(i),x=sgai*inva(i)%mo;j<=N;j++,x=1ll*x*perx%mo)
			ad(ans,f[i][j]*jc[j]%mo*x%mo);
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 1536
/*input

*/


//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9+7,N = 2e5+5;
ll power(ll x,ll y)
{
	ll ans=1;
	while(y)
	{
		if(y&1) ans = (ans*x)%mod;
		y>>=1;
		x=(x*x)%mod;
	}
	return ans;
}

ll inv(ll n)
{
	return power(n,mod-2)%mod;
}


ll ncr(ll n,ll r)
{
	if(r<=n && n>=0 && r>=0)
	{
		ll ans = 1;
		rep(i,0,r)
		{ 
			ans =( ans * (((n-i)*inv(i+1))%mod))%mod;
		}
		return ans;
	}
	else return 0;
}




int solve()
{
	ll n,a,b;cin>>n>>a>>b;

	// cout<<ncr(10,5)<<"\n";

	cout<<(((power(2,n)-1 + mod)%mod - ncr(n,a) +mod)%mod -ncr(n,b)+mod)%mod<<"\n";
	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	// cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

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

int main() {
  int A, B, M;
  cin >> A >> B >> M;
  vector<int> a(A), b(B);
  for (int i = 0; i < A; i++) {
    cin >> a.at(i);
  }
  for (int i = 0; i < B; i++) {
    cin >> b.at(i);
  }
  int ans = 1000000000;
  for (int i = 0; i < M; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--;
    y--;
    ans = min(ans, a.at(x) + b.at(y) - c);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  ans = min(ans, a.at(0) + b.at(0));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4004
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i++)
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
    cout<<a+b+c-max(max(a,b),c);
}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(lint i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(lint i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

int main(){
    int n, m;
    cin >> n >> m;
    int dis[25][25];
    rep(i, 25){
        rep(j, 25){
            dis[i][j] = IINF;
        }
        dis[i][i] = 0;
    }
    string tmp;
    int l = 0;
    rep(i, m){
        cin >> tmp;
        l = 0;
        int a = 0, b = 0, c = 0, d = 0;
        while(true){
            if(tmp[l] == ','){
                break;
            }
            a *= 10;
            a += tmp[l] - '0';
            l++;
        }
        l++;
        while(true){
            if(tmp[l] == ','){
                break;
            }
            b *= 10;
            b += tmp[l] - '0';
            l++;
        }
        l++;
        while(true){
            if(tmp[l] == ','){
                break;
            }
            c *= 10;
            c += tmp[l] - '0';
            l++;
        }
        l++;
        while(l < tmp.size()){
            d *= 10;
            d += tmp[l] - '0';
            l++;
        }
        a--;
        b--;
        dis[a][b] = c;
        dis[b][a] = d;
    }
    cin >> tmp;
    l = 0;
    int s = 0, g = 0, v = 0, p = 0;
    while(true){
        if(tmp[l] == ','){
            break;
        }
        s *= 10;
        s += tmp[l] - '0';
        l++;
    }
    l++;
    while(true){
        if(tmp[l] == ','){
            break;
        }
        g *= 10;
        g += tmp[l] - '0';
        l++;
    }
    l++;
    while(true){
        if(tmp[l] == ','){
            break;
        }
        v *= 10;
        v += tmp[l] - '0';
        l++;
    }
    l++;
    while(l < tmp.size()){
        p *= 10;
        p += tmp[l] - '0';
        l++;
    }
    s--;
    g--;
    rep(k, n){
        rep(i, n){
            rep(j, n){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    int ans = v - (dis[s][g] + dis[g][s] + p);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

namespace FFT {
  using DBL = double;
  using CD = complex<DBL>; // SLOW
  using Poly = vector<CD>;
  const DBL PI = acos(-1);
  void fft(Poly& a, bool invert) {
    const int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
      int bit = n >> 1;
      for (; j & bit; bit >>= 1) {
        j ^= bit;
      }
      j ^= bit;
      if (i < j) {
        swap(a[i], a[j]);
      }
    }
    for (int len = 2; len <= n; len <<= 1) {
      DBL ang = 2 * PI / len * (invert ? -1 : 1);
      CD wlen(cos(ang), sin(ang));
      for (int i = 0; i < n; i += len) {
        CD w(1);
        for (int j = 0; j < len / 2; j++) {
          CD u = a[i + j], v = a[i + j + len / 2] * w;
          a[i + j] = u + v;
          a[i + j + len / 2] = u - v;
          w = w * wlen;
        }
      }
    }

    if (invert) {
      DBL nn = n;
      for (CD &x: a) x = x / nn;
    }
  }


  vector<ll> mult(const VI& a, const VI& b) {
    const int lim = (a.size() + b.size()) - 1;
    int sz = 1;
    while (sz < lim) sz *= 2;

    Poly da(sz, 0), db(sz, 0);
    for (int i = 0; i < (int) a.size(); i++) {
      da[i] = a[i];
    }
    for (int i = 0; i < (int) b.size(); i++) {
      db[i] = b[i];
    }

    fft(da, false);
    fft(db, false);
    for (int i = 0; i < sz; i++) {
      da[i] = da[i] * db[i];
    }
    fft(da, true);

    vector<ll> res(sz);
    for (int i = 0; i < sz; i++) {
      res[i] = llround(da[i].real());
    }

    return res;
  }
} // namespace FFT

const int P = 200'003, g = 2;
int dlog[P], pwr[P];

int main() {
#ifdef LOCAL_EXEC
//	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  for (int i = 0, v = 1; i < P - 1; i++) {
    pwr[i] = v;
    dlog[v] = i;
    v = v * g % P;
  }

  int n; cin >> n;
  VI f(P);
  for (int i = 0; i < n; i++) {
    int a; cin >> a;
    if (a != 0) {
      f[dlog[a]]++;
    }
  }

  auto f2 = FFT::mult(f, f);
  ll ans = 0;
  for (int i = 0, v = 1; i < P - 1; i++) {
    ans += v * 1ll * (f2[i] + f2[i + P - 1]);
    ans -= pwr[(2 * i) % (P - 1)] * 1ll * f[i];
    v = v * g % P;
  }
  ans /= 2;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 26432
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
char ch[MAXN];
int A[MAXN] , a[MAXN] , B[MAXN] , mn[MAXN] , mmn = 0x3f3f3f3f;
bool us[MAXN];
void solve() {
	scanf("%s",ch + 1);
	n = strlen( ch + 1 );
	int mx = 0 , ps;
	rep( i , 1 , n ) {
		if( ch[i] == '?' || ch[i] == '0' ) A[i] = A[i - 1] - 1;
		else A[i] = A[i - 1] + 1;
		a[i] = A[i];
		mx = max( mx , A[i] );
	}
	rep( i , 0 , n ) if( A[i] == mx ) ps = i;
	B[n] = A[n];
	per( i , n - 1 , 1 ) B[i] = max( A[i] , B[i + 1] );
	int t = 0;
	rep( i , ps , n ) {
		if( ch[i] == '?' && B[i] + t <= mx - 2 ) t += 2 , us[i] = 1;
		A[i] += t;
	}
	mmn = 0;
	rep( i , 1 , n ) mmn = min( mmn , A[i] );
	int as = mx - mmn , chp = 0;
	mem( us );
	
	rep( i , 1 , n ) A[i] = a[i];
	t = 0;
	rep( i , ps , n ) {
		if( ch[i] == '?' && B[i] + t <= mx - 1 ) t += 2 , us[i] = 1;
		A[i] += t;
	}
	mmn = 0;
	rep( i , 1 , n ) mmn = min( mmn , A[i] );
	int as1 = mx + 1 - mmn , chp1 = 0;
	
	printf("%d\n",min( as1 , as ));
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

Measured memory_bytes: 17508
#include<bits/stdc++.h>
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
int main(){
	int m,k;
	m=read();
	k=read();
	if(k>=(1<<m))
	{
		puts("-1");
		return 0;
	}
	if(m==0)
	{
		puts("0 0");
		return 0;
	}
	if(m==1)
	{
		if(k==1)puts("-1");
		else puts("0 0 1 1");
		return 0;
	}
	for(int i=0;i<(1<<m);i++)
	{
		if(i==k)continue;
		printf("%d ",i);
	}
	printf("%d ",k);
	for(int i=(1<<m)-1;i>=0;i--)
	{
		if(i==k)continue;
		printf("%d ",i);
	}
	printf("%d ",k);
	return 0;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h> 
#define int long long
#define quickie ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rep1(i, a, b) for(int i=a; i<=b; i++)
#define repp(i, a, b) for(int i=b-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define db double
#define mi map<int, int>
#define mc map<char, int>
#define ms map<string, int>
#define vi vector<int>
#define qi queue<int>
#define MI(x) power(x, mod-2)
#define test int t; cin >> t;
//#define mod 1000000007LL
#define mod 998244353 
using namespace std;
int power(int x, int y) ;
int gcd(int a, int b) ;
#define pi 3.141592653589
const int lll = 39800;
vi t(4*lll);
vi ans;

void solve(int v, int tl, int tr)
{
	if(tl==tr) {
		t[v] = ans[tl];
	}
	else {
		int tm = (tl+tr)/2;
		solve(v*2,tl,tm);
		solve(v*2+1,tm+1,tr);
		t[v]=t[v*2]+t[v*2+1];
	}
}

int fun(int v, int tl, int tr, int l, int r)
{
	if(l>r)
		return 0;
	if(tl==l&&tr==r)
		return t[v];
	int tm = (tl+tr)/2;
	return fun(v*2,tl,tm,l,min(r,tm))+fun(v*2+1,tm+1,tr,max(l,tm+1),r);
}

signed main() {
    quickie 
    int n, m ;
    cin >> n >> m ;
    if(m >= n) cout << "unsafe\n" ;
    else cout << "safe\n" ;
}

int power(int x, int y) {
    int res = 1; x %= mod;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res%mod;
}
 
int gcd(int a,int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

Measured memory_bytes: 4428
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int n;

char sol(char c) {
	int ci = c;
	ci += n;
	if (ci > 90) {
		ci -= 26;
	}
	char res = ci;
	return res;
}

int main() {
	cin >> n;
	string s;
	cin >> s;
	vector<char> svec;
	vector<char> ans;
	for (int i = 0; i < s.size(); i++) {
		char c = s.at(i);
		ans.push_back(sol(c));
	}
	for (char c : ans) {
		cout << c;
	}
}

Measured memory_bytes: 256
/*mokosucio's file*/
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define fs first
#define sc second
#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using ll = long long;
const ll inf = 1e9+5; 

const double PI =  3.141592653589793;

int main(){
	IO;
	double n;
	cin>>n;
	printf("%.12f",n*2*PI);
	return 0;
}



Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i=0;i<(int)(n);++i)
template <typename T> ll gcd(T a, T b) {return b?gcd(b, a%b):a;}
template <typename T> ll lcm(T a, T b) {return a * b / gcd(a, b);};
template <typename T> inline void chmin(T &a, const T& b){if(a>b)a=b;}
template <typename T> inline void chmax(T &a, const T& b){if(a<b)a=b;}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  bool ans = 1;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    if (a %2 == 0) {
      if (!(a % 3 == 0 || a%5 == 0)) ans = false; 
    } 
  }
  if (ans) cout << "APPROVED" << '\n';
  else cout << "DENIED" << '\n';
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int n,k;cin>>n>>k;
    map<int,int>b;
    rep(i,k){
        int d;cin>>d;
        rep(j,d){
            int a;cin>>a;
            a--;
            b[a]++;
        }
    }
    int ans=0;
    rep(i,n){
        if(b[i]==0)ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3576
#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


if __name__ == '__main__':
    main()


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

const int N = 1e6+100;
const ll INF = 1e18;

char* str[N];

int n, m;
int k;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

int getpos(int i, int j) {
    return (i-1)*m + j;
}

ll ans[N<<2];

int sta(int s, int dir) {
    return (s << 2) | dir;
}

ll anss(ll dis, ll use) {
    return (dis << 20) | use;
}

priority_queue<pii, vector<pii>, greater<pii> > que;
void dijkstra(int s) {

    for (int i = 0; i < (N<<2); i++) {
        ans[i] = INF;
    }

    for (int i = 0; i < 4; i++) {
        ans[sta(s, i)] = anss(0, k);
        que.push(pii(anss(0, k), sta(s, i)));
    }

    while (!que.empty()) {
        pii u = que.top();
        que.pop();

        if (u.first > ans[u.second]) {
            continue;
        }

        int pos = (u.second >> 2);
        int dir = (u.second & 3);
        int o_dis = (u.first >> 20);
        int use = (u.first & 0xfffff);
        int x, y;
        if (pos % m == 0) {
            x = pos/m, y = m;
        } else {
            x = pos/m+1, y = pos%m;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && str[nx][ny] == '.') {
                int ndis = o_dis;
                int nuse = 1;
                if (i == dir && use < k) {
                    nuse = use+1;
                } else {
                    ndis++;
                }
                ll curdis = anss(ndis, nuse);
                int cursta = sta(getpos(nx, ny), i);
                if (curdis < ans[cursta]) {
                    ans[cursta] = curdis;
                    que.push(pii(curdis, cursta));
                }
            }
        }

    }

}

void solve() {
    scanf("%d%d%d", &n, &m, &k);

    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

    for (int i = 1; i <= n; i++) {
        str[i] = new char [m+5];
        scanf("%s", str[i]+1);
    }

    dijkstra(getpos(x1, y1));

    int pos = getpos(x2, y2);

    ll o = INF;
    for (int i = 0; i < 4; i++) {
        o = min(o, ans[sta(pos, i)]);
    }

    if (o == INF) {
        printf("-1\n");
        return ;
    }

    printf("%lld\n", (o >> 20));

}

int main(){

    solve();
	return 0;
}


Measured memory_bytes: 39620
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict


class Solution:
    def main(self):
        N = int(input())
        W =list(map(int, input().split()))
        res = float('inf')
        for i in range(1, N):
            res = min(res, abs(sum(W[:i])-sum(W[i:])))
        print(res)


if __name__ == '__main__':
    Solution().main()

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP0(i, n) for (int i = (n)-1; i >= 0; --i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define RREP1(i, n) for (int i = (n); i >= 1; --i)
#define pow10(n) int(1e##n + n)

typedef long long LL;
typedef pair<int, int> P;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;

void solve()
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    map<char, int> mp;
    for (auto c : S)
    {
        mp[c]++;
    }

    LL triple_n = 1;
    triple_n *= mp['R'];
    triple_n *= mp['G'];
    triple_n *= mp['B'];

    for (int d = 1; d * 2 < N; d++)
    {
        for (int i = 0; i + d * 2 < N; i++)
        {
            if (S[i] != S[i + d] and S[i + d] != S[i + 2 * d] and S[i] != S[i + 2 * d])
                triple_n--;
        }
    }

    std::cout << triple_n << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(20);
    solve();
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define watch(x) cout<<"->"<<#x<<" : "<<x<<endl;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c)) 
typedef long long ll;
typedef unsigned long long llu;
const double PI = 2*acos(0.0);

signed main()
{
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	int h[n];
	for(int i=0;i<n;i++)cin>>h[i];
	sort(h,h+n);
	int res = INT_MAX;
	for(int i=0;i<=n-k;i++)
		res = min(res,h[i+k-1]-h[i]);
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;


int main() {
  int N;
  string s;

  cin >> N;
  cin >> s;

  int r = 0;
  int b = 0;
  for (int i = 0; i < N; i++) {
    if (s[i] == 'R') {
      r++;
    } else {
      b++;
    }
  }

  if (r > b) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int a,b;
	char c;
	cin >> a >> c >> b;
	if(c=='+') cout << a+b;
	if(c=='-') cout << a-b;
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()

using namespace std;

int _h[10001];
int _m[10001];

int H, N;
int A[1010];
int B[1010];

signed main()
{
	cin >> H >> N;
	REP(i, N) cin >> A[i] >> B[i];

	_h[0] = 0;
	_m[0] = 0;

	for (int i = 1; i <= H; i++)
	{
		int min_m = INT_MAX;
		int min_h = -1;

		for (int j = 0; j < N; j++)
		{
			int pi = MAX(0, i - A[j]);

			int new_m;
			int new_h;

			if (_h[pi] >= i)
			{
				new_m = _m[pi];
				new_h = _h[pi];
			}
			else
			{
				new_m = _m[pi] + B[j];
				new_h = _h[pi] + A[j];
			}

			if (min_m > new_m)
			{
				min_m = new_m;
				min_h = new_h;
			}
		}

		_h[i] = min_h;
		_m[i] = min_m;
	}

	cout << _m[H] << endl;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long x = in.nextLong();
		long y = in.nextLong();
		long count = 0;
		while(x<=y) {
			x = x<<1;
			count++;
		}
		System.out.println(count);
		in.close();
	}

}


Measured memory_bytes: 23764
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define LLI long long int

LLI comb[51][51];

void combtable(){
    for(int i = 0; i < 51; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0 || i == j){
                comb[i][j] = 1;
            }else{
                comb[i][j] = comb[i-1][j-1]+comb[i-1][j];
            }
        }
    }
}

int minimam(int a,int b){
    if(a < b){
        return a;
    }else{
        return b;
    }
}

LLI comb2(int n,int r,int m){
    LLI result = 0;

    for(int i = r; i <= m; i++){
        result += comb[n][i];
    }

    return result;

}

int main(){
    int n,a,b;

    cin >> n >> a >> b;

    vector<LLI> vec(n);

    combtable();

    for(int i = 0; i < n; i++){
        cin >> vec[i];
    }

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

    LLI mini,minm;

    double result = 0.0;

    int j = 0;

    for(int i = n-1;j < a && i >= 0; i--,j++){
        result += vec[i];
        mini = i;
        minm = vec[i];
    }

    int count = 1;
    int frag = 0;
    int mi,ma;
    for(int i = 0; i < n; i++){
        if(frag == 0){
            if(minm == vec[i]){
                mi = i;
                frag = 1;
            }
        }else if(frag == 1){
            if(minm != vec[i]){
                ma = i-1;
                frag = 2;
            }
        }
    }

    if(frag == 1){
        ma = n-1;
    }

    int must = ma-mini+1;
    int poss = ma-mi+1;
    int len = poss;
    poss = minimam(poss,b-(n-ma-1));


    if(ma != n-1){
        cout << fixed;
        cout << setprecision(17) << (result/(double)a) << endl;
        cout << comb[len][must] << endl;
    }else{
        cout << fixed;
        cout << setprecision(17) << (double)(result/(double)a) << endl;
        cout << comb2(len,must,poss) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;

//union_find begin
#define MAX 5000000
struct node{  int parent,size; };
node tree[MAX];
void init(){
  for(int i=0;i<MAX;i++){
    tree[i].parent=i;
    tree[i].size=1;    
  }
}
/*
int find(int x){ 
  if(tree[x].parent==x)return x;
  tree[x].parent = find( tree[x].parent );
  return tree[x].parent;
}
*/
int st[MAX],cnt;
int find(int x){
  cnt=0;
  while(tree[x].parent!=x){    
    st[cnt++]=x;
    x=tree[x].parent;
  }
  while(cnt>0){
    cnt--;
    tree[st[cnt]].parent=x;
  }
  return x;
}

int count(int x){
  x=find(x);
  return tree[x].size;
}

bool same(int x,int y){
  return ( find(x) == find(y) );
}

void unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return;  
  if(count(x)>count(y))swap(x,y);
  tree[x].parent=y;
  tree[y].size+=tree[x].size;
}
// union find end

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int W,H,N,target;
char t[1005][1005];

int change(int i,int j){
  return i*W+j;
}

int solve(){
  if(same(0,target))return 0;
  scanf("%d",&N);
  for(int ans=1;ans<=N;ans++){
    int i,j;
    scanf("%d %d",&j,&i);
    if(t[i][j]=='.')continue;
    t[i][j]='.';
    for(int k=0;k<4;k++){
      int ni=i+dy[k];
      int nj=j+dx[k];
      if(ni<0 || nj<0 || H<=ni || W<=nj)continue;
      if(t[ni][nj]=='#')continue;
      unite( change(i,j) , change(ni,nj) );
    }
    if(same(target,0))return ans;
  }
  return -1;
}

int main(){
  init();
  scanf("%d %d",&W,&H);
  for(int i=0;i<H;i++){
    scanf("%s",t[i]);
    for(int j=0;j<W;j++){
      if(t[i][j]=='t')target=change(i,j);
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(t[i][j]=='#')continue;
      for(int k=0;k<4;k++){
        int ni=i+dy[k];
        int nj=j+dx[k];
        if(ni<0 || nj<0 || H<=ni || W<=nj)continue;
        if(t[ni][nj]=='#')continue;
        unite( change(i,j) , change(ni,nj) );
      }
    }
  }
  printf("%d\n",solve());
  return 0;
}

Measured memory_bytes: 41284
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


int main() {
	int N; cin >> N;
	while (N--) {
		int nx = 0, ny = 0;
		int amax = 0;
		pair<int, int>ans;
		while (1) {
			int dx, dy; cin >> dx >> dy;
			if (!dx&&!dy)break;
			nx += dx; ny += dy;
			if (amax < nx*nx + ny*ny||(amax==nx*nx+ny*ny&&nx>ans.first)) {
				ans = make_pair(nx, ny);
				amax = nx*nx + ny*ny;
			}
		}
		cout << ans.first<<" "<<ans.second << endl;
	}
	return 0;
}

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010];
main(){
	int n;
while(cin>>n){

	int m=-1;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[a[i]]++;
		m=max(m,a[i]);
	}
	int cnt=0;
	for(int i=0;i<=m;i++)
		cnt=max(cnt,b[i]+b[i+1]+b[i+2]);
		cout<<cnt<<endl;

}
return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

int main() {
  int M, N;
  cin >> N >> M;
  vector<int> A(N);
  copy_n(istream_iterator<int>(cin), N, A.begin());
  int s = accumulate(A.begin(), A.end(), 0);
  int c = count_if(A.begin(), A.end(), [s, M](int n) {
    return 4 * M * n >= s;
  });
  cout << ((M <= c) ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define N 1000
using namespace std;
using Int = long long;
Int mx[N];

signed main(){
  while(1){
    memset(mx,0,sizeof(mx));
    Int n,m;
    cin>>n>>m;
    if(!n&&!m)break;
    for(Int i=0;i<n;i++){
      Int d,v;
      cin>>d>>v;
      mx[d-1] = max(mx[d-1],v);
    }

    Int sum = 0;
    for(Int i=0;i<m;i++) sum+=mx[i];
    cout<<sum<<endl;
  }
  return 0;
}



Measured memory_bytes: 3096
#include <cstdio>
#include <algorithm>

using std::max;

const int MAXN=300011;

int N, M;
int A[MAXN];

long long V[MAXN], T[MAXN], Val[MAXN];
long long Pre[MAXN], Suf[MAXN];
long long F[MAXN], G[MAXN];

struct Pos{
	int x;
	long long y;
	Pos(){};
	Pos(int _x, long long _y){x=_x;y=_y;}
	long long v(int k){
		return 1LL*k*x+y;
	}
};

inline Pos operator - (const Pos &A, const Pos &B){
	return Pos(A.x-B.x, A.y-B.y);
}

inline long double operator * (const Pos &A, const Pos &B){
	return 1.0L*A.x*B.y-1.0L*B.x*A.y;
}

Pos St[MAXN];
int Top;

long long S_[MAXN], O_[MAXN];

void Push(Pos P){
	while(Top>1 && (St[Top]-St[Top-1])*(P-St[Top])>=0.0L)	--Top;
	St[++Top]=P;
}

long long Ask(int k){
	while(Top>1 && St[Top].v(k)<St[Top-1].v(k))	--Top;
	return St[Top].v(k);
}

long long OY(int p){
	return ((O_[p]+S_[p])<<1)+1LL*p*p-(long long)(p);
}

long long XO(long long v, int p){
	return ((v+1LL*p*p+(long long)(p))>>1)-S_[p];
}

void Calc(){
	Top=0;
	for(int i=1;i<=N;++i){
		Push(Pos(i-1, OY(i-1)));
		O_[i]=XO(Ask(-(i<<1)), i);
		O_[i]=max(O_[i], O_[i-1]);
	}
}


long long F_(int p){
	return ((F[p]+Pre[p])<<1)+1LL*p*p+(long long)(p);
}

long long G_(int p){
	return ((G[p]+Suf[p])<<1)+1LL*p*p-(long long)(p);
}

void Deal(int l, int r){
	if(l>r)	return;
	int m=(l+r)>>1;
	
	for(int i=m;i<=r;++i)	T[i]=0;
	Top=0;
	for(int i=l-1;i<=m-1;++i)	Push(Pos(i, F_(i)));
	for(int i=m+1;i<=r+1;++i)	T[i-1]=max(T[i-1], Ask(-(i<<1))+G_(i));
	for(int i=r-1;i>=m;--i)	T[i]=max(T[i], T[i+1]);
	for(int i=m;i<=r;++i)	V[i]=max(V[i], T[i]);
	
	for(int i=l;i<=m;++i)	T[i]=0;
	Top=0;
	for(int i=m+1;i<=r+1;++i)	Push(Pos(i, G_(i)));
	for(int i=l-1;i<=m-1;++i)	T[i+1]=max(T[i+1], Ask(-(i<<1))+F_(i));
	for(int i=l+1;i<=m;++i)	T[i]=max(T[i], T[i-1]);
	for(int i=l;i<=m;++i)	V[i]=max(V[i], T[i]);
	
	Deal(l, m-1);Deal(m+1, r);
}

void Show(long long v){
	printf("%lld\n", v);
}

int main(){
	
	scanf("%d", &N);
	for(int i=1;i<=N;++i)	scanf("%d", &A[i]);
	
	for(int i=1;i<=N;++i)	Pre[i]=Pre[i-1]+(long long)(A[i]);
	for(int i=N;i>=1;--i)	Suf[i]=Suf[i+1]+(long long)(A[i]);
	
	for(int i=1;i<=N;++i)
		S_[i]=Pre[i];
	Calc();
	for(int i=1;i<=N;++i)	F[i]=O_[i];
	
	for(int i=1;i<=N;++i)
		S_[N-i+1]=Suf[i];
	Calc();
	for(int i=1;i<=N;++i)	G[i]=O_[N-i+1];
	
	//for(int i=1;i<=N;++i)	printf("%I64d ", F[i]);
	//puts("");
	
	//for(int i=1;i<=N;++i)	printf("%I64d ", G[i]);
	//puts("");
	
	Deal(1, N);
	
	for(int i=1;i<=N;++i)	Val[i]=F[i-1]+G[i+1];
	for(int i=1;i<=N;++i)	V[i]=(V[i]>>1)-Pre[N];
	
	
	scanf("%d", &M);
	
	for(int p, x;M--;){
		scanf("%d%d", &p, &x);
		x=x-A[p];
		Show(max(Val[p], V[p]-x));
	}
	
	return 0;
}

/*
5
1 1 4 1 1

*/

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

int main(){
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    int L = S.length();
    vector<int> cnt(L+1,0);
    
    for(int i=1; i<L; i++){
        if(S[i]=='C' && S[i-1]=='A'){
            cnt[i+1]++;
        }
    }
    for(int i=1; i<=L; i++) cnt[i] += cnt[i-1];

    vector<int> l(Q,0), r(Q,0);
    for(int i=0; i<Q; i++) {
        cin >> l[i] >> r[i];
    }
    for(int i=0; i<Q; i++){
        cout << cnt[r[i]] - cnt[l[i]] << endl;
    }
}


Measured memory_bytes: 2176
#include <iostream>
int main() {
    int w;
    int h;
    int x;
    int y;
    int r;

    std::cin >> w >> h >> x >> y >> r;

    bool ok = ((x - r) >= 0)
            && ((x + r) <= w)
            && ((y - r) >= 0)
            && ((y + r) <= h);
    if (ok) {
        std::cout << "Yes";
    } else {
        std::cout << "No";
    }
    std::cout << std::endl;

    return 0;
}


Measured memory_bytes: 3092
#![allow(unused)]
use std::io::{self, Read};

fn get_stdin() -> String {
    let mut buf = String::new();
    let mut stdin = io::stdin();
    stdin.read_to_string(&mut buf);
    return buf
}

fn to_nums(ss: &str) -> Vec<i32> {
    ss.split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect()
}

fn main() {
    let input = get_stdin();
    let v = to_nums(&input);
    let mut cnt = 0;
    for n in v[0]..(v[1]+1) {
        if v[2] % n == 0 {
            cnt += 1;
        }
    }
    println!("{}", cnt)
}



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

using namespace std;

int n, x, y, ans[20005];

int dist (int a, int b) {
    if (b >= y && a <= x)return (x - a + 1 + b - y);
    if (b >= y && a > x)return min (b - a, a - x + 1 + b - y);
    if (b < y && a <= x)return min (b - a, x - a + 1 + y - b);
    if (b < y && a > x)return min (b - a, a - x + 1 + y - b);
}

int main () {
    cin >> n >> x >> y;
    for (int i = 1;i <= n;i ++) {
        for (int j = i + 1;j <= n;j ++) {
            ans[dist (i, j)] ++;
            if (dist (i, j) == -1) {
                cout << i << ' ' << j;
                exit (0);
            }
        }
    }
    for (int i = 1;i < n;i ++) {
        cout << ans[i] << '\n';
    }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    private static Scanner scanner;

    public static int[] inputIntArray(int n) {
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            res[i] = scanner.nextInt();
        }

        return res;
    }

    // public static String[] <T> ToStringArray(T[] arr) {
    // String[] res = new String[arr.length];
    // for(int i = 0; i < arr.length; ++i) {
    // res[i] = String.valueOf(arr[i]);
    // }

    // return res;
    // }

    private static List<Integer> asIntergerList(int[] arr) {
        List<Integer> intList = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            intList.add(arr[i]);
        }

        return intList;
    }

    public static void main(String[] args) {
        scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] S = inputIntArray(n);

        int q = scanner.nextInt();
        int[] T = inputIntArray(q);

        int cnt = 0;
        for (int i = 0; i < q; ++i) {
            int res = Arrays.binarySearch(S, T[i]);

            if (res > 0 && S[res] == T[i])
                ++cnt;
        }

        System.out.println(cnt);

    }
}



Measured memory_bytes: 81036