akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define exists(x,m) m.find(x) != m.end()
#define umap unordered_map
#define uset unordered_set
#define pq priority_queue

const ll MOD = 1e9 + 7;

pair<vi, vector<bool>> prime_sieve(ll lim) {
	vi primes = vi();
	vector<bool> composite = vector<bool>(lim+1);
	for (int num = 2; num <= lim; num++) {
		if (!composite[num]) primes.pb(num);
		for (int i = 0; i < isize(primes) and num * primes[i] <= lim; i++) {
			composite[num * primes[i]] = true;
			if (num % primes[i] == 0) break;
		}
	}
	return {primes, composite};
}


int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n; cin >> n;
	vi A = vi();
	int maxx = 0;
	rep(i, n) {
		int x; cin >> x;
		A.pb(x);
		maxx = max(maxx, x);
	}	
	auto [primes, composite] = prime_sieve(min(1e3+100, ceil(sqrt(maxx)) + 100));
	umap<int, int> prime_freq = umap<int, int>();
	for (const int& a : A) {
		int b = a;
		for (int i = 0; primes[i]*primes[i] <= b; i++) {
			if (b % primes[i] == 0) prime_freq[primes[i]]++;
			while(b % primes[i] == 0) b /= primes[i];
		}
		if (b != 1) prime_freq[b]++;
	}
	int max_freq = 0;
	for (const auto& [p, freq] : prime_freq) {
		max_freq = max(max_freq, freq);
	}
	if (max_freq <= 1) {
		cout << "pairwise coprime";
	} else {
		cout << (max_freq < n ? "setwise coprime" : "not coprime");
	}
}

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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
ll n, k, MOD = 1e9+7;
ll arr[210];
int chk[210];

vector<pair<vector<ll>,pll>> lis;

