akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "
#define N 100010
int main(){
    int n,k;cin>>n>>k;
    ll sum = 0;
    rep(i,n){
        int tmp;cin>>tmp;
        sum+=min(2*abs(tmp),2*abs(tmp-k));
    }
    co(sum);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

// SegmentTree
template<typename T>
class SegTree{
public:
    int n;
    T defaultValue;
    vector<T> dat;

    SegTree(int m, T value){
        n = 1;
        while(n < m){
            n *= 2;
        }
        dat.assign(2 * n - 1, value);
        defaultValue = value;
    }

    void updateDiff(int i, T value){
        i += n - 1;
        dat[i] += value;
        while(i > 0){
            i = (i - 1) / 2;
            dat[i] = ope(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }

    T query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0){
            r = n;
        }

        if(r <= a || b <= l){
            return defaultValue;
        }
        if(a <= l && r <= b){
            return dat[k];
        }
        else{
            T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
            T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return ope(vl, vr);
        }
    }

private:
    T ope(T a, T b){
        return (a + b);
    }
};

int main(){

    int N;
    cin >> N;
    string S;
    cin >> S;

    vector<SegTree<int>> st(26, SegTree<int>(N, 0));

    for(int i = 0; i < N; i++){
        char c = S[i];
        int num = c - 'a';
        st[num].updateDiff(i, 1);
    }

    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int type;
        cin >> type;
        if(type == 1){
            int index;
            char c;
            cin >> index >> c;
            int oldNum = S[index - 1] - 'a';
            int newNum = c - 'a';
            st[oldNum].updateDiff(index - 1, -1);
            st[newNum].updateDiff(index - 1, 1);
            S[index - 1] = c;
        }
        else{   // type == 2
            int left, right;
            cin >> left >> right;
            left--;
            right--;
            int ans = 0;
            for(int i = 0; i < 26; i++){
                int cnt = st[i].query(left, right + 1);
                if(cnt > 0){
                    ans++;
                }
            }
            cout << ans << endl;
        }
    }

    return 0;
}

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

#define MAXN (200010)

int n, k, l;
std::vector<int> mat1[MAXN];
std::vector<int> mat2[MAXN];
bool vis1[MAXN], vis2[MAXN];
int cnt1, cnt2;
int bel1[MAXN], bel2[MAXN];
std::vector<int> nod1[MAXN];
std::vector<int> nod2[MAXN];
std::map<std::pair<int, int>, int> map;

template <class T> void readin(T &x,bool mark = 0){
    char tt = getchar();
	for(; tt < '0' || '9' < tt; tt = getchar()){
	    if(tt == '-'){
		    mark = 1;
		}
	}
	for(x = 0; '0' <= tt && tt <= '9'; x = x * 10 + tt - '0', tt = getchar())
	    ;
	x = mark ? - x : x;
}

void dfs1(int u){
	vis1[u] = true;
	bel1[u] = cnt1;
	nod1[cnt1].push_back(u);
	for(auto v : mat1[u]){
		if(vis1[v]) continue;
		dfs1(v);
	}
}

void dfs2(int u){
	vis2[u] = true;
	bel2[u] = cnt2;
	nod2[cnt2].push_back(u);
	for(auto v : mat2[u]){
		if(vis2[v]) continue;
		dfs2(v);
	}
}

int main(){
	readin(n); readin(k); readin(l);
	for(int i = 1; i <= k; ++ i){
		int u, v;
		readin(u); readin(v);
		mat1[u].push_back(v);
		mat1[v].push_back(u);
	}
	for(int i = 1; i <= l; ++ i){
		int u, v;
		readin(u); readin(v);
		mat2[u].push_back(v);
		mat2[v].push_back(u);
	}
	for(int i = 1; i <= n; ++ i){
		if(!vis1[i]){
			++ cnt1;
			dfs1(i);
			std::sort(nod1[cnt1].begin(), nod1[cnt1].end());
		}
		if(!vis2[i]){
			++ cnt2;
			dfs2(i);
			std::sort(nod2[cnt2].begin(), nod2[cnt2].end());
		}
	}
	for(int i = 1; i <= n; ++ i){
		++ map[{bel1[i], bel2[i]}];
	}
	for(int i = 1; i <= n; ++ i){
		printf("%d", map[{bel1[i], bel2[i]}]);
		printf(i == n ? "\n" : " ");
	}
	return 0;
}

Measured memory_bytes: 46848
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define OUT(s) cout << s << "\n";
using namespace std;

// https://atcoder.jp/contests/abc172


int A;

void Main()
{
    long ans = A + A * A + A * A * A;
    OUT(ans);

}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    cin >> A;
    Main();
    return 0;
}

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

#define debug(a) cout << #a << " " << a << endl;
#define _debug(a, i) cout << #a << "[" << i << "]" << " = " << a[i] << endl;
#define fastio ios_base::sync_with_stdio(false); \
		cin.tie(0);							     \
		cout.tie(0);
#define sz(arr) (ll)arr.size()

using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 9;
const double PI = 4.0 * atan(1.0);

