akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp make_pair
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

class SuffixArray {
public:
  string &s;
  vector<int> sa, rank;
  int n;
  void construct_sa(){
    sa.resize(n+1);
    rank.resize(n+1);
    rep(i,n+1){
      sa[i]=i;
      rank[i] = (i<n)?s[i]:(-1);
    }
    vector<int> tmp(n+1,0);
    for(int k=1; k<=n; k*=2){
      auto comp = [&](const int i, const int j){
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        int ri = (i+k<=n)?(rank[i+k]):-1;
        int rj = (j+k<=n)?(rank[j+k]):-1;
        return ri < rj;
      };
      sort(all(sa), comp);
      tmp[sa[0]]=0;
      rep(i,1,n+1){
        tmp[sa[i]] = tmp[sa[i-1]];
        if(comp(sa[i-1], sa[i])) tmp[sa[i]]++;
      }
      swap(tmp, rank);
    }
  }
  SuffixArray(string &str) : s(str){
    n = s.size();
    construct_sa();
  }
  int getRank(const string t) const {
    int m = t.size();
    int l = 0, r = n+1;
    while(r-l>1){
      int mid = (r+l)/2;
      if(s.compare(sa[mid], m, t) < 0) l = mid;
      else r = mid;
    }
    return r;
  }
};

int rank_v[100005];

class SegTree{
public:
  int n;
  vector<int> data[1<<18];
  SegTree(int n_){
    n=1;
    while(n<n_) n*=2;
    rep(i,n_){
      data[n-1+i].pb(rank_v[i]);
    }
    for(int i=n-2; i>=0; i--){
      int il = 2*i+1, ir = 2*i+2;
      data[i].resize(data[il].size()+data[ir].size());
      merge(all(data[il]), all(data[ir]), data[i].begin());
    }
  }
  // 区間[a,b)でx以下の個数
  int query(int a, int b, int x, int k, int l, int r) const {
    if(r<=a || b<=l) return 0;
    if(a<=l && r<=b){
      return upper_bound(all(data[k]), x) - data[k].begin();
    }
    int vl = query(a,b,x,k*2+1,l,(r+l)/2);
    int vr = query(a,b,x,k*2+2,(r+l)/2,r);
    return vl+vr;
  }
  int query(int a, int b, int x) const {
    return query(a,b,x,0,0,n);
  }
};


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

  string s;
  int q;
  cin>>s>>q;
  SuffixArray sa(s);
  int n = s.size();

  rep(i,n) rank_v[i] = sa.rank[i];
  SegTree st(s.size());
// dbg(sa.rank, sa.sa);
  rep(_,q){
    int l,r;
    string t;
    cin>>l>>r>>t;
    r = r+1 - (t.size()-1);
    int lb = sa.getRank(t);
    int ub = sa.getRank(t+'|');
    // dbg(lb,ub);

    int ans = st.query(l,r,ub-1) - st.query(l,r,lb-1);
    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 22252
#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define FAST ios_base::sync_with_stdio(false);cin.tie(0);
    const double EPS = 1e-9;
    const double PI = acos(-1);
    const int knightDir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2}};
    //const int dx[]={0,0,0,1,1,1,-1,-1,-1};
    //const int dy[]={-1,0,1,-1,0,1,-1,0,1};
    const int dx[] = {0 , 1 , 0 , -1};
    const int dy[] = {1 , 0 , -1 , 0};
    //#define MOD         1000000007LL
    #define MAX         1000005
    const ll MOD = 1000000000 + 7;
    
    int main()
    {
        FAST
        int t;
        t = 1;

        while(t--)
        {
           int n;
           cin >> n;
           
           vector<int> dp(n + 5);
           
           for(int i = 3 ; i <= n ; i++)dp[i] = 1;
           
           for(int i = 3 ; i <= n ; i++)
           {
               for(int j = 3 ; j <= n ; j++)
               {
                   if(i - j < 3)break;
                   
                   dp[i] += dp[i - j];
                   dp[i] %= MOD;
               }
           }
           
           cout << dp[n] << endl;
        }
    }



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

int main(){
    vector<double> a(10);
    double sum;

    while(cin >> a[0]){
        sum = 0.0;
        for(int i=1; i<=9; i++){
            if(i%2 == 1){
                a[i] = a[i-1] * 2.0;
            }else{
                a[i] = a[i-1] / 3.0;
            }
        }

        for(int i=0; i<10; i++){
            sum += a[i];
        }

        printf("%.8lf\n", sum);
    }

    return 0;
}

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

int main() {
  string N;
  cin >> N;
  string ans = "No";
  int sum =0;
  for(int i=0; i<N.size(); i++){
    sum += (N.at(i)-'0');
  }
  if(sum%9==0)ans = "Yes";
  
  cout << ans << endl;
}

Measured memory_bytes: 3720
main = do
  a <- readLn
  b <- readLn
  c <- readLn
  x <- readLn
  let ans = [na * 500 + nb * 100 + nc * 50 | na <- [0 .. a], nb <- [0 .. b], nc <- [0 .. c]]
  print $ length $ filter (==x) ans


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

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef unsigned long long int lli;
typedef pair<int, int> pi;

