akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 200005;
const double PI = acos(-1);

int n;
int x[maxn],y[maxn];
unordered_map<int,int>mpx,mpy;

int b[maxn];
int cal(vector<int>& a) {
  if(a.size()==0)return 0;
  n = a.size();
  int len = 1; b[0] = a[0];
  for (int i = 1; i < n; i++) {
    b[a[i] > b[len - 1] ? len++ : lower_bound(b, b + len, a[i]) - b] = a[i];
  }
  return len;
}

int main() {
#ifdef suiyuan2009
  freopen("in.cpp","r",stdin);
#endif // suiyuan2009
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  cin>>n;
  for(int i=0; i<n; i++) {
    cin>>x[i]>>y[i];
    mpx[x[i]]=y[i];
    mpy[y[i]]=x[i];
  }
  double ret=0,R=10.0;
  if(x1==x2) {
    int ty1=y1,ty2=y2;
    if(ty1>ty2)swap(ty1,ty2);
    if(mpx.find(x1)!=mpx.end()) {
      int tmp=mpx[x1];
      if(ty1<=tmp&&tmp<=ty2) {
        ret=(ty2-ty1)*100.0-2*R+PI*R;
      } else {
        ret=(ty2-ty1)*100.0;
      }
    } else {
      ret=(ty2-ty1)*100.0;
    }
  } else if(y1==y2) {
    int tx1=x1,tx2=x2;
    if(tx1>tx2)swap(tx1,tx2);
    if(mpy.find(y1)!=mpy.end()) {
      int tmp=mpy[y1];
      if(tx1<=tmp&&tmp<=tx2) {
        ret=(tx2-tx1)*100.0-2*R+PI*R;
      } else {
        ret=(tx2-tx1)*100.0;
      }
    } else {
      ret=(tx2-tx1)*100.0;
    }
  } else {
    if(x1>x2){
      swap(x1,x2);
      swap(y1,y2);
    }
    vector<pair<int,int>>vec;
    for(int i=0;i<n;i++){
      if(x[i]<=x2&&x[i]>=x1&&y[i]<=max(y1,y2)&&y[i]>=min(y1,y2))vec.push_back(make_pair(x[i],y[i]));
    }
    sort(vec.begin(),vec.end());
    vector<int>vec2;
    for(int i=0;i<vec.size();i++){
      vec2.push_back(vec[i].second);
    }
    if(y1>y2)reverse(vec2.begin(),vec2.end());
    int mx = cal(vec2);
    ret=abs(x2-x1)*100.0+abs(y2-y1)*100.0;
    ret=ret-mx*2*R+mx*R*PI/2;
    if(mx==abs(y1-y2)+1||mx==abs(x2-x1)+1){
      ret+=R*PI/2;
    }
  }
  printf("%.15f\n",ret);
  return 0;
}



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

using namespace std;
using ll = long long;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

#define READ(x) (cin >> (x))

#define WRITE_N(x) (cout << (x) << endl)
#define WRITE(x) (cout << (x))

using Tri_int = array<int, 3>;

//map<Tri_int, int> gcd_map;

int gcd_multi(vector<int> &v) {
    int m = *min_element(ALL(v));

    vector<int> tmp = v;
    for (auto &n : tmp) {
        n %= m;
    }
    tmp.erase(remove(ALL(tmp), 0), tmp.end());

    if (tmp.size() == 0) {
        return m;
    } else {
        tmp.push_back(m);
        return gcd_multi(tmp);
    }
}

//int gcd(int a, int b) {
//    if (b < a) {
//        return gcd(b, a);
//    }
//
//    int x = b % a;
//
//    if (x == 0) {
//        return a;
//    }
//
//    return gcd(x, a);
//}
//
//int gcd_tri(int a, int b, int c) {
//    return gcd(gcd(a, b), gcd(a, c));
//}

//int get_gcd_tri(int a, int b, int c) {
//    Tri_int t { a, b, c };
//    sort(ALL(t));
//
//    if (gcd_map.count(t) != 0) {
//        return gcd_map[t];
//    } else {
//        vector<int> v(ALL(t));
//        int g = gcd_multi(v);
//        gcd_map[t] = g;
//        return g;
//    }
//}

int main() {
    // get values from input
    int K;
    READ(K);

    // main procedure
    int sum = 0;
//    for (int a = 1; a <= K; ++a) {
//        for (int b = 1; b <= K; ++b) {
//            for (int c = 1; c <= K; ++c) {
//                sum += get_gcd_tri(a, b, c);
//            }
//        }
//    }
    for (int a = 1; a <= K; ++a) {
        for (int b = a; b <= K; ++b) {
            for (int c = b; c <= K; ++c) {
                vector<int> v{a, b, c};
                int g = gcd_multi(v);
                int distinct_count = 3 - (a == b ? 1 : 0) - (b == c ? 1 : 0);

                if (distinct_count == 3) {
                    sum += 6 * g;
                } else if (distinct_count == 2) {
                    sum += 3 * g;
                } else {
                    sum += g;
                }
            }
        }
    }

    // output
    WRITE_N(sum);
    return 0;
}


Measured memory_bytes: 3632
import os

s = list(map(str,input()))
t = list(map(str,input()))
s = s*2
n = len(t)