ll powmod(ll a, ll b, const ll MOD) { ll res = 1; a %= MOD; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % MOD; a = a * a % MOD; } return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll modInverse(ll n, const ll p) { return powmod(n, p - 2, p); }
/*ll f[200001];
ll kCn(ll k, ll n) { return (f[n] * modInverse((f[n - k] * f[k]) % MOD, MOD)) % MOD; }*/


int main() {
	//#ifndef ONLINE_JUDGE
	//	(void)freopen("input.txt", "r", stdin);
	//	(void)freopen("output.txt", "w", stdout);
	//#endif // !ONLINE_JUDGE
	fastio;
	int r;
	cin >> r;
	cout << 2 * 3.14159265359 * r;
	return 0;
}


Measured memory_bytes: 3800
#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<deque>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<limits>
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using namespace std;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
typedef long long ll;
typedef unsigned long long ull;
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}
template<class T>inline void outs(vector<T> V){int n=V.size();rep(i,n)cout<<V[i]<<" \n"[i==n-1];}
inline void solve(void){
  string S;in(S);
  int Q;in(Q);
  deque<char>d;
  for(auto e:S)d.pb(e);
  int mode=0;
  while(Q--){
    int t;in(t);
    if(t==1){
      if(mode==0)mode=1;
      else mode=0;
    }else{
      int f;char c;in(f,c);
      if(f==1){
        if(mode==0)d.pf(c);
        else d.pb(c);
      }
      else{
        if(mode==0)d.pb(c);
        else d.pf(c);
      }
    }
  }
  if(mode==0)for(auto e:d)cout<<e;
  else {
    while(!d.empty()){
      char c=d.back();d.pop_back();
      cout<<c;
    }
  }
  cout<<endl;
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 976
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

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

        if(a>0&&b>0) {
                cout << "Positive" << endl;
        }else if(a>=0&&b<=0) {
                cout << "Zero" << endl;
        }else if((a-b)%2==1) {
                cout << "Positive" << endl;

        }else{
                cout << "Negative" << endl;

        }





        return 0;
}


Measured memory_bytes: 256
n=int(input())
a=[0]
for i in map(int,input().split()):
    a.append(i)
a.append(0)
s=0
for i in range(n+1):
    s+=abs(a[i]-a[i+1])
ans=0
for i in range(n):
    print(s-abs(a[i]-a[i+1])-abs(a[i+1]-a[i+2])+abs(a[i]-a[i+2]))

Measured memory_bytes: 14048
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func main() {
	T := getStdin()
	S := ""

	prev := "N"
	next := "N"
	for i := 0; i < len(T); i++ {
		if i+1 < len(T) {
			next = T[i+1 : i+2]
		} else {
			next = "N"
		}
		if T[i] == '?' {
			if prev == "P" {
				if next == "D" || next == "?" {
					S += "D"
					prev = "D"
				} else {
					S += "D"
					prev = "D"
				}
			} else if prev == "D" {
				if next == "P" {
					S += "D"
					prev = "D"
				} else if next == "D" || next == "?" {
					S += "P"
					prev = "P"
				} else {
					S += "D"
					prev = "D"
				}
			} else {
				if next == "P" {
					S += "D"
					prev = "D"
				} else if next == "D" || next == "?" {
					S += "P"
					prev = "P"
				} else {
					S += "D"
					prev = "D"
				}
			}
		} else {
			S += T[i : i+1]
			prev = T[i : i+1]
		}
	}

	fmt.Printf("%s", S)
	fmt.Printf("\n")
}

func getStdin() string {
	return readLine()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	return rtn
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}

func getStdinIntArr64() []int64 {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}

func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, e := sc.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


Measured memory_bytes: 17352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) (vec).begin(),(vec).end()
#define int long long

signed main(){
    int n;cin>>n;
    int c=1;
    int ans=n;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        if(a==c){
            ans=min(ans,n-c);
            c++;
        }
    }
    if(ans==n)cout<<-1<<endl;
    else cout<<ans<<endl;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define each(it,v) for(auto &it : v)
#define all(v) (v).begin(),(v).end()
#define mod 1e9+7

using namespace std;
using vi = vector<int>;
using vl = vector<long>;
using P = pair<int,int>;

main()
{
        int a,b; cin>>a>>b;
        bool flag=false;
        if(a%3==0)flag=true;
        if(b%3==0)flag=true;
        if((a+b)%3==0)flag=true;
        cout<<(flag?"Possible":"Impossible")<<endl;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> x(n),y(n);
	for(int i=0;i<n;i++)cin >> x[i]>>y[i];
	vector<int> ind(n);
	for(int i=0;i<n;i++)ind[i]=i;
	
	int cnt=0;
	double sum=0;
	do{
		for(int i=0;i<n-1;i++){
			sum+= sqrt(pow(x[ind[i+1]]-x[ind[i]],2)+pow(y[ind[i+1]]-y[ind[i]],2));
		}
		cnt++;
	}while(next_permutation(ind.begin(),ind.end()));
	
	printf("%0.10f",sum/cnt);
	
	return 0;
}

Measured memory_bytes: 256
x , y = map(int , input().split());
ans = 0;
if(x == 1):
	ans += 300000;
if(x == 2):
	ans += 200000;