int main() {
    int i, j;

    scanf("%lld%lld",&n,&k);
    for (i=0;i<n;i++) scanf("%lld",&arr[i]);
    sort(arr,arr+n);
    for (i=0;i<62&&i<=k;i++) {
        ll uni = 1LL<<i;
        vector<pll> tmp;
        for (j=0;j<n;j++) tmp.push_back(pll(arr[j]%uni,j));
        sort(tmp.begin(),tmp.end());

        vector<ll> vec;
        for (int l=0;l<n;l++) {
            vec.push_back(arr[l]/uni-(arr[0]/uni));
        }
        lis.push_back(pair<vector<ll>,pll>(vec,pll(max(arr[0]/uni-(k-i),0LL),arr[0]/uni)));

        for (j=0;j<n;j++) {
            if ((j!=n-1&&tmp[j+1].first==tmp[j].first)||tmp[j].first==uni-1) continue;
            if (arr[tmp[j].second]<uni) break;
            int l, c = 1; ll val = ((j==n-1)?uni-1:tmp[j+1].first);
            for (l=i-1;l>=0;l--) {
                if ((tmp[j].first>>l)!=(val>>l)) break;
                c += (int)(tmp[j].first>>l&1);
            }
            if (k-c-i<0) continue;
            ll cnt = k-c-i;
            for (l=0;l<=j;l++) chk[tmp[l].second] = 1;
            vector<ll> vec;
            for (l=0;l<n;l++) {
                vec.push_back(arr[l]/uni-chk[l]-(arr[0]/uni-chk[0]));
            }
            lis.push_back(pair<vector<ll>,pll>(vec,pll(max(arr[0]/uni-chk[0]-cnt,0LL),arr[0]/uni-chk[0])));
            for (l=0;l<=j;l++) chk[tmp[l].second] = 0;
        }
    }
    sort(lis.begin(),lis.end());
    j = 0;
    ll ans = 0;
    for (i=0;i<lis.size();i++) {
        if (i+1!=lis.size()&&lis[i+1].first==lis[i].first) continue;
        ll s = -1, e = -1;
        for (;j<=i;j++) {
            if (s<0) s=lis[j].second.first,e=lis[j].second.second;
            else e=max(e,lis[j].second.second);
            if (j==i||lis[j+1].second.first>e) {ans += e-s+1;s=-1,e=-1;ans%=MOD;}
        }
    }
    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 15768
L,A,B,mod=map(int,input().split())

def keta(k):# k-桁の数の初項、末項、項数を求める
    if A>=10**k:
        return 0,0,0
    begin=10**(k-1)
    end=10**k

    if begin>A+B*(L-1):
        return 0,0,0

    sh=A+max(-1,(begin-1-A)//B)*B+B
    ma=min(A+max(0,(end-1-A)//B)*B,A+B*(L-1))
    kou=(ma-sh)//B+1
    
    return sh,ma,kou

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,r): # 1+r+...+r**(n-1)
    if n==1:
        return 1
    if n%2==0:
        return (f(n//2,r) + pow(r,n//2,mod)*f(n//2,r))%mod
    return (r*f(n-1,r)+1)%mod

@lru_cache(maxsize=None)
def g(n,r): # 0+r+2*r**2+...+(n-1)*r**(n-1)
    if n==1:
        return 0
    if n%2==0:
        return g(n//2,r)+pow(r,n//2,mod)*(g(n//2,r)+n//2*f(n//2,r))
    return r*g(n-1,r)+r*f(n-1,r)

keta_count=1
ANS=0
for i in range(18,0,-1):
    sh,ma,kou = keta(i)
    
    if kou<=0:
        continue
    

    #print(i,sh,ma,kou)

    ANS=(keta_count*(ma*f(kou,10**i)-B*g(kou,10**i))+ANS)%mod
    #print(ANS)
    keta_count = keta_count * pow(10,kou * i,mod)

print(ANS)
    
    


Measured memory_bytes: 4236
n = input()
s = list(n)
m = s[-1]
m = int(m)
if m == 0:
    print("pon")
elif m == 1:
    print("pon")
elif m == 2:
    print("hon")
elif m == 3:
    print("bon")
elif m == 4:
    print("hon")
elif m == 5:
    print("hon")
elif m == 6:
    print("pon")
elif m == 7:
    print("hon")
elif m == 8:
    print("pon")
elif m == 9:
    print("hon")


Measured memory_bytes: 9116
package main

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

var a [][]int
var b []int
var check [][]bool

func checkHit(num int) bool {
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if num == a[i][j] {
				check[i][j] = true
				return checkBingo()
			}
		}
	}

	return false
}

func checkBingo() bool {
	for i := 0; i < 3; i++ {
		if check[i][0] && check[i][1] && check[i][2] {
			return true
		}
		if check[0][i] && check[1][i] && check[2][i] {
			return true
		}
	}

	if check[0][0] && check[1][1] && check[2][2] {
		return true
	}

	if check[0][2] && check[1][1] && check[2][0] {
		return true
	}

	return false
}

func main() {
	a = make([][]int, 3)
	check = make([][]bool, 3)
	for i := 0; i < 3; i++ {
		a[i] = make([]int, 3)
		check[i] = make([]bool, 3)
		for j := 0; j < 3; j++ {
			a[i][j] = readInt()
			check[i][j] = false
		}
	}

	n := readInt()

	b = make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()

		if checkHit(b[i]) {
			fmt.Println("Yes")
			return
		}
	}

	fmt.Println("No")
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


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

class SCC {
private:
    std::vector<std::vector<int>> gg, rg;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> comp, order, used;
public:
    SCC(size_t v) : gg(v), rg(v), comp(v, -1), used(v, 0) {}

    void addEdge(int x, int y)
    {
        gg[x].push_back(y);
        rg[y].push_back(x);
        edges.push_back({x, y});
    }

    int operator[](int k)
    {
        return comp[k];
    }

    void dfs(int idx)
    {
        if (used[idx]) return;
        used[idx] = true;
        for (auto& to: gg[idx]) dfs(to);
        order.push_back(idx);
    }

    void rdfs(int idx, int cnt)
    {
        if (comp[idx] != -1) return;
        comp[idx] = cnt;
        for (auto& to: rg[idx]) rdfs(to, cnt);
    }

    void build(std::vector<std::vector<int>> &t)
    {
        for (int i{}; i < (int)gg.size(); i++)
            dfs(i);
        std::reverse(order.begin(), order.end());
        int ptr{};
        for (auto& e: order)
            if (comp[e] == -1)
                rdfs(e, ptr), ptr++;
        
        t.resize(ptr);
        std::set<std::pair<int, int>> connect;
        for (auto& e: edges)
        {
            int x{comp[e.first]}, y{comp[e.second]};
            if (x == y) continue;
            if (connect.count({x, y})) continue;
            t[x].push_back(y);
            connect.emplace(x, y);
        }
    }
};

class Solve {
private:
public:
    bool is_last_;
    Solve()
    {
        int n;
        std::cin >> n;
        if (n == 0)
        {
            is_last_ = true;
            return;
        }
        std::vector<long double> p(n);
        SCC sc(n);
        for (int i{}; i < n; i++)
        {
            std::cin >> p[i];
            int m;
            scanf("%d", &m);
            for (int j{}; j < m; j++)
            {
                int a;
                scanf("%d", &a);
                sc.addEdge(i, a - 1);
            }
        }
        std::vector<std::vector<int>> t;
        sc.build(t);
        std::vector<bool> isTop(t.size(), true);
        for (auto& e: t)
            for (auto& f: e)
                isTop[f] = false;
        std::vector<std::vector<int>> belong(t.size());
        for (int i{}; i < n; i++)
            belong[sc[i]].push_back(i);
        long double ans{1};
        for (int i{}; i < (int)t.size(); i++)
        {
            if (!isTop[i]) continue;
            long double tmp{1};
            for (auto& e: belong[i])
                tmp *= p[e];
            ans *= 1 - tmp;
        }
        printf("%.10Lf\n", ans);
    }
};

int main()
{
    while (!Solve().is_last_);
}


Measured memory_bytes: 3404
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = CRLF;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:
  Tmp(int N);
};

Tmp::Tmp(int N){}

void solve(void)
{
  int N; cin >> N;
  vector<int> A(N+3);
  for (int i = 1; i <= N; ++i) {
    cin >> A[i];
  }
  vector<int> C1(N+1);
  for (int i = 0; i <= N; ++i) {
    C1[i] = std::abs(A[i] - A[i+1]);
  }
  vector<int> C2(N+1);
  for (int i = 0; i <= N; ++i) {
    C2[i] = std::abs(A[i] - A[i+2]);
  }

  ll sum = std::accumulate(C1.begin(), C1.begin()+N+1, (ll)0);
  vector<ll> res(N);
  for (int i = 1; i <= N; ++i) {
    res[i-1] = sum - C1[i-1] - C1[i] + C2[i-1];
  }
  cout << res << CRLF;

  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 3200
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> P;
#define X first
#define Y second

int n;

int dis(int a,int b) {
	if(a<b) return b-a;
	return b+n-a;
}

int mid(int a,int b) {
	int x = dis(a,b);
	// cout << x << "*" << endl;
	return (a+(x+1)/2)%n;
}


bool ck(int a,string sa,int b,string sb) {
	int x = dis(a,b);
	// cout << x << " " << sa << " " << sb << endl;
	if(x%2==0 && sa==sb) return false;
	if(x%2==1 && sa!=sb) return false;
	return true;
}

void go() {
	cin >> n;
	int a,b,c;
	string sa,sb,sc;
	a = 0; b = n/2;
	cout << a << endl; fflush(stdout);
	cin >> sa; if(sa=="Vacant") return;
	cout << b << endl; fflush(stdout);
	cin >> sb; if(sb=="Vacant") return;

	if( ck(a,sa,b,sb) ) {
		c = mid(a,b);
		// cout << c << "-" << endl;
	} else {
		c = mid(b,a);
		swap(a,b);
		swap(sa,sb);
		// cout << c << "+" << endl;
	}
	for(;;) {
		cout << c << endl; fflush(stdout);
		cin >> sc; if(sc=="Vacant") return;
		if( ck(a,sa,c,sc) ) {
			b = mid(a,c);
			swap(c,b);
			swap(sc,sb);
		} else {
			a = mid(c,b);
			swap(c,a);
			swap(sc,sa);
		}
		c = mid(a,b);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	// int t; cin >> t; for(;t--;)
	go();
	return 0;
}



Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
     
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define bp __builtin_popcountll
#define MOD 1000000007
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL))

int main()
{
   ll n;
   cin >> n;
   ll a[n];
   for(ll i=0;i<n;i++)   cin >> a[i];
   for(ll i=0;i<n;i++)
   {
       if(a[i]%2==0)
       {
        
           if(a[i]%3== 0 || a[i]%5==0)   
           {
               
           }
           else
           {
               return cout<<"DENIED",0;
           }
       }
   }
   cout<<"APPROVED";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;
//========================================================================


int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================

	ll N;
	cin >> N;

	vstring S(N);
	for (ll i = 0; i < N; i++) {
		cin >> S[i];
	}

	ll middle = 0;
	ll start_B = 0;
	ll end_A = 0;
	ll both = 0;

	for (ll i = 0; i < N; i++) {
		if (S[i][0] == 'B') {
			start_B++;
			
			if (S[i][S[i].length() - 1] == 'A') {
				both++;
			}
		}
		
		if (S[i][S[i].length() - 1] == 'A') {
			end_A++;
		}

		for (ll j = 0; j < S[i].length() - 1; j++) {
			if (S[i][j] == 'A' && S[i][j + 1] == 'B') {
				middle++;
			}
		}


	}

	if (both == min(start_B, end_A) && start_B == end_A && start_B !=0) {
		cout << middle + both - 1;
	}
	else {
		cout << middle + min(start_B, end_A);
	}


}




Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using Tuple = tuple<int, int, int>;


int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    // dpテーブルの用意
    // dp[i][0] = a[0]~a[i]までからi/2個をとるときの最大値
    // dp[i][1] = a[0]~a[i]までから(i+1)/2個をとるときの最大値

    // 初期値は十分小さな値にしておくこと
    // a[i]が全て `-10^9` だとしたら、-10^9 * 10^5(nの最大値)より小さい値でないとだめ
    vector<vector<ll>> dp(n, vector<ll>(2, -1e17));
    // 初期値を埋めておく
    dp[0][0] = 0;
    dp[0][1] = a[0];
    dp[1][0] = max(a[0], a[1]);
    dp[1][1] = max(a[0], a[1]);

    // dpテーブルを埋めていく
    for(int i=2; i<n; i++) {
        // i番目を選んで, i/2が選ばれている状態
        dp[i][0] = max(dp[i][0], dp[i-2][0] + a[i]);
        // i番目を選ばずに, i/2が選ばれている状態
        dp[i][0] = max(dp[i][0], dp[i-1][1]);

        if(i%2==0) {
            // 奇数の場合 ... i+1が実際の番号...
            // i番目を選んで, (i+1)/2個選ばれてる状態
            dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
        } else {
            // 偶数の場合はi/2 == (i+1)/2
            // i番目を選んで, (i+1)/2個選ばれてる状態(偶数個の場合はi/2の状態と同じ)
            dp[i][1] = max(dp[i][1], dp[i][0]);
        }

        // iを選ばず, (i+1)/2個選ばれてる状態は存在しない
    }

    // 奇数でも偶数でもi/2を選んでる状態を出せばいい(nが奇数の時に(i+1)/2を選んだ状態出したら取りすぎになる
    cout << dp[n-1][0] << endl;

    return 0;
}

Measured memory_bytes: 15588
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();

		if (a == b + c || b == a + c || c == a + b) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 23252
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N=gets.to_i
A=get_i
table=array(N+1,0)
A.each do|a|
  table[a]+=1
end
if N.even?
  flag=true
  i=N-1
  while i>=0
    if table[i]!=2
        flag=false
        break
    end
    i-=2 
  end
  if flag
      puts (2**(N/2))% (10**9+7)
  else
      puts 0
  end
else
    flag=true
    i=N-1
    while i>=0
        if i!=0 and table[i]!=2
            flag=false
            break
        elsif i.zero? and table[i]!=1
            flag=false
            break
        end
        i-=2
    end
    if flag
        puts (2**(N/2)) % (10**9+7)
    else
        puts 0
    end
end

Measured memory_bytes: 9492
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll                long long int
#define ld                long double
#define pb                push_back
#define mk                make_pair
#define in(i,a,n)         for(ll i=0;i<n;++i) cin>>a[i];
#define out(i,a,n)        for(ll i=0;i<n;++i) cout<<a[i]<<" ";
#define sz                size()
#define all(c)            c.begin(), c.end()
#define rall(c)           c.rbegin(), c.rend()
#define loop(i,a,b)       for(ll i=a;i<b;i++)
#define rloop(i,a,b)      for(ll i=a;i>b;i--)
#define F                 first
#define S                 second
#define copy(a,b)         copy(all(a),back_inserter(b));
#define intersect(a,b,w)    set_intersection(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define union(a,b,w)      set_union(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define diff(a,b,w)       set_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define symdiff(a,b,w)    set_symmetric_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define fin               freopen( "input.txt", "r", stdin );
#define fout              freopen( "output.txt", "w", stdout );
#define deb(x) cout << #x << " " << x << endl
#define inf INT_MAX
const ll N = 200010;
const ll MOD = 1000 * 1000 * 1000 + 7;
ll mod(ll n) {
    return (n % MOD + MOD) % MOD;
}

ll** w;

ll knapsack(ll W, ll n){

    ll dp[n][W+1];

    for(ll i=0;i<=W;i++){
        if(i < w[0][0])
            dp[0][i] = 0;
        else dp[0][i] = w[0][1];
    }

    for(ll i=1;i<n;i++){
        for(ll j=0;j<=W;j++){
            if(j < w[i][0]) dp[i][j] = dp[i-1][j];
            else{
                dp[i][j] = max(dp[i-1][j], w[i][1] + dp[i-1][j-w[i][0]]);
            }
        }
    }

    return dp[n-1][W];
}


void solve(){
    ll n, W;
    cin >> n >> W;

    w = new ll*[n];
    for(int i=0;i<n;i++){
        w[i] = new ll[2];
    }

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

    cout << knapsack(W, n) << endl;

}

int main(){
    //fin fout
    fast
    ll T = 1; //cin >> T;
    loop(i, 0, T) solve();
    /*#ifdef LOCAL
    clock_t tStart = clock();
    cerr<<fixed<<setprecision(10)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
    #endif*/
}


/*339 341 1
342 343 2
342 342 2*/



Measured memory_bytes: 78336
# -*- coding: utf-8 -*-
#
# a = list(map(int, input().split('/')))
#
# # print(a)
#
# if a[0] <= 2018:
#     print('Heisei')
# else:
#     if a[0] == 2019 and a[1] <= 4:
#         print('Heisei')
#     else:
#         print('TBD')
#
#

S = input()

S = int(S[5:7])

if S <= 4:
    print('Heisei')
else:
    print('TBD')



Measured memory_bytes: 2940
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int N; cin>>N;
	vector<ll> A(N);
	for (int i=0; i<N; i++)
		cin>>A[i];
	ll S=0,O=0;
	for (int i=0; i<N; i++) {
		S+=A[i];
		if(i%2)
			O+=A[i];
	}
	vector<ll> X(N);
	X[0]=S-2*O;
	for (int i=1; i<N; i++)
		X[i]=2*A[i-1]-X[i-1];
	for (auto x : X)
		cout<<x<<" ";
	cout<<"\n";
	return 0;
}

Measured memory_bytes: 2944
n, m = map(int, input().split())
h = list(map(int, input().split()))
G = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

cnt = 0
for i in range(n):
    if all(h[i] > h[j] for j in G[i]):
        cnt += 1
print(cnt)


Measured memory_bytes: 93792
// 未解決

#include <bits/stdc++.h>

#include <iostream>
using namespace std;

#define EACH(i, a) for (auto &&i : a)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RFOR(i, a, b) for (int i = (int)b - 1; i >= (int)a; --i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREPS(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(x) (x).begin(), (x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define debug(x) cout << #x << ": " << x << endl

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define INF (1L << 30)
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
void pvp(T a, T b) {
  for (T i = a; i != b; ++i)
    cout << "(" << i->first << ", " << i->second << ") ";
  cout << endl;
}
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;
}
int in() {
  int x;
  scanf("%d", &x);
  return x;
}

