akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

template <class T>
class ConvexHullTrick {
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b){};
        T operator()(T x) const { return a * x + b; }
    };

public:
    vector<Line> lines;
    bool isMonotonicX;

    explicit ConvexHullTrick(bool xflag = false) : isMonotonicX(xflag){};

    // l2が必要か否か
    bool isneeded(Line l1, Line l2, Line l3) const {
        if (l1.a < l3.a) swap(l1, l3);  // 追加クエリが単調増加の場合に対応
        return (l3.b - l2.b) * (l2.a - l1.a) < (l3.a - l2.a) * (l2.b - l1.b);
    }

    // 直線y = ax + bを追加  aは単調であることを要求
    void add(T a, T b) {
        Line line(a, b);
        // 後ろから不要な直線を抜き続ける
        while (lines.size() >= 2 &&
               !isneeded(*(lines.end() - 2), lines.back(), line)) lines.pop_back();
        lines.push_back(line);
    }

    // xにおける最小値を返す
    T operator()(T x) const {
        if (isMonotonicX) {
            static int itr = 0;
            while (itr < lines.size() - 1 && lines[itr](x) > lines[itr + 1](x)) ++itr;
            return lines[itr](x);
        } else {
            // l[ok - 1](x) > l[ok](x)
            int ok = 0, ng = lines.size();
            while (ng - ok > 1) {
                int mid = (ok + ng) / 2;
                if (lines[mid - 1](x) > lines[mid](x)) {
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
            return lines[ok](x);
        }
    }
};

int main() {
    int N;
    ll C;
    cin >> N >> C;
    vector<ll> H(N);
    for (auto& h : H) cin >> h;

    vector<ll> dp(N, 0);
    ConvexHullTrick<ll> cht(false);
    cht.add(-2 * H[0], H[0] * H[0] + dp[0]);

    for (int i = 1; i < N; ++i) {
        dp[i] = cht(H[i]) + H[i] * H[i] + C;
        cht.add(-2 * H[i], H[i] * H[i] + dp[i]);
    }

    cout << dp[N - 1] << endl;
    return 0;
}


Measured memory_bytes: 9456
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ITP1_5_C
{
    class Program
    {
        static void Main(string[] args)
        {
            //縦Hcm、横Wcmの長方形を描く
            //1cm×1cmの正方形を'#'で表す
            //H,Wがともに0の時入力の終了
            //長方形の左上を#とし、その隣を.で表す。

            while (true)                                    //以下の処理をbreak条件が与えられるまで繰り返す
            {
                string[] str = Console.ReadLine().Split(' ');
                int H = int.Parse(str[0]);                  //H 長方形の縦
                int W = int.Parse(str[1]);                  //W 長方形の横

                int i1;                                     //以下のfor文にてHに対応して用いる変数
                int i2;                                     //以下のfor文にてWに対応して用いる変数

                if (H == 0 && W == 0)
                {
                    break;                                  //H,Wが0の時、処理の終了
                }

                else
                {
                    for (i1 = 0; i1 < H; i1++)              //縦に以下の処理を何回繰り返すか？(1行分の処理の記述)
                    {

                        for (i2 = 0; i2 < W; i2++)          //記号を書く処理を横に何回繰り返すか？
                        {
                            if (i1 % 2 == 0)                     //偶数行に対する処理
                            {
                                if (i2 % 2 == 0)                 //偶数番目に記入する記号は#
                                {
                                    Console.Write("#");
                                }
                                else
                                {
                                    Console.Write(".");
                                }
                            }

                            else                                //奇数行に対する処理
                            {
                                if (i2 % 2 == 0)                 //偶数番目に記入する記号は#
                                {
                                    Console.Write(".");
                                }
                                else
                                {
                                    Console.Write("#");
                                }
                            }
                        }
                        Console.WriteLine();                //改行する
                    }
                    Console.WriteLine("");
                }
            }
        }
    }
}




Measured memory_bytes: 17944
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
#define f2(i,j,k) for(int i=j;i>k;i--)
using namespace std;
int main(){
    long long n,m;
    cin>>n>>m;
    long long a[n],b[n],c[m],d[m];
    f(i,0,n){
        cin>>a[i]>>b[i];
    }
    f(i,0,m){
        cin>>c[i]>>d[i];
    }
    f(i,0,n){
        long long ans=400000000,ansi=0;
        f(j,0,m){
            if(ans>abs(a[i]-c[j])+abs(b[i]-d[j])){
                ans=abs(a[i]-c[j])+abs(b[i]-d[j]);
                ansi=j;
            }
        }
        cout<<ansi+1<<endl;
    }
    return 0;
}


Measured memory_bytes: 3568
def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def lcm(a, b):
    lcm = a * b // gcd(a,b)
    return lcm
a,b =map(int,input().split())
print(lcm(a,b))

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

int main(){
  int K, N;
  cin >> K >> N;
  int a[N];

  for(int i=0; i<N; i++){
    int A;
    cin >> A;
    a[i]=A;
  }
  int maxA = 0;
  maxA = a[0]+K-a[N-1];
  for(int i=0; i<N-1; i++){
    if(maxA < a[i+1]-a[i])maxA = a[i+1] - a[i];
  }
  cout << K-maxA << endl;
  return 0;
}

Measured memory_bytes: 1024
N, M = map(int,input().split())
conf = []
divp = []
for i in range(M):
  a, b = map(int, input().split())
  conf.append((b, a))

conf.sort()
divp.append(conf[0][0]-1)
for i in range(1, M):
  if divp[-1] < conf[i][1]:
    divp.append(conf[i][0]-1)
print(len(divp))  

Measured memory_bytes: 53336
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

int main() {
  
  int N, X, T;
  cin >> N >> X >> T;

  cout << (N + X - 1) / X * T << endl;

  return 0;
}

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

#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define FORW(a, b, c) for(int a= b; a>=c; a-=1)
#define fi first
#define se second
#define pb push_back
#define int long long

const int N = 60;
const int Maxn = 5e3 + 100;
const int mod = 2019;
const int oo = 1e18;

struct edge {
    int v, cost, time;
};

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

int n, m, s;
int dp[N][Maxn], ans[N];
int buy[N], buy_time[N];
vector<edge> vi[N];

void solve()    {
    FOR(i, 1, n) {
        ans[i] = oo;
        FOR(j, 0, Maxn - 1) dp[i][j] = oo;
    }

    priority_queue<iii, vector<iii>, greater<iii> > pq;
    dp[1][min(s, Maxn - 1)] = 0;
    pq.push( { 0, {1, min(s, Maxn - 1)} } );
    while(!pq.empty()) {

        int du = pq.top().fi, u = pq.top().se.fi, remain = pq.top().se.se;
        pq.pop();

        ans[u] = min(ans[u], du);

        if(dp[u][remain] != du) continue;

        for(auto v: vi[u]) if(v.cost <= remain) {
            int time = du + v.time, coin = remain - v.cost;
            if(dp[v.v][coin] > time) {
                dp[v.v][coin] = time;
                pq.push({ time, {v.v, coin} });
            }
        }
        FOR(i, 1, 1) {
            int time = du + i * buy_time[u], coin = min(Maxn - 1, remain + buy[u] * i);

            if(dp[u][coin] > time) {
                dp[u][coin] = time;
                pq.push({ time, {u, coin} });
            }
            if(coin == Maxn - 1) break;
        }
    }
    FOR(i, 2, n) cout << ans[i] << '\n';
}

signed main() {
//    freopen("test.inp", "r", stdin);
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    cin >> n >> m >> s;
    FOR(i, 1, m) {
        int u, v, cost, time; cin >> u >> v >> cost >> time;
        vi[u].pb({v, cost, time});
        vi[v].pb({u, cost, time});
    }
    FOR(i, 1, n) cin >> buy[i] >> buy_time[i];
    solve();
}


Measured memory_bytes: 11400
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll,ll> pll;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define MOD 1000000007
#define ARRAY_MAX 105

const int INF = 1e9+7;


int main(){

    int n,m;
    cin >> n >> m;
    vector<int> p(ARRAY_MAX,0);

    for(int i = 0;i < m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        p[a] = max(p[a],b);
    }
    
    int ma = 0,r = 0,ans = 0;
    for(int i = 0;i <= r;i++){

        ma = max(ma,p[i]);//現状でどこまで進めるか
        if(i == r){
            r = max(r,ma);//１人増やして右に1つ伸ばす
            ans++;
            if(ma == n){
                break;
            }
        }
    }
    if(r == n){
        cout << ans << endl;
    }else{
        cout << "Impossible" << endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct edge {
	int to, cost, tp;
};
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
int N, M, a, b, c;
int main() {
	while (cin >> N >> M, N) {
		vector<vector<edge> > G(N);
		for (int i = 0; i < M; i++) {
			cin >> a >> b >> c; a--, b--;
			G[a].push_back(edge{ b, c, 0 });
			G[b].push_back(edge{ a, c, 0 });
		}
		vector<vector<edge> > gt = G;
		for (int i = 0; i < N; i++) {
			vector<vector<bool> > dp(3, vector<bool>(N, false)); dp[0][i] = true;
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < N; k++) {
					if (!dp[j][k]) continue;
					for (edge e : gt[k]) dp[j + 1][e.to] = true;
				}
			}
			for (int j = 0; j < N; j++) {
				if (dp[2][j]) G[i].push_back(edge{ j, 0, 1 });
			}
		}
		priority_queue<edge> que; que.push(edge{ 0, 0, 0 });
		vector<vector<int> > dist(N, vector<int>(2, 999999999)); dist[0][0] = 0;
		while (!que.empty()) {
			edge u = que.top(); que.pop();
			for (edge e : G[u.to]) {
				int cost = dist[u.to][u.tp] + e.cost;
				int ntp = u.tp + e.tp;
				if (ntp == 2) continue;
				if (dist[e.to][ntp] > cost) {
					dist[e.to][ntp] = cost;
					que.push(edge{ e.to, -cost, ntp });
				}
			}
		}
		cout << min(dist[N - 1][0], dist[N - 1][1]) << endl;
	}
	return 0;
}

Measured memory_bytes: 3112
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdio> 

#define nl '\n'

using namespace std;

float n, m, a, t, x;

int main(){

    cin >> n >> m;

    vector<float> v;

    for(int i = 0; i < n; i++) {
        cin >> a;
        v.push_back(a);
        t += a;
    }

    for(int i = 0; i < v.size(); i++) {
        if((v[i] >= (1/(4*m))*t)) {
            x++;
        }
    }

    if(x >= m) {
        cout << "Yes";
        return 0;
    }
    cout << "No";






}
 
//g++ -std=c++14 comp.cpp -o c && c.exe
//g++ -std=c++14 comp.cpp -o c; ./c.exe
//g++ -std=c++14 comp.cpp && ./a.out


//Surely this is going to AC

Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        d: i64,
        mut xy: [(i64, i64); n]
    }

    let mut ans = 0;

    for &(x, y) in xy.iter() {
        if x*x + y*y <= d*d {
            ans += 1;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 7816
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll a, b, k;
    cin >> a >> b >> k;
    for(int i = 0; i < k; i++){
        if(i % 2){
            b /= 2;
            a += b;
        }
        else{
            a /= 2;
            b += a;
        }
    }
    cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <string>
#include <bitset>
#include <stack>
#include <queue>
#include <tuple>
#include <regex>
#include <cmath>
#include <map>
#include <set>
#include <functional>
#include <cstring>

using namespace std;

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

using ll = long long;
using Pint = pair<int, int>;
using Pll  = pair<ll, ll>;

#define eb emplace_back
#define pb push_back
#define mp make_pair

#define F first
#define S second

#define popcnt __builtin_popcountll

#define rep( i, n ) for ( ll i = 0; i < (ll)( n ); ++i )
#define reps( i, n ) for ( ll i = 1; i <= (ll)( n ); ++i )
#define rrep( i, n ) for ( ll i = (ll)( ( n ) - 1 ); i >= 0; --i )
#define rreps( i, n ) for ( ll i = (ll)( ( n ) ); i > 0; --i )
#define arep( i, v ) for ( auto &&i : ( v ) )

#define ALL( c ) ( c ).begin(), ( c ).end()
#define RALL( c ) ( c ).rbegin(), ( c ).rend()
#define UNIQUE( c ) ( c ).erase( unique( ( c ).begin(), ( c ).end() ), ( c ).end() )

template<typename T = ll> constexpr T MAX = numeric_limits<T>::max();
template<typename T> T gcd( const T a, const T b ) { return ( b ? gcd( b, a % b ) : a ); }
template<typename T> T lcm( const T a, const T b ) { return ( a / gcd( a, b ) * b ); }


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

	ll tmp = 0;
	rep( i, n.size() )
	{
		tmp += n[i] - '0';
	}

	if ( tmp % 9 )
		cout << "No" << endl;
	else
		cout << "Yes" << endl;

	return ( 0 );
}


Measured memory_bytes: 3376
import java.util.*;



public class Main {

	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int bit = 0;
		for (int i=0; i<N; i++) {
			bit |= sc.nextInt();
		}
		System.out.println(Integer.numberOfTrailingZeros(bit));
		
		sc.close();
	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,A,B;cin>>N>>A>>B;
  int ans = 0;
  repeat(i,N){
    int x=i+1;
    int f=0;
    while(x>0){
      f += x%10;
      x/=10;
    }
    if(A<=f&&f<=B)ans+=i+1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		
		char[][] s = new char[H + 2][W + 2];
		String[] x = new String[H + 1];
		
		for(int i = 1; i < H + 1; i++) {
			x[i] = sc.next();
		}
		
		for(int i = 1; i < H + 1; i++) {
			for(int j = 1; j < W + 1; j++) {
				s[i][j] = x[i].charAt(j - 1);		
			}
		}
		
		int check = 0;
		
		loop:
		for(int i = 1; i < H + 1; i++) {
			for(int j = 1; j < W + 1; j++) {
				if(s[i][j] == '#') {
					if(s[i - 1][j] != '#' && s[i][j - 1] != '#' && s[i + 1][j] != '#' && s[i][j + 1] != '#') {
						check++;
						break loop;
					}
				}
			}
		}
		if(check > 0) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
		}
	}
}


