akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

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

    vector<long long> B(N + 1);
    B[0] = 0;
    for (int i = 0; i <= N; i++)
        B[i] = A[i - 1] + B[i - 1];

    unordered_map<int, int> hash;
    for (int i = 0; i <= N; i++)
        hash[B[i] % M]++;

    long long res = 0;
    for (auto it = hash.begin(); it != hash.end(); it++) {
        pair<int, int> p = *it;
        res += (long long)p.second * (p.second - 1) / 2;
    }

    cout << res << endl;
    return 0;
}



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

#define LL long long
typedef pair<int, int> pii;

template< typename T > inline void read(T &x)
{
    static char _c;
    static bool _f;

    x = 0;
    _f = 0;
    _c = getchar();

    while(_c < '0' || '9' < _c) {if(_c == '-') _f = true; _c = getchar();}
    while('0' <= _c && _c <= '9') {x = (x << 1) + (x << 3) + (_c & 15); _c = getchar();}
    if(_f) x = -x;
}

template < typename T > inline void Min(T &x, T y) {if(y < x) x = y;}
template < typename T > inline void Max(T &x, T y) {if(x < y) x = y;}


#define lowbit(x) ((x) & -(x))
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(l,r) ((l)+(((r)-(l))>>1))
#define fi first
#define se second
#define mk make_pair
#define pb push_back

const int INF = 0x3f3f3f3f;
const int MOD = (int) 1e9 + 7;
//const int MOD = (int) 998244353;
const int maxn = (int) 2e5 + 20;
const int maxm = (int) 1e6 + 20;
const double pi = (double) acos(-1.0);
const double eps = (double) 1e-8;

inline int sig(double x) {return x < -eps ? -1 : eps < x;}
LL fp(LL a, LL n, LL m = MOD) {LL res = 1; for(; n; n >>= 1, a = a * a % m) if(n & 1) res = res * a % m; return res;}

int n, k;
int a[maxn];

void work()
{
    cin >>n >>k;
    for(int i = 0; i < n; i++) cin >>a[i];
    sort(a, a + n);

    LL ans = 0;
    for(int i = 0; i < n - k; i++) ans += a[i];
    cout <<ans <<endl;
}

int main()
{
#ifdef yukihana0416
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // yukihana0416
//    get_prime();
    int tc = 1;
//    read(tc);
    for(int ca = 1; ca <= tc; ca++)
    {
//        printf("Case #%d: ", ca);
        work();
    }
    return 0;
}


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

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define clr(ar, val) memset(ar, val, sizeof(ar))
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 gcd(int a,int b){return b?gcd(b,a%b):a;}
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main(void)
{
	int n, p[20], t[3], ans = 0;
	cin >> n;
	rep(i, n) cin >> p[i];
	repp(i, 1, n - 1){
		t[0] = p[i-1];t[1] = p[i];t[2] = p[i+1];
		sort(t, t + 3);
		if(p[i] == t[1]) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void)
{
    int N[4];
    cin >> N[0] >> N[1] >> N[2] >> N[3];
    int judge=1;
    for(int i=0;i<4;i++){
        if(N[i]==1) judge *= 2;
        else if(N[i]==9) judge *= 3;
        else if(N[i]==7) judge *= 5;
        else if(N[i]==4) judge *= 7;
    }
    if(judge==210){
        cout << "YES" << endl;
        return 0;
    }
    else{
        cout << "NO" << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define repe1(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
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; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a * b / gcd(a, b);}

int main() {
  ll a,b;
  cin >> a >> b;
  cout << lcm(a,b) << "\n";
}


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

int main() {
	for(int c=1;;c++) {
		int n; cin >> n;
		if(!n) return 0;
		
		int x[55] = {}, y[55] = {};
		for(int i = 0; i < n; i++) {
			cin >> x[i] >> y[i];
		}
		x[n] = x[0], y[n] = y[0];
		
		double area = 0;
		
		for(int i = 0; i < n; i++) {
			area += .5 * ( x[i]*y[i+1] - x[i+1]*y[i] );
		}
		
		area = abs(area);
		
		printf("%d %0.1lf\n",c,area); 
	}
}

Measured memory_bytes: 3192
//49
#include<iostream>
#include<algorithm>

using namespace std;

struct E{
  int t,s,d;
  bool operator<(E a)const{
    return t<a.t;
  }
};

int main(){
  for(int n,m;cin>>n>>m,n|m;){
    E p[20000];
    for(int i=0;i<m;i++){
      int t,s,d;
      cin>>t>>s>>d;
      E c={t,s,d};
      p[i]=c;
    }
    sort(p,p+m);
    bool in[20001]={false,true};
    for(int i=0;i<m;i++){
      in[p[i].d]|=in[p[i].s];
    }
    cout<<count(in,in+n+1,true)<<endl;;
  }
  return 0;
}

Measured memory_bytes: 1436
#include <stdio.h>
#include <algorithm>
int n, k, s, t, a, b, e;
long long p = 1000000007;
long long c;
long long x[200000];
long long y[200000];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &c);
		if (c < 0) {
			x[s] = c;
			s++;
		}
		if (c > 0) {
			y[t] = c;
			t++;
		}
	}
	if (s + t < k) {
		printf("0\n");
		return 0;
	}
	std::sort(x, x + s);
	std::sort(y, y + t);
	c = 1;
	if (t == 0) {
		if (k % 2) {
			if (s + t < n)c = 0;
			for (int i = 0; i < k; i++) {
				c *= -x[s - 1 - i];
				c %= p;
				c = p - c;
			}
		}
		else {
			for (int i = 0; i < k; i++) {
				c *= -x[i];
				c %= p;
				c = p - c;
			}
		}
		printf("%lld\n", c % p);
		return 0;
	}
	b = t - 1;
	for (int i = 0; i < k; i++) {
		if (b == -1) {
			a++;
			e++;
		}
		else if (a == s) {
			b--;
		}
		else {
			if (-x[a] > y[b]) {
				a++;
				e++;
			}
			else {
				b--;
			}
		}
	}
	if (e % 2) {
		if ((b == -1 && a != s) || a == 0) {
			a++;
			b++;
		}
		else if ((b != -1 && a == s) || b == t - 1) {
			a--;
			b--;
		}
		else if (b != -1 && a != s) {
			if (x[a] * x[a - 1] > y[b + 1] * y[b]) {
				a++;
				b++;
			}
			else {
				a--;
				b--;
			}
		}
	}
	if (a % 2 && s + t < n)c = 0;
	for (int i = 0; i < a; i++) {
		c *= -x[i];
		c %= p;
		c = p - c;
	}
	for (int i = b + 1; i < t; i++) {
		c *= y[i];
		c %= p;
	}
	printf("%lld\n", c % p);
}

