akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <set>
#include <climits>
#include <map>

using namespace std;

long long A[300][300];
long long required_mp[90001];
map <int, pair <int, int> > pos_map;
int main(){
  int H;
  int W;
  int D;
  cin >> H >> W >> D;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> A[i][j];
      pos_map[A[i][j]] = make_pair(i, j);
    }
  }

  for(int i = 1; i <= D; i++){
    required_mp[i] = 0;
  }
  
  for(int i = D + 1; i <= H * W; i++){
    int cur_h = pos_map[i].first;
    int cur_w = pos_map[i].second;
    int prev_h = pos_map[i - D].first;
    int prev_w = pos_map[i - D].second;

    required_mp[i] = abs(cur_h - prev_h) + abs(cur_w - prev_w) + required_mp[i - D];
  }
  
  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++){
    int L;
    int R;
    cin >> L >> R;
    cout << required_mp[R] - required_mp[L] << endl;
  }
  return 0;
}


Measured memory_bytes: 8192
#include <stdio.h>
#define S_MAX 1000

int main(void)
{
    int sum, min, max, n, t, i;

    while(scanf("%d", &n), n!=0)
    {
        sum = max = 0, min = S_MAX;

        for(i=0; i<n; i++)
        {
            scanf("%d", &t);

            if(min > t) min = t;
            if(max < t) max = t;

            sum += t;
        }

        printf("%d\n", (sum-min-max) / (n-2));
    }

    return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
int n,x,y,t,u,v,w,num,type=0;
int main()
{
	w=0;
	u=0;
	v=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&t,&x,&y);
		num=abs(x-u)+abs(y-v);
		//printf("%d %d\n",t-w,num);
		if(t-w>=num&&((t-w)%2==num%2))
		{
			
		}else
		{
			type=-1;
		}
		w=t;
		u=x;
		v=y;
	}
	if(type==0)
	{
		printf("Yes");
	}else
	{
		printf("No");
	}
}

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

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

    int ans = 0;
    rep (i, N) {
        if (a[a[i]-1] == i+1) ans++;
    }
    cout << ans / 2 << endl;
}

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

int main() {
    int n;
    cin >> n;
    bool b[10] = {false};
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a < 400) b[0] = true;
        else if (a < 800) b[1] = true;
        else if (a < 1200) b[2] = true;
        else if (a < 1600) b[3] = true;
        else if (a < 2000) b[4] = true;
        else if (a < 2400) b[5] = true;
        else if (a < 2800) b[6] = true;
        else if (a < 3200) b[7] = true;
        else cnt++;
    }

    int ans_mn = 0, ans_mx = 0;
    for (int i = 0; i < 8; i++) {
        if (b[i] == true) {
            ans_mn++;
            ans_mx++;
        }
    }

    if (cnt != 0) ans_mx += cnt;
    if (ans_mn == 0) ans_mn++;

    cout << ans_mn << " " << ans_mx << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<62);

int main() {
    vec h(2), m(2);
    rep(i,2) cin>>h[i]>>m[i];
    ll res = h[1] - h[0];
    res *= 60;
    res += m[1] - m[0];
    cin>>A;
    cout<<res - A<<endl;
}

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

using namespace std;

const int INF = 1e9;
const int MAX_V = 100;
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
int V;

int prim() {
    fill(mincost, mincost + V, INF);
    fill(used, used + V, false);
    mincost[0] = 0;
    int res = 0;

    while (true) {
        int v = -1;
        for (int u = 0; u < V; u++)
            if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
        
        if (v == -1) break;
        used[v] = true;
        res += mincost[v];

        for (int u = 0; u < V; u++)
            mincost[u] = min(mincost[u], cost[v][u]);
    }

    return res;
}

int main() {
    while (scanf("%d", &V), V) {
        int m;
        scanf("%d", &m);
                
        for (int i = 0; i < V; i++)
            fill(cost[i], cost[i] + V, INF);

        for (int i = 0; i < m; i++) {
            int a, b, d;
            scanf("%d,%d,%d", &a, &b, &d);
            cost[a][b] = cost[b][a] = d;
        }
        
        int ans = prim() / 100 - (V - 1);
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3152
n=int(input())
a=list(map(int,input().split()))
dp=[0,abs(a[0]-a[1])]
for i in range(2,n):
 dp.append(min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2])))
print(dp[-1])


Measured memory_bytes: 13980
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