using ll = long long;
#define int ll

//**********

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

  int n, m;
  int a[10010];
  cin >> n >> m;
  REP(i, m) { cin >> a[i]; }

  int ans = n;

  REP(i, m) { ans -= a[i]; }
  if (ans < 0) {
    cout << "-1" << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
};


Measured memory_bytes: 3736
#include<stdio.h>

#define N 100000

int partition(int*,int,int);

int main(){
  int i,j,a,b,n,A[N];

  scanf("%d",&n);

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

  a=partition(A,0,n-1);

  printf("%d",A[0]);
  for(i=1;i<n;i++){
    if(i==a) printf(" [%d]",A[i]);

    else printf(" %d",A[i]);
  }

  printf("\n");

  return 0;
}

int partition(int *A,int p,int r){
  int x,i,j,temp;

  x=A[r];
  i=p-1;

  for(j=p;j<r;j++){
    if(A[j]<=x){
      i=i+1;
      temp=A[i];
      A[i]=A[j];
      A[j]=temp;
    }
  }

  temp=A[i+1];
  A[i+1]=A[r];
  A[r]=temp;

  return i+1;
}



Measured memory_bytes: 2124
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,k,temp;
	cin>>n>>k;
	ll arr[n];
	ll res[n][k];
	ll min[n];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
		min[i]=1e16+250;
	}
	temp=abs(arr[1]-arr[0]);
	for(int i=0;i<k;i++)
	{
		res[0][i]=0;
		res[1][i]=temp;
	}
	min[0]=0;
	min[1]=temp;
	for(int i=2;i<n;i++)
	{
		for(int j=1;j<=k;j++){
			if((i-j)<0)
				break;
			res[i][j-1]=abs(arr[i]-arr[i-j])+min[i-j];
			if(res[i][j-1]<min[i])
				min[i]=res[i][j-1];
		}
	}
	cout<<min[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 80000
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll a,b;
int32_t main(){
CODE_START;
cin>>a;
cin>>b;
cout<<a*b-1-a+1-b+1;
}


Measured memory_bytes: 256
//package Codes;

import java.util.*;
import java.io.*;
import java.math.*;


class Main {
    public static void main(String args[] ) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        int t=Integer.parseInt(br.readLine());
        HashSet<String> hs=new HashSet<>();
        
        while(t-- > 0)
        {
        	String s=br.readLine();
        	hs.add(s);
        }
        System.out.println(hs.size());
    }
}
/*
 * package NomuraContest2020;

import java.util.*;
import java.io.*;
import java.math.*;


class C {
    public static void main(String args[] ) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //Start here:
        String input[]=br.readLine().split(" ");
        
        int h1=Integer.parseInt(input[0]);
        int m1=Integer.parseInt(input[1]);
        int h2=Integer.parseInt(input[2]);
        int m2=Integer.parseInt(input[3]);
        
        int time=Integer.parseInt(input[4]);
        
        int t=(h2-h1)*60+(m2-m1);
        
        int ans=t-time;
        if(ans<0)
        {
        	System.out.println(-1);
        }
        else
        {
        	System.out.println(ans);
        }
        
        

    }
}*/