Measured memory_bytes: 22868
from itertools import combinations_with_replacement

N,M,Q = [int(i) for i in input().split(" ")]
A = []
for i in range(Q):
    a = [int(i) for i in input().split(" ")]
    A.append(a)

ans = 0

for i in combinations_with_replacement(range(1,M+1),N):
    tmp_ans = 0
    for j in A:
        if i[j[1] - 1] - i[j[0] - 1] != j[2]:
            continue
        tmp_ans += j[3]

    if ans < tmp_ans:
        ans = tmp_ans

print(ans)

Measured memory_bytes: 9112
#include<stdio.h>
#pragma GCC optimize("O3")
static inline char CH()
{
  static char buf[100000],*ptr1=buf,*ptr2=buf;
  return ptr1==ptr2&&(ptr2=(ptr1=buf)+fread(buf,1,100000,stdin),ptr1==ptr2)?EOF:*ptr1++;
}
static inline int IN(void)
{
  int x=0,f=0,c=CH();while(c<48||c>57){f^=c==45,c=CH();}
  while(c>47&&c<58){x=x*10+c-48,c=CH();}return f?-x:x;
}


int main(){
    int n=IN(),i=0,u,v;
    long x = n;
    long a = x*(x+1)*(x+2)/6;
    while(i++ < n-1){
        u=IN();
        v=IN();
        if(u<v){
            a -= 1l * u * (n-v+1);
        }else{
            a -= 1l * v * (n-u+1);
        }
    }
    return printf("%ld", a), 0;
}


