akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
 
void Main() {
  int n;
  cin >> n;
  set<int> s;
  rep(i,n) {
    int x;
    R x;
    if(s.count(x)) s.erase(x);
    else s.in(x);
  }
  pr(s.size());
}
 
int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}

Measured memory_bytes: 4992
import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+1, N+1), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S = np.zeros((N+1, N+1), dtype=int)
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        S[i,:] = S[i-1,:] + A[i,:]
    for j in range(1, N+1):
        S[:,j] += S[:,j-1]
    res = []
    for i in range(Q):
        x1, x2 = p[i]-1, q[i]
        a = S[x2,x2]
        b = S[x1,x2]
        c = S[x2,x1]
        d = S[x1,x1]
        res.append(a - b - c + d)
    return "\n".join(map(str, res))

N, M, Q = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i], R[i] = map(int, input().split())
p, q = [0]*Q, [0]*Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())
print(solve(N, M, Q, L, R, p, q))

Measured memory_bytes: 41280
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define rep(i, n) for(int i = 0; i < n; i++)
#define repp(i, n) for(int i = 1; i <= n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define pb push_back
#define mp make_pair
#define riverse(v) reverse((v).begin(), (v).end())
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
const int MOD = 1e9+7;
vi alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m',
               'n','o','p','q','r','s','t','u','v','w','x','y','z'};

int main() {
	int A,B,C;
  	cin >> A >> B >>C;
  	if(A<=C &&C<=B)	cout << "Yes" << endl;
  	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>

using namespace std;

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

long long int INF = 1e18;
long long int mod = 1000000007;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "RULD";
//↓,→,↑,←

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl

ll rui(ll number1,ll number2){
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
    if(number1 > number2){
        swap(number1 , number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1 , number1);
    }
}

ll i,j,k,ii,jj,n,m,a,b,c,e,f,g,h,r,w,l,num,ans,sum,ok,ng;
ll x[500005],y[500005],z[500005];
ll ban[30][30];
ll dp[50][2100000];
char s[500005],t[500005],u[500005];
bool dame,flag;

int main(){
	cin >> n;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cin >> ban[i][j];
		}
	}
	dp[0][0] = 1;
	
	//i人目の男を使う
	for(j=0;j<(1 << n);j++){
		i = 0;
		for(k=0;k<n;k++){
			if(j & (1 << k))i++;
		}
		for(k=0;k<n;k++){
			if(ban[i-1][k] == 1 && (j & (1 << k))){
				dp[i][j] += dp[i-1][j ^ (1 << k)];
				dp[i][j] %= mod;
			}
		}
	}
	
	p(dp[n][(1 << n) - 1]);
	return 0;
}