int main()
{
    lli n;
    cin >> n;
    lli ans = 1000*(n/500);
    n = n%500;
    ans += 5*(n/5);
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, l[N], r[N], lid[N], rid[N], u[N];
int cmp1(int i, int j) {
	return l[i] != l[j] ? l[i] > l[j] : r[i] > r[j];
}
int cmp2(int i, int j) {
	return r[i] != r[j] ? r[i] < r[j] : l[i] < l[j];
}
int main() {
	// freopen("c.in", "r", stdin);
	scanf("%d", & n);
	for (int i = 1; i <= n; i ++)
		scanf("%d %d", l + i, r + i), lid[i] = rid[i] = i;
	sort(lid + 1, lid + n + 1, cmp1), sort(rid + 1, rid + n + 1, cmp2);
	long long ans = - ~ 0ull >> 2;
	for (int S = 0; S <= 1; S ++) {
		memset(u, 0, sizeof u);
		long long sum = 0;
		int cur = 0;
		for (int dir = S, rc = 0, lc = 0; ; dir ^= 1)
			if (! dir) {
				int id = rid[++ rc];
				if (r[id] >= cur)
					break;
				sum += cur - r[id], cur = r[id];
			}
			else {
				int id = lid[++ lc];
				if (l[id] <= cur)
					break;
				sum += l[id] - cur, cur = l[id];
			}
		sum += abs(cur), ans = max(ans, sum);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main () {

	int n;
	vector<int> values;

	cin >> n;
	cin.ignore();

	for (int i = 1; i <= n; i++){
		string tmp_value;
		
		if(i == n)
			getline(cin, tmp_value);
		else
			getline(cin, tmp_value, ' ');

		values.push_back(stoi(tmp_value));
	}
	
	for (int i = n; i != 0; i--){
		
		if (i == 1)
			cout << values[i - 1] << endl;
		else
			cout << values[i - 1] << ' ';
	}

	return 0;
}




Measured memory_bytes: 3184
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int t[100], h[100];

int main() {
  int  N, T, H, L;
  while(cin>>N>>T>>H>>L) {
    REP(i,N) cin >> t[i] >> h[i];
    int id = 0;
    int now = 0;
    while(1) {
      if (t[id]) {
        t[id]--;
        T++;
        now++;
      } else if (h[id]) {
        h[id]--;
        now+=10;
      } else break;
      if (T >L) break;
      if (now >= 9) {
        t[id] += now-9;
        T -= now-9;
        if (T<0) break;
        now = 0;
      }
      //cout << id << " " << h[id] << " " << t[id] << endl;
      id = (id + 1) % N;
    }
    cout << id+1 << endl;
  }
}

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

using namespace std;

#define FOR(i,s,e) for((i)=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)

#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

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

const double EPS = 1e-10;

typedef struct point_def {
  double x;
  double y;

  point_def(double _x, double _y) {
    x = _x;
    y = _y;
  }

} p;

void koch(int d, p pl, p pr) {

//pl__s//u\\t__pr

  if (!d) return;

  p ps(0, 0), pt(0, 0), pu(0, 0);
  ps.x = (pl.x * 2 + pr.x)/3;
  ps.y = (pl.y * 2 + pr.y)/3;
  pt.x = (pl.x + pr.x * 2)/3;
  pt.y = (pl.y + pr.y * 2)/3;
  pu.x = ps.x + (pt.x-ps.x)*0.5 - (pt.y-ps.y)*sqrt(3.0)*0.5;
  pu.y = ps.y + (pt.x-ps.x)*sqrt(3.0)*0.5 + (pt.y-ps.y)*0.5;

  koch(d-1, pl, ps); printf("%.8f %.8f\n", ps.x, ps.y);
  koch(d-1, ps, pu); printf("%.8f %.8f\n", pu.x, pu.y);
  koch(d-1, pu, pt); printf("%.8f %.8f\n", pt.x, pt.y);
  koch(d-1, pt, pr);
}

int main() {
  int n;
  p pl = p(0.0, 0.0);
  p pr = p(100.0, 0.0);
  scanf("%d ", &n);
  printf("%.8f %.8f\n", pl.x, pl.y);
  koch(n, pl, pr);
  printf("%.8f %.8f\n", pr.x, pr.y);
  return 0;
}

Measured memory_bytes: 1232
"""

https://atcoder.jp/contests/arc066/tasks/arc066_c

最終的な式における寄与を考える
-はどういう効果を持っている？

愚直な方法としてdpがある
dp[i][mnum] = i番目まで見て、-がmnum個重なってる状態での最大値
→ O(N^2)
じつは簡単にできる・保持しておくべき(答えになる)状態はもっと少ないのでは？
→これ、割と濃厚…か？

-の効果は、それ以降の寄与を反転させる
なるべく必要のない(無駄な)ところでは戻さない方が最適に近づく
現状 - で、足すやつを寄与+にしたい! → 戻す
現状 + で、足すやつを寄与-にしたい！→そんな場合はない
－直後のやつを寄与+にしたい！→ 戻せる+なら直前で-に戻せばいい

お？？？
A-B+C-D+E+F-…とやっていく
一度マイナスのカッコに入ると決めたとする
A-(B+C-(D+E+F)-G-(H+I))
すると、次の-以降はすべて+の寄与にできる

あとは耳dp！
dp[i][state] = i番目まで見て,stateの時の最大値
state = 0 #かっこをつけないで計算するモード
state = 1 #全引きモード
state = 2 #全足しモード

"""

N = int(input())

A = input().split()

dp = [int(A[0]),float("-inf"),float("-inf")]

for i in range(N-1):

    op = A[i*2+1]
    a =  int(A[i*2+2])

    ndp = [float("inf")] * 3

    if op == "+":

        ndp[0] = dp[0] + a
        ndp[1] = dp[1] - a
        ndp[2] = dp[2] + a

    else:

        ndp[0] = dp[0] - a
        ndp[1] = dp[0] - a
        ndp[2] = max(dp[2]+a ,dp[1]+a)

    dp = ndp

print (max(dp))
        


Measured memory_bytes: 91932
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  int n,h;
  cin >> n >> h;
  vector<int> A(n);
  vector<int> B(n);
  rep(i,n){
    int a,b;
    cin >> a >> b;
    A.at(i) = a;
    B.at(i) = b;
  }
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  int bound = lower_bound(B.begin(),B.end(),A.at(n-1)) - B.begin();
  int cnt = 0;
  for(int i=n-1;i>=bound;i--){
    if(h <= 0) break;
    h -= B.at(i);
    cnt ++;
  }
  if(h > 0){
    cnt += (h+A.at(n-1)-1)/A.at(n-1);
  }
  cout << cnt << endl;

    return 0;
}



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

int main(){
  vector<int> index(100);
  for(int i = 0; i < 9; i++){
    int a;
    cin >> a;
    index[a-1] = i+1;
  }
  int N;
  cin >> N;
  vector<int> row(3);
  vector<int> col(3);
  vector<int> sla(2);
  bool bingo = false;
  for(int k = 0; k < N; k++){
    int b;
    cin >> b;
    if(index[b-1] > 0){
      int i = floor((index[b-1]-1)/3);
      int j = (index[b-1]-1)%3;
      row[i] += 1;
      col[j] += 1;
      if(i == j){
        sla[0] += 1;
      }
      if(i == 2-j){
        sla[1] += 1;
      }
      if(row[i] == 3 || col[j] == 3 || sla[0] == 3 || sla[1] == 3){
        bingo = true;
      }
    }
  }
  if(bingo){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<utility>
#include<cstdio>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <bitset>
using namespace std;
const int mod=1e9+7;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,x,n) for (int i= x;i<n;i++)
#define all(v) v.begin(), v.end()
#define nepe(v) next_permutation(all(v))
#define F first 
#define S second
#define PB push_back 
#define MP make_pair
using ll = long long;
using vi = vector<int>; 
using vvi = vector<vi>;
using vl=vector<long long>;
using vp =vector<pair<int,int>>;

typedef pair<int,int> P;
string s;
int k;
ll INF = 10000000000000000;

int c(string S){
    int n = S.size();
    int count = 0;
    rep(i,n-1){
        if(S.substr(i,2)=="AB") count++;
    }
    return count;
}

int jAB(string S){
    int n = S.size();
    int j=0;
    if(S[0]=='B') j+=1;
    if(S[n-1]=='A') j+=2;
    return j;
}

int main(){
    int N;
    cin >>N;
    vector<string> S(N);
    int ans=0;
    vi AB(4,0);
    rep(i,N){
        cin >>S[i];
        ans += c(S[i]); 
    }
    rep(i,N){
        int n=jAB(S[i]);
        AB[n]++;
    }
    if(AB[1]==0&&AB[2]==0) ans += max(0,AB[3]-1);
    else if(AB[3]==0) ans += min(AB[1],AB[2]);
    else if(AB[1]==AB[2]) ans+=AB[3]+AB[1];
    else ans += AB[3]+min(AB[1],AB[2]);
    cout <<ans<<endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;

int main() {
    string S; cin >> S;
    if(S == "Sunny"){
        cout << "Cloudy" << endl;
    }
    else if(S == "Cloudy"){
        cout << "Rainy" << endl;
    }
    else if(S == "Rainy"){
        cout << "Sunny" << endl;
    }
}

Measured memory_bytes: 256
from collections import Counter,defaultdict
H,W= list(map(int,input().split()))

C = [list(map(int,input().split())) for _ in range(10)]

A =  [list(map(int,input().split())) for _ in range(H)]


cost = dict()

#d= defaultdict(int)
d = Counter()

for a in A:
    for i in a:
        if i==-1 or i==1:
            continue
        else:
            d[i]+=1

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return [get_path(start, goal, prev), cost[goal]]
ans = 0
for key in d:
    ans += d[key]*search(C,key,1)[1]
print(ans)

Measured memory_bytes: 3692
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = (ll)(1e+9) + 7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
ll l; int n;
ll x[1 << 18]; ll sx[1 << 18];
ll y[1 << 18]; ll sy[1 << 18];
int main() {
	cin >> l >> n;
	rep(i, n)cin >> x[i];
	rep(i, n) {
		sx[i + 1] = sx[i] + x[i];
	}
	rep(i, n) {
		y[i] = l - x[n - 1 - i];
		sy[i + 1] = sy[i] + y[i];
	}
	ll ans = 0;
	rep(i, n) {
		//左に属す
		ll sum = sx[i + 1] + sy[n - 1 - i]; sum *= 2;
		sum -= x[i];
		int nl = i; int nr = n - 1 - i;
		if (nl >= nr + 1) {
			int dif = nl - nr;
			sum -= 2 * sx[dif];
		}
		else if (nl + 2 <= nr) {
			int dif = nr - nl - 1;
			sum -= 2 * sy[dif];
		}
		ans = max(ans, sum);
		//cout << i << " " << sum << endl;
		//右に属す
		sum = sx[i] + sy[n - i]; sum *= 2;
		sum -= y[n - 1 - i];
		if (nl >= nr + 2) {
			int dif = nl - nr - 1;
			sum -= 2 * sx[dif];
		}
		else if (nl + 1 <= nr) {
			int dif = nr - nl;
			sum -= 2 * sy[dif];
		}
		ans = max(ans, sum);
		//cout << i << " " << sum << endl;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8064
#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<int,int>;

vector<int> to[100005];
const int INF =1001001001;

int main() {
int k,s;
cin>>k>>s;
int ans=0;
k++;
rep(i,k){
  rep(j,k){
    if(s-i-j<=k-1&&s-i-j>=0)ans++;
  }
}
cout << ans <<endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
const int K = (int)1e4 + 5;
int a[K];

int main()
{
	int N, M;
	cin >> N >> M;
	long long sum = 0;
	for (int i = 1; i <= M; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	if (sum > N) cout << -1;
	else cout << N - sum;

}




Measured memory_bytes: 3632
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int main(){
	int x,n,m,k,i;
	for(;scanf("%d",&n),n;){
		vector<set<int> >v;
		for(i=0;i<n;i++){
			set<int>s;
			for(scanf("%d",&m),k=0;k<m;k++)scanf("%d",&x),s.insert(x);
			v.push_back(s);
		}
		set<int>t;
		for(scanf("%d",&k),m=0;m<k;m++)scanf("%d",&x),t.insert(x);
		vector<int>w;
		for(k=0;k<n;k++){
			set<int>s;
			set_intersection(v[k].begin(),v[k].end(),t.begin(),t.end(),inserter(s,s.end()));
			if(s.size()==t.size()){w.push_back(k);if(w.size()>1)break;}
		}
		printf("%d\n",w.size()==1?w[0]+1:-1);
	}
}

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

int n;

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

    sort(array, array + n);

    cout << array[n-1] - array[0];

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (auto &x: a) cin >> x;

  int total = 0;
  for (auto &x: a) total += x;

  int required = (total + 4 * m - 1) / (4 * m);
  int selectable = 0;
  for (auto &x: a) {
    if (x >= required) selectable++;
  }

  if (selectable >= m) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
H, W, K = map(int, input().split())
grid = [input() for _ in range(H)]
ans = [[0] * W for _ in range(H)]

cnt = 1
for h in range(H):
    for w in range(W):
        if grid[h][w] == "#":
            ans[h][w] = cnt
            cnt += 1

# left -> right
for h in range(H):
    for w in range(1, W):
        if ans[h][w] == 0 and ans[h][w - 1] != 0:
            ans[h][w] = ans[h][w - 1]

# right -> left
for h in range(H):
    for w in range(W - 2, -1, -1):
        if ans[h][w] == 0 and ans[h][w + 1] != 0:
            ans[h][w] = ans[h][w + 1]

# top -> bottom
for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0 and ans[h - 1][w] != 0:
            ans[h][w] = ans[h - 1][w]

# bottom -> top
for h in range(H - 2, -1, -1):
    for w in range(W):
        if ans[h][w] == 0 and ans[h + 1][w] != 0:
            ans[h][w] = ans[h + 1][w]

for a in ans:
    print(*a)


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

int main(){
	int N, i;
	scanf("%d", &N);
	vector<int> a(N);
	for(i = 0; i < N; i++){
		scanf("%1d", &a[i]);
	}
	int b = 0;
	for(i = 0; i < N; i++){
		b ^= ((((N - 1) & i) == i) * (a[i] & 1));
	}
	if(b == 1){
		printf("1\n");
		return 0;
	}
	vector<int> a2(N - 1);
	for(i = 0; i < N - 1; i++){
		a2[i] = abs(a[i] - a[i + 1]);
		if(a2[i] == 1){
			printf("0\n");
			return 0;
		}
	}
	b = 0;
	for(i = 0; i < N - 1; i++){
		b ^= ((((N - 2) & i) == i) * (a2[i] == 2));
	}
	if(b == 1){
		printf("2\n");
	}
	else{
		printf("0\n");
	}
	return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
using namespace std;

/*int main(){
	int n,q;
	while(1){
		pair<int,int> data[101]={};
		rep(i,0,101){
			data[i].second=-i;
		}
		cin>>n>>q;
		if(n==0 && q==0) break;
		rep(i,0,n){
			int m,d;
			cin>>m;
			rep(j,0,m){
				cin>>d;
				data[d].first++;
			}
		}
		sort(data,data+101);
		reverse(data,data+101);
		if(data[0].first<q) cout<<0<<endl;
		else cout<<-data[0].second<<endl;
	}
}*/

int main(){
	int n,q;
	while(1){
		cin>>n>>q;
		if(n==0 && q==0) break;
		map<int,int> dat;
		rep(i,0,n){
			int m,d;
			cin>>m;
			rep(j,0,m){
				cin>>d;
				dat[d]++;
			}
		}
		int max=0,ans=0;
		for(map<int,int>::iterator it=dat.begin();it!=dat.end();it++){
			if(it->second>max){
				max=it->second;
				ans=it->first;
			}
		}
		if(max<q) cout<<0<<endl;
		else cout<<ans<<endl;
	}
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define rep(n) for(int i=0;i<n;i+=1)
#define prarr(a,n) rep(n) cout<<a[i]<<endl printf("%s\n"," " );
#define sc(a) scanf("%d",&a);
#define scl(a) scanf("%lld",&a);
#define scf(a) ascanf("%f",&a);
#define fi first
#define se second
#define pu push_back
#define inf 1000000001
#define MOD 1000000007 
#define INF 100000000000001
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    int co=0,ce=0;
    int ans=0;
    if(a&1) co++; else ce++;
    if(b&1) co++; else ce++;
    if(c&1) co++; else ce++;
	if(a>b) swap(a,b);
	if(b>c)swap(b,c);
	if(a>b) swap(a,b);
    if(ce==0 || co ==0)
    {
    
    	ans+=(c-a)/2+(c-b)/2;
    }
    else
    {
    	ans++;
    	if(co==2)
    	{
    		if(c&1 && b&1) {c++;b++;}
    		else if(b&1) {a++;b++;}
    		else {c++;a++;}
	if(a>b) swap(a,b);
	if(b>c)swap(b,c);
	if(a>b) swap(a,b);
    		ans+=(c-a)/2+(c-b)/2;
    	}
    	else
    	{
    		if(c%2==0 && b%2==0){c++;b++;}
    		else if(b%2==0){b++;a++;}
    		else{c++;a++;}
	if(a>b) swap(a,b);
	if(b>c)swap(b,c);
	if(a>b) swap(a,b);
		ans+=(c-a)/2+(c-b)/2;

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


}
    

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N):
    ans = 0

    for i in range(1, N+1, 2):
        c = 1
        for j in range(1, i//2 + 1):
            if i % j == 0:
                c += 1
        if c == 8:
            ans += 1

    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()


Measured memory_bytes: 62828
#include <stdio.h>
typedef long long ll;
using namespace std;

int main(void) {
  ll i, j, k, a, b, c, n, m;
  scanf("%lld%lld%lld", &a, &b, &c);
  printf("%lld", b / a > c ? c : b / a);
  return 0;
}

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


void solve(long long N){
    vector<vector<int>> res(N, vector<int>(N,-1));
    int k=2;
    for(int t=0;t<11;++t){
        for(int i=0;i<N;++i){
            for(int j=i+1;j<N;++j){
                if((i>>t)%2!=(j>>t)%2){
                    if(res[i][j]==-1)res[i][j]=t+1;
                }
            }
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=i+1;j<N-1;++j){
            cout<<res[i][j]<<" ";
        }
        cout<<res[i][N-1]<<endl;
    }
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


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

int main(){
  int n;
  cin>>n;
  int o=0;
  for(int i=0;i<n;i++){
    int a;
    cin >>a;
    if(a%2 != 0) o++;
  }
  if(o%2 == 0) cout << "YES"<<endl;
  else cout <<"NO"<<endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_v

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%lld%c", a[i], i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 1e5;
const int M_MAX = 1e9;

int N, M;

//------------------------------------------------------------------------------
const int V_MAX = N_MAX;

int V;
vector<int> G[V_MAX];

void add_edge(int from, int to) {
  G[from].push_back(to);
  G[to].push_back(from);
}

//------------------------------------------------------------------------------
#define LF(i)   (n - 1 + i)
#define PA(k)   ((k - 1) / 2)
#define LC(k)   (k * 2 + 1)
#define RC(k)   (k * 2 + 2)
#define M(l,r)  ((l + r) / 2)

template<typename T> class SegTree {
public:
  int n;
  int sz;
  T def;
  vector<T> dat;

  void init(int _n, T _def) {
    n = 1; while (n < _n) n <<= 1;
    sz = n * 2 - 1;
    def = _def;
    dat.resize(sz, def);
  }

  void update(int i, T x) {
    int k = LF(i);
    dat[k] = x;
    while (k > 0) {
      k = PA(k);
      dat[k] = dat[LC(k)] * dat[RC(k)] % M;
    }
  }

  T query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return def;
    if (a <= l && r <= b) return dat[k];
    T vl = query(a, b, LC(k), l, M(l, r));
    T vr = query(a, b, RC(k), M(l, r), r);
    return vl * vr % M;
  }

  T query(int a, int b) {
    if (a >= b) return def;
    return query(a, b, 0, 0, n);
  }

  T except(int i) {
    return query(0, i) * query(i + 1, n) % M;
  }

  void dump() {
    REP(i, sz) printf("%d%c", dat[i], i + 1 == sz ? '\n' : ' ');
  }
};

//------------------------------------------------------------------------------
SegTree<ll> dp[V_MAX];
int pi[V_MAX];

void dfs(int p, int v) {
  dp[v].init(G[v].size(), 1);
  REP(i, G[v].size()) {
    int u = G[v][i];
    if (u == p) {
      pi[v] = i;
      continue;
    }
    dfs(v, u);
    dp[v].update(i, (dp[u].dat[0] + 1) % M);
  }
  // printf("v=%d : ", v); dp[v].dump();
}

void dfs2(int p, int v, int vi) {
  if (p >= 0) dp[v].update(pi[v], (dp[p].except(vi) + 1) % M);
  REP(i, G[v].size()) {
    int u = G[v][i];
    if (u == p) continue;
    dfs2(v, u, i);
  }
}

void solve() {
  dfs(-1, 0);
  dfs2(-1, 0, -1);
  REP(v, V) printf("%lld\n", dp[v].dat[0]);
}

void input() {
  scanf("%d%d", &N, &M);
  V = N;
  REP(i, N - 1) {
    int x, y;
    scanf("%d%d", &x, &y);
    add_edge(x - 1, y - 1);
  }
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 24576
// 2020-07-24 07:52:55
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

using P = pair<int, int>;
const int INF = 1e9+5;
int G[300][300]; // cost
P dp[300][300]; // supply, used
int n, m, l;
void bfs(int s) {
  using T = tuple<int, int, int>; // supply, used, to
  priority_queue<T, vector<T>, greater<T> > que;
  que.emplace(T(0, 0, s));
  while(!que.empty()) {
    int supply, used, to;
    tie(supply, used, to) = que.top(); que.pop();
    if(chmin(dp[s][to], P(supply, used))) {
      rep(v, n) if(G[to][v] <= l) {
        int nsupply = supply, nused = used + G[to][v];
        if(nused > l) {
          nsupply++;
          nused = G[to][v];
        }
        if(dp[s][v] > P(nsupply, nused)) {
          que.emplace(T(nsupply, nused, v));
        }
      }
    }
  }
}
void answer() {
  cin >> n >> m >> l;
  rep(i, n) rep(j, n) {
    G[i][j] = INF;
    dp[i][j] = P(INF, 0);
    if(i == j) G[i][j] = 0;
  }
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    G[a][b] = c;
    G[b][a] = c;
  }
  rep(i, n) bfs(i);
  int q;
  cin >> q;
  rep(qi, q) {
    int s, t;
    cin >> s >> t;
    s--; t--;
    if(dp[s][t].first == INF) cout << -1 << '\n';
    else cout << dp[s][t].first << '\n';
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 5588
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int N,D,X;
    cin >> N >> D>> X;
    int A[N];
    for(int i = 0;i < N;i++) cin >> A[i];
    int ans = 0;
    for(int i = 0;i < N;i++){
        for(int j = 0;j < D;j++){
            if(j == 0) ans++;
            else{
            if(A[i] * j + 1 <= D) ans++;
            }
        }
    }
    cout << ans + X << endl;
}   

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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  int n,m;cin>>n>>m;
  while(n!=0||m!=0)
  {
    vector<int> a(m);
    vector<int> b(m);
    int i;
    rep(i,m)cin>>a[i]>>b[i];
    rep(i,m)
    {
      a[i]--;
      b[i]--;
    }
    vector<vector<int>> e(n);
    rep(i,m)
    {
      e[a[i]].emplace_back(b[i]);
      e[b[i]].emplace_back(a[i]);
    }
    vector<int> paint(n,-1);
    paint[0]=0;
    queue<int> q;
    queue<int> q2;
    q.push(0);
    int j;
    bool out=false;
    while(!q.empty())
    {
      int now=q.front();
      q.pop();
      rep(i,e[now].size())
      {
        if(paint[e[now][i]]==-1)
        {
          paint[e[now][i]]=(1-paint[now]);
          q2.push(e[now][i]);
        }
        else if(paint[e[now][i]]==paint[now])
        {
          out=true;
        }
      }
      while(!q2.empty())
      {
        q.push(q2.front());
        q2.pop();
      }
    }
    if(out)cout<<0<<endl;
    else
    {
      int count0=0;
      int count1=0;
      rep(i,n)
      {
        if(paint[i]==0)count0++;
        else if(paint[i]==1)count1++;
      }
      vector<int> ans(0);
      if(count0%2==0)ans.push_back(count0/2);
      if(count1%2==0)ans.push_back(count1/2);
      sort(all(ans));
      int ind=unique(all(ans))-ans.begin();
      cout<<ind<<endl;
      rep(i,ind)
      {
        cout<<ans[i]<<endl;
      }
    }
    cin>>n>>m;
  }
}




Measured memory_bytes: 3088
A_1 = list(map(int, input().split()))
A_2 = list(map(int, input().split()))
A_3 = list(map(int, input().split()))
N = int(input())

A = A_1 + A_2 + A_3

for i in range(N):
    b = int(input())
    if b in A:
        A[A.index(b)] = 0

bingo = [
    A[0] + A[1] + A[2],
    A[3] + A[4] + A[5],
    A[6] + A[7] + A[8],
    A[0] + A[3] + A[6],
    A[1] + A[4] + A[7],
    A[2] + A[5] + A[8],
    A[0] + A[4] + A[8],
    A[2] + A[4] + A[6],
    ]

if 0 in bingo:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, m = map(int, input().split())
    L, R = 1, n
    for _ in range(m):
        l, m = map(int, input().split())
        if l > L: L = l
        if m < R: R = m
    if R-L+1 < 0:
        print(0)
    else:
        print(R-L+1)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9096
#include<iostream>
#include<iomanip>
#include<cstring>

int n;
int tbl[11][11];

int main()
{
	while( std::cin >> n, n )
	{
		memset( tbl, 0, sizeof( tbl ) );

		for( int i = 0; i != n; ++i )
		{
			for( int j = 0; j != n; ++j )
			{
				std::cin >> tbl[i][j];
	
				tbl[i][n] += tbl[i][j];
				tbl[n][j] += tbl[i][j];
				tbl[n][n] += tbl[i][j];
			}
		}

		for( int i = 0; i <= n; ++i )
		{
			for( int j = 0; j <= n; ++j )
				std::cout << std::setw( 5 ) << std::right << tbl[i][j];	
	
			std::cout << std::endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
#include<math.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)


int main() {
  int N;
  cin>>N; 
  vector<long> c(87);
  c.at(0)=2;
  c.at(1)=1;
  rep2(i,2,87){
    c.at(i)=c.at(i-1)+c.at(i-2);
  }
  
    cout << c.at(N)<< endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;

ull PickLargestMinimumPiece(const ull _total_size, const ull _piece1_s, const ull _piece1_l, const ull _piece3_s, const ull _piece3_l){
	ull tmp = min(_piece1_s, _piece3_s);
	
	ull piece2 = _total_size - _piece1_s - _piece3_l;
	tmp = max(tmp, min(_piece1_s, piece2));

	piece2 = _total_size - _piece1_l - _piece3_s;
	tmp = max(tmp, min(_piece3_s, piece2));

	piece2 = _total_size - _piece1_l - _piece3_l;
	tmp = max(tmp, piece2);

	return tmp;
}

void CalcPiece1(int *_i2, ull *_piece1_s, ull *_piece1_l, const int _i1, const int _N, const ull _one_third_size, const int *_A){
	for (; *_i2 < _i1 + _N - 2;){
		*_piece1_s = *_piece1_l;
		*_piece1_l += _A[*_i2%_N];
		(*_i2)++;
		if (*_piece1_l > _one_third_size) break;
	}
}

void CalcPiece3(int *_i3, ull *_piece3_s, ull *_piece3_l, const int _i1, const int _N, const ull _one_third_size, const int *_A){
	for (; *_i3 < _i1 + _N - 1;){
		*_piece3_l = *_piece3_s;
		*_piece3_s -= _A[*_i3%_N];
		(*_i3)++;
		if (*_piece3_s <= _one_third_size) break;
	}
}

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

	int N;
	cin >> N;

	int *A = new int[N];
	ull total_size = 0;
	int i1_ini = 0;
	int A_max = 0;
	for(int i=0; i<N; i++){
		cin >> A[i];
		total_size += A[i];
		if (A[i] > A_max){
			A_max = A[i];
			i1_ini = i;
		}
	}
	ull one_third_size = total_size / 3;

	ull answer = 0;
	if (A_max > one_third_size){
		ull half_size = (total_size - A_max) / 2;
		ull tmp = 0;
		ull piece2 = 0;
		int i3 = i1_ini + 1;
		/*CalcPiece1(&i3, &piece2, &tmp, i1_ini + 1, N, half_size, A);
		ull piece3 = total_size - A_max - tmp;*/
		ull piece3 = total_size - A_max;
		CalcPiece3(&i3, &piece3, &tmp, i1_ini, N, half_size, A);
		piece2 = total_size - A_max - tmp;
		answer = max(piece2, piece3);
		cout << answer << endl;
		delete[] A;
		return 0;
	}

	int i2 = i1_ini;
	ull piece1_s = 0;
	ull piece1_l = 0;
	CalcPiece1(&i2, &piece1_s, &piece1_l, i1_ini, N, one_third_size, A);
	const int i1_fin = i2;

	int i3 = i2;
	ull piece3_s = total_size - piece1_l;
	ull piece3_l = 0;
	CalcPiece3(&i3, &piece3_s, &piece3_l, i1_ini, N, one_third_size, A);

	answer = PickLargestMinimumPiece(total_size, piece1_s, piece1_l, piece3_s, piece3_l);

	for (int i1 = i1_ini + 1; i1 < i1_fin; i1++){
		int A_tmp = A[(i1 - 1) % N];
		piece1_l -= A_tmp;
		if (piece1_l > one_third_size) piece1_s -= A_tmp;
		else CalcPiece1(&i2, &piece1_s, &piece1_l, i1, N, one_third_size, A);

		piece3_s += A_tmp;
		if (piece3_s <= one_third_size) piece3_l += A_tmp;
		else CalcPiece3(&i3, &piece3_s, &piece3_l, i1, N, one_third_size, A);

		answer = max(answer, PickLargestMinimumPiece(total_size, piece1_s, piece1_l, piece3_s, piece3_l));
	}

	cout << answer << endl;

	delete[] A;

	return 0;
}

Measured memory_bytes: 1536
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<ctime>
#include<complex>
#include<list>
#include<limits.h>
#include<iomanip>
using namespace std;

const int N=5005;
const int MOD=1e9+7;
int n,ans;
vector<int> nei[N];
int f[N],siz[N];
int dp[N][N][2],tmp[2];

inline void add(int &x,int y){
	x+=y;
	if(x>=MOD) x-=MOD;
	if(x<0) x+=MOD;
}

void dfs(int x,int p){
	dp[x][1][0]=1;siz[x]=1;
	for(int i=0;i<nei[x].size();i++){
		int to=nei[x][i];
		if(to==p) continue;
		dfs(to,x);
		for(int j=siz[x];j>=1;j--){
			tmp[0]=dp[x][j][0];
			tmp[1]=dp[x][j][1];
			dp[x][j][0]=0;
			dp[x][j][1]=0;
			for(int k=0;k<2;k++) if(tmp[k]) for(int l=1;l<=siz[to];l++) for(int o=0;o<2;o++){
				add(dp[x][j+l][k^o],1ll*tmp[k]*dp[to][l][o]%MOD);
				if(l%2==0) add(dp[x][j][k^o^1],1ll*tmp[k]*f[l]%MOD*dp[to][l][o]%MOD);
			}
		}
		siz[x]+=siz[to];
	}
}

int main(){
	f[0]=1;
	for(int i=2;i<=5000;i++) f[i]=1ll*f[i-2]*(i-1)%MOD;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	dfs(1,-1);
	for(int i=2;i<=n;i+=2){
		add(ans,1ll*dp[1][i][0]*f[i]%MOD);
		add(ans,-(1ll*dp[1][i][1]*f[i]%MOD));
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 195200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

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;
}

int main(){

    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for(int i = 0; i < m; i++){
        cin >> x[i];
    }
    sort(x.begin(), x.end());
    vector<int> dist(m-1);
    for(int i = 0; i < m-1; i++){
        dist[i] = x[i+1] - x[i]; 
    }
    sort(dist.rbegin(), dist.rend());
    int ans = 0;
    for(int i = n-1; i < m-1; i++){
        ans += dist[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int N, W, H;
    cin >> N >> W >> H;

    int vertical[W + 1];
    int horizon[H + 1];
    for (int i = 0; i < W + 1; i++) {
        vertical[i] = 0;
    }
    for (int i = 0; i < H + 1; i++) {
        horizon[i] = 0;
    }

    for (int times = 0; times < N; times++) {
        int x, y, w;
        cin >> x >> y >> w;
        int temp;
        temp = (x - w >= 0) ? x - w : 0;
        vertical[temp]++;
        temp = (x + w <= W) ? x + w : W;
        vertical[temp]--;

        temp = (y - w >= 0) ? y - w : 0;
        horizon[temp]++;
        temp = (y + w <= H) ? y + w : H;
        horizon[temp]--;
    }


    for (int i = 1; i < W + 1; i++) {
        vertical[i] += vertical[i - 1];
    }
    for (int i = 1; i < H + 1; i++) {
        horizon[i] += horizon[i - 1];
    }
    bool flagv = true;
    bool flagh = true;
    for (int i = 0; i < W; i++) {
        if (vertical[i] == 0) {
            flagv = false;
            break;
        }
    }
    for (int i = 0; i < H; i++) {
        if (horizon[i] == 0) {
            flagh = false;
            break;
        }
    }

    if (!flagv && ! flagh) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 3868
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007


struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll n, m, s[110000], ans = 0;
UnionFind uni(110000);
int main() {
	cin >> n >> m;
	REPO(i, n) cin >> s[i];
	REP(i, m) {
		ll a, b;
		cin >> a >> b;
		uni.unionSet(a, b);
	}
	REPO(i, n) {
		if (uni.findSet(s[i], i))ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
import java.util.*;

class Main {
    
    static int[][] queen = new int[8][8];
    static int[][] ok = new int[8][8];
    static int cnt = 0;
    
    static void mark(int a, int b, int x){
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++){
                if(i == a || j == b || Math.abs(i - a) == Math.abs(j - b)){
                    ok[i][j] += x;
                }
            }
        }
    }
    
    static void dfs(int a){
        
        if(cnt == 8) return;
        if(a == 64) return;
        
        int i = a / 8;
        int j = a % 8;
        if(ok[i][j] == 0){
            
            mark(i, j, 1);
            queen[i][j] = 1;
            cnt++;
            dfs(a + 1);
            if(cnt == 8) return;
            
            mark(i, j, -1);
            queen[i][j] = 0;
            cnt--;
            dfs(a + 1);
            if(cnt == 8) return;
        }else{
            dfs(a + 1);
            if(cnt == 8) return;
        }
    }
    
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        for(int i = 0; i < k; i++){
            int r = sc.nextInt();
            int c = sc.nextInt();
            mark(r, c, 1);
            queen[r][c] = 1;
        }
        cnt = k;
        dfs(0);
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++){
                if(queen[i][j] == 1){
                    System.out.print("Q");
                }else{
                    System.out.print(".");
                }
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 27084
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            string N = Console.ReadLine();
            string ans = "No";
            if (N[0] == N[2]) { ans = "Yes"; }
            Console.WriteLine(ans);



            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 13140
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Scan()
	l := sc.Text()
	words := strings.Split(l, " ")

	frequency := map[string]int{}
	long := map[string]int{}
	var maxFrequency, longest int
	var frequentWord, longestWord string
	for _, w := range words {
		frequency[w]++
		long[w] = len(w)
		if frequency[w] > maxFrequency {
			maxFrequency = frequency[w]
			frequentWord = w
		}
		if len(w) > longest {
			longest = long[w]
			longestWord = w
		}
	}

	fmt.Println(frequentWord + " " + longestWord)
}



Measured memory_bytes: 1092
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String plus = "+", minus = "-", time = "*", divide = "/", end = "?";
        while(true){
            int a = sc.nextInt();
            String op = sc.next();
            int b = sc.nextInt();
            if(op.equals(plus)){
                System.out.println(a + b);
            }else if(op.equals(minus)){
                System.out.println(a - b);
            }else if(op.equals(time)){
                System.out.println(a * b);
            }else if(op.equals(divide)){
                System.out.println(a / b);
            }else if(op.equals(end)){
                break;
            }
        }
        sc.close();
    }
}


Measured memory_bytes: 26512
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	ll N, A, B;
	cin >> N >> A >> B;
	ll num = A + B;
	ll ans = A * (N / num);
	N %= num;
	ans += min(A, N);
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define f(p,n) for(ll i=p;i<n;i++)
ll exp(ll a,ll b,ll m);
ll n;
ll ans=0;
ll h[101]={0};
bool vis[101]={0};
int main()
{
 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

 	cin>>n;
 	f(0,n) cin>>h[i];

 	ll ma=0;
 	f(0,n) ma=max(ma,h[i]);

 	for(ll op=1;op<=ma;op++)
 	{
 		bool lop=0;
 		for(ll j=0;j<n;j++)
 		{
 			if(h[j]>=op)
 			{
 				if(lop==0)
 				{
 					ans++;
 					lop=1;
 				}
 			}
 			else lop=0;
 		}
 	}
	cout<<ans<<endl;
return 0;
}

ll exp(ll a,ll b,ll m)
{
	if(b==0)
	{
		return 1;
	}
	ll temp =exp(a,b/2,m);
	temp=(temp*temp)%m;
	if(b&1)
	{
		return (temp*(a%m))%m;
	}
	return temp;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){

    double r, area, circ;
    cin >> r;
    area = M_PI * r * r;
    circ = 2 * M_PI * r;
    printf("%f %f\n", area, circ);
    return 0;
}



Measured memory_bytes: 3292
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Diagnostics;
using static System.Console;
using static System.Math;

namespace CodeForces
{
    class CodeForcesss
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            int[] ls = ReadLine().Split(' ').Select(int.Parse).ToArray();
            WriteLine(
                ls.Sum() - ls.Max() > ls.Max() ? "Yes": "No"
                );
        }
    }
}


Measured memory_bytes: 13396
dic={}
def gcd(x,y):
  if x<y:
    a=x
    x=y
    y=a
  t=(x,y)
  if t in dic:
    return dic[t]
  else:
    while y!=0:
      a=x%y
      x=y
      y=a
    dic[t]=x
    return x

s=0
n=int(input())
for i in range(1,n+1):
  for j in range(1,n+1):
    g=gcd(i,j)
    for k in range(1,n+1):
      s+=gcd(g,k)

print(s)

Measured memory_bytes: 78604