// A Holiday of Miss Brute Force
// 2012/09/19
public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;

	int sx, sy, gx, gy;
	int n;
	int[] xs, ys;
	int lx, ly;

	void run(){
		sx=sc.nextInt();
		sy=sc.nextInt();
		gx=sc.nextInt();
		gy=sc.nextInt();
		n=sc.nextInt();
		xs=new int[n];
		ys=new int[n];
		for(int i=0; i<n; i++){
			xs[i]=sc.nextInt();
			ys[i]=sc.nextInt();
		}
		lx=sc.nextInt();
		ly=sc.nextInt();
		solve();
	}

	void solve(){
		int[] dx={0, 1, 1, 0, -1, -1, 0};
		int[] dy0={1, 0, -1, -1, -1, 0, 0};
		int[] dy1={1, 1, 0, -1, 0, 1, 0};

		LinkedList<P> que=new LinkedList<P>();
		HashMap<P, Integer> map=new HashMap<P, Integer>();

		HashSet<P> wall=new HashSet<P>();
		for(int i=0; i<n; i++){
			for(int t=0; t<6; t++){
				wall.add(new P(xs[i], ys[i], t));
			}
		}

		que.addFirst(new P(sx, sy, 0));
		map.put(new P(sx, sy, 0), 0);

		for(; !que.isEmpty();){
			P p=que.removeLast();
			int[] dy=abs(p.x)%2==0?dy0:dy1;
			int op=abs(p.x*p.y*p.t)%6;
			for(int i=0; i<7; i++){
				P q=new P(p.x+dx[i], p.y+dy[i], (p.t+1)%6);
				if(abs(q.x)>lx||abs(q.y)>ly||wall.contains(q)){
					continue;
				}
				int ignore=map.get(p)+(i==op?0:1);
				if(map.containsKey(q)){
					if(ignore<map.get(q)){
						map.put(q, ignore);
						que.addFirst(q);
					}
				}else{
					map.put(q, ignore);
					if(ignore==map.get(p)){
						que.addLast(q);
					}else{
						que.addFirst(q);
					}
				}
			}
		}

		int min=INF;
		for(int i=0; i<6; i++){
			P p=new P(gx, gy, i);
			if(map.containsKey(p)){
				min=min(min, map.get(p));
			}
		}
		println((min<INF?min:-1)+"");
	}

	class P{
		int x, y, t;

		P(int x, int y, int t){
			this.x=x;
			this.y=y;
			this.t=t;
		}

		@Override
		public int hashCode(){
			return t*200*200+(y+100)*200+x;
		}

		@Override
		public boolean equals(Object o){
			P p=(P)o;
			return x==p.x&&y==p.y&&t==p.t;
		}
	}

	void println(String s){
		System.out.println(s);
	}

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

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

int main(){
    long long N;
    cin >> N;
    vector<long long> A(N+1);
    vector<long long> B(N);
    long long count=0;
    for(long long  i=0;i < N+1; i++){
        cin >> A[i];
    }
    for(long long  i=0;i < N; i++){
        cin >> B[i];
    }

    for(long long i=0; i<N;i++){
        if(B[i] < A[i]){
            count += B[i];
        }
        else{
            count += A[i];
            if(B[i]-A[i] < A[i+1]){
                count += B[i]-A[i];
                A[i+1] -= B[i]-A[i];
            }
            
            else{
                count+= A[i+1];
                A[i+1] = 0;
            }
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		System.out.println((((a / n + (a % n == 0 ? 0 : 1)) * n)) <= b ? "OK" : "NG");

	}

	static class FastScanner {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public FastScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					return reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}

			return tokenizer.nextToken("\n");
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
	}
}