for i in range(n):
    flag = True
    for j in range(n):
        if s[i+j]!=t[j]:
            flag = False
            break
    if flag:
        print("Yes")
        exit()

print("No")


Measured memory_bytes: 3060
N, P = map(int,input().split())
bis = list(map(int, input().split()))
if P == 0:
    ans = 2 ** N
else:
    ans = 0

for i in range(N):
    if bis[i] % 2 == 1:
        ans = 2 ** (N-1)
        break
print(ans)

Measured memory_bytes: 3060
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		
        if((a*b)%2 == 0){
          System.out.println("Even");
        }else{
          System.out.println("Odd");
        }
	}
}

Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <utility>
#include <tuple>
#include <map>
using namespace std;


int main() {
    int x;
    cin >> x;
    if (x >= 30) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 3068
N,D = map(int,input().split())

X = []
for i in range(N):
    X.append([int(j) for j in input().split()])

ans = 0

def dist(a,b):
    dist = 0
    for j in range (len(a)):
        dist += (a[j]-b[j])**2
    return(dist**0.5 == int(dist**0.5))
    
for k in range (len(X)):
    for l in range (k+1, len(X)):
        ans += (dist(X[k],X[l]))

print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

ll n;
P x[200000];
ll r[200000];
 
int main(int argc, char **argv) {
	cin >> n;
	REP(i, n) {
		x[i].S = i;
		cin >> x[i].F;
	}
	sort(x, x+n);
	REP(i, n) r[x[i].S] = i;
	REP(i, n) cout << (r[i] >= n/2 ? x[n/2-1].F : x[n/2].F) << endl;
	return 0;
}
 

Measured memory_bytes: 6912
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String in[] = new String[2];
		long l = 0, r = 0;
		try {
			line = br.readLine();
			in = line.split(" ");
			l = Long.parseLong(in[0]);
			r = Long.parseLong(in[1]);
		} catch (IOException e) {
			e.getStackTrace();
		}
		
		int min = 2020;
		int mod;
		for (long i = l; i < r; i++) {
			for (long j = i+1; j <= r; j++) {
				if(min > (mod =(int) ((i*j) % 2019))) {
					min = mod;
					if(min == 0) break;
				}
			}
			if(min == 0) break;
		}
	System.out.println(min);		
	}
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  
  int ALICE = 0;
  int BOB = 0;
  for (int i = 0; i< N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  
  if (N % 2) {
    for (int i = 0; i < N / 2 + 1; i++) {
      ALICE += vec.at(2 * i);
    }
    for (int i = 0; i < N / 2; i++) { 
      BOB += vec.at(2 * i + 1); 
    }
    cout << ALICE - BOB << endl;
    return 0;
  } else {
    for (int i = 0; i < N / 2; i++) {
      BOB += vec.at(2 * i);
    }
    for (int i = 0; i < N / 2; i++) {
      ALICE += vec.at(2 * i + 1); 
    }
    cout << ALICE - BOB << endl;
    return 0;
  }

}


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