Measured memory_bytes: 3280
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    int N;cin>>N;
    vector<int> L(N);
    REP(i,N) cin>>L[i];
    int ans=0;
    REP(i,N) rep(j,i+1,N) rep(k,j+1,N){
        if(L[i]==L[j]||L[j]==L[k]||L[k]==L[i]) continue;
        ans++;
        if(max({L[i],L[j],L[k]})>=min({L[i]+L[j],L[j]+L[k],L[k]+L[i]})) ans--;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3628
import java.util.*;

public class Main{
  public static void main(String[] args) {
    try {
      Scanner scan = new Scanner(System.in);
      int x, a, b;

      x = Integer.parseInt(scan.next());
      a = Integer.parseInt(scan.next());
      b = Integer.parseInt(scan.next());

      System.out.println((x-a)%b);
      
    }
    catch (Exception e) {
      
    }
  }
}

Measured memory_bytes: 23636
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanBytes)

	bytes := make([]byte, 4)
	for i := 0; i < 4; i++ {
		sc.Scan()
		bytes[i] = []byte(sc.Text())[0]
	}

	if bytes[0] == bytes[1] && bytes[2] == bytes[3] && bytes[0] != bytes[2] {
		fmt.Println("Yes")
	} else if bytes[0] == bytes[2] && bytes[1] == bytes[3] && bytes[0] != bytes[1] {
		fmt.Println("Yes")
	} else if bytes[0] == bytes[3] && bytes[1] == bytes[2] && bytes[0] != bytes[1] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define ls(x) x*2
#define rs(x) x*2+1
#define rg register
#define ll long long
#define LDB long double
#define ull unsigned long long
#define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt)
#define go(i,x,a) for(rg int i=a;i<x;i++)
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define mod 924844033
using namespace std;

const int maxn=2005;
int n,K,ok[maxn*2],vis[maxn*2],tl;
ll f[maxn*2][maxn][2],g[maxn],fac[maxn],ans;

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

void pre(){
	fac[0]=1; 
	go(i,n+1,1) fac[i]=(fac[i-1]*i)%mod;
	ans=fac[n];
}

int main(){
	#ifndef OLINE_JUDGE
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	#endif
	n=rd(); K=rd(); pre();
	go(i,n*2,0){
		if(vis[i]) continue; vis[i]=1;
		int pos=(i^1)+K*2; ok[++tl]=0;
		while(pos < n*2){
			vis[pos]=1;
			ok[++tl]=1;
			pos=(pos^1)+K*2;
		}
	}
	go(i,tl+1,1) f[i][0][0]=1;
	go(i,tl+1,1)
		go(j,n+1,1){
			if(ok[i]) f[i][j][1]=f[i-1][j-1][0];
			f[i][j][0]=(f[i-1][j][1]+f[i-1][j][0])%mod;
		}
	go(i,n+1,0) g[i]=(f[tl][i][0]+f[tl][i][1])%mod;
	for(rg int i=1,j=-1;i<=n;i++,j=-j)
		ans=(ans+(ll)j*g[i]%mod*fac[n-i]%mod+mod)%mod;
	printf("%lld",ans);
	return 0;
}//Faze


Measured memory_bytes: 125568
#include<stdio.h>
#include<string.h>

const int MAX = 100000;