Measured memory_bytes: 32864
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

    void run() {
        FastReader sc = new FastReader();
        int j = 0;
        for(int i = 0; i < 3; i++) {
            String s = sc.next();
            System.out.print(s.charAt(j++));
        }
        System.out.println();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 21076
n = int(input())
a, b = map(int, input().split())
p = list(map(int, input().split()))
small = 0
medium = 0
large = 0
for score in p:
    if score <= a:
        small += 1
    elif a < score <= b:
        medium += 1
    elif score > b:
        large += 1
ans = min(small, medium, large)
print(ans)


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

int main(){
  int a;
  
  cin>>a;
  int tmp1,tmp2,tmp3;
  tmp1 = a/100;
  tmp2 = (a-(100*tmp1))/10;
  tmp3 = a-(100*tmp1)-(10*tmp2);
  cout<<tmp1+tmp2+tmp3<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out() cout << endl
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

int main() {
    ll a, b;
    cin >> a >> b;

    if(a < 10 && b < 10) {
        cout << a*b;
    }
    else {
        cout << -1;
    }
    
    re0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	
	int ans=min(A,B)+min(C,D);
	cout<<ans;
}

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

int main(){
    int n;
    cin>>n;
    string ans="";
    if(n==0)ans="0";
    while(n!=0){
        if(n%2!=0){
            n--;
            ans='1'+ans;
        }
        else{
            ans='0'+ans;
        }
        n/=-2;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
def daydream():
	S = input()
	flag = False
	divide = ['dreamer', 'dream', 'eraser', 'erase']
	while True:
		if len(S) == 0:
			flag = True
			break
		for d in divide:
			if S.endswith(d):
				S = S[:-len(d)]
				break
		else:
			break
	if flag:
		print('YES')
	else:
		print('NO')

daydream()

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

typedef long long int ll;

int main()
{
    map<ll,ll>mp;

    ll n;
    cin>>n;
    vector<ll> vv;

    set<ll> ss;

    for(ll i=0; i<n; i++)
    {
        ll a;
        scanf("%d",&a);
        vv.emplace_back(a);
        ss.insert(a);
        mp[a]++;
    }

    ll sum=0;

    for(ll it : ss)
    {
        ll x = mp[it];

        x--;

        //if(it == vv[i]) x--;

        sum += (x*(x+1))>>1;
    }

    for(ll i=0;i<n;i++)
    {
        ll x = mp[vv[i]];
        x--;
        ll y = (x*(x+1))>>1;

        ll sum1 =sum;

        sum1-=y;

        //cout<< sum1 <<' ';

        ll xx = mp[vv[i]];
        xx--;
        xx--;
        ll yx = (xx*(xx+1))>>1;

        cout<<sum1+yx<<endl;
    }





}


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

int main(){
  int N;
  cin >> N;
  vector<bool> rate(8, false);
  int free = 0;//3200超えてる人の数
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    if(a<400){
      rate[0] = true;
    }
    else if(a<800){
      rate[1] = true;
    }
    else if(a<1200){
      rate[2] = true;
    }
    else if(a<1600){
      rate[3] = true;
    }
    else if(a<2000){
      rate[4] = true;
    }
    else if(a<2400){
      rate[5] = true;
    }
    else if(a<2800){
      rate[6] = true;
    }
    else if(a<3200){
      rate[7] = true;
    }
    else{
      free++;
    }
  }
  
  int number = 0;
  for(int i = 0; i < 8; i++){
    if(rate[i]) number++;
  }
  
  int M, m;//最大値、最小値
  
  M = number + free;

  
  m = number;
  if(m == 0) m = 1;
  
  cout << m << " " << M << endl;
  
}

Measured memory_bytes: 256
BIG_NUM = 2000000000

table = [[[0]*10 for i in range (0,3)] for k in range (0,4)]

N = int(input())

for loop in range(N):
    house_id,floor,room,add = map(int,input().split())
    table[house_id-1][floor-1][room-1] += add


x = 0

for i in range(4):
    if x != 0:
        print("#"*20)
    x += 1

    for a in range(3):
        for b in range(10):
            print(" %d"%(table[i][a][b]),end = "")
        print()



Measured memory_bytes: 5624
#include <bits/stdc++.h>
using namespace std;
 
using tpl = tuple<char, int>;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

pll dp[51]; // パンの総数, パティ総数
pll dfs(int level){
    pll res = pll(0, 0);
    if(dp[level].first != -1) return dp[level];
    if(level == 0 ) {
        res = pll(0, 1);
    }
    else{
        ll pan = 2 + 2 * dfs(level - 1).first;
        ll paty = 1 + 2 * dfs(level - 1).second;
        res = pll(pan, paty);
    }
    return dp[level] = res;
}

ll rec(int level, ll x){
    ll next_barger_sum = dfs(level - 1).first + dfs(level - 1).second;
    if(level == 0){
        return 1;
    }
    if(x == 1) {
        return 0;
    }
    if(x <= next_barger_sum + 1) {
        return rec(level - 1, x - 1);
    }
    else if(x == next_barger_sum + 2) {
        return dfs(level - 1).second + 1;
    }
    else if(x <= next_barger_sum * 2 + 2) {
        return dfs(level - 1).second + rec(level - 1, x - (2 + next_barger_sum)) + 1;
    }
    else{
        return dfs(level).second;
    }
}


int main(){

    ll N, X;
    cin >> N >> X;
    for(int i = 0; i <= N; i++) dp[i] = pii(-1,-1);
    cout << rec(N, X) << endl;

    return 0;
}


Measured memory_bytes: 256
///  author:Kissheart  ///
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#define INF 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
#define gcd(a,b) __gcd(a,b)
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t);b>>=1;t=(t*t);}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
//freopen( "in.txt" , "r" , stdin );
//freopen( "data.txt" , "w" , stdout );
int n;
int p[105];
int A,B;
int main()
{
    scanf("%d",&n);
    scanf("%d%d",&A,&B);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    sort(p+1,p+1+n);
    int sum1=0,sum2=0,sum3=0,ans=0;

    for(int i=1;i<=n;i++)
    {
        if(p[i]<=A)
            sum1++;
        else if(p[i]>A && p[i]<=B)
            sum2++;
        else if(p[i]>B)
            sum3++;

    }
    printf("%d\n",min(sum1,min(sum2,sum3)));
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using ll = long long;
using namespace std;

/* initialize */
class DisjointSet {
public:
    vector<int>rank, p; // rank : データの階層, p[i]: 要素iの親
    DisjointSet() = default;;

    explicit DisjointSet(int size){
        rank.resize(static_cast<unsigned int>(size), 0);
        p.resize(static_cast<unsigned int>(size), 0);
        for (int i = 0; i < size; ++i) makeSet(i);

    }

    void makeSet(int i) {
        p[i] = i;
        rank[i] = 0;
    }

    bool same(int x, int y){
        return findSet(x) == findSet(y);
    }

    void unite (int x, int y){
        link(findSet(x), findSet(y));
    }

    void link(int x, int y){
        if (rank[x] > rank[y]){
            p[y] = x;
        } else {
            p[x] = y;
            if(rank[x] == rank[y]) rank[y]++;
        }
    }

    int findSet(int x){
        if (x != p[x]){
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};
/* main */
int main() {
    int n, a, b,q;
    int t;
    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);
    for (int i = 0; i < q; ++i) {
        cin >> t >> a >> b;
        if (t == 0) ds.unite(a, b);
        else if (t == 1) {
            if (!ds.same(a, b)) cout << 0 << "\n";
            else cout << 1 << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, First = 0, Second = 0;  
  cin >> N;
  vector<int> A(N);
  
  for(int i = 0; i < N; ++i){
    cin >> A.at(i);
  }
  
  for(int i = 0; i <N; ++i){
    if(A.at(i) >= First){
      Second = First;
      First = A.at(i);
    }
    if(A.at(i) < First && A.at(i) > Second){
      Second = A.at(i);
    }
  }
  
  for(int i = 0; i < N; ++i){
    if(A.at(i) == First){
      cout << Second << endl;
    }else{
      cout << First << endl;
    }
  }
}   


Measured memory_bytes: 2432
#include<cstdio>
#include<algorithm>
using namespace std;
int C[2010][2010][3], Mod = 924844033;
int D[2010], K, n, T[2010], F[2010], res;
void Calc(int m, int rr) {
	int i, j, k, l;
	C[0][0][0] = 1;
	for (i = 1; i <= m; i++) {
		int x = (i - 1) * 2 * K + rr;
		for (j = 0; j <= i; j++)for (k = 0; k < 3; k++)C[i][j][k] = 0;
		for (j = 0; j < i; j++) {
			for (k = 0; k < 3; k++) {
				int t = C[i - 1][j][k];
				for (l = 0; l < 3; l++) {
					if (x-K<0 && l == 1 || x+K>=n &&l == 2 || k==2&&l==1)continue;
					if(l)C[i][j+1][l] = (C[i][j+1][l] + t) % Mod;
					else C[i][j][l] = (C[i][j][l] + t) % Mod;
				}
			}
		}
	}
	for (i = 0; i <= m; i++) {
		int s = 0;
		for (j = 0; j < 3; j++)s = (s + C[m][i][j]) % Mod;
		for (j = 0; j <= n - i; j++) {
			T[i + j] = (T[i + j] + (long long)D[j] * s) % Mod;
		}
	}
	for (i = 0; i <= n; i++) {
		D[i] = T[i];
		T[i] = 0;
	}
}
int main() {
	int i, j;
	scanf("%d%d", &n, &K);
	D[0] = 1;
	F[0] = 1;
	for (i = 1; i <= n; i++)F[i] = (long long)F[i - 1] * i%Mod;
	for (i = 0;i<2*K; i++) {
		Calc((n + 2 * K - 1 - i) / (2 * K), i);
	}
	int res = 0, t = 1;
	for (i = 0; i <= n; i++) {
		D[i] = (long long)D[i] * F[n - i] % Mod;
		res = (res + (long long)t*D[i]) % Mod;
		t = (long long)t*(Mod-1)%Mod;
	}
	printf("%d\n", res);
}

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

void solve() {
    int X; cin >> X;
    vector<int> dp(101110);
    dp[0] = 1;
    for(int a = 0; a < 6; ++a) {
        int m = 100 + a;
        for(int i = 0; i < 100010; ++i) {
            if(dp[i]) dp[i + m] = 1;
        }
    }
    if(dp[X]) cout << 1 << '\n';
    else cout << 0 << '\n';
}

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


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    int r = 0;
    for (int k = 28; k >= 0; k--) {
        int l = 1 << k;
        sort(b.begin(), b.end());

        int s = 0;
        for (int h = 0; h < 3; h++) {
            int t = l * (h + 1);
            for (int i = 0; i < n; i++) {
                s ^= b.end() - lower_bound(b.begin(), b.end(), t - a[i]);
            }
        }
        if (s & 1) r ^= l;

        for (int i = 0; i < n; i++) {
            a[i] &= ~l;
            b[i] &= ~l;
        }
    }

    cout << r << endl;

    return 0;
}

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

int main(){
  int N;
  cin >>N;
  int s1=0,s2=0,ans,s;
  vector<vector<int>> vec(2,vector<int>(N));
  for(int i=0;i<2;i++){
    for(int j=0;j<N;j++){
      cin >> vec[i][j];
      if(i==0){
        s1+=vec[i][j];
      }
      else{
        s2+=vec[i][j];
      }
    }
  }
  ans=0;
  for(int i=0;i<N;i++){
    if(i==0){
      s=vec[0][i]+s2;
    }
    else{
      s=s+vec[0][i]-vec[1][i-1];
    }
    ans=max(ans,s);
  }
  cout << ans <<endl;
}


Measured memory_bytes: 3592
x1, y1, x2, y2 = map(int, input().split())
a = x2 - x1
b = y2 - y1
x3, y3 = x2 - b, y2 + a
x4, y4 = x3 - a, y3 - b

print(x3, y3, x4, y4)

Measured memory_bytes: 3444
use proconio::{
   fastout, input,
   marker::{Bytes, Chars, Isize1, Usize1},
};

fn main() {
   input! {
      n:usize
   }
   let mut vmax = vec![];
   let mut vmin = vec![];
   for _ in 0..n {
      input! {a:usize,b:usize}
      vmax.push(b);
      vmin.push(a);
   }
   vmax.sort();
   vmin.sort();
   if n % 2 == 0 {
      let max1 = vmax[n / 2 - 1];
      let max2 = vmax[n / 2];
      let min1 = vmin[n / 2 - 1];
      let min2 = vmin[n / 2];
      let mmax = (max2 + max1);
      let mmin = (min2 + min1);
      //dbg![max1, max2, min1, min2, mmax, mmin];
      println!("{}", mmax - mmin + 1);
   } else {
      let max = vmax[n / 2];
      let min = vmin[n / 2];
      println!("{}", max - min + 1);
   }
}


Measured memory_bytes: 9696
using Yorukatsu024.Questions;
using Yorukatsu024.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yorukatsu024.Questions
{
    /// <summary>
    /// ABC107 C
    /// </summary>
    public class QuestionD : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var nk = inputStream.ReadIntArray();
            var n = nk[0];
            var k = nk[1];
            var x = inputStream.ReadIntArray();

            var minDistance = int.MaxValue;
            for (int i = 0; i < n - k + 1; i++)
            {
                var left = x[i];
                var right = x[i + k - 1];
                var distance = right - left + Math.Min(Math.Abs(left), Math.Abs(right));
                minDistance = Math.Min(minDistance, distance);
            }

            yield return minDistance;
        }
    }
}


namespace Yorukatsu024
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionD();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Yorukatsu024.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Yorukatsu024.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 21728
#define _USE_MATH_DEFINES
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

int main(){
	string str;

	while(getline(cin, str)){
		//cout << (int)'a' <<" "<< (int)'A' <<" "<< (int)'z'<<" "<<(int)'Z'<<" "<<endl;
		for(int i=0;i<str.size();i++){
			if(str[i]>='a' && str[i]<='z'){
				int j = str[i]-'a';
				str[i]=(char)('A'+j);
			}
		}
		cout << str << endl;
	}

	return 0;
}

Measured memory_bytes: 1172
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

var grid [][]string

type alice struct {
	A int
	B int
}

type bob struct {
	C int
	D int
}

func main() {
	sc.Split(bufio.ScanWords)

	alice := alice{nextInt(), nextInt()}
	bob := bob{nextInt(), nextInt()}

	max := math.Max(float64(alice.A), float64(bob.C))
	min := math.Min(float64(alice.B), float64(bob.D))

	if max <= min {
		fmt.Println(int(min - max))
	} else {
		fmt.Println(0)
	}

}


Measured memory_bytes: 640
use std::io;

fn gets() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn main() {
    let line = gets();
    let mut it = line.trim().split_whitespace().map(|n| n.parse::<usize>().unwrap());
    let (a, b, c, d) = (it.next().unwrap(), it.next().unwrap(), it.next().unwrap(), it.next().unwrap());
    let ans: &str;
    if (a + b) > (c + d) {
      ans = "Left";
    } else if (a + b) == (c + d) {
      ans = "Balanced";
    } else {
      ans = "Right";
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <stdio.h>
#include <set>

const int Z = 1<<18;

struct node{
	node(){
		sz = 0; a[0] = a[1] = 0x7fffffff;
	}
	node(int x, int i){
		if (x == 0x7fffffff) sz = 0, a[0] = a[1] = x;
		else sz = 1, a[0] = x, a[1] = 0x7fffffff, p[0] = i;
	}
	int sz,a[2],p[2];

	node operator +(const node &t)const{
		node r = (*this);
		for (int k=0;k<2;k++){
			if (r.a[k] > t.a[(k + r.sz)%2]){
				r.a[k] = t.a[(k + r.sz)%2];
				r.p[k] = t.p[(k + r.sz)%2];
			}
		}
		r.sz += t.sz;
		return r;
	}
}IT[Z*2];

void in(int x)
{
	x += Z;
	IT[x] = node(); x /= 2;
	while (x){
		IT[x] = IT[x*2] + IT[x*2+1];
		x /= 2;
	}
}

node out(int l, int r)
{
	node u,v;
	l += Z; r += Z;
	while (l <= r){
		if (l & 1) u = u + IT[l++];
		if (~r & 1) v = IT[r--] + v;
		l /= 2; r /= 2;
	} if (l == r) u = u + IT[l];
	return u + v;
}

int main()
{
	int N; scanf ("%d",&N);
	for (int i=0;i<N;i++){
		int x; scanf ("%d",&x);
		IT[i+Z] = node(x,i);
	}
	for (int i=Z-1;i>=1;i--) IT[i] = IT[i*2] + IT[i*2+1];

	std::set<int> div; div.insert(N);
	for (int i=N/2;i>=1;i--){
		node p = out(0,N-1);
		in(p.p[0]);
		int lim = *div.lower_bound(p.p[0]);
		div.insert(p.p[0]);
		node q = out(p.p[0],lim-1);
		in(q.p[0]);
		div.insert(q.p[0]);
		printf ("%d %d%c",p.a[0],q.a[0],i>1?' ':'\n');
	}

	return 0;
}

Measured memory_bytes: 21120
#include <bits/stdc++.h>
using namespace std;
int abs(int x){
    if(x<0) return -x;
    else return x;
}

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    int alice=0,bob=0;
    for(int i=0;i<n;i++) cin>>a.at(i);
    sort(a.begin(),a.end());
    for(int i=0;i<n;i+=2){
        alice+=a.at(i);
    }
    for(int i=1;i<n;i+=2){
        bob+=a.at(i);
    }
    cout<<abs(alice-bob)<<endl;
}

Measured memory_bytes: 3616
N, M, X, Y = map(int, input().split())

# めっちゃ回りくどい解法
# x_list = sorted([int(i) for i in input().split()])
# y_list = sorted([int(i) for i in input().split()])
#
# x = x_list[-1]
# y = y_list[0]
# if x < y and any([X < z <= Y for z in range(x+1, y+1)]):
#     print('No War')
# else:
#     print('War')
#

# https://atcoder.jp/contests/abc110/submissions/9348852 がとてもスマート

x_list = [int(i) for i in input().split()] + [X]
y_list = [int(i) for i in input().split()] + [Y]

if max(x_list) < min(y_list):
    print('No War')
else:
    print('War')


Measured memory_bytes: 2940
#include<stdio.h>
int main ()
{
    int x,y,temp;
    while (1){
        
        scanf("%d %d",&x,&y);
        
        if (x == 0 && y == 0) break;
        
        else if (x >= y){
            temp = x;
            x = y;
            y = temp;
        }
        
        printf("%d %d\n",x,y);
        
    }
    return 0;
}


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

const int MOD = (int)1e9+7;

int main(){
	int N;
	cin >> N;
	vector<int> A(N),B(N);
	for(int i=0;i<N;i++){
		cin >> A.at(i);
		B.at(i)=A.at(i);
	}

	sort(B.begin(),B.end());
	int ma1=B.at(N-1),ma2=B.at(N-2);
	for(int i=0;i<N;i++){
		if(A.at(i)==ma1)	cout << ma2 << endl;
		else	cout << ma1 << endl;
	}

	return 0;
}


Measured memory_bytes: 3200
#include <iostream>
#include <string>
 
using namespace std;
 
int main(){
  int n, k, i, ans;
	cin >> n >> k;
  int h[n];
  ans = 0;

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

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

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll              long long
#define pb              push_back
#define ppb             pop_back
#define endl            '\n'
#define mii             map<ll,ll>
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define vs              vector<string>
#define all(a)          (a).begin(),(a).end()
#define F               first
#define S               second
#define sz(x)           (ll)x.size()
#define hell            1000000007
#define inf             (ll)1e18 + 5
#define PI              3.14159265358979323844
#define rep(i,a,b)      for (ll i=a;i<b;i++)
#define repr(i,a,b)     for (ll i=a-1;i>=b;i--)
#define lbnd            lower_bound
#define ubnd            upper_bound
#define mp              make_pair
#define ios             ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ordered_set     tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define trace(...)      __f(#__VA_ARGS__, __VA_ARGS__)

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

using namespace std;
using namespace __gnu_pbds;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//primes for hashing 937,991,1013,1409,1741

void solve() {
    ll l;
    cin>>l;
    double ans=(l*l*l*1.0)/27;
    cout << fixed << setprecision(8)<<ans<<endl;
}

signed main() {
    ios
    ll test=1;
    //cin>>test;
    while (test--) solve();
    return 0;
}

Measured memory_bytes: 256
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}
ll mp[Max+10];

int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;


    cin>>n;

    while(n>0)
    {
         a=n%26;

         if(a)
            str+=a-1+'a';

         else str+='z';

         n/=26;

         if(a==0)n--;


    }

    reverse(vll(str));

    cout<<str<<endl;







}



Measured memory_bytes: 3664
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define mt(a) memset(a,0,sizeof(a))
#define MAXN 50+10
#define ll long long
const ll INF = 0x3f3f3f3f;
using namespace std;
bool vis[MAXN][MAXN];
int main (void)  
{   
	int n,m;
	cin>>n>>m;
	getchar();
	char c;
	mt(vis);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			if(c=='#')
				vis[i][j] = true;
		}
		getchar();
	}
	bool flag = false;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(vis[i][j])
			{
				if(vis[i+1][j]||vis[i-1][j]||vis[i][j-1]||vis[i][j+1])
					continue;
				else
					flag = true;
			}
		}
	}
	if(flag)
		cout<<"No\n";
	else
		cout<<"Yes\n"; 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