Measured memory_bytes: 65860
#include<bits/stdc++.h>
using namespace std;
int main () {
  string masu;
  cin >> masu;
  int total = 0;
  for (int i = 0; i < masu.size(); i ++) {
    if (masu.at(i) == '1') total ++ ;
  }
  cout << total << endl;
}

Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, res = 0;
  cin >> n;
  vector<int> d(n);
  REP(i,n) cin >> d[i];
  REP(i,n) {
    REP(j,n) {
      if(i == j) continue;
      res += d[i] * d[j];
    }
  }
  cout << res / 2 << endl;
  return 0;
}
//templete by private_yusuke

Measured memory_bytes: 256
#include <iostream>

using namespace std;

const int NUM = 105;
int T[NUM] = {0};
int n,m,p,x;

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> T[i];
    cin >> m;
    for(int i=1; i<=m; i++){
        cin >> p >> x;
        int t = T[p];
        T[p] = x;
        int sum = 0;
        for(int i=0; i<=n; i++)
            sum += T[i];
        cout << sum << endl;
        T[p] = t;
    }
    return 0;
}


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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector< pair<int,int> > v;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    v.emplace_back(a, b);
  }
  sort(v.begin(), v.end(), [](pair<int,int> i, pair<int,int> j) { 
    int a = i.first + i.second;
    int b = j.first + j.second;
    return a > b;
  });

  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (i & 1) res -= v[i].second;
    else res += v[i].first;
  }
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 1400
//=====================COMPILER OPTIMIZATION STARTS=======================
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//======================COMPILER OPTIMIZATION ENDS=======================