Measured memory_bytes: 339072
n,k=map(int,input().split())
a=list(map(int,input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
if k in a:
    print("POSSIBLE")
elif k>max(a):
    print("IMPOSSIBLE")
else:
    x=a[0]
    for i in range(1,n):
        x=gcd(x,a[i])
    if k%x==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Measured memory_bytes: 63600
#include <bits/stdc++.h>
using namespace std;
#define INF 105

int n,k;
int a[INF];
int mem[100005][3];

bool rec(int tot,int player)
{
	if(mem[tot][player]!=-1) return mem[tot][player];
	bool ans=false;
	for(int i=0;i<n;i++)
	{
		if(tot-a[i]>0)
		{
			bool next=rec(tot-a[i],player^1);
			if(next==false)
			{
				ans=true;
			}
		}else
		if(tot-a[i]==0)
		{
			ans=ans|true;
		}
	}
	return mem[tot][player]=ans;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    memset(mem,-1,sizeof(mem));
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> a[i];
    bool ans=false;
	for(int i=0;i<n;i++)
	{
		bool next=rec(k-a[i],1);
		if(next==false)
		{
			ans=true;
		}
	}
	if(ans==true)
	{
		cout << "First" << "\n";
	}else
	{
		cout << "Second" << "\n";
	}
}

Measured memory_bytes: 7680
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

const int MAX = 1e6+1;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
  if(n >= MAX){
    ll tmp = 1;
    rep(i,k){
      tmp *= (n-i);
      tmp %= MOD;
    }
    return tmp*finv[k]%MOD;
  }

  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll POW(ll x, ll n){
  ll ret = 1;

  if(n < 0){// n < 0 にも対応
    n *= -1;
    x = inv[x];
  }

  while(0 < n){
    if(n%2 == 0){
      x = x*x%MOD;
      n /= 2;
    }
    else{
      ret = ret*x%MOD;
      n--;
    }
  }

  return ret;
}

int main(){
  int n,q; cin >> n >> q;
  vector<tuple<int,int,int>> a;
  rep(i,n) {
    int s,t,x; cin >> s >> t >> x;
    a.pb(make_tuple(x,s-x,t-x));
  }
  sort(all(a));
  set<pii> C;
  rep(i,q) {
    int d; cin >> d;
    C.insert(pii(d,i));
  }

  vi ans(q,-1);

  rep(i,n) {
    int x,l,r;
    tie(x,l,r) = a[i];
    auto p = C.lower_bound(pii(l,-1));
    while(p != C.end()){
      if(p->first >= r) break;
      ans[p->second] = x;
      C.erase(p++);
    }
  }
  rep(i,q) cout << ans[i] << endl;
}


Measured memory_bytes: 14832
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		int S = sc.nextInt();

		long ans = 0;
		for(int i=0; i<=K; i++)
			for(int j=0; j<=K; j++)
				if(0<=S-i-j && S-i-j<=K)
					ans++;
		
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 9812
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    ll a,b;
    cin>>a>>b;
    if( a > b )swap( a,b);
    for(int i=0;i<b;i++)cout<<a;
    cout<<endl;
    return 0;
}


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

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

    int cnt=0;

    rep(i,0,s.size()-1){
        if(s[i]!=s[i+1]){
            cnt++;
        }
    }

    cout<<cnt<<endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;
  vector<vector<int> > G(n);
  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  
  vector<int> mx(n,0);
  function<void(int, int, int)> dfs1=
    [&](int v,int p,int d){
      chmax(mx[v],d);
      for(int u:G[v]){
        if(u==p) continue;
        dfs1(u,v,max(v,mx[v]));
      }      
    };
  dfs1(0,-1,0);
  
  vector<map<int, int> > dp(n);
  function<int(int, int, int)> dfs4=
    [&](int v,int p,int d){
      if(dp[v].count(d)) return dp[v][d];
      int &res=dp[v][d];
      res=v<d;
      for(int u:G[v]){
        if(u==p||u>d) continue;
        res+=dfs4(u,v,d);
      }
      return res;
    };
  
  vector<int> ans(n,0);
  function<void(int, int)> dfs2=
    [&](int v,int p){      
      for(int u:G[v]){
        if(u==p) continue;
        dfs2(u,v);
      }
      if(p<0) return;
      ans[v]=1+dfs4(v,p,mx[v]);
      if(mx[v]>v) ans[v]-=1+(v<mx[p]?dfs4(v,p,mx[p]):0);      
    };
  dfs2(0,-1);
  
  function<void(int, int)> dfs3=
    [&](int v,int p){
      for(int u:G[v]){
        if(u==p) continue;
        ans[u]+=ans[v];
        dfs3(u,v);
      }
    };
  dfs3(0,-1);

  for(int i=1;i<n;i++){
    if(i>1) cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 51584
fn main() {
    let mut s = io::read_line();
    loop {
        s.pop();
        s.pop();
        let (front, back) = s.split_at(s.len() / 2);
        if front == back || s.len() == 0 {
            break;
        }
    }

    println!("{}", s.len());
}

pub mod io {
    use std::io;

    pub fn read_line() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }

    pub fn readln<T: Read>() -> T {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        T::read(s.trim())
    }

    pub trait Read {
        fn read(s: &str) -> Self;
    }

    impl Read for String {
        fn read(s: &str) -> Self {
            s.to_string()
        }
    }

    impl<T: Read> Read for Vec<T> {
        fn read(s: &str) -> Self {
            s.split_whitespace().map(|w| T::read(w)).collect()
        }
    }

    macro_rules !def_read {
        ($t : ty) => {
            impl Read for $t {
                fn read(s : &str)->$t { s.parse().unwrap() }
            }
        }
    }

    macro_rules !def_read_tuple {
        ($($t : ident), *) => {
            impl<$($t : Read + Default), *> Read for ($($t), *) {
                fn read(s : &str)->Self {
                    let mut iter = s.split_whitespace();
                    ($($t::read(iter.next().unwrap())), *)
                }
            }
        };
    }

    def_read!(i32);
    def_read!(i64);
    def_read!(isize);
    def_read!(usize);
    def_read!(f32);
    def_read!(f64);
    def_read_tuple!(T0, T1);
    def_read_tuple!(T0, T1, T2);
    def_read_tuple!(T0, T1, T2, T3);
    def_read_tuple!(T0, T1, T2, T3, T4);
}

Measured memory_bytes: 4352
import java.util.Scanner;

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

        


Measured memory_bytes: 26352
import typing
def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())*2
ans=n-1
i=2
factors=[]
while i*i<=n:
  if n%i==0:
    tmp=1
    while n%i==0:
      n=n//i
      tmp=tmp*i
    factors.append(tmp)
  else:
    i+=1
if n!=1:
  factors.append(n)
for i in range(2**len(factors)):
  s=base10toN(i,2)
  slist=[]
  for j in s:
    slist.append(j)
  slist.reverse()
  for j in range(len(factors)-len(s)):
    slist.append('0')
  left=1
  right=1
  for j in range(len(factors)):
    if slist[j]=='0':
      left=left*factors[j]
    else:
      right=right*factors[j]
  if left*_inv_gcd(left,right)[1]>1:
    ans=min(ans,left*_inv_gcd(left,right)[1]-1)
print(ans)
      