int main(){
  char S[100000];
  scanf("%s ", S);
  
  int n = strlen(S);
  int K = n;
  
  for(int i = 1; i < n; i++){
    if(S[i] != S[i - 1]){
      if(i + i < n && n - i < K){
        K = n - i;
      }else if(i < K){
        K = i;
      }
    }
  }
  
  printf("%d\n", K);
  
  return 0;
}

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

using namespace std;
int kq,trace[205],n,m,s,t,u,v,c[205][205],f[205][205],hs,ht;
char kitu;
vector<int> a[205];
bool fip()
{
    memset(trace,0,sizeof(trace));
    trace[s]=-1;queue <long long > p;
    p.push(s);
    while (!p.empty())
    {
        u=p.front();p.pop();
        for (int j=0;j<a[u].size();j++)
        {

        v=a[u][j];
        if (trace[v]==0 && c[u][v]>f[u][v])
        {
            trace[v]=u;if (v==t) return true;
            p.push(v);
        }}
    }
    return false;
}
void incflow()
{
    u=t; int mi=round(1e9);
    while(u!=s)
    {
        v=trace[u];
        mi=min(mi,c[v][u]-f[v][u]);
        u=v;
    }
    u=t;kq+=mi;
    while(u!=s)
    {
        v=trace[u];
        f[v][u]+=mi; f[u][v]-=mi;
        u=v;
    }

}
int main()
{
  

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>m>>n;
    for (int i=1;i<=m;++i)
     for (int j=1;j<=n;++j)
    {
        cin>>kitu;
        if (kitu=='S')
        {
            s=j+m;hs=i;
            a[i].push_back(j+m);
            a[j+m].push_back(i);
            c[i][j+m]=c[j+m][i]=1e9;
        }
        if (kitu=='T')
        {
            t=j+m;ht=i;
            a[i].push_back(j+m);
            a[j+m].push_back(i);
            c[i][j+m]=c[j+m][i]=1e9;
        }
        if (kitu=='o')
        {
            a[i].push_back(j+m);
            a[j+m].push_back(i);
            c[i][j+m]=c[j+m][i]=1;
        }
    }
    if (hs==ht || s==t) {cout<<-1;return 0;}
    while (fip()) incflow();
    cout<<kq;























    return 0;
}


Measured memory_bytes: 768
n = int(input())
A = list(map(int, input().split()))

box = [0] * n
ans = []

cnt = 0
for itr, val in enumerate(A[::-1]):
  idx = n - itr -1
  sums_mod2 = sum(box[idx::idx+1]) % 2
  if val != sums_mod2:
    box[idx] += 1
    cnt += 1
    ans.append(idx + 1)
    
print(cnt)
print(*ans)

Measured memory_bytes: 14652
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <cstdint>
#include <cmath>
#include <bitset>
#include <string>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

#define N_TIMES(i, n)     for ( uint64_t i = 0;     i <  n; ++i )
#define N_TIMES_REV(i, n) for (  int64_t i = n - 1; i >= 0; --i )

using namespace std;

vector<set<uint64_t>> edge;
vector<int64_t> dp;
// dp[i]; ノードiを始点とした有向パスの最大長

int64_t dfs(uint64_t src) {
  if (dp[src] > 0) { return dp[src]; }

  for (uint64_t dst : edge[src]) {
    dp[src] = max(dp[src], dfs(dst) + 1);
  }

  return dp[src];
}

int main()
{
  uint64_t N, M;
  cin >> N >> M;

  edge = vector<set<uint64_t>>(N);
  N_TIMES(m, M) {
    uint64_t x, y;
    cin >> x >> y;

    edge[x - 1].insert(y - 1);
  }

  dp = vector<int64_t>(N, 0);

  N_TIMES(i, N) {
    if (dp[i] == 0) {
      dp[i] = dfs(i);
    }
  }

  cout << *max_element(dp.begin(), dp.end()) << endl;

  return 0;
}

Measured memory_bytes: 15164
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.Integer;
import java.lang.Math;
import java.lang.System;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        Walker walker = new Walker();
        String str;
        while ((str = r.readLine()) != null) {
            String input[] = str.split(",");
            int step = Integer.parseInt(input[0]);
            int angle = Integer.parseInt(input[1]);

            if (step == 0 && angle == 0) {
                break;
            }

            walker.walk(step);
            walker.turn(angle);
        }

        System.out.println(walker.getX());
        System.out.println(walker.getY());
    }
}

class Walker {
    static double x, y;
    static int angle;

    Walker() {
        x = 0;
        y = 0;
        angle = 0;
    }

    static void walk(int step) {
        double t = Math.PI*angle/180.0;
        x += step * Math.sin(t);
        y += step * Math.cos(t);
    }

    static void turn(int th) {
        angle += th;
    }

    static int getX() {
        return (int)x;
    }

    static int getY() {
        return (int)y;
    }
}

