akhauriyash/Code-Regression huggingface dataset:
local mmi, mma = math.min, math.max

local n, wtot = io.read("*n", "*n")
local w, v = {}, {}
for i = 1, n do
  w[i], v[i] = io.read("*n", "*n")
end
local buf = w[1] - 1
for i = 1, n do
  w[i] = w[i] - buf
end

local map = {}
for i = 1, n do
  map[i] = {}
  local lim = wtot - buf * i
  lim = mmi(lim, 500)
  for j = 1, lim do
    map[i][j] = 0
  end
end

for i_n = 1, n do
  local iw, iv = w[i_n], v[i_n]
  for i = i_n - 1, 1, -1 do
    for j = 1, #map[i] do
      if 0 < map[i][j] then
        if j + iw <= #map[i + 1] then
          map[i + 1][j + iw] = mma(map[i + 1][j + iw], map[i][j] + iv)
        end
      end
    end
  end
  if iw <= #map[1] then
    map[1][iw] = mma(map[1][iw], iv)
  end
end

local ret = 0
for i = 1, n do
  for j = 1, #map[i] do
    ret = mma(ret, map[i][j])
  end
end
print(ret)


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
int A,B;
  cin>>A>>B;
  int ans=0;
  for(int i=A;i<=B;i++){
  string S=to_string(i);
    int n=S.size();
    bool b=true;
    for(int j=0;j<n/2;j++){
    if(S.at(j)!=S.at(n-j-1)){
     b=false; break;
    }
    } if(b) ans++;
  
  }cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class PaizaSample
{

    public class Station
    {
        public string name;
        public int time;

        public Station(string name, int time)
        {
            this.name = name;
            this.time = time;
        }
    }

    static void Main()
    {

        int[] nt = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        int n = nt[0];
        int t = nt[1];

        List<Station> list = new List<Station>();

        DateTime before = new DateTime();

        for (int i = 0; i < n; i++)
        {
            string[] inp = Console.ReadLine().Split(' ').ToArray();
            string dep = inp[1];

            DateTime depTime = DateTime.Parse(inp[0]);
            DateTime arrTime = DateTime.Parse(inp[2]);

            if (i != 0)
            {
                TimeSpan ts = depTime - before;
                if (ts >= new TimeSpan(0, 0, t, 0))
                {
                    list.Add(new Station(dep, ts.Hours * 60 + ts.Minutes));
                }
            }

            before = arrTime;

        }

        Console.WriteLine(list.Count);

        foreach(Station st in list){
            Console.WriteLine("{0} {1}", st.name, st.time);
        }

        Console.ReadKey();

    }
}

Measured memory_bytes: 10524
#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0); cin.sync_with_stdio(false);
	int q;
	cin >> q;
	priority_queue<int> lft, rgt;
	long long ret = 0;
	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			long long a, b;
			cin >> a >> b;
			ret += b;
			lft.push(a);
			rgt.push(-a);
			long long l = lft.top(); lft.pop();
			long long r = -rgt.top(); rgt.pop();
			long long d = l - r;
			if (d > 0) {
				ret += d;
				swap(l, r);
			}
			lft.push(l);
			rgt.push(-r);
		} else {
			cout << lft.top() << " ";
			cout << ret << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3828
#include <stdio.h>
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<complex>
#include<vector>

using namespace std;

int nx[]={0,1,0,-1};
int ny[]={0,1,0,-1};
//*****************************************


int main(void){

    int a,b,t;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&t);

    int ans=t/a;
    ans*=b;
    

    cout << ans<<endl;

    return 0;
}





Measured memory_bytes: 256
def main(x,y,xlst,ylst):
    xlst.append(x)
    ylst.append(y)
    xmax =max(xlst)
    ymin = min(ylst)
    if xmax<ymin:
        print("No War")
    else:
        print("War")
n,m,x,y = map(int,input().split())
xlst = list(map(int,input().split()))
ylst = list(map(int,input().split()))
main(x,y,xlst,ylst)


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

int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    cout << a[k-1] << endl;
    return 0;
}


Measured memory_bytes: 3616
#include<stdio.h>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
using namespace std;
char in[20];
int to[110];
int ijk[110];
int v[110];
string s[110];
int main(){
	int a;scanf("%d",&a);
	map<string,int>m;
	int n=0;
	for(int i=0;i<a;i++){
		scanf("%s",in);
		bool lb=false;
		for(int j=0;in[j];j++){
			if(in[j]==':')lb=true;
		}
		if(lb){
			string tmp=in;
			m[tmp]=i;
			to[i]=-1;
		}else{
			scanf("%s",in);
			string tmp=in;
			tmp[tmp.size()-1]=':';
			s[i]=tmp;
		//	to[i]=m[tmp];
		}
	}
	for(int i=0;i<a;i++){
		if(!~to[i])continue;
		to[i]=m[s[i]];
	}
	//for(int i=0;i<a;i++)printf("%d\n",to[i]);
	for(int i=0;i<110;i++)ijk[i]=999999999;
	ijk[0]=0;
	priority_queue<pair<int,int> >Q;
	Q.push(make_pair(0,0));
	while(Q.size()){
		int cost=-Q.top().first;
		int at=Q.top().second;
		Q.pop();
		if(v[at])continue;
		v[at]=1;
		if(at==a)continue;
		if(to[at]==-1&&!v[at+1]&&ijk[at+1]>cost){
			ijk[at+1]=cost;
			Q.push(make_pair(-cost,at+1));
		}
		if(to[at]!=-1){
			if(!v[at+1]&&ijk[at+1]>cost+1){
				ijk[at+1]=cost+1;
				Q.push(make_pair(-cost-1,at+1));
			}
			if(!v[to[at]]&&ijk[to[at]]>cost){
				ijk[to[at]]=cost;
				Q.push(make_pair(-cost,to[at]));
			}
		}
	}
	printf("%d\n",ijk[a]);
}