Measured memory_bytes: 71056
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    sort(S.begin(), S.end());
    if (S == "abc") {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main(){
  int N, ans=0;
  cin >> N;
  int X[N];
  for(int i=0; i<N; i++){
    cin >> X[i];
    ans += 100 * 100;
  }

  for(int P=1; P<101; P++){
    int tmp=0;
    for(int i=0; i<N;i++){
      tmp += (X[i]-P) * (X[i]-P);
    }
    if(ans > tmp){
      ans = tmp;
    }
  }

  printf("%d\n", ans);
}


Measured memory_bytes: 3744
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>

using namespace std;
using vec = vector<int>;
using lst = list<int>;

bool solve()
{
    int n,l,r;
    cin >> n >> l >> r;

    if(n==0)return 0;

    vec ar(r-l+1);
    lst A;

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

    while(!A.empty())
    {
        for(int i=l;i<=r;++i)
        {
            if(i%A.back()==0)
            {
                ar[i-l] = A.size() % 2;
            }
        }
        A.pop_back();
    }

    int ans = 0;
    for(int i=l;i<=r;++i)
    {
        ans += ar[i-l];
    }

    cout << ans << endl;

    return true;
}

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



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

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

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

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N;
int B[100010];

int main() {
    cin >> N;
    for (int i = 0; i < N-1; ++i) cin >> B[i];

    int ans = B[N-2];
    for (int i = N-2; i > 0; --i) {
        ans += min(B[i], B[i-1]);
    }
    ans += B[0];
    cout << ans << endl;
    return 0;
}

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

int main(){
  int N; cin >>N;
  int A[N];
  ll sum = 0;
  map<ll,ll> mp;
  for(int i=0;i<N;i++){
    cin >> A[i];
    sum += A[i];
    mp[A[i]]++;
  }
  sort(A,A+N);
  int Q; cin >>Q;
  ll B[Q],C[Q],d[Q];
  
  for(int i=0;i<Q;i++){
    cin >> B[i] >> C[i];
    d[i] = C[i]-B[i];
  }
  for(int i=0;i<Q;i++){
    sum += mp[B[i]]*d[i];
    mp[C[i]]+= mp[B[i]];
    mp[B[i]]=0;
    cout << sum << endl;
  }
  
  
}

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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

struct modint {
    static constexpr int MOD = 998244353;
    ll v;

    bool operator==(const modint& other) const {
        return v == other.v;
    }

    modint& operator+=(const modint& other) {
        v += other.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }

    modint& operator-=(const modint& other) {
        v -= other.v;
        if (v < 0)
            v += MOD;
        return *this;
    }

    modint& operator*=(const modint& other) {
        v = v * other.v % MOD;
        return *this;
    }

    modint& operator/=(const modint& other) {
        *this *= other.inv();
        return *this;
    }

    modint operator+(const modint& other) const {
        return modint { v } += other;
    }

    modint operator-(const modint& other) const {
        return modint { v } -= other;
    }

    modint operator*(const modint& other) const {
        return modint { v } *= other;
    }

    modint operator/(const modint& other) const {
        return modint { v } /= other;
    }

    static modint pow(modint b, ll e) {
        modint res { 1 };
        for (ll p = 1; p <= e; p <<= 1) {
            if (p & e)
                res *= b;
            b *= b;
        }

        return res;
    }

    modint pow(ll e) const {
        return pow(*this, e);
    }

    modint inv() const {
        return pow(MOD - 2);
    }

    friend ostream& operator<<(ostream& os, modint m) {
        return os << m.v;
    }
};

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

    int n;
    cin >> n;

    modint ans = modint::pow(modint { 3 }, n);
    modint cur = { 0 };
    modint term = { 1 };
    modint p = { 2 };
    // n choose k * 2^k for k in range()
    for (int k = n; k > n / 2; --k) {
        cur += term * p;
        // going from n!/k!(n-k)! to n!/(k-1)!(n-k+1)!
        // multiply by k/(n-k+1)
        term /= modint { n - k + 1 };
        term *= modint { k };
        p += p;
    }

    cout << ans - cur << '\n';
 
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
int n, k, p[110], dp[110][4][4];//day,plan|1 origin!

int s(int now, int typ, int ren) {//now>>n日目まで、同種類ren日連続
	if (ren == 3)return 0;
	if (now == n)return 1;
	if (dp[now][typ][ren] != -1)return dp[now][typ][ren];
	if (p[now] != -1) {
		if (typ == p[now])dp[now][typ][ren] = s(now + 1, typ, ren + 1);
		else {
		dp[now][typ][ren] = s(now + 1, p[now], 1);
		}
	}
	else {
		dp[now][typ][ren] = s(now + 1, typ, ren + 1) + s(now + 1, (typ + 1) % 3, 1) + s(now + 1, (typ + 2) % 3, 1);
	}
	dp[now][typ][ren] %= 10000;
	return dp[now][typ][ren];
}


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

	for (int i = 0; i <= n; i++) {
		p[i] = -1;
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++)dp[i][j][k] = -1;
		}
	}

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		p[a-1] = b % 3;
	}

	cout << s(0, 0, 0)%10000 << endl;

	return 0;
}