Measured memory_bytes: 1668
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <array>
#include <cmath>

using namespace std;

using ll = long long int;

// GCDを計算します
template <typename NumType>
NumType calcGCD(NumType a, NumType b) {
    if (a < b) {
        NumType tmp = a;
        a = b;
        b = tmp; 
    }

    NumType r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

// 約数を数えます
template <typename NumType>
NumType cntDivisor(const NumType & num) {
    NumType cnt = 0;
    for(NumType i = 1; i * i <= num; ++i) {
        if(num % i == 0) {
            cnt++;
            if(i * i != num) cnt++;
        }
    }

    return cnt;
}

// [beg, end)の範囲を，添え字indexでループするfor文に置換します
#define FOR_RANGE(index, beg, end)     for (ll index = beg; index < N; ++index)

#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

template<class T>
T Min(T a, T b) {
    return (a < b) ? a : b;
}

template<class T>
T Max(T a, T b) {
    return (a > b) ? a : b;
}

int main() {
    int N;
    
    constexpr int MAX = (ll)1e5;
    array<ll, MAX+1> A;
    array<ll, MAX> B;

    cin >> N;

    ll totalEnemies = 0;
    for (int i = 0; i < N+1; i++) { 
        cin >> A[i];
        totalEnemies += A[i];
    }
    for (int i = 0; i < N; i++) cin >> B[i];


    for (int i = 0; i < N; i++) {
        int kill = Min(A[i], B[i]);
        A[i] -= kill;
        A[i+1] -= Min(A[i+1], B[i] - kill);
    }

    ll remainedEnemies = 0;
    for (int i = 0; i < N + 1; i++ ) {
        remainedEnemies += A[i];
    }

    cout << totalEnemies - remainedEnemies;

    return 0;
}



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

using namespace std;

int nenn(int sum,int a)
{
	if(sum==a){
		return 1;
	}
	int res=0;
	if(sum+1<=a){
		res=res+nenn(sum+1,a);
	}
	if(sum+2<=a){
		res=res+nenn(sum+2,a);
	}
	if(sum+3<=a){
		res=res+nenn(sum+3,a);
	}
	return res;
}
int main(void)
{
	while(true){
		int x;
		int y,z;
		cin>>x;
		if(x==0){
			break;
		}
		if(nenn(0,x)%10==0){
			y=nenn(0,x)/10;
		}else{
			y=nenn(0,x)/10+1;
		}
		if(y%365==0){
			z=y/365;
		}else{
			z=y/365+1;
		}
		cout<<z<<endl;
	}
	return 0;
}


Measured memory_bytes: 2976
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 998244353;
int modpow(int a, int n){
    if(n < 1) return 1;
    return modpow(a * a % MOD, n / 2) * ((n % 2) ? a : 1) % MOD;
}
int modinv(int a){
    return modpow(a, MOD - 2);
}
int modfact(int a){
    if(a < 2) return 1;
    return a * modfact(a - 1) % MOD;
}
signed main() {
    INCANT;
    int n, fac, inv[11111111], res, tmp = 0, cnt = 1;
    cin>>n;
    res = modpow(3, n);
    fac = modfact(n);
    inv[n] = modinv(fac);
    rev(i, n){
        inv[i] = inv[i + 1] * (i + 1);
        inv[i] %= MOD;
    }
    rep(i, n / 2){
        tmp += inv[i] * inv[n - i] % MOD * cnt % MOD;
        tmp %= MOD;
        cnt *= 2;
        cnt %= MOD;
    }
    tmp = tmp * 2 * fac % MOD;
    cout<<(res - tmp + MOD) % MOD<<endl;
}


Measured memory_bytes: 236544
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

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

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 51;
int64 cnt[N], len[N];

int64 solve(int n, int64 m) {
  if (m == 0) return 0;
  if (n == 0) return 1;
  // trace(n, m);
  if (m <= 1 + len[n - 1]) {
    return solve(n - 1, m - 1);
  } else {
    return solve(n - 1, m - len[n - 1] - 2) + cnt[n - 1] + 1;
  }
}

int main() {
  len[0] = cnt[0] = 1;
  for (int i = 1; i < N; ++i) {
    cnt[i] = cnt[i - 1] * 2 + 1;
    len[i] = len[i - 1] * 2 + 3;
  }
  int64 n, m;
  cin >> n >> m;
  int64 ret = solve(n, m);
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define rrep1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n, k, a[100010];

template<typename T>
T gcd(T x, T y) {
    if (y==0) return x;
    return gcd(y, x % y);
}

template<typename T>
T lcm(T x, T y) {
    T g = gcd(x, y);
    return x / g * y;
}

int main() {
    cin >> n >> k;
    rep(i, n) cin >> a[i];

    int g = a[0];
    rep(i, n) {
        if (i == 0) continue;
        g = gcd(g, a[i]);
    }

    int m = -1;
    rep(i, n) chmax(m, a[i]);
    if (k % g == 0 && k <= m) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//--<for debugging>
#define whatis(x) cout << #x << " is " << x<<" ";
#define whatisl(x) cout << #x << " is " << x<<"\n";
#define parr(array,end)for(ll loop=0;loop<end;loop++)cout<<array[loop]<<" ";cout<<"\n";
#define lline cout<<"\n";
#define errorl(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"\n";}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"___";}
    
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a <<" , ";
    err(++it, args...);
}
//--</for debugging> 
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define testcase ll tt; cin >> tt; while(tt--)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define vars ll h,i,j,k,d,l,p,q,r,x,y,a,b,c,v,var,n,m,z,s,ans,ind1,ind2,flag,limit1,limit2,limit3,mod;
#define vll vector<ll>
#define pll pair<ll,ll>
#define sll set<ll>
#define pint pair<int,int>
const ll INF=1e9+7;
const ll MOD=1e9+7;
int main()
{
    boost vars
    double pi=acos(-1),cans,aa,bb,xx,yy,theta;
    cin>>aa>>bb>>xx>>yy;
    theta=(pi/6)*(xx-(11*yy)/60);
    cans=aa*aa+bb*bb-2*aa*bb*cos(theta);
    cans=sqrt(cans);
    cout << fixed << setprecision(12) << cans; 
}

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

int search(char x,int y,string &S) {
  int n=-1;
  for (int i=y;i<S.size();i++) {
    if (S.at(i)==x) {
      n = i;
      break;
    }
  }
  return n;
}

int main() {
  int N;
  string S;
  cin >> N >> S;
  int count=0;
  for (char x='0';x<='9';x++) {
    int I=search(x,0,S);
    if (I!=-1) {
      for (char a='0';a<='9';a++) {
        int J=search(a,I+1,S);
        if (J!=-1) {
          for (char b='0';b<='9';b++) {
            int K=search(b,J+1,S);
            if (K!=-1) count++;
          }
        }
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            #未満:Trueの場合
            dp[("T",i,k)]+=dp[("T",i-1,k)]      #k桁目の数字pが0の場合
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9  #k桁目の数字pが0以外の場合。1-9までの9個の数を使用して良い
            #未満:Falseの場合
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) #k桁目の数字pが0<p<xなのは、x-1通り。この場合は未満の方に移動
                dp[("T",i,k)]+=dp[("F",i-1,k)]  #k桁目の数字pが0の場合は1通り。この場合は未満の方に移動
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 #k桁目の数字p=xの場合はゼロでない数字が1個増える
            else: #k桁の目の数字xが0の場合
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]


Measured memory_bytes: 32236
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long,long>> vpll;
typedef vector<pair<int,int>> vpii;
int main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall

	ll  a,b,c;
	in(a);
	in(b);
	in(c);
	c -= a + b;
	if(c>0 and 4*a*b<c*c)out("Yes");
	else{
		out("No");
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint a[6];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	for(int i = 1; i <= 5; i++) cin >> a[i];
	for(int i = 1; i <= 5; i++){
		if(a[i] == 0){
			cout << i << endl;
			return 0;
		}
	}
	
	return 0;
}

Measured memory_bytes: 3652
using System;
using System.Linq;


namespace AOJ0006
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var str = Console.ReadLine();
                if(str == null||str=="") return;
                
                var s = str.ToCharArray().Reverse();
                foreach (var st in s)
                {
                    Console.Write(st);
                }

                Console.WriteLine();

            }
        }
    }
}