Measured memory_bytes: 1092
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <time.h>
#include <cstdlib>
#include <cmath>
#include <fstream>

int main(void) {

	//test??¨
	//std::ifstream in("test.txt");
	//std::cin.rdbuf(in.rdbuf());

	std::string W;
	std::cin >> W;
	std::transform(W.begin(), W.end(),W.begin(),tolower);

	int count = 0;
	std::string str;
	while (std::cin >> str) {
		if (W.length() == str.length()) {
			std::transform(str.begin(), str.end(), str.begin(), tolower);
			if (W == str) {
				count++;
			}
		}
	}

	std::cout << count << std::endl;

}

Measured memory_bytes: 1184
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#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(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#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;
const ll MAX_N = 100010;

ll ceil(ll a, ll b) {  // a÷b以上の最小の整数
    if(b == 0) {
        return 0;
    }
    return (a+b-1)/b;
}

int main() {
    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    out(ceil(n, min({a, b, c, d, e})) + 4);
    re0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

    private void run() {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int[] A = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = in.nextInt();
            }
            init(A);

            int max = 0;
            for (int i = 0; i < N; i++) {
                int a = i - 1 >= 0 ? query(0, i) : 0;
                int c = i + 1 < N ? query(i + 1, N - 0) : 0;
                max = Math.max(max, gcd(a > 0 ? a : c, c > 0 ? c : a));
            }

            System.out.println(max);
        }
    }

    private int[] tree;
    private int n;

    public void init(int[] a) {
        for (n = 1; n < a.length; n *= 2) {
        }
        tree = new int[2 * n - 1];
        for (int i = 0; i < a.length; i++) {
            tree[i + (n - 1)] = a[i];
        }
        for (int i = (n - 1) - 1; i >= 0; i--) {
            tree[i] = gcd(tree[getIndexOfLeftChild(i)], tree[getIndexOfRightChild(i)]);
        }
    }

    private int getIndexOfLeftChild(int current) {
        return 2 * current + 1;
    }

    private int getIndexOfRightChild(int current) {
        return 2 * current + 2;
    }

    public int query(int l, int r) {
        return query(l, r, 0, 0, n);
    }

    private int query(int left, int right, int currentNodeIndex, int leftOfCurrentNodeIndex, int rightOfCurrentNodeIndex) {
        assert leftOfCurrentNodeIndex == getLeft(currentNodeIndex);
        assert rightOfCurrentNodeIndex == getRight(currentNodeIndex);
        if (right <= leftOfCurrentNodeIndex || left >= rightOfCurrentNodeIndex) {
            return 0;
        }
        if (left <= leftOfCurrentNodeIndex && rightOfCurrentNodeIndex <= right) {
            return tree[currentNodeIndex];
        } else {
            int vl = query(left, right, getIndexOfLeftChild(currentNodeIndex), leftOfCurrentNodeIndex, (leftOfCurrentNodeIndex + rightOfCurrentNodeIndex) / 2);
            int vr = query(left, right, getIndexOfRightChild(currentNodeIndex), (leftOfCurrentNodeIndex + rightOfCurrentNodeIndex) / 2, rightOfCurrentNodeIndex);
            return gcd(vl > 0 ? vl : vr, vr > 0 ? vr : vl);
        }
    }

    private int getLeft(int currentNodeIndex) {
        int index = currentNodeIndex + 1;
        int high = Integer.highestOneBit(index);
        int multi = index - high;
        int left = multi * (n / high);
        return left;
    }

    private int getRight(int currentNodeIndex) {
        int index = currentNodeIndex + 1;
        int high = Integer.highestOneBit(index);
        int multi = index - high;
        int right = (multi + 1) * (n / high);
        return right;
    }

    public static final int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}


Measured memory_bytes: 50588
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    if(n>3){
        if(a[n-1]==0){
            cout <<"Yes"<<endl;
        }
        else if(n%3){
            cout << "No"<<endl;
        }
        else{
            if(a[0]==a[n/3-1]&&a[n/3]==a[2*n/3-1]&&a[2*n/3]==a[n-1]&&(a[0]^a[n/3]^a[n-1])==0){
                cout << "Yes"<<endl;
            }
            else{
                cout <<"No"<<endl;
            }
        }
    }
    else{
        if(a[0]^a[1]^a[2]){
            cout << "No"<<endl;
        }
        else{
            cout <<"Yes"<<endl;
        }
    }
    return 0;
}



Measured memory_bytes: 4012
#include <iostream>
#include <string>

int main() {
  int N, K;
  std::string S;
  std::cin >> N;
  std::cin >> S;
  std::cin >> K;
  
  for (int i=0; i<N; i++) {
    if (S[i] != S[K-1]) S[i] = '*';
  }
  
  std::cout << S << std::endl;
  
  return 0;
}