Measured memory_bytes: 3100
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int A[1000000], n;

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

  int q, k, sum=0;

  cin >> q;
  for(int i=0; i<q; i++){
    scanf("%d", &k);
    if (*lower_bound(A, A+n, k) == k) sum++;
  }

  cout << sum << endl;
  return 0;
}

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

int main() {
  ll N = 0;
  map <string,ll> mp;
  cin >> N;
  rep(i,N){
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    mp[S]++;
  }
  ll ans = 0;
  for (auto p : mp) {
    ans += p.second * (p.second - 1) / 2;
  }
  cout << ans;
}
  
  

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	int cnt=0;
	cin>>a;
	for (int i=0;i<a.size();i++)
		cnt+=(int)(a[i]-'0');
	cout<<(cnt%9?"No":"Yes")<<endl;
	return 0;
}


Measured memory_bytes: 3752
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;

int N;
int num[101];
ll dp[101][21];
ll solve(int ,int);
int main(void){
	cin >> N;
	fill_n(*dp, 101*21, -1);
	for(int i = 0; i < N; i++){
		cin >> num[i];
	}
	cout << solve(1,num[0]) << endl;

}

ll solve(int now, int sum){
	if(sum < 0 || sum > 20){return 0;}
	if(dp[now][sum] != -1){return dp[now][sum];}
	if(now == N-1){
		if(sum == num[N-1]){return 1;}
		else return 0;
	}
	return dp[now][sum] = solve(now+1, sum+num[now])+solve(now+1, sum-num[now]);

}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

const int N = 100000;
vector<bool> isp(N + 1, true);

void sieve(){
    isp[0] = false;
    isp[1] = false;
    for (int i = 2; i < N; i++){
        if(isp[i]){
            for (int j = 2; i * j <= N; j++){
                isp[i * j] = false;
            }
        }
    }
}

int main(){
    int q;
    cin >> q;
    sieve();
    vector<int> num(100001,0);
    for (int i = 1; i < 100001; ++i)
    {
        if(i%2==0)
            continue;
        if (isp[i] && isp[(i + 1) / 2])
            num[i]++;
    }
    rep(i, 100001) num[i + 1] += num[i];
    int l, r;
    rep(i, q)
    {
        cin >> l >> r;
        cout << num[r] - num[l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

ll cnto[3010][3010];
ll cnti[3010][3010];
char fi[3010][3010];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int h,w; cin >> h >> w;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> fi[i][j];
		}
	}
	for(int i=0;i<h;i++){
		for(int j=w-1;j>0;j--){
			if(fi[i][j]=='O'){
				cnto[i][j-1]=cnto[i][j]+1;
			}
			else{
				cnto[i][j-1]=cnto[i][j];
			}
		}
	}
	for(int i=0;i<w;i++){
		for(int j=h-1;j>0;j--){
			if(fi[j][i]=='I'){
				cnti[j-1][i]=cnti[j][i]+1;
			}
			else{
				cnti[j-1][i]=cnti[j][i];
			}
		}
	}
	ll ans=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(fi[i][j]=='J'){
				ans+=cnto[i][j]*cnti[i][j];
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 153092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(), (x).end()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end());
// map<int,int> mp;

int main() {
  int A, B;
  cin >> A >> B;
  if (A >= 13) {
    cout << B << endl;

  } else if (A >= 6) {
    cout << B / 2 << endl;

  } else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int d = sc.nextInt();
		Map<Integer, Integer> hs = new HashMap<>();
		Map<Integer, Integer> ws = new HashMap<>();

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				int x = sc.nextInt() - 1;
				hs.put(x, i);
				ws.put(x, j);
			}
		}

		int maxSteps = (h * w / d) + 1;
		int[][] costs = new int[d][maxSteps];

		for (int i = 0; i < d; i++) {
			int ihPrev = hs.get(i);
			int iwPrev = ws.get(i);
			int steps = 1;
			while (steps < maxSteps) {
				if (i + steps * d > h * w - 1) break;
				int ih = hs.get(i + steps * d);
				int iw = ws.get(i + steps * d);
				costs[i][steps] = Math.abs(ih - ihPrev) + Math.abs(iw - iwPrev) + costs[i][steps - 1];
				ihPrev = ih;
				iwPrev = iw;
				steps++;
			}
		}

		int q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		while (q-- > 0) {
			int l = sc.nextInt() - 1;
			int r = sc.nextInt() - 1;
			sb.append(costs[r % d][r / d] - costs[l % d][l / d]);
			sb.append("\n");
		}

		System.out.print(sb.toString());
	}
}


Measured memory_bytes: 104272
from collections import deque

s = deque(input())
q = int(input())
flag = 0
for i in range(q):
    query = list(input().split())
    if query[0] == "1":
        flag = (flag+1)%2
    else:
        if flag == 0:
            if query[1] == "1":
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if query[1] == "2":
                s.appendleft(query[2])
            else:
                s.append(query[2])

s = list(s)
if flag == 0:
    for i in s:
        print(i, end="")
if flag == 1:
    l = len(s)
    for i in range(l):
        print(s[l-i-1], end="")

print()

Measured memory_bytes: 95576
from collections import deque
N,M,Q = map(int,input().split())

numbers = deque([[i+1] for i in range(M)])