//compile using : g++ -D DEB file.cpp
#ifdef DEB
    //to check from out of bounds errors
    #define _GLIBCXX_DEBUG
#endif
//=============================DEBUG PART ENDS===========================

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

#define ll long long int
#define pi pair<ll,ll>

ll power(ll x, ll y, ll mod = 1e9+7){
    ll res = 1;
    while(y > 0){
        if(y & 1)
            res = (res * x) % mod;
        y = y >> 1;
        x = (x*x)% mod;
    }
    return res % mod;
}

int Stoi(char c) {
    return c - '0';
}

void solve(){
    string s, target = "753";   cin >> s;
    int ans = INT_MAX;

    if (s.size() <= 3) {
        ans = abs(stoi(s) - stoi(target));
        cout << ans << '\n';
        return;
    }

    for (int i = 0; i+3 <= s.size(); i += 1) {
        string cur = s.substr(i, 3);
        ans = min(ans, abs(stoi(cur) - stoi(target)));
    }

    cout << ans << '\n';
}

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

    int test = 1;
    // cin >> test;
    while(test--)
        solve();
    return 0;
}

Measured memory_bytes: 256
<?php
// 解説の解答コードをPHPに起こす
fscanf(STDIN, "%d %d %d %d", $N, $A, $B, $C);
for($i=0; $i<$N; $i++) {
    fscanf(STDIN,"%d",$L[$i]);
}
$INF = 10 ** 9;
function dfs($cur, $a, $b, $c) {
    global $L, $N, $A, $B, $C, $INF;
    if($cur == $N) {
        if(min([$a, $b, $c])>0) {
            return abs($a - $A) + abs($b - $B) + abs($c - $C) - 30;
        }else {
            return $INF;
        }
    }
    $ret[0] = dfs($cur + 1, $a, $b, $c);
    $ret[1] = dfs($cur + 1, $a + $L[$cur], $b, $c) + 10 ;
    $ret[2] = dfs($cur + 1, $a, $b+ $L[$cur], $c) + 10 ;
    $ret[3] = dfs($cur + 1, $a, $b, $c+ $L[$cur]) + 10 ;
    return min($ret);
}