int main() {
    int n,k,a,cnt=0;
    cin>>n>>k;
    for(int i=0;i<n;++i){
      cin>>a;
      if(a>=k)cnt++;
    }
    cout<<cnt<<endl;

   return 0;
 }


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,kk;
struct node {
	int t,s,id,k;
}a[11];/*
int ans=999999999;
void dfs(int x,int s) {
	if(x>ans)return ;
	if(s>=k)ans=min(x,ans);
	for(int i=n;i>=1;--i) {
		for(int j=1;j<=a[i].t;++j) {
			if(a[i].k>0) {
				int tt=s;
				a[i].k--;s+=a[i].id*100;
				if(a[i].k==0)s+=a[i].s;
				dfs(x+1,s);
				a[i].k++;s=tt;
			}
		}
	}
}*/
int f[110000];
int main() {
	
	scanf("%d%d",&n,&kk);kk/=100;/*
	for(int i=1;i<=n;++i)scanf("%d%d",&a[i].t,&a[i].s),a[i].id=i,a[i].k=a[i].t;
	dfs(0,0);
	printf("%d\n",ans);*/
	int ans=0,sum=0;
	for(int i=1;i<=n;++i) {
		scanf("%d%d",&a[i].t,&a[i].s);
		a[i].id=i;ans+=a[i].t;a[i].s/=100;
		sum+=a[i].t*a[i].id+a[i].s;
	}
	memset(f,-1,sizeof(f));f[0]=0;
	for(int i=1;i<=n;++i) {
		for(int j=sum;j>=i;--j) {
			for(int k=a[i].t;k>0;--k) {
				int s=i*k;if(k==a[i].t)s+=a[i].s;
				if(s>j)continue;
				if(f[j-s]!=-1) {
					if(f[j]==-1)f[j]=f[j-s]+k;
					else f[j]=min(f[j],f[j-s]+k);
					if(j>=kk)ans=min(f[j],ans);
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
/*
 * :(
 * You taught me so much, I'm not scared anymore
 * 	I have to left go your hands that are holding me
 * 	 Even if I'm alone, I'll go on, even if it hurts
 * 	  I'll never forget the dream, I shared with you
 * 	   I'm glad to be with everyone, I'm glad to have been with everyone
 * 	    But on the morning when I wake up, no one is there
 */
//#define opti
#ifdef opti
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#ifndef opti
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef rd
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
#define double long double
#define pii pair<int,int>
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define all(con) con.begin(),con.end()
#define shuffle(a,b) random_shuffle(a,b,rng)
#define deb cout<<"Line: "<<__LINE__<<" pls "
typedef long long ll;
const ll mod=1000000007;
const ll inf=1e18;
//const ll mod=998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll powm(ll a, ll b, ll m);

void solve()
{
	int n,q;
	string s;
	cin>>n>>s>>q;
	while(q--)
	{
		int k;
		cin>>k;
		int ans=0;
		int d=0,m=0,dm=0;
		for(int i=1; i<=n; i++)
		{
			if(s[i-1]=='D')
				d++;
			if(s[i-1]=='M')
			{
				m++;
				dm+=d;
			}
			if(i>k)
			{
				if(s[i-k-1]=='D')
				{
					d--;
					dm-=m;
				}
				if(s[i-k-1]=='M')
					m--;
			}
			if(s[i-1]=='C')
				ans+=dm;
		}
		cout<<ans<<endl;
	}
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	#ifdef rd
		clock_t clk = clock();
	#endif
	int t=1;
//	cin>>t;
	while(t--)
		solve();
	#ifdef rd
		clk = clock() - clk;
		cout<<endl<<endl<< "Time Elapsed: " << fixed << setprecision(10) << ((double)clk)/CLOCKS_PER_SEC <<endl;
	#endif
	return 0;
}
ll powm(ll a,ll b, ll m)
{
	ll te=1;
	while(b)
	{
		if(b&1)
			te=(te*a)%m;
		a=(a*a)%m;
		b>>=1;
	}
	return te;
}


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

typedef long long ll;

#define INF 1e18
#define MAX_N 100005

ll N, K, h[MAX_N], memo[MAX_N];

ll dp(int p) {
  if (p < 1) {
  	return INF;
  }
  if (p == 1) {
  	return 0;
  }
  if (p <= K + 1) {
  	return abs(h[p] - h[1]);
  }
  ll opt = INF;
  for (int i = 1; i <= K; i++) {
  	opt = min(opt, abs(h[p] - h[p - i]) + dp(p - i));
  }
  return memo[p] = opt;
}

int main() {
  scanf("%lli %lli", &N, &K);
  for (int i = 1; i <= N; i++) {
  	scanf("%lli", &h[i]);
  }
  // printf("%lli\n", dp(N));
  for (int i = 2; i <= 1 + K; i++) {
  	memo[i] = abs(h[i] - h[1]);
  }
  for (int i = 2 + K; i <= N; i++) {
  	ll opt = INF;
  	for (int j = 1; j <= K; j++) {
  	  opt = min(opt, abs(h[i] - h[i - j]) + memo[i - j]);
	}
	memo[i] = opt;
  }
  printf("%lli\n", memo[N]);
}

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

int main(){
    int N,K;
    cin >> N >> K;
    int x;
    int i;
    int dist=0;
    for(i=0; i<N; i++){
        cin >> x;
        if(x>K-x) dist+=2*(K-x);
        else dist+=2*x;
    }

    cout << dist << endl;

    return 0;

}

Measured memory_bytes: 3576
N=int(input())
a = list(map(int,input().split()))
S = sum(a)
S1 = 0
for i in range(N):
    if i%2 == 1:
        S1 += a[i]
b = [0 for i in range(N)]
b[0] = S - 2*S1
print(b[0],end=' ')
for j in range(1,N):
    b[j] = 2*a[j-1] - b[j-1]
    print(b[j],end=' ')

Measured memory_bytes: 14092
#include <stdio.h>
 
#define max 100
#define inf 999999999
 
int m[max+1][max+1], p[max +1];
 
int min(int x, int y){
  if(x < y){
      return x;
    } else {
      return y;
      }
}

int matrixChainMultiplication(int n){
  int i, j, k, l, num1;
   
  for(i=1; i <= n; i++){
    m[i][i] = 0;
  }
  for(l=2; l <= n; l++){
      for(i=1; i <= n-l+1; i++){
        j = i + l - 1;
        m[i][j] = inf;
        for(k=i; k < j; k++){
            num1 = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
            m[i][j] = min(m[i][j], num1);
      }
    }
  }
  return m[1][n];
}
 
int main(){
  int i, n;
  scanf("%d", &n);
  for(i=0; i < n; i++){
    scanf("%d%d", &p[i], &p[i+1]);
  }
  printf("%d\n", matrixChainMultiplication(n));
  return 0;
}


Measured memory_bytes: 2100
import math
import itertools
N, D = map(int, input().split())

nums = []
for _ in range(N):
    nums.append(list(map(int, input().split())))

com = itertools.combinations(nums, 2)
ans =0
for c in com: 
    d = 0
    for y, z in zip(c[0], c[1]):
        d += abs(y - z) ** 2
    d = math.sqrt(d)
    ans += 1 if d == int(d) else 0

print(ans)



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
const ll LL_INF = 1LL<<60;

int main(){
    int n;
    cin >> n;
    vector<ll> A(n);
    ll allsum = 0;
    vector<ll> sum(n+1,0);
    for(int i=0;i<n;i++){
        cin >> A[i];
        allsum += A[i];
        sum[i+1] = sum[i] + A[i];
    }
    ll ans = LL_INF;
    for(int i=1;i<n;i++){
        ll p = sum[i];
        ll q = allsum - sum[i];
        ll diff = abs(p-q);
        ans = min(ans,diff);
    }
    cout << ans << endl;


}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define mkp make_pair
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<endl;
#define debug2(a,b) cout<<a<<' '<<b<<endl;
#define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,a,b)for(int i=a;i<b;i++)
#define repre(i,a,b)for(int i=a;i<=b;i++)
#define clr1(arr) memset(arr,-1,sizeof(arr));
#define clr0(arr) memset(arr,0,sizeof(arr));
#define pi pair<int,int>
#define pii pair<int,pi>
#define sortV(v) v.begin(),v.end()
#define pq priority_queue
#define mpq priority_queue<int,vector<int>,greater<int> >
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> orderedSet;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> orderedMSet;
//*p.find_by_order(index) return value at index
//p.order_of_key(key) return index
// DSU
/*
const int maxn=100009;
int arr[maxn];
int sz[maxn];
void init(){rep(i,maxn){arr[i]=i;sz[i]=1;}}
int root(int a){while(a!=arr[a]){arr[a]=arr[arr[a]];a=arr[a];}return a;}
int check(int a,int b){if(root(a)==root(b))return 1;return 0;}
int un(int a,int b)
{
  int roota=root(a);int rootb=root(b);
  if(sz[roota]>=sz[rootb]){sz[roota]+=sz[rootb];arr[rootb]=roota;}
  else {sz[rootb]+=sz[roota];arr[roota]=rootb;}
}
*/
int32_t main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
   fastio
   int a,b,c,d,e;
   cin>>a>>b>>c;
   if(c<=a-b)cout<<0;
   else cout<<c-(a-b)<<endl;

   return 0;
}


Measured memory_bytes: 764
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
  public static void main(String[] args) {
    Main m = new Main();
    m.run();
  }
  private void run() {
    int n = 0;
    Ball[] b = new Ball[0];
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
      n = Integer.parseInt(br.readLine());
      b = new Ball[n];
      for (int i=0;i<n;i++) {
        String[] s = br.readLine().split("\\s+");
        long x = Long.parseLong(s[0]);
        long y = Long.parseLong(s[1]);
        b[i] = x < y ? new Ball(x,y) : new Ball(y,x);
      }
    } catch (IOException e) {
      e.printStackTrace();
    }
    if (n == 1) {
      System.out.println(0);
      System.exit(0);
    }
    long rmin = 1000000001L;
    long rmax = 0L;
    long bmin = 1000000001L;
    long bmax = 0L;
    for (Ball a : b) {
      if (rmin > a.x) rmin = a.x;
      if (rmax < a.x) rmax = a.x;
      if (bmin > a.y) bmin = a.y;
      if (bmax < a.y) bmax = a.y;
    }
    long m = (rmax-rmin)*(bmax-bmin);
    Arrays.sort(b,Comparator.comparingLong(a -> ((Ball)a).x));
    bmin = rmin;
    long d = 1000000001L;
    long xmin = b[1].x;
    long ymin = b[0].y;
    for (int i=0;i<n-1;i++) {
      xmin = b[i+1].x;
      if (ymin > b[i].y) ymin = b[i].y;
      if (rmax < b[i].y) rmax = b[i].y;
      rmin = Math.min(xmin,ymin);
      if (d > rmax-rmin) d = rmax-rmin;
    }
    if (m > d*(bmax-bmin)) m = d*(bmax-bmin);
    System.out.println(m);
  }
  private class Ball {
    private long x,y;
    Ball(long x,long y) {
      this.x = x;
      this.y = y;
    }
  }
}

Measured memory_bytes: 97248
#include<stdio.h>
int main()
{
	int n,t,a,h,i,in;
	float temp, dif, tmin = 10000;
	scanf("%d %d %d", &n, &t, &a);
	for(i=0; i<n; i++)
	{
		scanf("%d", &h);
		temp = t-h*.006;
		dif = a-temp;
		if(dif<0) dif = -dif;
		if(dif<tmin)
		{
			tmin = dif;
			in = i+1;
		}
	}
	printf("%d\n", in);
	return 0;
}

Measured memory_bytes: 760
#include <iostream>
#include <vector>
#include <string>

using namespace std;
string S;
int K;

int main()
{
	cin >> S;
	cin >> K;

	long long ans = 0;

	int count = 1;
	for (unsigned int i = 1; i < S.size(); i++) {

		if (S.at(i) == S.at(i - 1)) {
			count++;
		}

		if (S.at(i) != S.at(i - 1) || i == S.size() - 1) {
			ans += count / 2;
			count = 1;
		}

	}

	ans *= K;


	if (S.at(0) == S.at(S.size() - 1)){
		unsigned cb = 0;
		unsigned ce = (unsigned)S.size() - 1;

		while (cb<S.size() && S.at(cb) == S.at(0)) {
			cb++;
		}

		if (cb == S.size()) {
			if (S.size() % 2 == 1) {
				ans += K / 2;
			}
		}
		else {

			while (S.at(ce) == S.at(0)) {
				ce--;
			}

			if ((S.size() - 1 - ce) % 2 == 1 && cb % 2 == 1) {
				ans += K - 1;
			}
		}
	}


	cout << ans <<endl;

	return 0;
}


Measured memory_bytes: 256