for i in range(N):
    a = deque([])
    while numbers:
        l = numbers.pop()
        b = l[-1]
        for j in range(b,M+1):
            a.append(l+[j])
    numbers = a

X = []
for i in range(Q):
    a,b,c,d = map(int,input().split())
    X.append((a,b,c,d))

ans = 0
while numbers:
    cnt = 0
    L = numbers.pop()
    for x in X:
        a,b,c,d = x
        if L[b-1]-L[a-1]==c:
            cnt+=d
    ans = max(ans,cnt)
print(ans)

Measured memory_bytes: 137600
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
typedef pair<int, int> P;
class BiOp1 {
public:
	ll operator()(ll a, ll b) const {
		return max(a, b);
	}
};
class BiOp2 {
public:
	ll operator()(ll a, ll b) const {
		return a + b;
	}
};
class BiOp3 {
public:
	ll operator()(ll a, ll b) const {
		return a + b;
	}
};
template<class T1, class T2, class BiOp1, class BiOp2, class BiOp3>
struct LazySegmentTree {
	//BiOp1:T1×T1->T1
	//BiOp2:T2×T2->T2
	//BiOp3:T1×T2->T1
	vector<T1> data;
	vector<T2> lazy;
	T1 e1;
	T2 e2;
	BiOp1 op1;
	BiOp2 op2;
	BiOp3 op3;
	int size;
	LazySegmentTree(int n, T1 init, T1 e1, T2 e2, BiOp1 op1, BiOp2 op2, BiOp3 op3) :e1(e1), e2(e2), op1(op1), op2(op2), op3(op3) {
		size = 1;
		while (size < n) size *= 2;
		data.resize(size * 2 - 1);
		lazy.resize(size * 2 - 1);
		for (int i = 0; i < size * 2 - 1; i++) {
			data[i] = init;
			lazy[i] = e2;
		}
	}
	void push(int k) {
		if (lazy[k] == e2) return;
		if (k < size) {
			lazy[k * 2 + 1] = op2(lazy[k * 2 + 1], lazy[k]);
			lazy[k * 2 + 2] = op2(lazy[k * 2 + 2], lazy[k]);
		}
		data[k] = op3(data[k], lazy[k]);
		lazy[k] = e2;
	}
	T1 query(int a, int b, int k, int l, int r) {
		if (b <= l || r <= a) return e1;
		if (a <= l && r <= b) return op3(data[k], lazy[k]);
		push(k);
		return op1(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
	T1 get(int x) {
		return query(x, x + 1, 0, 0, size);
	}
	void update(int a, int b, T2 v, int k, int l, int r) {
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lazy[k] = op2(lazy[k], v);
			return;
		}
		push(k);
		update(a, b, v, k * 2 + 1, l, (l + r) / 2);
		update(a, b, v, k * 2 + 2, (l + r) / 2, r);
		data[k] = op1(op3(data[k * 2 + 1], lazy[k * 2 + 1]), op3(data[k * 2 + 2], lazy[k * 2 + 2]));
	}
	void update(int a, int b, T2 v) {
		update(a, b, v, 0, 0, size);
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	vector<P> taka;
	for (int i = 0; i < N; i++) {
		int L, R;
		cin >> L >> R;
		taka.emplace_back(L, R);
	}
	sort(taka.begin(), taka.end());
	LazySegmentTree<ll, ll, BiOp1, BiOp2, BiOp3> seg(M + 10, 0, -INF, 0, BiOp1(), BiOp2(), BiOp3());
	for (int i = 1; i <= M; i++) {
		seg.update(i, i + 1, -(M - i + 1));
	}
	ll ans = N - M;
	for (int i = 0; i < N; i++) {
		seg.update(1, taka[i].second + 1, 1);
		ll cnt = seg.query(taka[i].first + 1, seg.size, 0, 0, seg.size);
		cnt -= taka[i].first;
		ans = max(ans, cnt);
	}
	cout << max(ans, 0LL) << endl;
}


Measured memory_bytes: 10096
import math
import sys
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())

S = []
for h in range(H):
    s = input()
    t = []
    for ss in s:
        if ss==".":
            t.append(True)
        else:
            t.append(False)
    S.append(t)

# print(S)

V = H*W

d = [[float("inf") for i in range(V)] for j in range(V)]

for h in range(H):
    for w in range(W):
        i = h*W+w
        if S[h][w]:
            if 0<=h<=H-2 and S[h+1][w]:
                j = (h+1)*W+w
                d[i][j], d[j][i] = 1,1
            if 1<=h<=H-1 and S[h-1][w]:
                j = (h-1)*W+w
                d[i][j], d[j][i] = 1,1
            if 0<=w<=W-2 and S[h][w+1]:
                j = h*W+(w+1)
                d[i][j], d[j][i] = 1,1
            if 1<=w<=W-1 and S[h][w-1]:
                j = h*W+(w-1)
                d[i][j], d[j][i] = 1,1

# print(d)

def warshall_floyd(d, V): 
    # dd = [[float("inf") for i in range(V)] for j in range(V)]
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

# 例一個作ってみる．
dd = warshall_floyd(d, V)

# print(dd)
mx = 0
for i,ddd in enumerate(dd):
    for j,n in enumerate(ddd):
        if math.isfinite(n) and i!=j:
            mx = max(mx, n)

print(mx)

# 6 4
# #...
# #.#.
# #...
# #.#.
# #.#.
# #.#.

# 2 1
# .
# .



Measured memory_bytes: 135432
def ret_kaibun(Str):
    lens = len(Str)
    #print(Str)
    if lens > 3:
        a = ret_kaibun(S[0:int(lens/2)])
        b = ret_kaibun(S[int((lens+3)/2-1):lens])
        if a == 1 and b == 1:
            return 1
    else:
        if not Str[0] == Str[int((lens+1)/2)]:
            return 0
        return 1
    return 0
def kaibun(S):
    for i in range(int(len(S)/2)):
        if not S[i] == S[len(S)-i-1]:
            return 0
    return 1

if __name__ == '__main__':
    S = input()
    lens = len(S)
    check1 = kaibun(S)
    check2 = kaibun(S[0:int(lens/2)])
    check3 = kaibun(S[int((lens+3)/2-1):lens])
    if check1 == 1 and check2==1 and check3==1:
        print('Yes')
    else:
        print('No')
        #ret = ret_kaibun(S)
        #if ret == 1 and check == 1:
        #    print('Yes')
        #else:
        #    print('No')


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

int n;
int a[100005], l[100005], r[100005];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	l[0] = a[0]; r[n-1] = a[n-1];