echo dfs(0, 0, 0, 0)."\n";


Measured memory_bytes: 4856
#include<iostream>
using namespace std;
int main()
{

  int n;
  int p[105];
  int box = 0;
  int ans;

  cin >> n;
  for( int i=0;i<n;i++ ) cin >> p[i];

  for( int i=1;i<=n;i++ ){
    for( int j=0;j<n;j++ ){
      if( i <= p[j] ) box++;
    }
    if( box >=  i ){
      ans = i;
    }
    box = 0;
  }

  cout << ans << endl;

  return 0;

}



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

int main() {
   string s;
   cin >> s;
   int ans=0,cnt=0;
   for(char c : s){
      if(c=='A'||c=='C'||c=='G'||c=='T'){
         cnt++; ans=max(cnt,ans);
      } else 
         cnt=0;
   }
   cout << ans << endl;
}

Measured memory_bytes: 256
import datetime

l = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday" ]

while True:
  m, d = raw_input().rstrip().split(" ")
  if int(m) == 0 and int(d) == 0: break
  print(l[datetime.date(2004, int(m), int(d)).weekday()])

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

// 
int main() {
    int N;
    cin >> N;
    int a[N];
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    int countMus = 0;
    for (int i = 0; i < N; i += 2) {
        if (a[i] % 2 == 1) {
            countMus++;
        }
    }
    cout << countMus;
}


Measured memory_bytes: 3620
#include <stdio.h>
 
int
main (
  int   argc,
  char *argv[ ]
  )
{
  int i, j;
 
  for ( ; ; )
  {
    int h, w;
 
    scanf ( "%d%d", &h, &w );
    if ( h == 0 && w == 0 ) break ;
 
    for ( i = 0; i < h; ++i )
    {
      for ( j = 0; j < w; ++j )
      {
        if ( i == 0 || i == h - 1
          || j == 0 || j == w - 1 )
        {
          putchar ( '#' );
        }
        else
        {
          putchar ( '.' );
        }
      }
      puts ( "" );
    }
    puts ( "" );
  }
 
  return ( 0 );
}