Measured memory_bytes: 16916
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	int n;
	cin >> n;
	vector<i64> a(n), b(n);
	rep(i, 0, n) {
		cin >> a[i] >> b[i];
	}
	i64 cou = 0;
	for (int i = n - 1; i >= 0; i--) {
		a[i] += cou;
		if (a[i] % b[i] != 0) {
			cou += b[i] - (a[i] % b[i]);
		}
	}
	cout << cou << endl;
}

Measured memory_bytes: 1792
N = int(input())
A = list(map(int,input().split()))

all_xor = 0
for a in A:
  all_xor = all_xor^a

ans = [] 
for a in A:
  ans.append(all_xor^a)
  
ans = [str(a) for a in ans]
ans = " ".join(ans)
print(ans)  

Measured memory_bytes: 39300
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    string s, t;
    cin >> s >> t;
    sort(all(s));
    sort(rall(t));
    
    yns(s < t);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>                                                                               
using namespace std;
#define FOR(v1, v2) for (v1 = 0; v1 < v2; ++v1)
int n, m, i;
int main () {
  cin >> n >> m;
  vector<int> v(n, 0); 
  vector<int> wa(n, 0); 
  int wacnt = 0;
  int sum = 0;
  FOR(i, m) {
    int p;
    char r[3];
    cin >> p >> r;
    --p;
    if (r[0] == 'A' && r[1] == 'C') {
      v[p] |= 1;
    } else if (r[0] == 'W' && r[1] == 'A') {
      wa[p] += (1 - v[p]);
    }   
  }   

  FOR(i, n) {
    sum += v[i];
    if (v[i] > 0) {
      wacnt += wa[i];
    }   
  }

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

Measured memory_bytes: 1024
import java.util.*;
public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            double x1 = Double.parseDouble(sc.next()),y1 = Double.parseDouble(sc.next());
            double x2 = Double.parseDouble(sc.next()),y2 = Double.parseDouble(sc.next());
            double x3 = Double.parseDouble(sc.next()),y3 = Double.parseDouble(sc.next());
            double x4 = Double.parseDouble(sc.next()),y4 = Double.parseDouble(sc.next());
            x2-=x1;
            y2-=y1;
            x4-=x3;
            y4-=y3;
            if(Math.abs(x2*x4+ y2*y4) <= 1.0e-10)System.out.println("YES");
            
            else System.out.println("NO");
            
        }
    }
}
     