Measured memory_bytes: 768
// Created by sz
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;

const int N = 1e5 + 5;

struct node{
    int x, y;
    node(int x = 0,int y = 0):x(x), y(y){}
    bool operator < (const node& rhs) const {
        return x>rhs.x;
    }
};

priority_queue<node> cans;



int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,m;
    cin>>n>>m;
    int num, price;
    for (int i = 0; i < n; i++){
        cin>>price>>num;
        cans.push(node(price, num));
    }
    
    ll ans = 0;
    while (m) {
        auto cur = cans.top();
        cans.pop();
        int use = min(m, cur.y);
        ans += (ll)cur.x *use;
        m -= use;
    }
    
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1400
#include <stdio.h>

int main(){
	int count[4][3][10] = {0}, b, f, r, v, n, i;
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		scanf("%d %d %d %d", &b, &f, &r, &v);
		count[b - 1][f - 1][r - 1] += v;
	}
	for(b = 0; b < 4; b++){
		for(f = 0; f < 4; f++){
			for(r = 0; r < 10; r++){
				if(b == 3 && f == 3) break;
				if(b != 3 && f == 3){
					printf("##");
				} else {
					printf(" %d", count[b][f][r]);
				}
			}
		if(b == 3 && f == 3) break;
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int n;

int main() {
	int cnt = 1, sum = 0;
	cin >> n;
	while (sum + cnt < n) {
		sum += cnt;
		cnt++;
	}
	for (int i = cnt; i >= 1; i--) {
		if (n >= i) {
			n -= i;
			cout << i << endl;
		}
	}
}

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

int main(){
    bool flag=false;
    int res=0;
    int a, b, c;
    int a_sub, b_sub, c_sub;
    cin >> a >> b >> c;

    while(true){
        if(a%2==1 || b%2==1 || c%2==1){
            break;
        }
        if(a==b && b==c){
            flag=true;
            break;
        }
        a_sub = a/2; b_sub=b/2; c_sub=c/2;
        a = b_sub+c_sub; b = a_sub+c_sub; c = a_sub+b_sub;
        res++;
    }

    if(flag)
        cout << "-1" << endl;
    else
        cout << res << endl;

    return 0;  
}

Measured memory_bytes: 3616
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <tuple>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
ll n, a, b;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> a >> b;

  ll ans = 0;
  ll c;
  cin >> c;
  REP(i, n) {
    ll d;
    cin >> d;
    ans += min((d - c) * a, b);
    c = d;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define PPC(x) __builtin_popcount(x)
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...)
#endif
using namespace std;

const int maxN = 1 << 11;

char in[2][maxN];

int main()
{
	int n;
	scanf ("%d", &n);
	FOR(s, 0, 2)
		scanf ("%s", &in[s][0]);

	FOR(i, 0, n)
		printf("%c%c", in[0][i], in[1][i]);
	printf("\n");

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<ctype.h>
#include<string.h>
int main(void){
	int x,y,i,j,k,m;
	char a[101],b[101];
	scanf("%d",&m );
	x=0;
	y=0;
	for(i=0;i<m;i++){
		scanf("%s %s",a,b );

		for(j=0;;j++){
			if(a[j]=='\0'&& b[j]=='\0'){
				x++;
				y++;
				break;
			}else if(a[j]>b[j]){
				x+=3;
				break;
			}else if(a[j]<b[j]){
				y+=3;
				break;
			}
		}

	}
	printf("%d %d\n",x,y);

	return 0;
}

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

int main() {
  for(int n, m; cin >> n >> m, n|m; ) {
    vector<int> a(n), b(m);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < m; ++i) cin >> b[i];
    int s = -1, t = -1;
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < m; ++j) {
        swap(a[i], b[j]);
        if(accumulate(a.begin(), a.end(), 0)
           == accumulate(b.begin(), b.end(), 0)) {
          if(s == -1 || a[s] + b[t] > a[i] + b[j]) {
            s = i;
            t = j;
          }
        }
        swap(a[i], b[j]);
      }
    }
    if(s == -1) cout << -1 << endl;
    else cout << a[s] << " " << b[t] << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
def main():
    K = int(input())
    N = 50
    ans = list(range(50, 0, -1))
    if K <= 50:
        ans = ans[:K] + [0]*(50-K)
    else:
        x = (K-50) // 50
        y = (K-50) % 50
        for i in range(50):
            ans[i] += x
            if i < y:
                ans[i] += 1
    print(N)
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 38384
#include<stdio.h>
#include<stdlib.h>
int main(void){
  int n, k, i, count = 0;
  int *h;
  scanf("%d %d", &n, &k);
  h = (int *)malloc(n * sizeof(int));
  
  for (i = 0; i < n; i++) {
    scanf("%d", h + i);
  }
  for (i = 0; i < n; i++){
    if (k <= h[i])count++;
  }
  printf("%d", count);
  return (0);
}

Measured memory_bytes: 512
///cREATED bY BERNARB.01
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef priority_queue<int,vector<int>,greater<int>> pqil;
typedef priority_queue<int> pqig;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef priority_queue<pii> pqiig;
typedef vector<pii> vii;
typedef vector<piii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef map<int, int> mii;
#define mid ((l+r)/2)
#define PB push_back
#define PP pop_back
#define PF push_front
#define DF pop_front
#define F first
#define S second
#define MP make_pair
#define C continue
#define B break
#define R return
#define sz(v) (int)(v).size()
#define len(s) (int)(s).length()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(arr, x) memset((arr), (x), sizeof (arr))
#define loop(n) for(int i=0; i<(n); i++)
#define jloop(n) for(int j=0; j<(n); j++)
#define rloop(n) for(ll i=(n)-1; i>=0; i--)
const ll N = 2e5+9;
const ll INF = 2e17+423;
const ll mod = 1e9+7; //998244353;
const ld pi = acos(-1.0);
const ld cmpf = 1e-9;
//__int128_t
#define endl '\n'
ll po(ll,ll);














int main() {
  /*#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  #endif // ONLINE_JUDGE*/
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  if(m==n) cout << "Yes\n";
  else cout << "No\n";
  R 0;
}
/*

*/



































ll po(ll x, ll n){
  if(n==0) R 1;
  ll y = po(x, n/2);
  y = ((y)*(y));
  if(n%2) y = (y*(x));
  R y;
}


Measured memory_bytes: 256
N=int(input())
s=[int(input()) for i in range(N)]
ans=sum(s)
s.sort()
if ans%10!=0:
    print(ans)
else:
    for i in range(N):
        if(ans-s[i])%10!=0:
            ans-=s[i]
            break
    if ans%10==0:
        print(0)
    else:
        print(ans)

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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

bool ok(VI& xs, VI& ys, VI& ps, int n){
  REP(i,n-1) if(xs[i] >= xs[i+1]) return false;
  REP(i,n-1) if(ys[i] <= ys[i+1]) return false;
  REP(i,n-1) if(xs[ps[i]]+ys[ps[i]] >= xs[ps[i+1]]+ys[ps[i+1]])
	return false;
  return true;
}

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

  int N; cin >> N;
  VI ps(N);
  REP(i,N){
	cin >> ps[i];
	--ps[i];
  }
  
  vector<int> xs(N), ys(N);
  REP(i,N) xs[i] = (i+1)*N;
  REP(i,N) ys[N-1-i] = (i+1)*N;
  REP(i,N)
	xs[ps[i]] += i;

  REP(i,N) cout << (i?" ":"") << xs[i]; cout << endl;
  REP(i,N) cout << (i?" ":"") << ys[i]; cout << endl;

  return 0;
}


Measured memory_bytes: 896
#!/usr/bin/env python
"""エイシング プログラミング コンテスト 2020: A - Number of Multiples
https://atcoder.jp/contests/aising2020/tasks/aising2020_a
"""


def main():
    L, R, d = list(map(int, input().split()))
    ans = 0
    for n in range(L, R + 1):
        if n % d == 0:
            ans += 1
    print('{}'.format(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9168
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def round(x,d=0):
    p = 10**d
    return (x * p * 2 + 1) // 2 / p

def solve():
    n = II()
    A = LI()

    ave = int(round(sum(A) / n))

    cost = 0
    for a in A:
        cost += pow(a-ave, 2)
    print(cost)




if __name__ == '__main__':
    solve()


Measured memory_bytes: 9028
#include<iostream>
#include<cstdio>
using namespace std;
int cnt;
int main()
{
  int a,b,sum;
  cin>>a>>b;
  for(int i=a;i<=b;i++)
  {
    int n=i;
     sum=0;
     while(n)
     {
       int r=n%10;
       sum=sum*10+r;
        n/=10;

     }
     if(sum==i) cnt++;

  }


   cout<<cnt<<'\n';




    return 0;

}

Measured memory_bytes: 3592
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

int main() {
    ll N;
    cin >> N;
    vector<double> pis;
    for (ll i = 0; i < N; i++) {
        double pi;
        cin >> pi;
        pis.push_back(pi);
    }
    auto dp = make_vec_nd((double)0.0, N, N+1);
    dp[0][0] = 1.0 - pis[0];
    dp[0][1] = pis[0];
    for (ll i = 0; i < N-1; i++) {
        for (ll head_cnt = 0; head_cnt <= i+1; head_cnt++) {
            // dp[i][head_cnt]確定
            dp[i+1][head_cnt] += dp[i][head_cnt] * (1.0 - pis[i+1]);
            dp[i+1][head_cnt+1] += dp[i][head_cnt] * pis[i+1];
        }
    }
    double ans = 0.0;
    for (ll head_cnt = 0; head_cnt <= N; head_cnt++) {
        if (head_cnt > N - head_cnt) {
            ans += dp[N-1][head_cnt];
        }
    }
    cout << fixed << setprecision(10) << ans << endl;
}



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

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  vector<int> check(n, 0);	//右隣以上なら1
  for(int i = 0; i < n; i++) {
    cin >> h.at(i);
  }
  
  
  for(int i = 0; i < n-1; i++) {
    if(h.at(i) >= h.at(i+1)) check.at(i) = 1;
  }
  
  //集計
  int count = 0;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    if(check.at(i) == 1) {
      count++;
    } else {
      ans = max(ans, count);
      count = 0;
    }
  }
  ans = max(ans, count);
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#define ll long long 
#define pb push_back
#define pf push_front

using namespace std;

void solve(){
    char a; cin>>a;
    if(a-'a'>=0) cout<<"a"<<endl;
    else cout<<"A"<<endl;

}

int main(){
	int t=1; //cin>>t;
	while(t--){
		solve();
	}
return 0;
}

Measured memory_bytes: 3544
n = int(input())
g = [[] for _ in range(n)]
e = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
    e.append((a - 1, b - 1))
m = int(input())
l = [set() for _ in range(m)]
for i in range(m):
    u, v = map(int, input().split())
    s = [u - 1]
    dist = [-1] * n
    dist[u - 1] = 0
    r = [-1] * n
    while s:
        d = s.pop()
        for node in g[d]:
            if dist[node] == -1:
                s.append(node)
                dist[node] = dist[d] + 1
                r[node] = d
    d = v - 1
    while r[d] != -1:
        a, b = min(d, r[d]), max(d, r[d])
        l[i].add(e.index((a, b)))
        d = r[d]
ans = 0
for i in range(2 ** m):
    cnt = 0
    s = set()
    for j in range(m):
        if (i >> j) & 1:
            cnt += 1
            s |= l[j]
    if cnt % 2:
        ans -= 2 ** (n - len(s) - 1)
    else:
        ans += 2 ** (n - len(s) - 1)
print(ans)


Measured memory_bytes: 44616
# include <bits/stdc++.h>
# define rep(i, n) for(ll i = 0; i < (n); ++i)
# define reps(i, n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(ll i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(ll i=((int)(n)); i>0; --i)
# define ll long long
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
# define P pair<int, int>
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; }
ll lmax(ll a, ll b){if(a>= b) return a;return b;}
ll lmin(ll a, ll b){if(a>= b) return b;return a;}


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

  while(true){
    bool flag = true;
    for(int i = 2; i * i <= x; i++){
      if(x%i==0) flag = false;
    }
    if(flag){
      cout << x << endl;
      return 0;
    }
    x++;
  }
}


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