if(x == 3):
  	ans += 100000;
if(y == 1):
	ans += 300000;
if(y == 2):
	ans += 200000;
if(y == 3):
  	ans += 100000;
if(x + y == 2):
  	ans += 400000;
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;

namespace AizuOnlineJudge {
    class Program {
        static void Main() {
            var nq = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var stack = Enumerable.Range(0, nq[0]).Select(_ => new Stack<string>()).ToArray();
            for (var i = 0; i < nq[1]; ++i) {
                var query = Console.ReadLine().Split();
                var index = int.Parse(query[1]);
                switch (query[0]) {
                    case "0":
                        stack[index].Push(query[2]);
                        break;

                    case "1":
                        if (stack[index].Any()) {
                            Console.WriteLine(stack[index].Peek());
                        }
                        break;

                    case "2":
                        if (stack[index].Any()) {
                            stack[index].Pop();
                        }
                        break;
                }
            }
        }
    }
}



Measured memory_bytes: 31576
#include <iostream>
#include <vector>
 
int main() {
 
    std::vector<int> a;
    std::vector<std::vector<long long int>> dp;
    int n;
 
    dp.resize(200);
 
    for (int i = 0; i < 200; ++i) {
        dp[i].resize(21);
    }
 
    for (int i = 0; i < 200; ++i) {
        for (int j = 0; j < 21; ++j) {
            dp[i][j] = 0;
        }
    }
 
    std::cin >> n;
 
    for (int i = 0; i < n; ++i){
        int tmp;
        std::cin >> tmp;
        a.push_back(tmp);
    }
 
    //std::cin >> b;
    //dp[0][0] = 1;
	dp[1][a[0]] = 1;
 
    for (int i = 1; i < n-1; ++i){
 
        /*
        if (i == 0) {
            for (int j = 0; j < 21; ++j) {
                dp[0][j] = 1;
            }
        }*/
 
        for (int j = 0; j < 21; ++j) {
 
            if (dp[i][j] != 0 && j + a[i] < 21) {
                dp[i + 1][j+a[i]] += dp[i][j];
            }
 
            if (dp[i][j] != 0 && 0 <= j - a[i]) {
                dp[i + 1][j-a[i]] += dp[i][j];
            }
 
        }
 
    }
	// n-1?????§????¨?????????????a[n-1](=n)??§???????????°
    std::cout << dp[n-1][a[n-1]] << std::endl;
	/*
	for(int i = 0; i < 10; ++i){
		for(int j = 0; j < 10; ++j){
			std::cout << i << ":" << j << "|" << dp[i][j] << std::endl;
		}
	}
	*/
 
    return 0;
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    int N, D;
    cin >> N >> D;

    vector<vector<int>> point(N, vector<int>(D));

    rep(i, N) {
        rep(j, D) {
            cin >> point[i][j];
        }
    }

    int ans = 0;

    rep(i, N) {
        repd(j, i + 1, N) {
            float x = 0;
            rep(k, D) {
                x += (point[i][k] - point[j][k]) * (point[i][k] - point[j][k]);
            }
            x = sqrt(x);
            if (ceil(x) == floor(x)) {
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
int n;
lld A[2020];
lld dp[2020][2020];

int m(int i){
  return (i-1+n)%n;
}

int p(int i){
  return (i+1)%n;
}

lld solve(int left,int right){
  if(m(left) == right) return min(A[left],A[right]);
  if(left == right) return 0;
  if(dp[left][right] != -1) return dp[left][right];
  lld ret = 0;
  if(A[left] > A[right]){
    ret = max(ret,solve(m(left),p(right))+A[right]);
    ret = max(ret,solve(m(left-1),right)+A[m(left)]);
  }
  else {
    ret = max(ret,solve(m(left),p(right))+A[left]);
    ret = max(ret,solve(left,p(right+1))+A[p(right)]);
  }
  return dp[left][right] = ret;
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> A[i];
  }
  memset(dp,-1,sizeof(dp));
  lld ans = 0;
  for(int i=0;i<n;i++){
    ans = max(ans,solve(m(i),p(i))+A[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 33124
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define endl '\n'
int main() {
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "rt", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    fast
    int a[3][3];
    set<int> s;
    for(int i=0; i<3; ++i){
    	for(int j=0; j<3; ++j){
    		cin>>a[i][j];
    		s.insert(a[i][j]);
    	}
    }
    int n;cin>>n;
    for(int i=0;i <n; ++i){
    	int t;cin>>t;
    	if(s.find(t)!=s.end()){
    		for(int j=0; j<3; j++){
    			for(int k=0; k<3; ++k){
    				if(a[j][k]==t){
    					a[j][k]=0;
    				}
    			}
    		}
    	}
    }

    for(int i=0; i<3; ++i){
    	if(a[i][0]==0 && a[i][1]==0 && a[i][2]==0){
    		cout<<"Yes";return 0;
    	}
    }
    for(int i=0; i<3; ++i){
    	if(a[0][i]==0 && a[1][i]==0 && a[2][i]==0){
    		cout<<"Yes";return 0;
    	}
    }
    if(a[0][0]==0 && a[1][1]==0 && a[2][2]==0){
    	cout<<"Yes";return 0;
    }if(a[0][2]==0 && a[1][1]==0 && a[2][0]==0)
    	{cout<<"Yes";return 0;}
    cout<<"No";


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
 
using namespace std;

bool func(int a1, int a2) {

    return a1 > a2;
}

int main()
{
    int n;

    cin >> n;

    vector<int> a = vector<int>(n);

    for (int i = 0; i < n; i++) {

        cin >> a[i];
    }

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

    long long sum = a[0];

    int k = 2;

    int j = 1;

    for (int i = 2; i < n; i++) {
        
        if (k > 0) {
            k--;
        }
        else {
            k = 1;
            j++;
        }

        sum += a[j];
    }

    cout << sum;

}

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

using namespace std;

int n , x , y , z = 0;
const int maxn = 1e3 + 20;

int a[maxn];

int main()
{
	cin >> n;
	
 	for (int i = 0 ; i < (2*n) ; i++){
 		cin >> a[i];
	 }
	 sort( a , a + ( 2 * n));
	 
	 for(int i = 0 ; i < (2 * n) ; i+=2){
	 	z += a[i];
	 }
	 cout << z;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
#define PI 3.14159265359 //πの値
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
ll N; cin >> N;
ll sum = 0;
ll ans = 0;
vector<ll> data(N);
REP(i, N){
  cin >> data[i];
  sum += data[i];
}
  REP(i, N-1){
   sum -= data[i];
   ans += data[i]*(sum%MOD);
   ans %= MOD;
  }
  cout << ans;
}

Measured memory_bytes: 4756
//#include<bits/stdc++.h>
#include<iostream>
#include<climits>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<list>
#include<string>
#include <unordered_map>
#include <unordered_set> 
#include<iomanip>
#include<iterator>
#include<cmath>
#include<fstream>
using namespace std;
#define F0(i,n) for(int i=0;i<int(n);++i)
#define F1(i,n) for(int i=1;i<=int(n);++i)
#define X first
#define Y second
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef pair<int,int> pii;
int n;
string s;
set<string> t;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    F0(i,n){
        cin>>s;
        t.insert(s);
    }
    cout <<t.size()<<endl;
}


Measured memory_bytes: 15648
t=input()
for p in range(t):
    H=W=5
    L=[["0"]+raw_input().split()+["0"] for i in range(H)]
    L.append(["0"]*(W+2))
    L.insert(0,["0"]*(W+2))
    dp=[[set() for i in range(W+2)] for i in range(H+2)]
    T=[[[0,0] for i in range(W+2)] for i in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if L[i][j]=="1":
                T[i][j][0]+=T[i][j-1][0]+1
                T[i][j][1]+=T[i-1][j][1]+1
    maxInt=0
    for i in range(1,H+2):
        for j in range(1,W+2):
            if L[i][j]=="1":
                if L[i-1][j]==L[i][j-1]=="0":
                    dp[i][j].add((1,1))
                    maxInt=max(maxInt,1)
                elif L[i-1][j]=="0":
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,1))
                        maxInt=max(maxInt,k[0]+1)
                elif L[i][j-1]=="0":
                    for k in dp[i-1][j]:
                        dp[i][j].add((1,k[1]+1))
                        maxInt=max(maxInt,k[1]+1)
                else:
                    h=T[i][j][1]
                    l=T[i][j][0]
                    for k in dp[i][j-1]:
                        m=min(k[1],h)
                        dp[i][j].add((k[0]+1,m))
                        maxInt=max(maxInt,(k[0]+1)*m)
                    for k in dp[i-1][j]:
                        m=min(k[0],l)
                        dp[i][j].add((m,k[1]+1))
                        maxInt=max(maxInt,m*(k[1]+1))
        dp[i-1]=[]
    print maxInt
    if p!=t-1:
        skip=raw_input()

Measured memory_bytes: 4388
def dist(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
G = {}
for i in range(H):
    for j in range(W):
        G[A[i][j]] = (i,j)
C = {}
for j in range(1,D+1):
    k = 1
    C[j] = 0
    while j+k*D<=H*W:
        C[j+k*D] = C[j+(k-1)*D]+dist(G[j+(k-1)*D],G[j+k*D])
        k += 1
Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    print(C[R]-C[L])

Measured memory_bytes: 75996
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long a = sc.nextInt();
		long b = sc.nextInt();
		int num = 1;
		
		while(true) {
					for(int i = 2; i <= 100000; i++) {
			if(a % i == 0  && b % i == 0) {
				a /= i;
				b /= i;
				num *= i;
				break;
			} else if (i == 100000) {
				System.out.println(a * b * num);
				return;
			}
		}
		}
	}
}


Measured memory_bytes: 23764
N = int(input())
xy = []
xy = [list(map(int,input().split())) for i in range(N)]

import itertools

town_number = [i for i in range(N)]
town_group = list(itertools.combinations(town_number,2))

length = []

for i in range(len(town_group)):
    x = xy[town_group[i][0]][0] - xy[town_group[i][1]][0]
    y = xy[town_group[i][0]][1] - xy[town_group[i][1]][1]
    length.append((x**2 + y**2)**0.5)
    
print(sum(length)*2/N)

Measured memory_bytes: 3064
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import Debug.Trace
import Data.List
import Control.Monad
import Control.Arrow
import Data.Ord


r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine



main :: IO ()
main = do
    as <- replicateM 3 r'
    n <- readLn
    bs <- replicateM n readLn :: IO [Int]
    putStrLn $ if ev (op as bs) then "Yes" else "No"

op :: [[Int]] -> [Int] -> [[Bool]]
op as bs = map (map (\a -> a `elem` bs)) as

ev :: [[Bool]] -> Bool
ev xs@[ [a,b,c],
        [d,e,f],
        [g,h,i]] = or (map and xs) || and [a,e,i] || and [g,e,c]
                    || and [a,d,g] || and [b,e,h] || and [c,f,i] 

Measured memory_bytes: 508
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int N = in.Int();
            int[] a = in.Int(N);
            int ans = 0;
            for (int n : a) {
                while (1 != (n & 1)) {
                    ans++;
                    n >>= 1;
                }
            }
            out.println(ans);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int Int() {
            return Integer.parseInt(next());
        }

        public int[] Int(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Int();
            }
            return a;
        }

    }
}



Measured memory_bytes: 25300
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define SIZE 10000
#define BC 50
#define BS 5000
#define MOD 1000000000LL
#define MAXV 555
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef vector<vector<long long> > mat;

int d[1001][1001];

int dp(int x, int y) {
	// printf("%d %d\n",x,y);
	int ret = -1;
	if(d[x][y])	return d[x][y];
	// getchar();
	for(int i=1;2*i<=x;i++)		ret = max(ret, -dp(x-2*i,y+i));
	for(int i=1;2*i<=y;i++)		ret = max(ret, -dp(x+i,y-2*i));
	return d[x][y] = ret;
}

int main () {
	ll x,y;
	scanf("%lld%lld",&x,&y);
	ll chk = x-y;
	if(chk>=-1 && chk<=1)	printf("Brown\n");
	else				printf("Alice\n");
}

Measured memory_bytes: 256
n = gets.to_i
S = gets.to_s.split(" ").map(&:to_i)
q = gets.to_i
T = gets.to_s.split(" ").map(&:to_i)

count = 0
for i in T do
    left = 0
    right = S.count - 1
    while left <= right do
        middle = (left + right) / 2
        if S[middle] < i then
            left = middle + 1
        elsif S[middle] > i then
            right = middle - 1
        else
            count += 1
            break
        end
    end
end
puts count

Measured memory_bytes: 17296
import heapq

N, M = map(int, input().split())
a = [(-1)*int(i) for i in input().split()]
heapq.heapify(a)

for i in range(M):
  tmp = (-1)*heapq.heappop(a)
  tmp = tmp // 2
  heapq.heappush(a, (-1)*tmp)
  
print((-1)*sum(a))

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

#define ll long long

#define ff first
#define ss second
bool comp(ll a,ll b){
    return a > b;
}

bool check(vector<ll> &a,ll k){
    ll n = a.size();
    
    for(ll i=0;i<n-1;i+=2){
        ll x = max(a[i],a[i+1]);
        k-=x;
        if(k<0) return false;
    }
    
    if(n&1){
        k-= a[n-1];
    }
    if(k<0) return false;
    return true;
    
}

void solve()
{
    std::deque<char> v;
    string s;cin>>s;
    
    for(ll i=0;i<s.size();i++){
        v.push_back(s[i]);
    
    }

    ll q;cin>>q;
    ll start = 0;
    ll end = 199-1;
    while(q--)
    {
        ll type;
        cin>>type;
        if(type==1){
            swap(start,end);
        }
        else{
            ll a;
            char b;
            cin>>a>>b;
            
            if(a==1){
                if(start==0){
                    v.push_front(b);
                }
                else{
                    v.push_back(b);
                }
            }
            
            else{
                if(start!=0){
                    v.push_front(b);
                }
                else
                    v.push_back(b);
            }
            
        }
        
    }
    
    if(start!=0){
        reverse(v.begin(),v.end());
    }
    
    for(auto i:v)
        cout<<i;
        
        
}

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // ll t;cin>>t;while(t--)
        solve();
    
}

Measured memory_bytes: 976
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007


int main() {

  string S;
  cin >> S;

  string X = "CODEFESTIVAL2016";
  int ans = 0;
  for(int i = 0;i < S.size();i++) {
    if(S.at(i) != X.at(i)) ans++;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
int SIZE(string s){ return (int)s.size(); }

bool isprime(ll n){
    if(n == 2 || n == 3) return true;
    else if(n <= 1 || n % 2 == 0 || n % 3 == 0) return false;
    for(int i = 5; i*i <= n; i += 6) if(n % i == 0 || n % (i+2) == 0) return false;
    return true;
}

int main(){
    cout << setprecision(16);
    int x; cin >> x;
    int ans = 1;
    if(x == 1) cout << ans << endl;
    else {
        for(int i = 2; i*i <= x; i++){
            int num = i*i;
            while(num <= x){
                ans = max(ans, num);
                num *= i;
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using P = pair<ll,ll>;
const ll INF = ll(1e18)+5;
ll H,W,K;

bool onBoard(int y,int x){
    if(y>=0 && y<H && x>= 0 && x<W){
        return true;
    }
    return false;
}

int main() {
    cin >> H >>W>>K;
    int sx,sy,gx,gy;
    cin >> sy >> sx >>gy >> gx;
    --sy;--sx;--gx;--gy;
    vector<string> S(H);
    for(int i=0;i<H;i++){
        cin >> S[i];
    }
    int dy[] = {1,0,-1,0};
    int dx[] = {0,1,0,-1};



    ll d[H][W];
    for(int i=0;i<H;i++)for(int j=0;j<W;j++){
        d[i][j] = INF;
    }
    priority_queue<P,vector<P>,greater<P>> pq;
    pq.push(P(0,sy*W+sx));
    d[sy][sx] = 0;
    while(!pq.empty()){
        P p =pq.top();
        ll y= p.second/W;ll x = p.second%W;
        // cerr <<"y=" << y <<"x=" <<x  <<"d=" <<d[y][x]<<endl;
        pq.pop();
        if(p.first > d[y][x]){
            continue;
        }
        for(int i=0;i<4;i++){
            for(int j=1;j<=K;j++){
                ll ny = y + dy[i]*j;
                ll nx = x+ dx[i]*j;
                if(!onBoard(ny,nx)|| S[ny][nx] == '@'){
                    break;
                }
                if(d[ny][nx] <d[y][x] +1){
                    // cerr <<"ny=" <<ny <<"nx="<<nx <<"breaked"<<endl;
                    break;
                }
                if(d[ny][nx] <= d[y][x]+1){
                    continue;
                }
                
                // cerr <<"ny=" <<ny <<"nx=" <<nx << endl;
                d[ny][nx] = d[y][x] + 1;
                pq.push(P(d[ny][nx],ny*W+nx));
            }
        }
    }
    if(d[gy][gx] == INF){
        d[gy][gx] = -1;
    }
    cout << d[gy][gx] << endl;
    return 0;
}

Measured memory_bytes: 14496
#include <stdio.h>

int
main(int argc, char *argv[])
{
  int a[5], k;
  for(int i = 0; i < 5; i++){
    scanf("%d", &a[i]);
  }
  scanf("%d", &k);
  int l = 0;
  
  for(int i = 0; i < 4; i++){
    for(int j = i+1; j < 5; j++){
      if(a[j] - a[i] > k){
        l += 1;
      }
    }
  }
  
  if(l > 0){
    printf("%s\n", ":(");
  }
  else{
    printf("%s\n", "Yay!");
  }
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int a[n-1];
  int ans[n]={0};
  rep(i,n-1){
    cin>>a[i];
    ans[a[i]-1]++;
  }
  rep(i,n){
    cout<<ans[i]<<endl;
  }

  return 0;
}


Measured memory_bytes: 6748
s = gets.chomp
puts (s==s.reverse&&(s[0..((s.size-1)/2-1)]==s[0..((s.size-1)/2-1)].reverse)&&(s[((s.size+3)/2-1)..(s.size-1)]==s[((s.size+3)/2-1)..(s.size-1)].reverse)) ? 'Yes' : 'No'

Measured memory_bytes: 1788
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[1100][1100];
pair<int,int>p[1100];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		int b,c;scanf("%d%d",&b,&c);
		p[i]=make_pair(c,b);
	}
	std::sort(p,p+a);
	for(int i=0;i<=a;i++)for(int j=0;j<=a;j++)
		dp[i][j]=1999999999;
	dp[0][0]=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<=i;j++){
			if(dp[i][j]+p[i].second<=p[i].first)dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+p[i].second);
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
	}
	int ret=0;
	for(int i=0;i<=a;i++)if(dp[a][i]<1999999999)ret=i;
	printf("%d\n",ret);
}

Measured memory_bytes: 1096
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static void solve() {
		char c = in.next().charAt(0);
		switch (c) {
			case 'a': case 'i': case 'u': case 'e': case 'o':
			out.println("vowel");
			return;
		}
		out.println("consonant");
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 9680
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> >a(11,vector<int>(331));
void r(int n,int u,int s,int d){
a[n][s]++;
for(int i=0;i<10;i++)
  if(!(u>>i&1))r(n+1,u^1<<i,s+d*i,d+1);
}

main(){
r(0,0,0,1);
for(int n,s;cin>>n>>s;)cout<<a[n][s]<<endl;
}

Measured memory_bytes: 0
package main

import (
	"bufio"
	"fmt"
	"os"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

func main() {
	scanner.Split(bufio.ScanWords)

	s1 := nextString()
	s2 := nextString()

	dp := make([][]int, len(s1)+1)
	for i := 0; i < len(s1)+1; i++ {
		dp[i] = make([]int, len(s2)+1)
	}

	for i := 0; i < len(s1)+1; i++ {
		dp[i][0] = i
	}
	for j := 0; j < len(s2)+1; j++ {
		dp[0][j] = j
	}

	// fmt.Println(dp)

	for k := 0; k < len(s1)+len(s2)+1; k++ {
		for j := 1; j < k; j++ {
			i := k - j
			// fmt.Println(i, j)
			if i > 0 && i <= len(s1) && j > 0 && j <= len(s2) {
				// fmt.Println(i, j, k)
				if s1[i-1] == s2[j-1] {
					dp[i][j] = dp[i-1][j-1]
				} else {
					// fmt.Println(i, j, dp[i-1][j], dp[i][j-1])
					dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
				}
			}
		}
	}

	// for i := 0; i < len(s1)+1; i++ {
	// 	fmt.Println(dp[i])
	// }

	fmt.Println(dp[len(s1)][len(s2)])
}



Measured memory_bytes: 9756
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  string s,t;
  cin >> s >> t;
  for(int i=0;i<=n;i++){
    if(s.substr(i,s.size())==t.substr(0,t.size()-i)){
      cout << n+i;
      return 0;
    }
  }
}


Measured memory_bytes: 256
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 空白区切の入力値を数値の配列で返却する
def gets_i_list()
  gets.chomp.split(" ").map(&:to_i)
end
n, k = gets_i_list
p_list = gets_i_list

p_list.sort!

total = 0
k.times do |i|
  total += p_list[i]
end

puts total

Measured memory_bytes: 14500
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


NN = 202020
MOD = 10**9+7
# MOD = 998244353
INF = float("inf")

n, a, b, c = map(int, input().split())
s = [input() for i in range(n)]
num = [a, b, c]

ans = []
for i in range(n):
    if s[i] == "AB":
        if num[0] > num[1]:
            num[0], num[1] = num[0]-1, num[1]+1
            ans.append("B")
        elif num[0] < num[1]:
            num[0], num[1] = num[0]+1, num[1]-1
            ans.append("A")
        else:
            if num[0] == num[1] == 0:
                print("No")
                exit()
            if i < n-1 and s[i+1] == "BC":
                num[0], num[1] = num[0] - 1, num[1] + 1
                ans.append("B")
            else:
                num[0], num[1] = num[0] + 1, num[1] - 1
                ans.append("A")

    elif s[i] == "AC":
        if num[0] > num[2]:
            num[0], num[2] = num[0]-1, num[2]+1
            ans.append("C")
        elif num[0] < num[2]:
            num[0], num[2] = num[0]+1, num[2]-1
            ans.append("A")
        else:
            if num[0] == num[2] == 0:
                print("No")
                exit()
            if i < n-1 and s[i+1] == "BC":
                num[0], num[2] = num[0] - 1, num[2] + 1
                ans.append("C")
            else:
                num[0], num[2] = num[0] + 1, num[2] - 1
                ans.append("A")

    elif s[i] == "BC":
        if num[1] > num[2]:
            num[1], num[2] = num[1]-1, num[2]+1
            ans.append("C")
        elif num[1] < num[2]:
            num[1], num[2] = num[1]+1, num[2]-1
            ans.append("B")
        else:
            if num[1] == num[2] == 0:
                print("No")
                exit()
            if i < n-1 and s[i+1] == "AC":
                num[1], num[2] = num[1] - 1, num[2] + 1
                ans.append("C")
            else:
                num[1], num[2] = num[1] + 1, num[2] - 1
                ans.append("B")
    # print(num)

print("Yes")
for i in range(n):
    print(ans[i])


Measured memory_bytes: 85480
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 5000;
const int MOD = int(1E9) + 7;
const int INV2 = (MOD + 1) >> 1;

struct edge{
	edge *nxt; int to;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = edges;
void addedge(int u, int v) {
	edge *p = (++ecnt);
	p->to = v, p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->nxt = adj[v], adj[v] = p;
}

int fct[MAXN + 5], ifct[MAXN + 5], coef[MAXN + 5];
void init() {
	fct[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fct[i] = 1LL*fct[i-1]*i%MOD;
	ifct[1] = 1;
	for(int i=2;i<=MAXN;i++)
		ifct[i] = (MOD - 1LL*(MOD/i)*ifct[MOD%i]%MOD);
	ifct[0] = 1;
	for(int i=1;i<=MAXN;i++)
		ifct[i] = 1LL*ifct[i-1]*ifct[i]%MOD;
	int t = INV2;
	for(int i=2;i<=MAXN;i+=2,t=1LL*t*INV2%MOD)
		coef[i] = 1LL*fct[i]*ifct[i/2]%MOD*t%MOD;
}

int dp[MAXN + 5][MAXN + 5], siz[MAXN + 5];
void dfs(int x, int f) {
	dp[x][siz[x] = 1] = 1;
	for(edge *p=adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		dfs(p->to, x);
		int t1 = siz[x], t2 = siz[p->to], del = 0;
		for(int i=2;i<=t2;i+=2)
			del = (del + 1LL*dp[p->to][i]*coef[i]%MOD) % MOD;
		del = (MOD - del) % MOD;
		for(int i=t1;i>=1;i--) {
			for(int j=t2;j>=1;j--)
				dp[x][i+j] = (dp[x][i+j] + 1LL*dp[x][i]*dp[p->to][j]%MOD) % MOD;
			dp[x][i] = 1LL*del*dp[x][i] % MOD;
		}
		siz[x] += siz[p->to];
	}
}

int main() {
	int N; init();
	scanf("%d", &N);
	for(int i=1;i<N;i++) {
		int x, y; scanf("%d%d", &x, &y);
		addedge(x, y);
	}
	dfs(1, 0);
	int ans = 0;
	for(int i=1;i<=N;i++)
		ans = (ans + 1LL*dp[1][i]*coef[i]%MOD) % MOD;
	printf("%d\n", ans);
}

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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (1000000001)
#define MOD (1000000007)
#define PI (acos(-1))

int main(){
  int N,K;
  cin >> N >> K;
  int a[100010];
  rep(i,N){
    cin >> a[i];
  }
  ll sum[100010],psum[100010];
  sum[0] = a[0];
  psum[0] = max(0,a[0]);
  reps(i,1,N){
    sum[i] = sum[i-1]+a[i];
    psum[i] = psum[i-1]+max(0,a[i]);
  }

  ll ans = 0;
  rep(i,N-K+1){
    ll tmp;
    if(i==0 || i==N-1){
      if(i==0)tmp = max((ll)0,sum[K-1])+psum[N-1]-psum[K-1];
      else tmp = psum[N-K-1]+max((ll)0,sum[N-1]-sum[N-K-1]);
    }else{
      tmp = psum[i-1]+max((ll)0,sum[i+K-1]-sum[i-1])+psum[N-1]-psum[i+K-1];
    }
    ans = max(ans,tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=nxt();
    map<int,int> m;
    for(int i=0;i<n;i++)
    {
        int x=nxt();
        m[x]+=1;
    }
    bool f=1;
    for(int i=n-1;i>0;i-=2)
    {
        if(m[i]!=2)
        {
            f=0;
            break;
        }
    }
    if(n%2&&m[0]!=1)
    {
        f=0;
    }
    if(!f)
        cout<<"0\n";
    else
        cout<<power(2,n/2,1e9+7)<<endl;

    
    
    return 0;   
}




 
 


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main() {
    cin.tie(0)->sync_with_stdio(false);

	ll n; cin >> n;
	vector<ll> a(n), b(n), c(n);
	REP(i, n) cin >> a[i];
	sort(a.begin(), a.end());
	REP(i, n) cin >> b[i];
	sort(b.begin(), b.end());
	REP(i, n) cin >> c[i];
	sort(c.begin(), c.end());

	ll res = 0;
	REP(i, n) {
		auto itr = lower_bound(a.begin(), a.end(), b[i]);
		ll cnt_a = distance(a.begin(), itr);
		itr = upper_bound(c.begin(), c.end(), b[i]);
		ll cnt_c = distance(itr, c.end());
		res += cnt_a * cnt_c;
	}
	cout << res << '\n';
    return 0;
}


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

struct query {
  int v, d, c;
};

long long n, m, q;
vector<vector<int>> g;
vector<query> v;
vector<int> res;
vector<vector<int>> col;

void solve();

int main() {
  cin >> n >> m;
  g.resize(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    g[--a].push_back(--b);
    g[b].push_back(a);
  }
  cin >> q;
  v.resize(q);
  for (int i = 0; i < q; ++i) {
    cin >> v[i].v >> v[i].d >> v[i].c;
    --v[i].v;
  }
  solve();
  for (auto p : res) cout << p << endl;
  return 0;
}

void solve() {
  col.assign(n, vector<int>(11, 1000000));
  res.assign(n, 0);
  reverse(v.begin(), v.end());
  for (int i = 0; i < q; ++i)
    if (col[v[i].v][v[i].d] > i) {
      using P = pair<int, int>;
      queue<P> qu;
      qu.push(P(v[i].v, v[i].d));
      col[v[i].v][v[i].d] = i;
      while (qu.size()) {
        P now = qu.front();
        qu.pop();
        if (now.second == 0) continue;
        for (auto to : g[now.first]) {
          P tov = now;
          tov.first = to;
          --tov.second;
          if (col[tov.first][tov.second] > i) {
            col[tov.first][tov.second] = i;
            qu.push(tov);
          }
        }
      }
    }
  for (int i = 0; i < n; ++i) {
    int id = 1000000;
    for (int j = 0; j <= 10; ++j) id = min(id, col[i][j]);
    if (id != 1000000) res[i] = v[id].c;
  }
}


Measured memory_bytes: 17144
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <map>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> ans(N);
    for(int i=2; i<=N; i++) {
        int A;
        cin >> A;
        ans[--A]++;
    }

    for(auto e: ans){
        cout << e << endl;
    }
    return 0;
}


Measured memory_bytes: 4052
from math import gcd

n,k = map(int, input().split())
al = list(map(int, input().split()))
a_gcd = al[0]
for a in al[1:]:
    a_gcd = gcd(a_gcd,a)

if k%a_gcd == 0 and k <= max(al):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 85444
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N, A, B;
	int X, PX;
	cin >> N >> A >> B;
	int ans = 0;
	rep(i, 0, N)
	{
		cin >> X;
		if (i > 0)
		{
			ans += min(A*(X - PX), B);
		}
		PX = X;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256