Measured memory_bytes: 5520
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);i <= (e);(i)++)

string sa[3];
queue<int> card[3]; 

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


  for(int i = 0;i < 3;i++){
    for(int j = 0;j < sa[i].length();j++){
      card[i].push((int)sa[i][j] - 'a');
    }
  }

  int turn = 0;

  while(1){
    if(card[turn].empty()){
      cout << (char)(turn  + 'A') << endl;
      break;
    }
    else{
      int temp = turn;
      turn = card[turn].front();
      card[temp].pop();
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
//Thank you. //From : 16:34~17:34 + 19:21~19:31
int main(){
int n;
cin >> n;

vector <vector<int>> l(n+1,vector<int>(3));
//.at(i)番目の目的地 t=0 (x,y)=(1,2); t[i][0],t[i][1],t[1][2]
//.at(0)はスタート地点 (0,0)

l.at(0).at(0)=0;
l.at(0).at(1)=0;
l.at(0).at(2)=0; 

rep(i,n)
{int t,x,y;
  cin >> t >> x >> y;
  //at(0)をスタート地点にするため、1から目的地配列をはじめたくて、i+1
  l[i+1][0]=t;
  l[i+1][1]=x;
  l[i+1][2]=y;
}

string ans="Yes";

//なんでn+1回じゃなくてn回かというと、移動回数がnだから。（ゴール地点からは次の目的地探索しない）
int ft;
rep(i,n)
{int ot=l[i][0]; int nt=l[i+1][0];//nt=到着する時間;
 int ox=l[i][1]; int nx=l[i+1][1];//old x ,new x
 int oy=l[i][2]; int ny=l[i+1][2];//old y, new y
 
 int t=nt-ot;//所要時間(nt-ot)
 ft=abs(ox-nx)+abs(oy-ny);  //ft=fastest time; 最速時間に2の倍数を足してできる時間には到達できると考えた
 
 /*
 cout<<"i = "<<i<<endl;
 cout<<"ox = "<<ox<<" nx = "<<nx<<endl;
 cout<<"oy = "<<oy<<" ny = "<<ny<<endl;
 cout<<"ot = "<<ot<<" nt = "<<nt<<endl;
 cout<<"ft = "<<ft<<" t  = "<<t<<endl;*/

 if(ft%2==t%2 && ft<=t)
 {
   
 }
 else
 {
   ans="No"; break;
 }
 
 
}




cout << ans <<endl;
return 0;




}


Measured memory_bytes: 5760
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int a[200000];
long long dp[200001];

int main() {
    int n, l = 0, r = -1, p = 0, m = 1000000007, i;
    long long sum = 0;
    vector <pair<int, int> > v;
    map <int, int> mp;
    map <int, int>::iterator it;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        v.push_back(make_pair(x, y));
        mp[y] = 1;
    }
    
    for (it = mp.begin(), i = 0; it != mp.end(); it++, i++) it->second = i;
    
    for (i = 0; i < n; i++) v[i].second = mp[v[i].second];
    
    sort(v.begin(), v.end());
    
    for (i = n - 1; i >= 0; i--) {
        if (i == n - 1 || v[a[i + 1]].second > v[i].second) {
            a[i] = i;
        } else {
            a[i] = a[i + 1];
        }
    }
    
    dp[0] = 1;
    
    for (i = 0; i < n; i++) {
        if (v[i].second > v[p].second) p = i;
        
        while (r <= v[p].second) {
            sum += dp[++r];
            if (sum >= m) sum -= m;
        }
        
        while (l < v[a[i]].second) {
            sum -= dp[l++];
            if (sum < 0) sum += m;
        }
        
        dp[r] += sum;
        if (dp[r] >= m) dp[r] -= m;
        
        sum *= 2;
        if (sum >= m) sum -= m;
    }
    
    printf("%lld\n", dp[mp.size()]);
    
    return 0;
}


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

using namespace std;

typedef long long int lli;

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

    lli mod = 1000000007;
    string l;

    cin >> l;

    int len = l.size();
    vector<vector<lli>> dp(2, vector<lli>(len, 0));
    dp[0][0] = 2; dp[1][0] = 1;
    for (int i=1; i<len; i++) {
        dp[0][i] = (l[i] == '1') ? (dp[0][i-1]*2)%mod : dp[0][i-1];
        dp[1][i] = (l[i] == '1') ? (dp[1][i-1]*3+dp[0][i-1])%mod : (dp[1][i-1]*3)%mod;
    }
/*
    for (int i=0; i<2; i++) {
        for (int j=0; j<len; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
*/

    cout << (dp[0][len-1] + dp[1][len-1])%mod << endl;

    return 0;
}