Measured memory_bytes: 588
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define REP(i, n) for (LL i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (LL i = m; i n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define int long long
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
signed main() {
    int k;
  string s;
    cin >> k >>s;
    if(s.size()<=k){
      cout <<s;
    }
     else{
       REP(i,k)cout <<s[i];
       cout<<"...";
     }
  
}

Measured memory_bytes: 3652
def modinv2(a,m):
    return pow(a,m-2,m)

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
P = 10**9+7

cominv = [0 for i in range(N-1)]
for i in range(N-1):
    if i+2 == K:
        cominv[i] = 1
    elif i+1 == K:
        cominv[i] = (i+1)%P
    elif i+1 > K:
        a = modinv2(i-K+2,P)
        cominv[i] = cominv[i-1]*(i+1)*a%P

#print(cominv)
ans = 0

for i in range(N):
    if i <= N-K:
        b = A[i]*cominv[N-i-2]%P
        ans = (ans-b+P)%P
    if i >= K-1:
        c = A[i]*cominv[i-1]%P
        ans = (ans+c)%P

print(ans)


Measured memory_bytes: 14416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

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

    for(int i=0; i<26; i++){
        for(int j=0; j<20; j++){
            if(4*i + 7*j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

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

vector<vector<char> > M;
queue<vector<int> > q1;
queue<vector<int> > q2;
int h, w;
int ch, cw, dh, dw;
int cost;

void ins(int hh, int ww, int radius = 1) {
  if (hh == dh && ww == dw) {
    cout << cost << endl;
    exit(0);
  }

  if (radius == 1 && M[hh][ww] == '#') return;

  M[hh][ww] = '#';
  vector<int> p(2);

  if (radius == 1) {
    p[0] = hh;
    p[1] = ww;
    q2.push(p);

    if (hh - 1 >= 0) {
      p[0] = hh - 1;
      p[1] = ww;
      q1.push(p);
    }
    if (hh + 1 < h) {
      p[0] = hh + 1;
      p[1] = ww;
      q1.push(p);
    }
    if (ww - 1 >= 0) {
      p[0] = hh;
      p[1] = ww - 1;
      q1.push(p);
    }
    if (ww + 1 < w) {
      p[0] = hh;
      p[1] = ww + 1;
      q1.push(p);
    }
  } else {
    for (int th = max(0, hh - 2); th < min(h, hh + 3); th++) {
      for (int tw = max(0, ww - 2); tw < min(w, ww + 3); tw++) {
        p[0] = th;
        p[1] = tw;
        q1.push(p);
      }
    }
  }
}

int main() {
  cin >> h >> w >> ch >> cw >> dh >> dw;
  ch--;
  cw--;
  dh--;
  dw--;

  rep(i, h) {
    M.push_back(vector<char>());
    rep(j, w) {
      char c;
      cin >> c;
      M[i].push_back(c);
    }
  }

  ins(ch, cw);

  while (!q1.empty()) {
    // cout << "## Q1" << endl;
    while (!q1.empty()) {
      ins(q1.front()[0], q1.front()[1]);
      // for (auto f : q1.front()) cout << f;
      // cout << endl;
      q1.pop();
    }

    // cout << "## Q2" << endl;
    while (!q2.empty()) {
      ins(q2.front()[0], q2.front()[1], 2);
      // for (auto f : q2.front()) cout << f;
      // cout << endl;
      q2.pop();
    }
    cost++;
  }

  cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 18876
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int h, w, d;
	cin >> h >> w >> d;
	map<int, pair<int, int> > m;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			int a;
			cin >> a;
			a--;
			m[a] = make_pair(i, j);
		}
	}
	vector<vector<int> > result(d);
	for(int i = 0; i < d; i++){
		result[i].push_back(0);
		for(int j = 1; d * j + i < h * w; j++){
			result[i].push_back(result[i][j - 1] + abs(m[d * j + i].first - m[d * (j - 1) + i].first) + abs(m[d * j + i].second - m[d * (j - 1) + i].second));
		}
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		cout << result[r % d][r / d] - result[l % d][l / d] << endl;
	}
}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
#define ll long long
int main()
{
    ll n;
    std::vector<ll> a;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        ll temp = 0;
        std::cin >> temp;
        a.push_back(temp);
    }
    ll temp_max = a[0];
    ll ans = 0;
    for (int i = 1; i < n; ++i) {
        temp_max = std::max(temp_max, a[i]);
        ans += (temp_max - a[i]);
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 5284
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define pi 3.14159265358979323846
#define ll long long
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int n;
  cin >> n;
  if(n < 1200){
    cout << "ABC\n";
    return 0;
  }
  cout << "ARC\n";
}

Measured memory_bytes: 3640
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)
#print(gcd_l_li)
#print(gcd_r_li)

ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  # かきかえる整数が右端のときと左端のとき
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[n-2-target]))
print(ans)




Measured memory_bytes: 92264
n = int(input())