int main(void) {
	int A, B, M;
	cin >> A >> B >> M;
	vector <int> a(A);
	for (int i = 0; i < A; i++) cin >> a[i];

	vector <int> b(B);
	for (int i = 0; i < B; i++) cin >> b[i];
	

	int ans = 100000+100000;
	for (int i = 0; i < M; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		ans = min(ans, a[x-1]+b[y-1]-c);
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	ans = min(ans, a[0]+b[0]);

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


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

const int MAX = 1e2 + 5;
const int INF = 1e6 + 5;

#define dbg(a) cout << "-> " << __LINE__ << ": " << #a << " = " << a << endl

int h, w;
string str[MAX];

int dp[MAX][MAX][3];
int vis[MAX][MAX][3], p = 1;

int solve (int i, int j, int ww) {
	if (i > h or j > w) {
		return INF;
	}
	if (i == h and j == w) {
		if (str[i][j] == '#' and ww == 1) {
			return 1;
		}
		return 0;
	}
	if (vis[i][j][ww] == p) {
		return dp[i][j][ww];
	}
	vis[i][j][ww] = p;
	int &ret = dp[i][j][ww];
	ret = min(solve(i + 1, j, str[i][j] == '.'), solve(i, j + 1, str[i][j] == '.'));
	if (str[i][j] == '#' and ww == 1) {
		++ret;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> h >> w;
	for (int i = 1; i <= h; i++) {
		cin >> str[i];
		str[i] = ' ' + str[i];
	}
	cout << solve(1, 1, 1) << '\n';
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define acc(v) accumulate(v.begin(), v.end(), 0)

using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

int main()
{
    string s,t;
    cin >> s >> t;
    rep(i,s.length()){
        if(s[i]!=t[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

//ユークリッドの互除法
template <class T>
T gcd(T a, T b) {
    if(b == 0){
        return a;
    }
    gcd(b, a % b);
}

int main(){

    int x, y;
    cin >> x >> y;

    cout << gcd(x, y) << endl;

    return 0;
}


Measured memory_bytes: 3092
#include <stdio.h>
#define MAX 100000

int main()
{
  int n, i, j, A[MAX], x, y;
  
  scanf("%d", &n);

  for(i = 0; i < n; i++) scanf("%d", &A[i]);

  x = A[n - 1];
  i = 0;

  for(j = i; j < n; j++){
    if(A[j] <= x){
      y = A[i];
      A[i] = A[j];
      A[j] = y;
      i++;

    }
  }     

  for(j = 0; j < n; j++){
    if(i - 1 == j) printf("[%d] ", A[j]);
    else if(j == n - 1) printf("%d", A[j]);
    else  printf("%d ", A[j]);
  }
  printf("\n");
  
  return 0;
}

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

/**
 * vector<int>ar(3);
 * for(auto&e:ar){
 *     scanf("%d",&e);
 * }
 * sort(ar.begin(),ar.end())
 * int sum=accumulate(ar.begin(),ar.end(),0);
 ***/
void solve(){
}
int main(){
    double pai=3.141592653589;
    int dice[6],tmp;
    char c[100];
    for(int i=0;i<6;i++){
        scanf("%d",&dice[i]);
    }
    scanf("%s",&c);
    for(int i=0;c[i];i++){
        if(c[i]=='S'){
            tmp=dice[4];
            dice[4]=dice[5];
            dice[5]=dice[1];
            dice[1]=dice[0];
            dice[0]=tmp;
        }else if(c[i]=='N'){
            tmp=dice[1];
            dice[1]=dice[5];
            dice[5]=dice[4];
            dice[4]=dice[0];
            dice[0]=tmp;
        }else if(c[i]=='W'){
            tmp=dice[2];
            dice[2]=dice[5];
            dice[5]=dice[3];
            dice[3]=dice[0];
            dice[0]=tmp;
        }else if(c[i]=='E'){
            tmp=dice[3];
            dice[3]=dice[5];
            dice[5]=dice[2];
            dice[2]=dice[0];
            dice[0]=tmp;
        }
    }
    printf("%d\n",dice[0]);
    return 0;
}

Measured memory_bytes: 1176
#include <stdio.h>

int main(){
	int N,Y;
	scanf("%d %d",&N,&Y);
	int i,j;
	for(i = 0;i<=Y/10000;i++){
		for(j = 0;j<=(Y-i*10000)/5000;j++){
			if((i*10000 + j*5000 + (N-i-j)*1000) == Y){

				printf("%d %d %d\n",i,j,N-i-j);
				return 0;
			}
		}
	}
	printf("-1 -1 -1\n");

}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <list>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <map>

using namespace std;

int h, a[500000+1];

void maxHeapify( int i) {
	int l = 2*i, r = 2*i+1;
	int largest;
	if( l <= h && a[l] > a[i]) largest = l;
	else largest = i;
	if( r <= h && a[r] > a[largest]) largest = r;
	
	if( largest != i) {
		swap(a[i], a[largest]);
		maxHeapify(largest);
	}
	return;
}

int main(){
	cin >> h;
	for( int i = 1; i <= h; i++) cin >> a[i];
	for( int i = h/2; i >= 1; i--) maxHeapify(i);
	for( int i = 1; i <= h; i++) cout << " " << a[i];
	cout <<endl;
	return 0;
}

Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
long long a[3][105]; 
long long n;
int main(){
    cin >> n;
    for(int i=1;i<=2;i++){
        for(int j=1;j<=n;j++)  cin >> a[i][j];
    }
    a[1][n]+=a[2][n];
for(int i=n-1;i>=1;i--){
    a[2][i]+=a[2][i+1];
    a[1][i]=a[1][i]+max(a[2][i],a[1][i+1]);
}
cout<<a[1][1];
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	auto fn = [](ll i) {
		return i * i * i * i * i;
	};
	ll x;
	cin >> x;
	map<ll, ll> mp;
	for(ll i = -250; i <= 250; i++) mp[fn(i)] = i;

	for(ll i = 0; i <= 250; i++) {
		ll dff = fn(i) - x;
		if(!mp.count(dff)) continue;
		cout << i << ' ' << mp[dff] << '\n'; return 0;
	}
}



Measured memory_bytes: 3692
from collections import deque
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
magic = [[i, j] for i in range(-2, 3) for j in range(-2, 3)]
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
S = [list(input()) for i in range(H)]
is_visited = [[-1 for j in range(W)]for i in range(H)]

d = deque()
d.appendleft((0, (Ch, Cw)))
while d:
    cost, (x, y) = d.popleft()
    if is_visited[x][y] != -1:
        continue
    is_visited[x][y] = cost
    for dx, dy in lrud:
        nx, ny = x+dx, y+dy
        if 0 <= nx < H and 0 <= ny < W and is_visited[nx][ny] == -1 and S[nx][ny] == '.':
            d.appendleft((cost, (nx,ny)))
    for dx, dy in magic:
        nx, ny = x+dx, y+dy
        if 0 <= nx < H and 0 <= ny < W and is_visited[nx][ny] == -1 and S[nx][ny] == '.':
            d.append((cost+1, (nx,ny)))

# print(is_visited)
print(is_visited[Dh][Dw])

Measured memory_bytes: 232044
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string str;
	while (cin >> str) cout << str[0];
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = np.array([0] + A + [0])
# print('A', A)
D = np.abs(A[1:] - A[:-1])
# print('D', D)

sum_D = D.sum()
for i in range(1, N + 1):
    c = np.abs(A[i - 1] - A[i + 1])
    print(sum_D - (D[i - 1] + D[i]) + c)


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

class FenwickTree {
private:
    int n;
    vector<ll> dat;
public:
    FenwickTree(int _n): n(_n), dat(_n+1, 0) {}
    FenwickTree(int _n, ll init): n(_n), dat(_n+1, 0) {
        for (int i = 0; i <= _n; i++) {
            add(i, init);
        }
    }
    
    void add(int idx, ll value) {
        for (idx++; idx <= n; idx += idx & -idx) {
            dat[idx] += value;
        }
    }

    ll query(int l, int r) {
        ll ans = 0;
        for (r++; r > 0; r -= r & -r) {
            ans += dat[r];
        }
        for (; l > 0; l -= l & -l) {
            ans -= dat[l];
        }
        return ans;
    }
};

bool comp(pair<int,int> a, pair<int,int> b)
{
    return a.second - a.first < b.second - b.first;
}

int main(void)
{
    int n, m;
    cin >> n >> m;

    vector< pair<int,int> > A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i].first >> A[i].second;
    }
    sort(A.begin(), A.end(), comp);

    FenwickTree ft(m+1);

    int idx = 0;
    for (int d = 1; d < m+1; d++) {
        for(; idx < n && A[idx].second - A[idx].first < d; idx++) {
            ft.add(A[idx].first, 1);
            ft.add(A[idx].second+1, -1);
        }
        ll count = n - idx;
        for (int i = 0; i < m+1; i += d) {
            count += ft.query(0, i);
        }
        cout << count << endl;
    }
}


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

using namespace std;

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

int main(){
    int N;
    string S;

    int wa=0;
    int mx=0;

    cin>>N>>S;

    REP(0,N){
        if(S[i]=='I') wa++;
        else wa--;
        mx=max(wa,mx);
    }

    cout<<mx<<endl;
}


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

using namespace std;

const int N=305;

typedef long long LL;

int n,m,mo,f[N][N],g[N][N],s[N][N],C[N][N],ans;

int main()
{
	scanf("%d%d%d",&n,&m,&mo); n++;
	C[0][0]=1;
	for (int i=1;i<=n;i++)
	{
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
	f[1][0]=1;
	for (int i=0;i<=m;i++) s[1][i]=(i+1)%mo,g[1][i]=1;
	for (int i=2;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			for (int x=1;x<i;x++) g[i][j]=(g[i][j]+(LL)s[x][j-1]*g[i-x][j]%mo*C[i-2][x-1])%mo;
		}
		for (int j=m;j;j--) f[i][j]=((LL)g[i][j]-g[i][j-1])%mo;
		for (int j=1;j<=m;j++)
		{
			s[i][j]=(s[i][j-1]+g[i][j])%mo;
			//g[i][j]=(g[i][j]+g[i-1][j-1])%mo;
		}
	}
	//for (int i=1;i<=m;i++) ans=(ans+f[n][i])%mo;
	ans=g[n][m];
	if (ans<0) ans+=mo;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1664
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def nCr(n: int, r: int):
    dp = [0] * (n + 1)
    for i in range(n + 1):
        pre = 1
        for j in range(i + 1):
            if j == 0 or j == i:
                dp[j] = 1
            else:
                temp, dp[j] = dp[j], dp[j] + pre
                pre = temp

    return dp[r]


def main():
    N, A, B = map(int, input().split())
    V = list(sorted(list(map(int, input().split())), reverse=True))

    use = V[:A]

    c1 = Counter(V)
    c2 = Counter(use)
    ave = sum(use) / A
    print("{0:.7f}".format(ave))

    if len(set(use)) == 1:
        ans = 0
        num = c1[use[0]]
        for n in range(A, min(B, num) + 1):
            ans += nCr(num, n)
        print(ans)

    else:
        num_total = c1[V[A]]
        num_use = c2[V[A]]
        print(nCr(num_total, num_use))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3956
S = input()
from collections import Counter
c = Counter(S)

if len(set(S)) == 2:
    a =  c.most_common(2)[0][1]
    b = c.most_common(2)[1][1]
    if a  == b:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

signed main(void)
{
	int n, ans, tmp;
	cin >> n;
	long long p[n], q[n];
	rep(i, n) 
	{
		cin >> p[i];
		p[i]--;
		q[p[i]] = i;
	}
	ans = 0;
	tmp = 1;
	rep(i, n - 1)
	{
		if (q[i] > q[i + 1]) 
		{
			ans = max(ans, tmp);
			tmp = 1;
		}
		else
			tmp++;
	}
	ans = max(tmp, ans);
	cout << n - ans << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
using namespace std;
typedef long long ll;
ll divisor(ll a,ll b){
  if(a % b == 0)return b;
  else return divisor(b,a % b);
}
int main(){
  ll k = 0;
  cin >> k;
  ll res = 0;
  for(int i = 1;i <= k;i++){
    for(int j = 1;j <= k;j++){
      for(int l = 1;l <= k;l++){
        ll a = 0;
        ll b = 0;
        ll c = 0;
        a = max({i,j,l});
        c = min({i,j,l});
        b = i + j + l - a - b;
        res += divisor(divisor(c,b),a);
      }
    }
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 3580
import java.util.*

fun main(args: Array<String>) = abc160e()

fun abc160e() {
    val (x, y, a, b, c) = readLine()!!.split(' ').map { it.toInt() }
    val pList = readLine()!!.split(' ').map { it.toLong() }
    val qList = readLine()!!.split(' ').map { it.toLong() }
    val rList = readLine()!!.split(' ').map { it.toLong() }

    val redQueue = PriorityQueue<Long>(a)
    redQueue.addAll(pList.sortedDescending().take(x))
    val greenQueue = PriorityQueue<Long>(b)
    greenQueue.addAll(qList.sortedDescending().take(y))

    for (r in rList.sortedDescending()) {
        val redMin = redQueue.peek()
        val greenMin = greenQueue.peek()
        if (redMin < greenMin) {
            redQueue.poll()
            redQueue.add(Math.max(r, redMin))
        } else {
            greenQueue.poll()
            greenQueue.add(Math.max(r, greenMin))
        }
    }

    val answer = redQueue.sum() + greenQueue.sum()

    println(answer)
}


Measured memory_bytes: 102028
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;

#define MAX_N 50

// int N = 4;
// vector<int> L = {3, 4, 2, 1};

int N;
vector<int> L;

int ans = 0;

int main() {
    cin >> N;
    rep(i, N) {
        // cout << i;
        int tmp;
        cin >> tmp;
        L.push_back(tmp);
    }
    sort(L.begin(), L.end());
    rep(i, N - 1) {
        for (int j = i + 1; j < N - 1; j++) {
            // printf("%d %d\n", i + 1, j + 1);
            for (int k = j + 1; k < N; k++) {
                if (L[i] + L[j] > L[k]) ans++;
                // printf("%d %d - %d\n", i + 1, j + 1, k + 1);
            }
        }
    }

    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
// end of Template

ll s[4][200000],n,val[4][200000];
ll ans;
void process(int x, int y){
    int idx1 = n;
    int idx2 = n;
    while(idx1 > 0 && idx2 > 0){
        if(s[x][idx1] < s[y][idx2]){
            val[x][idx1] += val[y][idx2] ;
            idx2 --;
        }
        else{
            idx1 --;
            val[x][idx1] = val[x][idx1+1];
        }
    }
    while(idx1 > 0){
        idx1 --;
        val[x][idx1] = val[x][idx1+1];
    }
}
int main(){

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n;j++){
            cin>>s[i][j];
        }
        sort(s[i]+1,s[i]+1+n);
    }
    for(int i=1;i<=n;i++)val[3][i]=1;
    process(2,3);
    process(1,2);
    for(int i=1;i<=n;i++)ans+=val[1][i];
    cout<<ans<<newl;

}


Measured memory_bytes: 11008
using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class ABC178D
    {
        // https://atcoder.jp/contests/abc178/tasks/abc178_d

        const long m = 1000000007;
        static long[] a = new long[2001];

        static void Main(string[] args)
        {
            int S = Int32.Parse(Console.ReadLine());

            if (S < 3)
            {
                Console.WriteLine(0);
            }
            else
            {
                Console.WriteLine(sub(S));
            }
        }

        static long sub(int N)
        {
            if (a[N] > 0)
            {
                return a[N];
            }

            long result = 1;

            if (N >= 6)
            {
                for (int i = 3; i < N - 2; i++)
                {
                    result += sub(N - i);
                    result %= m;
                }
            }

            a[N] = result;
            return result;
        }
    }
}


Measured memory_bytes: 27508
#include <iostream>
#include <map>
using namespace std;
int main()
{
    int N, K, i,i1,count=0;
    map<int,int> got;
    cin >> N >> K;
    for (int j=1; j<=K; j++)
    {
        cin >> i;
        for(int z=1;z<=i;z++)
        {
            cin >> i1;
            got[i1]=1000;
        }   
    }
    for(int i=1; i<=N; i++)
    {
        if (got.count(i)==0)
        {
            count ++;
        }
    }
    cout << count ;
    return 0;
}

Measured memory_bytes: 3596
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
      String p=sc.nextLine();
      char[] po=p.toCharArray();
      
      System.out.println(((int)po[0]==(int)po[2])?"=":((int)po[0]<(int)po[2])?"<":">");
      
    }
}


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

const int MAX = 100000;
int main() {
	int N, A[MAX];
	cin >> N;
	for (int i = 0;i < N;++ i) cin >> A[i];
	sort(A, A+N);
	
	int64_t ans1 = A[N >> 1] - A[0], ans2 = A[N - 1] - A[N >> 1];
	for (int i = 1;i < N - 1;++ i) {
		ans1 += abs(A[i >> 1] - A[N - (i + 1 >> 1)]);
		ans2 += abs(A[i - 1 >> 1] - A[N - (i + 2 >> 1)]);
	}
	cout << max(ans1, ans2);
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

*/

Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int a[maxn];
int main(){
  int n;scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",a+i);
  int Min=0x3f3f3f3f,Max=-1000000;
  for(int i=1;i<=n;++i)Min=min(Min,a[i]),Max=max(Max,a[i]);
  if(Min==Max){
    if(Min==n-1){
      printf("Yes\n");
    }else{
      if(1<=Max&&Max<=n/2){
	printf("Yes\n");
      }else{
	printf("No\n");
      }
    }
  }else if(Min+1==Max){
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;++i){
      if(a[i]==Min)cnt1++;
      else cnt2++;
    }
    if(cnt1-1+1<=Min&&Min<=cnt1-1+cnt2/2)printf("Yes\n");
    else printf("No\n");
  }else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 512
n=int(input())
S=[list(input()) for _ in range(n)]

chars=[chr(ord('a')+i) for i in range(26)]
ans=[]
for c in chars:
  min_=float('inf')
  for i in range(n):
    min_ = min(min_,S[i].count(c))
  for _ in range(min_):
    ans.append(c)
print(*ans,sep='')

Measured memory_bytes: 3064
while 1:
    N = int(input())
    if N == 0:
        break
    a = b = c = 0
    a0 = b0 = c0 = 0
    for i in range(N):
        s0, s1 = input().split()
        h, m = map(int, s0.split(":"))
        tm = 100*h + m
        m1 = int(s1)
        if m1 < m:
            m1 += 60
        if 1100 <= tm < 1500:
            if m1 - m <= 8:
                a += 1
            a0 += 1
        elif 1800 <= tm < 2100:
            if m1 - m <= 8:
                b += 1
            b0 += 1
        elif 2100 <= tm or tm < 200:
            if m1 - m <= 8:
                c += 1
            c0 += 1
    print("lunch", 100*a//a0 if a0 else "no guest")
    print("dinner", 100*b//b0 if b0 else "no guest")
    print("midnight", 100*c//c0 if c0 else "no guest")



Measured memory_bytes: 5596
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 100010
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;

struct edge {
	int to;
	ll cost;
};

vector<edge> G[INF];
ll dis[INF];

void dfs(int v, int p, ll d) {
	dis[v] = d;
	for (auto &it : G[v]) {
		if (it.to == p)continue;//一度訪れた頂点に戻ってしまうのを防ぐために親の情報が必要
		dfs(it.to, v, d + it.cost);
	}
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		G[a].push_back({ b,c });
		G[b].push_back({ a,c });
	}
	
	int q, k;
	cin >> q >> k;
	k--;

	dfs(k, -1, 0);

	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		cout << dis[x] + dis[y] << endl;
	}


	return 0;
}

Measured memory_bytes: 14336
from collections import defaultdict 
import sys,heapq,bisect,math,itertools,string

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N = int(input())
K = int(input())

ans = 1

for i in range(N):
	if ans > K:
		ans += K
	else:
		ans *= 2
		
print(ans)

Measured memory_bytes: 3896
def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        else:
            tree[x] = get_root(tree[x])
            return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    edges.sort()
    total = 0
    cnt = 0
    for w, s, t in edges:
        if unite(s, t):
            cnt += 1
            total += w
            if cnt == n - 1:
                break

    return total

while True:
    n = int(input())
    if not n:
        break
    m = int(input())
    inf = float("inf")

    edges = []
    for _ in [None]*m:
        s, t, d = map(int, input().split(","))
        edges.append((d//100-1, s, t))

    print(kruskal(n, edges))


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

int main(void)
{
    long long int a, b, c, d;

    cin >> a >> b >> c >> d;
    
    long long int ans = -1e18;

    ans = max(ans, a*c);
    ans = max(ans, b*c);
    ans = max(ans, a*d);
    ans = max(ans, b*d);

    if((a < 0 && b > 0) && (c < 0 && b >0)) ans = max((long long int) 0, ans);

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3636
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>

using namespace std;

/**
 * main
 */
int main () {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;

  // begin from the state that X and Y are satisfied with A and B pizza.
  int min_price = A * X + B * Y;

  // replace A and B with AB pizza and re-calculate the price.
  for (int i = max(X, Y); i >= 0; i--) {
    int price = A * max(0, X - i) + B * max(0, Y - i) + C * 2 * i;

    if (min_price > price) {
      min_price = price;
    }
  }

  cout << min_price << '\n';
}


Measured memory_bytes: 256
#pragma region head
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
#define double long double
typedef double ld;
const int INF = 1001001001001001001ll;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;
const double PI = acos(-1.0);

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

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

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
#pragma endregion

signed main() {
  int N;
  cin >> N;
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  B -= A;

  double E = (D - C) / 2.0;
  double CD = C + D;
  double BB = B + (CD / 2.0) * (N - 1) + EPS;

  int num = BB / CD;
  chmin(num, N - 2);
  double NN1 = CD * num, NN2 = NN1 + CD;


  bool ok = min(abs(BB - NN1), abs(BB - NN2)) < E * (N - 1) + EPS;
  if (ok)
    cout << "YES\n";
  else
    cout << "NO\n";
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	std::string S;
	in >> S;

	LL cnt = 0, ans = 0;
	rep(i, S.length())
	{
		if (S[i] == 'B') ++cnt;
		else ans += cnt;
	}

	out << ans << std::endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    int ans=A[0];
    rep(i,N-1){
        ans = __gcd(ans,A[i+1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
//
//  main.cpp
//  CoderTest
//
//  Created by yuya on 2019/05/20.
//  Copyright © 2019 yuya. All rights reserved.
//

#include<bits/stdc++.h>
#define ll long long
using namespace std;




int main(){
    
    int H,W;
    cin >> H >> W;
    vector<vector<char>> a(H);
    vector<int> rowchk(H), columnchk(W); // 黒があるなら1
    
    for(int i=0;i<H;i++){
        a[i].assign(W, 0);
        for(int j=0;j<W;j++){
            cin >> a[i][j];
            if(a[i][j]=='#') {
                rowchk[i]=1;
                columnchk[j]=1;
            }
        }
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(rowchk[i]==1 && columnchk[j]==1) {
                cout << a[i][j];
            }
        }
        if(rowchk[i]==1) cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll oo = 1e9 + 10;
const ll mod = 998244353,maxn = 110;
const double PI = acos(-1); 

int solve(vector<pll> &vs, int n, ll d){
    int ans = 0;
    for (int i=0; i<n; i++){
        ans += (d*d >= vs[i].ff*vs[i].ff + vs[i].ss*vs[i].ss);
    }
    return ans;
}

int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, d;
    cin >> n >> d;

    vector<pll> vs(n);

    for (int i=0; i<n; i++){
        cin >> vs[i].ff >> vs[i].ss;
    }

    auto ans = solve(vs, n, d);

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

Measured memory_bytes: 6340
from collections import Counter

S = input()
MOD = 2019
mods = [0]
r = 0
for i, c in enumerate(S[::-1]):
    r += int(c) * pow(10, i, MOD)
    mods.append(r % MOD)

counter = Counter(mods)
# print("counter: {}".format(counter))

ans = 0
for v in counter.values():
    ans += v * (v-1) // 2

print(ans)


Measured memory_bytes: 16784
#include<iostream>
#include<queue>
#include<vector>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define arep(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];
    priority_queue<ll> PQ;
    rep(i, 0, N) {
        PQ.push(A[i]);
    }
    rep(i, 0, M) {
        ll now = PQ.top();
        PQ.pop();
        if (now == 0) break;
        now /= 2;
        PQ.push(now);
    }
    ll ans = 0;
    while (!PQ.empty()) {
        ll now = PQ.top();
        PQ.pop();
        ans += now;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2168
#include<bits/stdc++.h>
#define N 55
#define ll long long
using namespace std;
inline void in(int &x) 
{
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
int n,m,fa[N],q[N],bk,state[N];
bool edge[N][N];
ll dp[N];
inline bool need_add(int i)
{
	int cnt=0;
	while(i)i-=i&-i,++cnt;
	return !(cnt&1);
}
int main()
{
	in(n);
	for(int i=1;i<n;++i)
	{
		int x,y;
		in(x);in(y);
		edge[x][y]=edge[y][x]=1;
	}
	q[bk++]=1;
	for(int i=0;i<n;++i)
	{
		int from=q[i];
		for(int to=1;to<=n;++to)
		if(edge[from][to]&&to!=fa[from])
		{
			fa[to]=from;
			q[bk++]=to;
		}
	}
	in(m);
	for(int i=0;i<m;++i)
	{
		int x,y;
		in(x);in(y);
		state[x]^=1<<i;
		state[y]^=1<<i;
	}
	for(int i=n-1;i>=0;--i)
	{
		int from=q[i];
		for(int to=1;to<=n;++to)
		if(edge[from][to]&&to!=fa[from])
		state[from]^=state[to];
	}
	ll ans=0;
	for(int mask=0;mask<(1<<m);++mask)
	{
		for(int i=n-1;i>=0;--i)
		{
			int from=q[i];
			dp[from]=1;
			for(int to=1;to<=n;++to)
			if(edge[from][to]&&fa[from]!=to)
			{
				if(mask&state[to])dp[from]*=dp[to];
				else dp[from]*=dp[to]<<1;
			}
		}
		if(need_add(mask))ans+=dp[1];
		else ans-=dp[1];
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3720
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#define _GLIBCXX_DEBUG
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <iomanip>
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
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; }
const int INF = 1001001000;
const int MOD = 1000000007;

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

using Graph = vector<vector<int>>;
//再帰とかグラフを使うときは予めNの最大値のグローバル配列を取っておく


//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}
long long nCr(long long n, long long r) {
    long long A = 1, B = 1;
    //Aが分子Bが1/r!
    for (long long i = n - r + 1; i <= n; i++) {
        A = A * i % MOD;
    }
    for (long long i = 1; i <= r; i++) {
        B = B * i % MOD;
    }
    B = mod_pow(B, MOD - 2);
    B %= MOD;
    //Bは割るのではなく掛ける
    return (A * B) % MOD;
}

bool E[2005][2005];
vector<bool> seen;
typedef pair<int, int> P;
typedef tuple<int, int, int> Tu;
//typedef pair<string, int> P;
int D[2005];
//頂点状態を表すcolor[]において、0は未訪問、1は訪問中、2は完了を表す。
int color[101];
int find_time = 0;

int main() {
    int A, B, C; cin >> A >> B >> C;
    cout << C << " "<< A << " " << B << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, char** argv)
{
	int i, num, list[100];
	scanf("%d", &num);

	for (i = 0; i < num; i++) {
		scanf("%d", &list[i]);
	}

	for (i = num - 1; i >= 0; i--) {
		if (i == 0) {
			printf("%d\n", list[i]);
		}
		else {
			printf("%d ", list[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 596
import std.stdio;
import std.conv, std.array, std.algorithm, std.string;
import std.math, std.random, std.range, std.datetime;
import std.bigint;

void main(){
	long n, l;
	{
		long[] tmp = readln.chomp.split.map!(to!long).array;
		n = tmp[0], l = tmp[1];
		}
	
	long[] as = readln.chomp.split.map!(to!long).array;
	
	string ans;
	int[] ans2;
	
	long center = -1;
	for(int i = 0; i < as.length - 1; i ++){
		if(as[i] + as[i + 1] >= l){
			center = i;
			break;
			}
		}
	
	if(center == -1) ans = "Impossible";
	else{
		ans = "Possible";
		for(int i = 0; i < center; i ++){
			ans2 ~= i + 1;
			}
		for(int i = cast(int) (as.length - 2); i >= center; i --){
			ans2 ~= i + 1;
			}
		}
	
	ans.writeln;
	foreach(i; ans2) i.writeln;
	
	
	}

Measured memory_bytes: 4808
#include<bits/stdc++.h>
using namespace std;
int n,a,x,y;
main(){
  cin>>n;
  for(int i=0;i<n;++i){
    cin>>a;
    if(a%4==0)x++;
    else if(a%2==0)y++;
  }
  cout<<(x+y/2+1>n/2?"Yes\n":"No\n")<<endl;
}


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

#define ll long long int
#define loop(i,s,e) for(ll i=s; i<e; i++)
#define endl '\n'
#define vll vector<ll>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define N 100001
#define pb push_back
#define INF LLONG_MAX
#define inf INT_MAX
#define minusinf INT_MIN

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

ll n, w;
ll value[101], weight[101];
ll dp[101][100001];

ll util(ll i, ll val){
	
	if(val <= 0) return 0;
	if(i>=n) return inf;	

	if(dp[i][val] != -1) return dp[i][val];

	ll a = weight[i] + util(i+1, val-value[i]);
	ll b = util(i+1, val);

	return dp[i][val] = min(a, b);
}

void alpha(){

	cin>>n>>w;
	loop(i,0,n) cin>>weight[i]>>value[i];

	memset(dp, -1, sizeof(dp));

	ll ans = minusinf;
	for(ll i=0; i<100001; i++){
		if(util(0, i)<=w) ans = i;
	}

	cout<<ans<<endl;

	return;

}

int main(){

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


    ll t=1;
	//cin>>t;

  	while(t--) alpha();

	return 0;

}

Measured memory_bytes: 79232
from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt1 = 0
for i in range(n - 1):
    for  j in range(i + 1, n):
        if a[i] > a[j]:
            cnt1 += 1

a.sort()
cnt2 = 0
c = 0
i = 0
c_n = a[0]
while True:
    cnt = 0
    while a[i + cnt] == c_n:
        cnt +=1
        if i + cnt == n:
            break
    cnt2 += cnt*c
    c += cnt
    i += cnt
    if i == n:
        break
    c_n = a[i]

ans = cnt1*k + cnt2*k*(k - 1)//2
print(ans%(10**9 + 7))

Measured memory_bytes: 9660
main=do
  [n,m]<-map read.words<$>getLine
  buf<-lines<$>getContents
  let a=take n buf
  let b=drop n buf
  putStrLn$if (length[1|i<-[0..n-m],j<-[0..n-m],f m i j a b])>0 then"Yes"else"No"
f m i j a b=(length[1|k<-[0..m-1],l<-[0..m-1],(a!!(i+k)!!(j+l))==(b!!k!!l)])==m^2


Measured memory_bytes: 1148
#include <bits/stdc++.h>
#define ll long long
#define V vector<long long>
#define VV vector<vector<long long>>
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

int main(){
    ll mod=1e9+7;
    ll h,w;
    cin>>h>>w;
    VV a(h,V(w,0));
    VV dp(h,V(w,0));
    rep(i,h){
        string str;
        cin>>str;
        rep(j,w){
            if(str[j]=='#')a[i][j]=1;
        }
    }
    rep(i,h){
        if(a[i][0]==1)break;
        dp[i][0]=1;
    }
    rep(i,w){
        if(a[0][i]==1)break;
        dp[0][i]=1;
    }
    for(ll i=1;i<h;i++){
        for(ll j=1;j<w;j++){
            if(a[i][j]==0){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                dp[i][j]%=mod;
            }
        }
    }
    cout<<dp[h-1][w-1]<<endl;
}


Measured memory_bytes: 16000
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 20200
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,a[MAX],b[MAX];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=i*(n+1),b[i]=(n-i+1)*(n+1);
	for(int i=1;i<=n;++i)a[read()]-=(n-i+1);
	for(int i=1;i<=n;++i)printf("%d ",a[i]);puts("");
	for(int i=1;i<=n;++i)printf("%d ",b[i]);puts("");
}


Measured memory_bytes: 768