Measured memory_bytes: 2768
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    int a = sc.nextInt();
	    int b = sc.nextInt();
	    sc.close();
	    
	    int i = b - a; //何番目の塔か
	    int answer = i * (i + 1) / 2 - b;
	    
	    System.out.println(answer);
	    System.exit(0);
	}
}

Measured memory_bytes: 23764
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        long MOD = (long) 1e9 + 7;
        boolean[][] field = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            char[] cs = sc.next().toCharArray();
            for (int j = 0; j < w; j++) {
                field[i][j] = cs[j] == '.';
            }
        }

        long[][] dp = new long[h + 10][w + 10];
        dp[0][0] = 1;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (field[i][j]) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD;
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD;
                }
            }
        }
        System.out.println(dp[h - 1][w - 1]);
    }


    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 49536
#include <stdio.h>
int main(void){
  int x, y;
  scanf("%d %d", &x, &y);
  int ans=0;

  if(x == 1 && y == 1) ans += 400000;
  if(x == 1) ans += 300000;
  if(y == 1) ans += 300000;
  if(x == 2) ans += 200000;
  if(y == 2) ans += 200000;
  if(x == 3) ans += 100000;
  if(y == 3) ans += 100000;

  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 128
s = input()
n = len(s)
res1 = s == s[::-1]
a = s[:(n-1)//2]
res2 = a == a[::-1]
b = s[(n+3)//2-1:]
res3 = b == b[::-1]
if res1 == res2 == res3 == True:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
import java.util.*;

public class Main{
	static Scanner sc = new Scanner(System.in);
	static int[][] inputArray(int size){
		int arr[][] = new int[size][3];
		for(int i=0;i<size;i++){
			arr[i][0]=sc.nextInt();
			arr[i][1]=sc.nextInt();
			arr[i][2]=sc.nextInt();
		}
		return arr;
	}
	public static void main(String[] args){
		int[][] arr = inputArray(sc.nextInt());
		int dp[][] = new int[arr.length][3];
		for(int i=0;i<3;i++){
			dp[0][i]=arr[0][i];
		}
		for(int i=1;i<arr.length;i++){
			for(int j=0;j<3;j++){
				if(j==0){
					dp[i][j]=Math.max(dp[i-1][j+1]+arr[i][j],dp[i-1][j+2]+arr[i][j]);
				}else if(j==2){
					dp[i][j]=Math.max(dp[i-1][j-1]+arr[i][j],dp[i-1][j-2]+arr[i][j]);
				}else{
					dp[i][j]=Math.max(dp[i-1][j-1]+arr[i][j],dp[i-1][j+1]+arr[i][j]);
				}
			}
		}
		int max = Integer.MIN_VALUE;
		for(int i=0;i<3;i++)max=Math.max(max,dp[arr.length-1][i]);
		System.out.println(max);
	}
}

Measured memory_bytes: 64520
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <stdlib.h>
#include <set>

using namespace std;

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) > (b)) ? (b) : (a))
#define abs(a) (((a) > 0) ? (a) : (-(a)))
#define ll  long long