v = list(map(int, input().split()))
c = list(map(int, input().split()))

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = max(dp[i - 1] + v[i - 1] - c[i - 1], dp[i - 1])
print(dp[-1])



Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
import numpy as np

# スペース区切りの整数の入力
a, b, x = map(int, input().split())

y = 2*x/(a*a) - b
if(y >= 0):
  theta = np.arctan((b-y)/a)
else:
  z = 2*x/(a*b)
  theta = np.arctan(b/z)

# 出力
print("{}".format(np.rad2deg(theta)))


Measured memory_bytes: 12504
import kotlin.math.abs
import kotlin.math.min

fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = MyScanner()
        val n = sc.nextInt()

        val a = sc.longList()

        var ans = Long.MAX_VALUE
        val sum = a.sum()
        var x = 0L
        for (i in 0 until n - 1) {
            x += a[i]
            val y = sum - x
            ans = min(ans, abs(x - y))
        }

        println(ans)
    }
}

class MyScanner {
    private var ptr = 0
    private var l = listOf<String>()

    fun next(): String {
        while (l.size <= ptr) {
            l = readLine()!!.split(' ')
            ptr = 0
        }
        return l[ptr++]
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextDouble() = next().toDouble()
    fun nextCharArray() = next().toCharArray()
    fun nextChar() = next()[0]

    fun list(): List<String> {
        ptr = l.size
        return readLine()!!.split(' ')
    }

    fun intList() = list().map { s -> s.toInt() }
    fun longList() = list().map { s -> s.toLong() }
    fun doubleList() = list().map { s -> s.toDouble() }

    fun array() = list().toTypedArray()
    fun intArray() = intList().toIntArray()
    fun longArray() = longList().toLongArray()
    fun doubleArray() = doubleList().toDoubleArray()
}


Measured memory_bytes: 64800
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;

int main(){
  int N; cin >> N;
  ll A[N]; rep(i,N) cin >> A[i];
  ll MOD = 1000000007;

  ll cumsum[N+1] = {};
  rep(i,N) cumsum[i+1] = (cumsum[i]+A[i])%MOD;

  ll ans = 0;
  rep(i,N){
    (ans += A[i]*(cumsum[N]-cumsum[i+1]+MOD))%=MOD;
  }
  cout << ans << endl;


  // cout << fixed << setprecision(10);
  
  return 0;
}

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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define MOD 1000000007

const int MAX_M = 100000;


int main(){
  ll n;
  //string s;
  cin >> n;
  
  vector<string> s(n);
  rep(i,0,n){
    cin >> s.at(i);
  }
  
  map<string,ll> d{};
  ll ans = 0;
  
  rep(i,0,n){
    d[s.at(i)]++;
    if(d[s.at(i)] == 1)
      ans++;
  }
  
    
  cout << ans << endl;
}

Measured memory_bytes: 25068
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include <fstream>
#include <time.h>
#include <iterator>
#include<random>



#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 REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
using namespace std;
int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 500050;

struct edge
{
	int to, cost;
};

vector<edge> G[30];
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int L; cin >> L;
	L--;
	int K, r;
	REPR(i, 20) {
		if (L - (1 << i) >= -1) {
			K = i;
			r = L - (1 << i) + 1;
			break;
		}
	}
	int N = K + 1;
	int M = 0;
	REP(i, N - 1) {
		G[i].push_back({ i + 1,1 << i });
		G[i].push_back({ i + 1,0 });
		M += 2;
	}
	int mx = 1 << K;
	REPR(i, 20) {
		if (r&(1 << i)) {
			G[i].push_back({ N - 1,mx });
			mx += 1 << i;
			M++;
		}
	}
	pe(N)print(M);
	REP(i, 30) {
		for (auto x : G[i]) {
			pe(i + 1)pe(x.to + 1)print(x.cost);
		}
	}
}

Measured memory_bytes: 256
a, b, k = map(int,input().split())


dList = []
i = 0 
while True :
  i += 1
  if a % i == 0 and b % i == 0:
    dList.append(i)
  if i >= a or i >= b:
    break

print(sorted(dList,reverse = True)[k-1])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, a;cin >> n >> a;
	vector<int> x(n);
	rep(i,n){
		cin >> x.at(i);
		x.at(i) -= a;
	}
	vector<vector<ll>> dp(n + 1, vector<ll>(5001));
	dp[0][2500] = 1;
	rep(i,n){
		rep(j,5001){
			if(j + x.at(i) >= 0 && j + x.at(i) <= 5000){
				dp[i + 1][j + x.at(i)] += dp[i][j];
			}
			dp[i + 1][j] += dp[i][j];
		}
	}
	cout << dp[n][2500] - 1 << endl;
}


Measured memory_bytes: 2304
#include <stdio.h>
int main(void){
    int a,b,c;
    
    scanf("%d %d", &a, &b);
    
    c=a*b;
    
    if(c % 2 == 0){
        printf("Even");
    }else{
        printf("Odd");
    }
    
    return 0;
}


Measured memory_bytes: 128