	for (int i = 1; i < n; i++) {
		l[i] = __gcd(l[i-1], a[i]);
	} 
	for (int i = n-2; i >= 0; i--) {
		r[i] = __gcd(r[i+1], a[i]);
	}

	int x=max(l[n-2], r[1]);
	for (int i = 1; i < n-1; i++) {
		x = max(x, __gcd(l[i-1],r[i+1]));
	}
	cout << x << endl;
}

Measured memory_bytes: 1408
import sys
n, m, k = [int(i) for i in sys.stdin.readline().split()]
flg = False
for y in range(n + 1):
    for x in range(m + 1):
        if y * (m - x) + x * (n - y) == k:
            flg = True
if flg:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3316
#include <stdio.h>
#include <math.h>

#define ELEMENT_CNT_MIN 1
#define ELEMENT_CNT_MAX 100
#define ELEMENT_MIN 0
#define ELEMENT_MAX 100

int bubble_sort(int *p_arr, int size);
void swap(int *px, int *py);
void put_arr(int *p_arr, int size);
int get_int_sequence(int *p_num, int min, int max, int size);
int get_int(int *p_num, int min, int max);
int judge_constraint(int test_num, int min, int max);


int main(void){
    
    int element_num;
    int element[ELEMENT_CNT_MAX];
    int cnt_exchange;
    
    if(get_int(&element_num, ELEMENT_CNT_MIN, ELEMENT_CNT_MAX) == -1)
    {
        return -1;
    }
    
    if(get_int_sequence(&element[0], ELEMENT_MIN, ELEMENT_MAX, element_num) == -1)
    {
        return -1;
    }
    
    cnt_exchange = bubble_sort(&element[0], element_num);
    
    put_arr(&element[0], element_num);
    printf("%d\n", cnt_exchange);
    
    return 0;
}

int bubble_sort(int *p_arr, int size)
{
    int i;
    int j;
    int cnt = 0;
    
    for(i = 0; i < size - 1; i++)
    {
        for(j = size - 1; j > i; j--)
        {
            if(p_arr[j] < p_arr[j - 1])
            {
                swap(&p_arr[j], &p_arr[j - 1]);
                cnt++;
            }
        }
    }
    
    return cnt;
}

void swap(int *px, int *py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
    
    return;
}

void put_arr(int *p_arr, int size)
{
	int i;
	
	for(i = 0; i < size - 1; i++)
	{
	    printf("%d ", p_arr[i]);
	}
	printf("%d\n", p_arr[size - 1]);
}

int get_int_sequence(int *p_num, int min, int max, int size)
{
    int i;
    
    for(i = 0; i < size; i++)
    {
        if(get_int(&p_num[i], min, max) == -1)
        {
            return -1;
        }
    }
    
    return 0;
}

int get_int(int *p_num, int min, int max)
{
	scanf("%d", p_num);
	
	if(judge_constraint(*p_num, min, max) == -1)
    {
        return -1;
    }
	
	return 0;
}
int judge_constraint(int test_num, int min, int max)
{
    if(test_num < min || test_num > max)
    {
        return -1;
    }
    
    return 0;
}

Measured memory_bytes: 1816
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define mx 200005
#define fr first
#define se second
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

string s1,s2;
ll dp[3003][3003];
string ans="";
ll func(ll i, ll j)
{
    if(s1[i] == 0 || s2[j] == 0) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    ll ans1=0,ans2=0,ans3=0;
    if(s1[i] == s2[j]){
        ans1 = 1+func(i+1,j+1);
    }
    ans2 = func(i+1,j);
    ans3 = func(i,j+1);
    return dp[i][j] = max({ans1,ans2,ans3});
}