Measured memory_bytes: 20172
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b, int n) {
	int i, j, k, t;
	vector<vector<ll>> c(n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			t = 0;
			for (k = 0; k < n; k++)
				t = (t + a[i][k] * b[k][j] % M) % M;
			c[i].push_back(t);
		}
	}
	return c;
}
ll c[55],x[55],y[55],n,p,q;
void search(ll a,ll b) {
	for (int i = 0; i < n; i++) {
		if (c[i] == 0) {
			if (x[i] == a + p && y[i] == b + q) {
				c[i]++;
				search(x[i], y[i]);
			}
			else if (x[i] == a - p && y[i] == b - q) {
				c[i]++;
				search(x[i], y[i]);
			}
		}
	}
}
int main() {
	ll i, j, k, l,  count, ans = 100;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> x[i] >> y[i];
	for (i = 0; i < n - 1; i++) {
		for (j = i + 1; j < n; j++) {
			p = x[j] - x[i];
			q = y[j] - y[i];
			for (k = 0; k < n; k++)
				c[k] = 0;
			count = 0;
				for (k = 0; k < n; k++) {
					if (c[k] == 0) {
						count++;
						c[k]++;
						search(x[k], y[k]);
					}
				}
			if (count < ans)
				ans = count;
		}
	}
	if (n == 1)
		ans = 1;
	cout << ans << endl;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

bool s[110][110];

int main(){
	int H, W, n;
	cin >> W >> H >> n;
	rep(i, n) {
		int X, Y, a;
		cin >> X >> Y >> a;
		if(a == 1) {
			for(int x = 0; x < X; x++) {
				for(int y = 0; y <= H; y++) s[y][x] = true;
			}
		}
		else if(a == 2) {
			for(int x = X; x < W; x++) {
				for(int y = 0; y < H; y++) s[y][x] = true;
			}
		}
		else if(a == 3) {
			for(int y = 0; y < Y; y++) {
				for(int x = 0; x < W; x++) s[y][x] = true;
			}
		}
		else {
			for(int y  = Y; y < H; y++) {
				for(int x = 0; x < W; x++) s[y][x] = true;
			}
		}
	}	
	int ans = 0;
	for(int x = 0; x< W; x++) {
		for(int y = 0; y < H; y++) if(!s[y][x]) ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
n = int(input())
s = input()
w = s.count("W")
r = s.count("R")

left_w = 0
right_r = r
count = [left_w+right_r]
for i in range(0, n):
    if s[i] == "W":
        left_w += 1
    else:
        right_r -=1
    #print(s[:i], s[i:], s[i], left_w, right_r)
    count.append(max(left_w,right_r))
print(min(count))

Measured memory_bytes: 17084
-- editorial

r :: IO [Int]
r = map read . words <$> getLine

main = do
    [_R,_G,_B,_N] <- r
    let r = sum [1 | r<-[0.._N], g<-[0.._N],
                        let b = fromIntegral (_N - r*_R - g*_G) / fromIntegral _B,
                        b >= 0, b == fromIntegral (floor b) ]
    print r



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

int main() {
  int N, r, l;
  int number = 0;
  cin >> N;
  
  for ( int i=0; i<N; i++) {
    cin >> l >> r;
    number += r-l+1;
  }
  cout << number << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>; // グラフ型


int main()
{
  int n; cin >> n;
  //set<int> s; 重複のとき0にできない
  //rep(i,n){
  //  int a; cin >> a; s.insert(a);
  //}
  vector<int> s(n); rep(i,n) cin >> s[i];
  vector<int> cnt(1000005);
  for(int x : s){
    if(cnt[x] != 0){
      cnt[x] = 2;
      continue;
    }
    for(int i=x; i<1000005; i+=x) cnt[i]++;
  }
  int ans = 0;
  for(int x : s){
    //cout << x << endl;
    if(cnt[x] == 1) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 8016
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <cstdio>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define SINV(t) greater<t>()
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP2(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

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

typedef long long ll;
#define vv(t) vector<t>

template<typename T>
void SV(vector<T> v){
    REP(i,v.size()){
        #ifdef LOCAL
            cout << i << " : " << v[i] << endl;
        #endif
    }
}

int bitCount(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16);
}


int main(){
    ll N, K;
    cin >> N >> K;
    printf("%lld\n", min(N%K, K-N%K));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> P;
#define fi first
#define se second
int main(){
    int n,ans=0;
    cin >> n;
    vector<P> r(n), b(n);
    for(int i=0;i < n;i++){
        cin >> r.at(i).fi >> r.at(i).se;
    }
    for(int i=0;i < n;i++){
        cin >> b.at(i).se >> b.at(i).fi;
    }
    sort(r.begin(),r.end());
    sort(b.begin(),b.end());

    for(int i=n-1;i>=0;i--){
        for(int j=0;j < b.size();j++){
            if(r.at(i).fi < b.at(j).se && r.at(i).se<b.at(j).fi){
                ans++;
                r.erase(r.begin()+i);
                b.erase(b.begin()+j);
                break;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;

class Program {
    static void Main( string[] args )
    {
        for ( int i = 0; i < 10000; ++i ) {
            string[] s = Console.ReadLine().Split();

            int a = int.Parse( s[ 0 ] );
            int b = int.Parse( s[ 1 ] );

            if ( a + b < 1 ) {
                break;
            }

            Console.WriteLine( ( a < b ? "{0} {1}" : "{1} {0}" ), a, b );
        }
    }
}

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

int main()
{
    array<int, 5> x;
    int k;
    for (int i = 0; i < 5; i++) {
        cin >> x.at(i);
    }
    cin >> k;
    bool ok = (x.at(4) - x.at(0)) <= k;
    if (!ok) {
        cout << ":(" << endl;
    } else {
        cout << "Yay!" << endl;
    }
}

Measured memory_bytes: 256
"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.split(/ |\n/),
    cid = 0;

// number一個取得
// eslint-disable-next-line no-unused-vars
const next = () => +cin[cid++];

// 文字列一個取得
// eslint-disable-next-line no-unused-vars
const nextstr = () => cin[cid++];

// BigInteger一個取得
// eslint-disable-next-line no-unused-vars
const nextbig = () => BigInt(cin[cid++]);

// 長さnの配列として取得。aは文字列フラグ
// eslint-disable-next-line no-unused-vars
const nexts = (n, a) =>
    a ? cin.slice(cid, (cid += n)) : cin.slice(cid, (cid += n)).map((a) => +a);

// w個ずつを組にして長さhの配列。aは文字列フラグ。
// eslint-disable-next-line no-unused-vars
const nextm = (h, w, a) => {
    var r = [],
        i = 0;
    if (a) for (; i < h; i++) r.push(cin.slice(cid, (cid += w)));
    else for (; i < h; i++) r.push(cin.slice(cid, (cid += w)).map((a) => +a));
    return r;
};
// 多次元配列。v,a1,a2,a3 なら、3次元。[[値vで長さa3の配列]をa2個並べた配列]をa1個並べた配列。
// eslint-disable-next-line no-unused-vars
const xArray = (...args) => {
    var a = args,
        l = a.length,
        r = "Array(a[" + --l + "]).fill().map(x=>{return " + a[0] + ";})";
    while (--l) r = "Array(a[" + l + "]).fill().map(x=>" + r + ")";
    return eval(r);
};

console.log(main());

function main() {
    let x = next();
    let n = next();
    if (n == 0) return x;
    let p = nexts(n);
    let min = 200;
    let v = 200;
    p = Array.from(new Set(p));
    p = p.sort((a, b) => {
        let j = Math.abs(x - a) - Math.abs(x - b);
        //console.log(a, b, j);
        if (j != 0) return j;
        if (j == 0) return a - b;
    });
    //console.log(p);
    if (x != p[0]) return x;
    let j = 1; //pのindex
    for (let i = 1; i < 110; i++) {
        if (x - i != p[j]) return x - i;
        j++;
        if (x + i != p[j]) return x + i;
        j++;
    }
}


Measured memory_bytes: 29676
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;

void solve(){
    string n;
    cin>>n;
    int ans=0;
    bool judge=true;
    for(int i=1;i<n.size();++i)if(n[i]!='9')judge=false;
    rep(i,n.size()-1){
        ans+=9;
    }
    if(judge)ans+=n.front()-'0';
    else ans+=(n.front()-'0')-1;
    cout<<ans<<"\n";
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 256
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*n
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]

N, M, *L = map(int, open(0).read().split())
u = UnionFind(N+1)
m = N*(N-1)//2
ans = []
for a, b in zip(*[iter(L[::-1])]*2):
  ans.append(m)
  A = u.find(a)
  B = u.find(b)
  if A!=B:
    na = u.count(A)
    nb = u.count(B)
    u.unit(a,b)
    m -= na*nb

print(*reversed(ans),sep='\n')

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

int main(){
    vector<int> a(5);
    rep(i,5) cin >>a[i];
    int final_answer = 100000000;
    vector<int>P = {0,1,2,3,4};
    do{
        int ans=0;
        rep(i,5){
            while(ans %10 != 0) ans+=1;
            ans +=a[P[i]];
        }
        final_answer = min(final_answer,ans);
    }while (next_permutation(P.begin(),P.end()));
    cout << final_answer << endl;
    return 0;
    
}

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

int main(){
    int n;
    cin >> n;
    int ret = 0;
    priority_queue<int> pq;
    for(int i = 0; i < n; i++){
        int x;  cin >> x;
        if(pq.empty() || -pq.top() >= x)    ret++;
        pq.push(-x);
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define double long double
using namespace std;

ll n, k, a[200005], mux;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> k >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i < n; i ++)
        mux = max(mux, abs(a[i] - a[i + 1]));
    mux = max(mux, abs(a[1] + k - a[n]));
    cout << k - mux;
    return 0;
}


Measured memory_bytes: 1792
n=int(input())
a=list(map(int,input().split()))
ans=0
b=[]
sum=0
for i in range(n):
    sum+=a[i]
    b.append(sum)
b=sorted(b)
b.append(float("inf"))
k=0
for i in range(n):
    if b[i]==b[i+1]:
        k+=1
    else:
        if not k==0:
            ans+=k*(k+1)//2
        k=0
for i in range(n):
    if b[i]==0:
        ans+=1
print(ans)


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

using namespace std;

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

  int n, k; 
  cin >> n >> k;
  long long res, num;
  if (k%2 == 0) {
    num = n/(k/2);
    res = (num/2)*(num/2)*(num/2);
    res += (num-num/2)*(num-num/2)*(num-num/2);
  } else {
    num = n/k;
    res = num*num*num;
  }
  cout << res << endl;

  return 0;
}



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

ll f(ll n){
  if(n%2==0){
    if((n/2)%2==0){
      return n^0;
    }else{
      return n^1;
    }
  }else{
    if((n/2)%2==1){
      return n^1^(n-1);
    }else{
      return n^(n-1);
    }
  }
}

int main(){
  ll a,b; cin>>a>>b;
  if(a==0 || b==0){
    cout<<max(a,b)<<endl;
    return 0;
  }ll ans= f(b)^f(a-1);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
D - Christmas
https://atcoder.jp/contests/abc115/tasks/abc115_d

"""
import sys


def create_burger(n):
    if n == 0:
        return 'P'
    return 'B' + create_burger(n-1) + 'P' + create_burger(n-1) + 'B'


def solve(N, X):
    def eat_p(level, x):
        if level == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + T[level-1]:
            return eat_p(level-1, x-1)
        else:
            return P[level-1] + 1 + eat_p(level-1, x-2-T[level-1])

    T, P = [1], [1]
    for _ in range(N):
        T.append(T[-1] * 2 + 3)
        P.append(P[-1] * 2 + 1)

    return eat_p(N, X)


def main(args):
    N, X = map(int, input().split())
    ans = solve(N, X)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3064
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;


int main(){
    long long H;
    long long N = 1;
    long long ans = 0;
    
    cin >> H;

    while(H){
        ans += N;
        H /= 2;
        N *= 2;
    }

    cout << ans << endl;

    return 0;
}

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

#define ll long long
#define fi first
#define sec second

ll n,m,k,x,x2,y,y2;
char c;
string s;
vector <ll> V;
vector <ll> sol;
ll L[30];

int main()
{
    cin >> n;
    k=0;
    for (int i=0;i<n;i++){
        cin >> x;
        V.push_back(x);
        k=k^x;
    }
    for (int i=0;i<n;i++){
        x=V[i];
        k=k^x;
        cout << k << " ";
        k=k^x;
    }
}


Measured memory_bytes: 5344
#include <bits/stdc++.h> //REMEMBER TO REMOVE '/'
#include <iostream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define int ll
const int INF = 100000000000;

signed main(){
    int n,W;
    cin>>n>>W;
    pair<int,int> arr[n+1];
    for(int i=1;i<=n;i++)cin>>arr[i].second>>arr[i].first;
    int dp[n+1][W+1];
    for(int w=0;w<=W;w++){
        dp[0][w]=0;
    }
    for(int i=1;i<=n;i++){
        for(int w=0;w<=W;w++){
            if(arr[i].second<=w){
                dp[i][w]=max(dp[i-1][w],dp[i-1][w-arr[i].second]+arr[i].first);
            }
            else dp[i][w]=dp[i-1][w];
        }
        
    }
    cout<<dp[n][W]<<endl;
    

}









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

int main()
{
    vector<int> hills;
    for(int i = 0; i < 10; ++i) {
        int h;
        cin >> h;
        hills.push_back(h);
    }
    sort(hills.begin(), hills.end(), greater<int>());
    cout << hills[0] << endl;
    cout << hills[1] << endl;
    cout << hills[2] << endl;
    
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VP = vector<P>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

ll solve(ll n, ll x, ll m){
    VL r(m);
    deque<ll> dq;
    rep(i, min(n, m)){
        r[x]++;
        dq.push_back(x);
        x *= x;
        x %= m;

        // 巡回検出
        if (r[x] != 0) break;
    }

    // 残りの数
    n -= dq.size();

    if (n != 0){
        // ループサイズ
        while(dq.front() != x) dq.pop_front();
        ll loop_sz = dq.size();

        // 何回ループするかを計算し、ループする数に対して加算する
        ll nq = n / loop_sz;
        while(!dq.empty()){
            ll y = dq.front(); dq.pop_front();
            r[y] += nq;
        }

        // 残りは普通に計算する
        ll nr = n % loop_sz;
        while(nr--){
            r[x]++;
            x *= x;
            x %= m;
        }
    }

    ll ans = 0;
    rep(i,m) ans += (ll)i * r[i];
    return ans;
}

int main(){
    ll n, x, m;
    cin >> n >> x >> m;
    cout << solve(n, x, m) << endl;
    
    return 0;
}


Measured memory_bytes: 4496
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy

def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("GREATER")
    elif (x<y): print("LESS")
    else: print("EQUAL")

def ip():
    return int(input())


#n = ip()                              #入力整数1つ
#n,m= (int(i) for i in input().split())      #入力整数横2つ
#a,b,k = (int(i) for i in input().split())    #入力整数横3つ
#n,a,b,c= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(h)]
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
b = []
red = 0
blue = 0
for i in range(len(a)):
    if a[i] == '0':
        red+=1
        b.append(0)
    else:
        blue+=1
        b.append(1)
print(min(red,blue)*2)

Measured memory_bytes: 24480
from collections import defaultdict
N=int(input())
A = {}
B = {}
for a in "ATGC":
    for b in "ATGC":
        for c in "ATGC":
            if a+b+c not in ["AGC", "ACG", "GAC"]:
                B[a+b+c] = 1
X=set()
for a in "ATGC":
    for b in "ATGC":
        for c in "ATGC":      
            for d in "ATGC":
                s=a+b+c+d
                t=b+a+c+d
                u=a+c+b+d
                v=a+b+d+c
                if any(["AGC" in x for x in [s,t,u,v]]):
                    X.add(s)

for _ in range(N-3):
    A = B
    B = defaultdict(int)
    for k in A:
        for l in "ATGC":
            if k+l not in X:
                B[k[1:]+l] += A[k]
    
print(sum(B.values())%(10**9+7))

Measured memory_bytes: 9316
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        n: usize,
        d: isize,
        xy: [(isize, isize); n],
    }
    let mut count = 0;
    for &(x, y) in &xy {
        if x * x + y * y <= d * d {
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 7768
K, N = STDIN.gets.chomp.split(' ').map{|s| s.to_i}
A = []
A[0] = 0
STDIN.gets.chomp.split(' ').each_with_index do |s, i|
  A[i + 1] = s.to_i
end

# Ad[i] = i-1 と iとの距離
Ad = []
Ad[0] = 0
1.upto(N) do |i|
  Ad[i] = A[i]  if i == 1
  Ad[i] = A[i] - A[i-1]
end
# Ad[1] = 1 <-> 0 <-> N の距離
Ad[1] = Ad[1] + (K - A[N])

sum = Ad.inject(0){|r, v| r += v}
max = Ad.max

puts sum - max


Measured memory_bytes: 18388
import java.util.*;
import java.io.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		char[] ans=new char[n];
		String[] s=new String[n];
		for(int i=0; i<n; i++){
			s[i]=sc.next();
		}
		for(int i=0; i<n; i++){
			if(s[i].equals("AB")){
				if(a>b){
					a--;
					b++;
					ans[i]='B';
				}else if(a<b){
					b--;
					a++;
					ans[i]='A';
				}else{
					if(i!=n-1 && !s[i+1].equals("AB")){
						if(s[i+1].equals("BC")){
							b++;
							a--;
							ans[i]='B';
						}else{
							b--;
							a++;
							ans[i]='A';
						}
					}else{
						a--;
						b++;
						ans[i]='B';
					}
				}
			}else if(s[i].equals("BC")){
				if(c>b){
					c--;
					b++;
					ans[i]='B';
				}else if(c<b){
					b--;
					c++;
					ans[i]='C';
				}else{
					if(i!=n-1 && !s[i+1].equals("BC")){
						if(s[i+1].equals("AB")){
							b++;
							c--;
							ans[i]='B';
						}else{
							b--;
							c++;
							ans[i]='C';
						}
					}else{
						c--;
						b++;
						ans[i]='B';
					}
				}
			}else{
				if(a>c){
					a--;
					c++;
					ans[i]='C';
				}else if(a<c){
					c--;
					a++;
					ans[i]='A';
				}else{
					if(i!=n-1 && !s[i+1].equals("AC")){
						if(s[i+1].equals("BC")){
							c++;
							a--;
							ans[i]='C';
						}else{
							c--;
							a++;
							ans[i]='A';
						}
					}else{
						a--;
						c++;
						ans[i]='C';
					}
				}
			}
			if(a<0 || b<0 || c<0){
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
		for(int i=0; i<n; i++){
			System.out.println(ans[i]);
		}
	}
	static class State{
		int count;
		String idx;
		State(int count,String idx){
			this.count=count;
			this.idx=idx;
		}
	}
}


Measured memory_bytes: 66324
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}

vvi memo(13,vi(100100,-1));

int dfs(string &s,int idx,int m) {
  int x = (4 * m) % 13;
  if(memo[x][idx] != -1) {
    return memo[x][idx];
  }
  if(idx == sz(s)-1) {
    if(s[idx] == '?') {
      int ans = 0;
      rep(i,10) {
        if((4 * i - x+13)%13 == 0) {
          ans++;
        }
      }
      memo[x][idx] = ans;
      return ans;
    } else {
      if((4 * (s[idx] - '0') - x+13)%13 == 0) {
        memo[x][idx] = 1;
        return 1;
      }
      memo[x][idx] = 0;
      return 0;
    }
  }
  
  if(s[idx] != '?') {
    int b = s[idx] - '0';
    ll a = dfs(s,idx+1,13 - (4 * b - x + 13) % 13);
    a %= MOD;
    memo[x][idx] = (int)a;
    return a;
  } else {
    int b = s[idx] - '0';
    ll temp = 0;
    rep(i,10) {
      temp += (ll)dfs(s,idx+1,13 - (4*i-x+13)%13);
      temp %= MOD;
    }
    memo[x][idx] = (int)temp;
    return temp;
  }
}
  
int main() {
  string s;
  cin >> s;
  reverse(rng(s));
  cout << dfs(s,0,5) << endl;
  return 0;
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	string s; int k; read(s, k);
	set<string> ss;

	rep(i, 1, min(k, sz(s)) + 1)
		rep(j, 0, sz(s))
			ss.insert(s.substr(j, i));
	vector<string> vs(all(ss));
	die(vs[k - 1]);
}


Measured memory_bytes: 1792
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <cassert>
#include <fstream>
#include <stdio.h>
#include<unordered_map>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}

using namespace std;

int main(){
	int h,w; cin >> h >> w;
	vector<string> da(h);
	rip(i,h,0) cin >> da[i];
	vector<vector<int>> dp(h, vector<int>(w, INT_MAX));
	dp[0][0] = 0;
	rip(i,h,0){
		rip(j,w,0){
			if(h-1 > i){
				if(da[i][j] != da[i+1][j]){
					chmin(dp[i+1][j], dp[i][j]+1);
				}
				else{
					chmin(dp[i+1][j], dp[i][j]);
				}
			}
			if(w-1 > j){
				if(da[i][j] != da[i][j+1]){
					chmin(dp[i][j+1], dp[i][j]+1);
				}
				else{
					chmin(dp[i][j+1], dp[i][j]);
				}
			}
		}
	}
	int ans = (dp[h-1][w-1]+1)/2;
	if(da[0][0] == '#' && da[h-1][w-1] == '#'){
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include"iostream"
#include"vector"
#include"algorithm"
using namespace std;
 
int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> x(n);
	for (int i = 0; i < n; i++)
	{
		cin >> x[i];
	}
 
	int ans = 2*x[n-1]-2*x[0];
	for (int i = 0; i < n - k + 1; i++)
	{
		if (x[i] < 0 && x[i + k - 1] < 0)
		{
			ans = min({ ans,(-1)*x[i] });
		}
		else if (x[i] > 0 && x[i + k - 1] > 0)
		{
			ans = min({ ans,x[i + k - 1] });
		}
		else
		{
			ans = min({ ans,2 * x[i + k - 1] - x[i],x[i + k - 1] - 2*x[i] });
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640