int main() {
    int a;
    std::string s;
    std::cin>>a;
    std::cin>>s;
    if(a<3200){
        std::cout<<"red"<<'\n';
    }else{
        std::cout<<s<<'\n';
    }
    return 0;
}


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

int main(){
  double n,y,b[51],r,t;
  
  while(1){
    double ans[51]={};
    cin >> n;
    if(n==0){
      break;
    }
    cin >> y;
    for(int i=0;i<n;i++){
      cin >> b[i] >> r >> t;
      if(t==1){
	ans[i]=1+y*(r/100); // 0.12(2)
      }else{
	ans[i]=pow((1+r/100),y);  //0.003(1)
      }
    }
    int max=0;
    for(int i=0;i<n;i++){
      if(ans[max]<ans[i]){
	max=i;
      }
    }
    cout << b[max] << '\n';
  }

  return 0;
}



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

int main(){

    int a,b,d,e;
    int c=0;
    cin>>a;

b=a/500;
    d=b*1000;
    e=(a%500)/5;

    cout<<d+e*5<<endl;




}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> pii;
int miss[66][20];
int main(){
    
  int M,T,P,R;
  int m,t,p,j;
  int i,k;
  vector<pii> team;
  while(cin>>M>>T>>P>>R,M|T|P|R){
    memset(miss,0,sizeof(miss));
    team.clear();
    for(i=0;i<=T;i++){
      team.push_back(pii(0,0));
    }
    
    for(i=0;i<R;i++){
      cin>>m>>t>>p>>j;
      if(j==0){
	team[t].first++;
	team[t].second+=(m+miss[t][p]*20);
      }
      else{
	miss[t][p]++;
      }
    }
    /*
    for(i=0;i<T;i++){
      cout<<i<<":"<<team[i].first<<" : "<<team[i].second<<endl;
    }
    */
    int prei,tmpi,tmp;
    int use[60];
    memset(use,0,sizeof(use));
    for(j=0;j<T;j++){
      i=T;
      while(use[i]==1)i--;
      tmpi=i;
      for(i=i-1;i>0;i--){
	if(use[i]==1) continue;
	if(team[i].first>team[tmpi].first){
	  tmpi=i;
	}
	else if(team[i].first==team[tmpi].first){
	  if(team[i].second<team[tmpi].second){
	    tmpi=i;
	  }
	}
	
      }
      use[tmpi]=1;
      //cout<<"["<<tmpi<<"];"<<team[tmpi].first<<"---"<<team[tmpi].second<<endl;
      if(j==0) cout<<tmpi;
      else if(team[tmpi].first==team[prei].first&&team[tmpi].second==team[prei].second){
	cout<<"="<<tmpi;
      }
      else{
	cout<<","<<tmpi;
      }
      prei=tmpi;
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3084
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

C = Counter(A)

key = sorted(C.keys())  #Aに含まれる数の種類

if (N-len(key))%2 == 0:
	print(len(key))
else:
	print(len(key) - 1)


Measured memory_bytes: 22936
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val p = Array(n) { sc.nextInt() - 1 }
    val pos = Array(n) { 0 }
    for (i in 0 until n) {
        pos[p[i]] = i
    }
    var max = 1
    var cur = 1
    for (i in 1 until n) {
        if (pos[i - 1] < pos[i]) {
            cur++
        }
        if (pos[i - 1] > pos[i] || i == n - 1) {
            max = Math.max(max, cur)
            cur = 1
        }
    }
    println(n - max)
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 50460
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define F(i,a,n) for(int i=a; i<n; i++)
#define INF 100000000000 // long only

typedef struct DATA{
  int h;
  int flag;
}data;

int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  long h[n];
  F(i,0,n)scanf("%ld",h+i);
  int a[m],b[m];
  F(i,0,m) scanf("%d%d",a+i,b+i);
  int ans[n];
  F(i,0,n)ans[i]=1;
  F(i,0,m){
    if(h[a[i]-1]>h[b[i]-1]) ans[b[i]-1]=0;
    else if(h[a[i]-1]==h[b[i]-1]){
      ans[a[i]-1]=0;
      ans[b[i]-1]=0;
    }
    else ans[a[i]-1]=0;
  } 
  int sum=0;
  F(i,0,n)if(ans[i]==1)sum++;
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 3684
n, x = map(int, input().split())

a, p = [1], [1]

for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def cnt_p(n, x):
    if n == 0:
        if x <= 0:
            return 0
        return 1
    elif x <= 1 + a[n - 1]:
        return cnt_p(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + cnt_p(n - 1, x - 2 - a[n - 1])


print(cnt_p(n, x))

Measured memory_bytes: 9064
<?php
fscanf(STDIN,"%d %d",$N,$D);
for($i=0;$i<$N;$i++){
  $X = fgets(STDIN);
  ${"array".$i} = explode(" ",$X);
}
$counter = 0;
for($i=0;$i<$N-1;$i++){
  for($j=$i+1;$j<$N;$j++){
    $result = calcDistance(${"array".$i},${"array".$j});
    if(is_decimal($result)){
      $counter++;
    }
  }
}
echo $counter;
//echo implode(",",$array);
//${"array".$i} = 0;

//2点の距離を求める
function calcDistance($arrayA,$arrayB){
  $result = 0;
  for($i=0;$i<count($arrayA);$i++){
    $result += ($arrayA[$i]-$arrayB[$i])**2;
  }
  return sqrt($result);
}

function is_decimal($value) {
    return filter_var($value, FILTER_VALIDATE_INT) !== false;
}


Measured memory_bytes: 3576
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner( System.in );
		
		int n	= sc.nextInt();
		int m	= sc.nextInt();
		
		int[][] vectorA = new int[n][m];
		int[]	vectorB = new int[m];
		int[]	vectorC = new int[n];
		
		// input
		for( int i = 0; i < n; i++ ) {
			for( int j = 0; j < m; j++ ) {
				vectorA[i][j] = sc.nextInt();

			}
			
		}
		
		// input
		for( int i = 0; i < m; i++ ) {
			vectorB[i] = sc.nextInt();
			
		}
		
		// calc and output
		for( int i = 0; i < n; i++ ) {
			vectorC[i] = 0;
			for( int j = 0; j < m; j++ ) {	
				vectorC[i] += ( vectorA[i][j] * vectorB[j] );
				
			}
			
			System.out.println( vectorC[i] );
		}
		
		
		
		
	}
	
}

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

#define REP(i, n) for (int i = 0; i < n; ++i)

int pls(int n1, int i, int n2) {
  if (i == 0) { return n1+n2; }
  if (i == 1) { return n1-n2; }
  return 0;
}

int plusall(int a, int b, int c, int d, int i, int j, int k) {
  int ans = pls(a, i, b);
  ans = pls(ans, j, c);
  ans = pls(ans, k, d);
  return ans;
}

char ijktochar(int i) {
  if (i == 0) { return '+'; }
  if (i == 1) { return '-'; }
  return '0';
}

int main() {
  string s;
  cin >> s;
  int a = s[0] - '0';
  int b = s[1] - '0';
  int c = s[2] - '0';
  int d = s[3] - '0';

  char op1, op2, op3;
  REP(i, 2) {
    REP(j, 2) {
      REP(k, 2) {
        if (plusall(a, b, c, d, i, j, k) == 7) {
          op1 = ijktochar(i);
          op2 = ijktochar(j);
          op3 = ijktochar(k);
          break;
        }
      }
    }
  }

  cout << a << op1 << b << op2 << c << op3 << d << "=7" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

		String str[] = br.readLine().split(" ");

		int a = Integer.parseInt(str[0]);
		int v = Integer.parseInt(str[1]);

		str = br.readLine().split(" ");

		int b = Integer.parseInt(str[0]);
		int w = Integer.parseInt(str[1]);

		int t = Integer.parseInt(br.readLine());

		int acr = v - w;

		if (acr <= 0) {
			System.out.println("NO");
		} else {
			if ((long) acr * t >= (long) Math.abs(a - b)) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
}


Measured memory_bytes: 32760
#include<stdio.h>
int main() {
	int n, m, x, j, k, a,sum,p,o,t;
	scanf("%d", &n);
	for (m = 0; n > m; m++) {
		scanf("%d %d %d %d", &x, &j, &k, &a);
		sum = x*k + j*a;
		o = k;
		t = a;
		if (k < 5) {
			o = 5;
		}
		if (a < 2) {
			t=2;
		}
		if (k >= 5 && a >= 2) {
			sum=sum * 8 / 10;
		}
		p = x*o + j*t;
		p = p * 8/10;
		if (p < sum) {
			sum = p;
		}
	printf("%d\n", sum);
	}
	return 0;
}


Measured memory_bytes: 2748
N = int(input())
S = [input() for _ in range(N)]
res = [0] * 5
ini = 'MARCH'
for i in range(N):
    for j in range(5):
        if S[i][0] == ini[j]:
            res[j] += 1

ans = 0
for i in range(5):
    for j in range(i+1,5):
        for k in range(j+1,5):
            ans += res[i]*res[j]*res[k]
print(ans)

Measured memory_bytes: 83076
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            abc043_b();
        }

        static void abc043_b()
        {
            // B - バイナリハックイージー
            string S = Console.ReadLine().Trim();
            char[] Sarr = S.ToCharArray();
            var stack = new Stack<char>();
            foreach (var c in Sarr)
            {
                if (c == 'B')
                {
                    if (stack.Count > 0) stack.Pop();
                }
                else
                {
                    stack.Push(c);
                }
            }
            string ans = string.Join("", stack.Reverse());
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13396
#include <stdio.h>

void	ft_swap(long *a, long *b)
{
	long tmp;
	
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void	a_qsort(long *tab, long left, long right)
{
	long Left = left;
	long Right = right;
	long pivot = tab[(left + right) / 2];

	while (1)
	{
		while (tab[Left] < pivot)
			Left++;
		while (tab[Right] > pivot)
			Right--;
		if (Left >= Right)
			break ;
		ft_swap(&tab[Left], &tab[Right]);
		Left++;
		Right--;
	}

	if (Left - 1 > left)
		a_qsort(tab, left, Left - 1);
	if (Right + 1 < right)
		a_qsort(tab, Right + 1, right);
}

void	d_qsort(long *tab, long left, long right)
{
	long Left = left;
	long Right = right;
	long pivot = tab[(left + right) / 2];

	while (1)
	{
		while (tab[Left] > pivot)
			Left++;
		while (tab[Right] < pivot)
			Right--;
		if (Left >= Right)
			break ;
		ft_swap(&tab[Left], &tab[Right]);
		Left++;
		Right--;
	}

	if (Left - 1 > left)
		d_qsort(tab, left, Left - 1);
	if (Right + 1 < right)
		d_qsort(tab, Right + 1, right);
}

int main(void)
{
	long N;
	long x;
	long i;
	scanf("%ld", &N);
	scanf("%ld", &x);
	long a[N + 1];
	long sum = 0;
	long count = 0;
	i = 1;
	while (i <= N)
	{
		scanf("%ld", &a[i]);
		sum += a[i];
		i++;
	}
	if (sum == x)
	{
		printf("%ld", N);
		return 0;
	}
	else if (sum < x)
	{
		d_qsort(a, 1, N);
		i = 1;
		while (i <= N)
		{
			if (i != N && x >= a[i])
			{
				x -= a[i];
				count++;
			}
			if (i == N)
				break ;
			i++;
		}
	}
	else if (sum > x)
	{
		a_qsort(a, 1, N);
		i = 1;
		while (i <= N)
		{
			if (x >= a[i])
			{
				x -= a[i];
				count++;
			}
			i++;
		}
	}
	printf("%ld", count);
	return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;


int main() {
    ll n, d; cin >> n >> d;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ll x, y; cin >> x >> y;
        if(x * x + y * y <= d * d) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <stdio.h>

using namespace std;

const int MAX_K = 201;
int mem[MAX_K][MAX_K][MAX_K];

int gcd(int a, int b)
{
    if(a < b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

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

void solve(long long K){
    long long result = 0;

    for(int i = 1; i <= (int)K; i++) {
        for(int j = 1; j <= (int)K; j++) {
            for(int k = 1; k <= (int)K; k++) {
                if(mem[i][j][k] != 0 || mem[k][i][j] != 0 || mem[j][k][j] != 0) {
                    result += mem[i][j][k];
                }else {
                    int ans_r = gcd(i, j);
                    int ans = gcd(ans_r, k);
                    mem[i][j][k] = ans;
                    mem[k][i][j] = ans;
                    mem[j][k][i] = ans;

                    result += ans;
                }
            }
        }
    }

    cout << result << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long K;
    scanf("%lld",&K);
    solve(K);
    return 0;
}


Measured memory_bytes: 34736
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char x;
  cin >> x;
  if(x>='A' && x<= 'Z')
  {
    cout << 'A' << endl;
  }
  if(x>='a' && x<= 'z')
  {
    cout << 'a' << endl;
  }
  return 0;
}


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

int f[45];
int n;

int fibonacci(int n){
	
	cin >> n;
	f[0]=f[1]=1;

	for(int i=2;i<=n;i++){
		f[i]=f[i-1]+f[i-2];
	}
	return f[n];
}


int main(){
	cout << fibonacci(n) << "\n";
    return 0;
}

Measured memory_bytes: 1164
H,W=map(int,input().split())
S=[input() for _ in range(H)]
dp=[[10**9]*W for _ in range(H)]
if S[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0
for i in range(H):
    for j in range(W):
        for di,dj in [(0,1),(1,0)]:
            ni=i+di
            nj=j+dj
            if ni<H and nj<W:
                if S[i][j]=='.' and S[ni][nj]=='#':
                    dp[ni][nj]=min(dp[ni][nj],dp[i][j]+1)
                else:
                    dp[ni][nj]=min(dp[ni][nj],dp[i][j])
print(dp[-1][-1])

Measured memory_bytes: 3188
n = int(input())
words = [input() for _ in range(n)]
use = [words[0]]
for i in range(1, n):
    if words[i] in use:
        print('No')
        exit()

    if use[-1][-1] != words[i][0]:
        print('No')
        exit()

    use.append(words[i])

print('Yes')

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

struct Edge {
    int to;
    lli cost;
    Edge(int t, lli c) {
        to = t;
        cost = c;
    }
    Edge() {}
    bool operator<(const Edge e) const {
        return cost > e.cost;
    }
};

const lli inf = 1LL << 60;

void dijk(vector<vector<Edge>> &G, vector<lli> &minCost, int srt, int node) {
    vector<bool> used(node, false);
    minCost.assign(node, inf);
    priority_queue<Edge, vector<Edge>> pq;
    pq.emplace(srt, 0);
    minCost[srt] = 0;
    while (pq.size()) {
        auto elem = pq.top();
        pq.pop();
        if (used[elem.to]) continue;
        used[elem.to] = true;
        for (auto nxt : G[elem.to]) {
            lli c = elem.cost + nxt.cost;
            if (c < minCost[nxt.to]) {
                minCost[nxt.to] = c;
                pq.emplace(nxt.to, c);
            }
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--;
    t--;
    vector<vector<Edge>> enG(n), snG(n);
    REP(i, 0, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        enG[u].push_back(Edge(v, a));
        enG[v].push_back(Edge(u, a));
        snG[u].push_back(Edge(v, b));
        snG[v].push_back(Edge(u, b));
    }
    vector<lli> enC(n), snC(n);
    dijk(enG, enC, s, n);
    dijk(snG, snC, t, n);
    vector<lli> minCost(n, inf);
    REP(i, 0, n) {
        minCost[i] = enC[i] + snC[i];
    }
    for (int i = n - 2; i >= 0; i--) {
        minCost[i] = min(minCost[i], minCost[i + 1]);
    }
    REP(i, 0, n) {
        cout << 1'000'000'000'000'000LL - minCost[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 19012
#include<stdio.h>
int main(void) {
	int N;
	int i, j;
	int M;
	int count;
	int max = 0;
	scanf("%d", &N);
	if (N >= 64) {
		max = 64;
	}
	else if (N >= 32) {
		max = 32;
	}
	else if (N >= 16) {
		max = 16;
	}
	else if (N >= 8) {
		max = 8;
	}
	else if (N >= 4) {
		max = 4;
	}
	else if (N >= 2) {
		max = 2;
	}
	else {
		max = 1;
	}
	printf("%d", max);
}

Measured memory_bytes: 128
from itertools import combinations
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]
ans = 0

def check(c, x, y, k, w, h):
    li = [[k for k in i[:]] for i in c[:]]
    for yy in y:
        li[yy] = ['x' for _ in range(w)]
    for xx in x:
        for yyy in range(h):
            li[yyy][xx] = 'x'
    ct = 0
    for i in li: ct += i.count('#')
    return ct == k

h, w, k = m_in(int)
c = [input() for _ in range(h)]
count = 0
for i in c: count += i.count('#')
xc = []
yc = []
for i in range(w):
    for res in combinations(range(w), i):
        xc.append(res)
for i in range(h):
    for res in combinations(range(h), i):
        yc.append(res)
for x in xc:
    for y in yc:
        if check(c, x, y, k, w, h):
            ans += 1

print(ans)

Measured memory_bytes: 9144
#include<iostream>
 
using namespace std;
 
int main() {
	int a,b;
	cin >> a >> b;
	int ans = 0;
	int sockets = 1;
	while(sockets < b){
        sockets--;
        sockets += a;
        ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3672
import java.util.Arrays;
import java.util.Scanner;

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

        long a[] = new long[n];
        long b[] = new long[n];
        long totala = 0, totalb = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
            totala += a[i];
        }
        for (int i = 0; i < n; i++) {
            b[i] = in.nextLong();
            totalb += b[i];
        }

        if (totala < totalb) {
            System.out.println(-1);
            return;
        }

        long d[] = new long[n];
        for (int i = 0; i < n; i++) {
            d[i] = a[i] - b[i];
        }

        Arrays.sort(d);

        int i = 0;
        long lack = 0;
        while (d[i] < 0) {
            lack += d[i];
            i++;
        }

        int j = n - 1;
        while (lack < 0) {
            lack += d[j];
            j--;
        }

        System.out.println(i + (n - 1 - j));
    }
}

Measured memory_bytes: 79120
import bisect
n,m = map(int,input().split())
a = list(map(int,input().split()))

s = []
k = 0
for i in range(0,n):
    k += a[i]
    s.append(k%m)

ass = 0
w = s.count(0)
ass += w*(w+1)//2
s.sort()

hj = w
while hj <= n-1:
    jkl = bisect.bisect_right(s,s[hj])
    w = jkl - hj
    if w != 1:
        ass += w*(w-1)//2
    hj = jkl
print(ass)

Measured memory_bytes: 14480