void Print(ll i, ll j)
{
    if(s1[i] == 0 || s2[j] == 0){
        cout << ans << "\n";
        return;
    }
    if(s1[i] == s2[j]){
        ans+=s1[i];
        Print(i+1,j+1);
    }
    else{
        if(dp[i][j+1]>dp[i+1][j]) Print(i,j+1);
        else Print(i+1,j);
    }
}

int main()
{
   fast;
   memset(dp,-1,sizeof dp);
   cin >> s1 >> s2;
   ll k = func(0,0);
   //cout << k;
   Print(0,0);
   return 0;
}


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

using str = string;
using ss = stringstream;

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

    int n,a,b,c,d;cin>>n>>a>>b>>c>>d;
    a--;b--;c--;d--;
    str s;cin>>s;

    vector<int> v;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(v.size()%2)
        {
            if(s[i]=='.'){v.push_back(cnt);cnt=0;}
        }
        else
        {
            if(s[i]=='#'){v.push_back(cnt);cnt=0;}
        }
        cnt++;
    }
    v.push_back(cnt);

    bool ans=true;

    int posa=0,suma=0;
    for(auto vv:v){suma+=vv;if(suma>a)break;posa++;}
    
    int posb=0,sumb=0;
    for(auto vv:v){sumb+=vv;if(sumb>b)break;posb++;}
    
    int posc=0,sumc=0;
    for(auto vv:v){sumc+=vv;if(sumc>c)break;posc++;}
    
    int posd=0,sumd=0;
    for(auto vv:v){sumd+=vv;if(sumd>d)break;posd++;}

    for(int i=posa+1;i<posc;i+=2)if(v[i]>=2){ans=false;break;}
    for(int i=posb+1;i<posd;i+=2)if(v[i]>=2){ans=false;break;}

    if(d<c)
    {
        bool f=false;
        for(int i=posb+2;i<posd;i+=2)if(v[i]>=3){f=true;break;}

        f|=(s[b-1]=='.'&&s[b+1]=='.')||(s[b+1]=='.'&&s[b+2]=='.');
        f|=(s[d-1]=='.'&&s[d+1]=='.')||(s[d-1]=='.'&&s[d-2]=='.');
        
        ans&=f;
    }

    puts(ans?"Yes":"No");

    return 0;
}


Measured memory_bytes: 4468
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main(){
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
program checker
  implicit none
  integer :: n, k, x, y, m, t
  integer :: i, j, g(0:4000,0:4000)
  character(1) :: c
  g = 0
  read(*,*) n, k
  do i = 1, n
    read(*,*) x, y, c
    if (c.eq."W") y = y + k
    x = mod(x,2*k)+1
    y = mod(y,2*k)+1
    g(x,y) = g(x,y) + 1
    g(x,y+2*k) = g(x,y+2*k) + 1
    g(x+2*k,y) = g(x+2*k,y) + 1
    g(x+2*k,y+2*k) = g(x+2*k,y+2*k) + 1
  end do
  do i = 1, 4*k
    do j = 1, 4*k
      g(i,j) = g(i,j) + g(i,j-1)
    end do
  end do
  do j = 1, 4*k
    do i = 1, 4*k
      g(i,j) = g(i,j) + g(i-1,j)
    end do
  end do
  m = 0
  do i = 0, 2*k
    do j = 0, 2*k
      t = g(i+2*k,j+2*k) + 2*g(i+k,j+k) + g(i,j) &
      & - (g(i+2*k,j+k) + g(i+k,j+2*k) + g(i+k,j) + g(i,j+k))
      if (m.lt.t) m = t
    end do
  end do
  write(*,'(i0)') m
  stop
end program checker

Measured memory_bytes: 62848
import java.util.*;

class Main{

    void solve(){
        Scanner sc = new Scanner(System.in);

        long INF = Long.MAX_VALUE;

        while(true){
            int n = sc.nextInt(), m = sc.nextInt();
            if(n==0 && m==0) break;

            int[] c = new int[m];
            for(int i=0; i<m; i++) c[i] = sc.nextInt();

            int[] x = new int[n];
            for(int i=0; i<n; i++) x[i] = sc.nextInt();

            long[][] dp = new long[n+1][256];
            for(int i=0; i<=n; i++) Arrays.fill(dp[i], INF);
            dp[0][128] = 0;

            for(int i=1; i<=n; i++){
                for(int j=0; j<=255; j++){
                    if(dp[i-1][j]==INF) continue;
                    for(int k=0; k<m; k++){
                        int idx = j+c[k];
                        if(idx<0) idx = 0;
                        if(idx>255) idx = 255;
                        dp[i][idx] = Math.min(dp[i][idx], dp[i-1][j] + (long)Math.pow((x[i-1]-idx), 2));
                    }
                }
            }

            long min = INF;
            for(int i=0; i<=255; i++) min = Math.min(min, dp[n][i]);
            System.out.println(min);
        }
    }

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

Measured memory_bytes: 145236
#include <bits/stdc++.h>
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
using namespace std;

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+9;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n;
	cin >> n;
	cout << n * (n + 1) / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
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 d = a / b;
		int r = a % b;
		double f = (double) a / b;

		System.out.printf(d + " " + r + " " + "%.5f",f);
	}

}

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