void solve()
{
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll c1, c2, c3, c4;
    c1 = a * c;
    c2 = a * d;
    c3 = b * c;
    c4 = b * d;
    if (c1 >= c2 && c1 >= c3 && c1 >= c4)
        cout << c1 << '\n';
    
    else if (c2 >= c1 && c2 >= c3 && c2 >= c4)
        cout << c2 << '\n';
    
    else if (c3 >= c1 && c3 >= c2 && c3 >= c4)
        cout << c3 << '\n';
    
    else if (c4 >= c1 && c4 >= c2 && c4 >= c3)
        cout << c4 << '\n';
    
}




int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    
}


Measured memory_bytes: 3592
from collections import Counter

n=int(input())
V=list(map(int,input().split()))

V1=V[0::2]
V2=V[1::2]

V1c=Counter(V1).most_common()
V2c=Counter(V2).most_common()



if V1c[0][0]==V2c[0][0]:
  if len(V1c)==1 and len(V2c)==1:
    print(n//2)
  elif len(V1c)==1:
    print(V2c[0][1])
  elif len(V2c)==1:
    print(V1c[0][1])   
  else:
    print(n-max(V1c[0][1]+V2c[1][1],V1c[1][1]+V2c[0][1]))
else:
  print(n-V1c[0][1]-V2c[0][1])


Measured memory_bytes: 21084
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#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>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

using namespace std;

static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> paii;

int dp[2][1000][1000];//0...head east 1...head north

int solve(int w, int h)
{
	CLR(dp);
	
	FOR(k, 0, h+w+1)
	{
		dp[0][k][1] = 1;
		dp[1][k][1] = 1;
		dp[0][1][k] = 1;
		dp[1][1][k] = 1;
	}

	FOR(j, 2, h+1)
		FOR(i, 2, w+1)
		{
			dp[0][j][i] = (dp[0][j][i-1] + dp[1][j-2][i])%100000;
			dp[1][j][i] = (dp[1][j-1][i] + dp[0][j][i-2])%100000;
		}
		
	return (dp[0][h][w-1] + dp[1][h-1][w])%100000;
}

int main()
{
	int w, h;
	
	while(cin >> w >> h, (w||h))
	{
		cout << solve(w, h) << endl;
	}

	return 0;
}

Measured memory_bytes: 8980
using System;
using static System.Console;

namespace AtCorder
{
  class Program
  {
    static void Main()
    {
      var age = int.Parse(ReadLine());
      
      if(age == 1)
      {
        WriteLine("Hello World");
      }
      else
      {
        var a = int.Parse(ReadLine());
        var b = int.Parse(ReadLine());
        WriteLine(a+b);        
      }
    }    
  }
}

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long
#define ALL(v) (v).begin(), (v).end()

typedef pair<ll, ll> P;

int main(){
   int n;
   ll ans = 0;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    REP(i, n) {
        cin >> a[i];
    }
    REP(i, n) {
        cin >> b[i];
    }
    REP(i, n) {
        cin >> c[i];
    }

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

    /* 真ん中を見る */
    REP(i, n) {
        int kijun = b[i];
        ll small = lower_bound(a.begin(), a.end(), kijun) - a.begin();
        ll big = c.end() - upper_bound(c.begin(), c.end(), kijun);
        ans += small * big;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1408
/*************************************************\
           In the name of almighty ALLAH
                 MD.Faysal Hasan
                Comilla Univesity
\*************************************************/

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

#define     ikarus_101  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef     long long             ll;
typedef     long double           ld;
typedef     unsigned long long    ull;
typedef     vector<ll>            vll;
typedef     pair<ll,ll>           pll;
typedef     vector<pll>           vpl;
typedef     map<ll,ll>            mll;
typedef     multiset<ll>          msl;
typedef     multimap<ll,ll>       Mll;
using pqboro=priority_queue<ll,vll,less<ll>>;
using pqchoto=priority_queue<ll,vll,greater<ll>>;

#define    all(str)       str.begin(),str.end()
#define    sajo(str)      sort(str.begin(),str.end())
#define    rev(str)       reverse(str.begin(),str.end())
#define    usajo(str)     sort(str.rbegin(),str.rend())
#define    vin(a)         for(auto &it : a) cin>>it
#define    vout(a)        for(auto it:a) cout<<it<<' ';cout<<nn
#define    pb             push_back
#define    eb             emplace_back
#define    mkp(x,y)       make_pair(x,y)
#define    F              first
#define    S              second
#define    yes            cout<<"YES"<<nn
#define    no             cout<<"NO"<<nn
#define    nn             "\n" ///endl
#define    rep(i,n)       for (i=0;i<n;++i )
#define    rep1(i,n)      for (i=1;i<=n;++i )

#define    min3(a,b,c)    min(a,min(b,c))
#define    max3(a,b,c)    max(a,max(b,c))
#define    sqr(x)         ((x)*(x))
#define    pi             2*acos(0.0)
#define    gcd(a,b)       __gcd(a,b)
#define    lcm(a,b)       (a/gcd(a,b))*b
#define    mem(a,b)       memset(a,b,sizeof (a))
#define    dec(x)         cout<<fixed<<setprecision(x)
#define    none(n)         __builtin_popcountll(n)

template < typename T > string toString ( T Number ) { stringstream ss ; ss << Number ; return ss.str() ; }
template < typename T > ll toll ( T str ) { stringstream ss ; ss << str ; ll num ; ss >> num ; return num ; }
ll power(ll n , ll k) { if(k == 0) return 1 ; if(k&1) return n*sqr(power(n,k/2)) ; else return sqr(power(n,k/2)); }

const   int  N   =   2e5+7;
const   int  M   =   1e9+7;
const   ll  inf  =   0x7f7f7f7f7f7f7f7f;
const   int dx[] =   {+1,+2,+2,+1,-1,-2,-2,-1};
const   int dy[] =   {-2,-1,+1,+2,+2,+1,-1,-2};

int main() {//ikarus_101

    int n,m,i,j,k,x;

    cin>>n;

    vll v(n);
    vin(v);
    sajo(v);
    ll ct = 0;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(v[i]==v[j]) {
                continue;
            }
            for(k=j+1;k<n;k++)
            {
                if(v[j]==v[k]) {
                    continue;
                }
                if(v[i] + v[j] > v[k]) {
                    ++ct;
                }
            }
        }
    }

    cout << ct << endl;

















    return 0;
}


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

int N,A,B,C,D;
bool dp[200010] = {};
string S;

bool judge(int s,int t){
    for(int i=0;i<N;i++) dp[i] = false;
    dp[s] = true;
    for(int i=s+1;i<=t;i++){
        if(S[i]=='#') continue;
        dp[i] = (dp[i] | dp[i-1]);
        dp[i] = (dp[i] | dp[i-2]);
    }
    return dp[t];
}

int main(){
    cin >> N >> A >> B >> C >> D;
    A--;
    B--;
    C--;
    D--;
    cin >> S;
    bool ok = true;
    if(C<D){
        ok = (judge(B,D) && judge(A,C));
    }else{
        bool c = false;
        if(A+1==B && S[B+1]=='.'){
            c = true;
            A = B+1;
        }
        else{
            if(judge(A,B-1)){
                A = B-1;
            }else if(judge(A,B-2)){
                A = B-2;
            }else{
                cout << "No" << endl;
                return 0;
            }
            int sb = -1;
            for(int i=B;i<=D;i++){
                if(S[i]=='.' && S[i-1]=='.' && S[i+1]=='.'){
                    sb = i;
                    break;
                }
            }
            if(sb==-1){
                cout << "No" << endl;
                return 0;
            }
            if(judge(B,sb)){
                B = sb;
                A = B+1;
            }else{
                cout << "No" << endl;
                return 0;
            }
            ok = (judge(A,C) && judge(B,D));
        }
    }
    cout << (ok? "Yes":"No") << endl;
}

Measured memory_bytes: 772
n=int(input())
a=list(map(int,input().split()))
q=int(input())

s=sum(a)
d=[0]*(10**5+1)
for i in a:
    d[i-1]+=1

for _ in range(q):
    b,c=map(int,input().split())
    tmp=0
    k=d[b-1]
    d[c-1]+=k
    d[b-1]=0

    tmp = k*c-k*b
    s+=tmp
    print(s)


Measured memory_bytes: 83336
#include <iostream>
#include <vector>
#include <array>

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

    //int v, e;
    //std::cin >> v >> e;
    //std::vector<int> weigh(e);
    //
    //for (int i = 0; i < e; i++) {
    //    std::cin.ignore();
    //    std::cin.ignore();
    //    std::cin >> weigh.at(i);
    //}
    //
    //int ve, ee;
    //std::cin >> ve >> ee;
    //
    //std::vector<int> king1(ee);
    //std::vector<int> king2(ee);
    //for (int i = 0; i < ee; i++) std::cin >> king1.at(i) >> king2.at(i);

    int data[3][6];

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 6; j++)
            std::cin >> data[i][j];

    int h, m, s;

    for (int i = 0; i < 3; i++) {
        h = data[i][3] - data[i][0];
        m = data[i][4] - data[i][1];
        s = data[i][5] - data[i][2];

        if (s < 0) {
            s += 60;
            m--;
        }
        if (m < 0) {
            m += 60;
            h--;
        }

        std::cout << h << " " << m << " " << s << "\n";
    }

    return 0;
}

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

int main(){
  int N;
  cin >> N;
  int t = 1;
  for(int i=0; i<8; i++){
    t *= 2;
    if(t > N){
      t /= 2;
      break;
    }
  }
  cout << t << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

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

    int n = s.size();

    bool ans = true;

    rep(i,(n-1)/2){
        if(s[i] != s[(n+1)/2 + i]) {
            ans = false;
            break;
        }
    }

    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
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 ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    char b;
    cin >> b;
    if(b=='A'){
        cout << "T" << endl;
    }else if(b=='T'){
        cout << "A" << endl;
    }else if(b=='C'){
        cout << "G" << endl;
    }else if(b=='G'){
        cout << "C" << endl;
    }

    return 0;
}

Measured memory_bytes: 3592