typedef long long ll;

int main(){
    int W, H, N;
    cin >> W >> H >> N;
    int area[W][H];
  	for(int i=0;i<W;i++){
        for(int j=0;j<H;j++){
            area[i][j]=0;
        }
    }

    int check[3];

    for(int i = 0; i<N; i++){
        for(int j=0;j<3;j++){
            cin >> check[j];
        }
        switch (check[2]){
            case 1:
                for(int i=0;i<check[0];i++){
                    for(int j=0;j<H;j++){
                        area[i][j] = 1;
                    }
                }
                break;
            case 2:
                for(int i=check[0];i<W;i++){
                    for(int j=0;j<H;j++){
                        area[i][j] = 1;
                    }
                }
                break;
            case 3:
                for(int i=0;i<W;i++){
                    for(int j=0;j<check[1];j++){
                        area[i][j] = 1;
                    }
                }
                break;
            case 4:
                for(int i=0;i<W;i++){
                    for(int j=check[1];j<H;j++){
                        area[i][j] = 1;
                    }
                }
                break;
        }
    }
    int result;
    for(int i = 0;i<W;i++){
        for(int j=0;j<H;j++){
            if(area[i][j]==	0){
                result++;
            }
        }
    }
    printf("%d\n",result);
    return 0;
}


Measured memory_bytes: 256
cardNumber = int(input())
Taro = 0
Hanako = 1
TaroScore = 0
HanakoScore = 0
winIndex = 0

for drawNumber in range(cardNumber):
    card = input().split(" ")
    sortedCard = sorted(card, reverse=True)
    winCard = card[card.index(sortedCard[winIndex])]
    if card[Taro] == winCard and card[Hanako] == winCard:
        TaroScore += 1
        HanakoScore += 1
    elif card[Taro] == winCard and card[Hanako] != winCard:
        TaroScore += 3
    elif card[Taro] != winCard and card[Hanako] == winCard:
        HanakoScore += 3
print("%d %d" %(TaroScore,HanakoScore))


Measured memory_bytes: 5596
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a) for(ll i=0;i<a;i++)
#define jkl ll debug = 0;
#define RREP(i,a) for(ll i=a-1;i>=0;i--)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define printall(n,array) {for(ll i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> Pi;
typedef pair<ll, Pi> V;
typedef vector<ll> VE;
const ll mod = 1e9 + 7; //10^9+7


int main(){
    int n, k;
    cin >> n >> k;
    int cnt;
    if(n%2){cnt = n / 2 + 1;}
    else{cnt = n / 2;}
    if(cnt>=k){print("YES");}
    else{print("NO");}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // clang-format off
using namespace std;
using Int = long long;
#define REP2(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REP3(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define OVERLOAD2(_1, _2, _3, name, ...) name
#define REP(...) OVERLOAD2(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
struct SetupIO { SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Feb 22 21:00:01 JST 2020
 **/

signed main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    REP(i, n) cin >> a[i];
    Int mean = double(accumulate(a.begin(), a.end(), 0LL)) / n + 0.5;
    Int ans = 0;
    REP (i, n) {
        ans += (mean - a[i]) * (mean - a[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def factorial(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
a,b,c,k = inp
if(k%2 == 1)
  if ((b-a).abs > 10**18)
    p 'Unfair'
  end
  p b-a
else
  if ((b-a).abs > 10**18)
    p 'Unfair'
  end
  p a-b
end

Measured memory_bytes: 1788
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MMAX 500000

struct Node{
  int key;
  struct Node *left;
  struct Node *right;
  struct Node *parent;
};

struct Node *root, *NIL;

void insert(int k){
  struct Node *y = NIL;
  struct Node *x = root;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key){
      x = x->left; //　大事　//
    }else{
      x = x->right; // 大事　//
    }
  }
  z->parent = y;
  if(y == NIL){
    root = z;
  }else{
    if(z->key < y->key){
      y->left = z;
    }else{
      y->right = z;
    }
  }
}

void inorder(struct Node *u){
  if(u == NIL){
    return;
  }
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(struct Node *u){
  if(u == NIL){
    return;
  }
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

void *find(struct Node *u,int k){
  while((u != NIL) && (k != u->key)){
    if(k < u->key){
      u = u->left;
    }else{
      u = u->right;
    }
  }
    return u;
}

int main(void){
  int m,i,x;
  char com[6];
  struct Node *t;
  scanf("%d",&m);

  for(i = 0;i < m;i++){
    scanf("%s",com);
    if(strcmp(com,"insert") == 0){
      scanf("%d",&x);
      insert(x);
    }else if(strcmp(com,"print") == 0){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(strcmp(com,"find") == 0){
      scanf("%d",&x);
      t = find(root,x);
      if(t != NIL){
	printf("yes\n");
      }else{
	printf("no\n");
      }
    }
  }

  return 0;
}
   
		       



Measured memory_bytes: 20448