akhauriyash/Code-Regression huggingface dataset:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def create_integer_string(counts):
    res = ""

    for i in range(9, 0, -1):
        count = counts[i]
        res += str(i) * count

    return res


def main():
    from copy import copy

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    pat = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    match_nums = dict()

    for x in a:
        match_num = pat[x]
        match_nums[match_num] = x

    dp = [0] * (n + 1)
    dp_c = [[0] * 10 for _ in range(n + 1)]

    for i in range(n + 1):
        for match_num, val in match_nums.items():
            if i + match_num > n:
                continue
            if i > 0 and dp[i] == 0:
                continue
            if dp[i + match_num] < dp[i] + 1:
                dp[i + match_num] = dp[i] + 1
                dp_c[i + match_num] = copy(dp_c[i])
                dp_c[i + match_num][val] += 1
            elif dp[i + match_num] == dp[i] + 1:
                counts_cur = copy(dp_c[i + match_num])
                cur = create_integer_string(counts_cur)
                counts_new = copy(dp_c[i])
                counts_new[val] += 1
                new = create_integer_string(counts_new)
                if new > cur:
                    dp[i + match_num] = dp[i] + 1
                    dp_c[i + match_num] = copy(dp_c[i])
                    dp_c[i + match_num][val] += 1

    counts = dp_c[n]

    print(create_integer_string(counts))


if __name__ == '__main__':
    main()


Measured memory_bytes: 54872
import java.util.Arrays;
import java.util.Scanner;
 
/**
 *http://abc075.contest.atcoder.jp/tasks/abc075_d
 */
public class Main {
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		final int N = sc.nextInt();
		final int K = sc.nextInt();
		Point[] points = new Point[N];
		long[] xList = new long[N];
		long[] yList = new long[N];
		for(int i=0; i<N; i++){
			points[i] = new Point(sc.nextLong(), sc.nextLong());
			xList[i] = points[i].x;
			yList[i] = points[i].y;
		}
		sc.close();
		
		long ans = Long.MAX_VALUE;
		Arrays.sort(xList);
		Arrays.sort(yList);
		for(int xi=0; xi<N; xi++){
			for(int xj=xi+1; xj<N; xj++){
				for(int yi=0; yi<N; yi++){
					for(int yj=yi+1; yj<N; yj++){
						long xl = xList[xi];
						long xr = xList[xj];
						long yb = yList[yi];
						long yu = yList[yj];
						int num = 0;
						for(Point p:points){
							if(xl<=p.x && p.x<=xr && yb<=p.y && p.y<=yu){
								num++;
							}
						}
						if(num>=K){
							ans = Math.min(ans, (xr-xl)*(yu-yb));
						}
					}
				}
			}
		}
		System.out.println(ans);
 
	}
	
	static class Point{
		public Point(long x, long y) {
			this.x = x;
			this.y = y;
		}
		long x;
		long y;
	}
 
}

Measured memory_bytes: 24404
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <cstring>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
typedef long long ll;
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}
struct edge {
    ll to,cost;
};
/*
const int COM_MAX = 500500;
long long fac[COM_MAX],finv[COM_MAX],inv[COM_MAX];
void init(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < COM_MAX; i++){
        fac[i] = fac[i-1]*i%MOD;
        inv[i] = MOD - inv[MOD%i]*(MOD/i)%MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}
long long COM(int n,int k){
    if(n < k || n < 0 || k < 0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
*/

int main(){
    int N; cin >> N;
    vector<vector<edge> > g(N);
    vector<int> dist(N,-1);
    for (int i = 0; i < N-1; i++){
        ll u,v,w; cin >> u >> v >> w; u--; v--;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    queue<int> que;
    que.push(0);
    dist[0] = 0;
    while (que.size()){
        int now = que.front();
        que.pop();
        for (auto e : g[now]){
            if (dist[e.to] != -1) continue;
            
            if (e.cost % 2 == 0){
                dist[e.to] = dist[now];
            } else {
                dist[e.to] = 1 - dist[now];
            }
            que.push(e.to);
        }
    }
    for (auto e : dist){
        if (e == -1) cout << 0 << endl;
        else cout << e << endl;
    }
}

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

const int maxn = 1024;

int n;
char s[maxn][maxn];
int x, y;

std::string s4[4], s5[5], s6[6], s7[7];

void init() {
	s4[0] = "aabc";
	s4[1] = "ddbc";
	s4[2] = "bcaa";
	s4[3] = "bcdd";
	s5[0] = "aabba";
	s5[1] = "bcc.a";
	s5[2] = "b..cb";
	s5[3] = "a..cb";
	s5[4] = "abbaa";
	s6[0] = "aabc..";
	s6[1] = "ddbc..";
	s6[2] = "..aabc";
	s6[3] = "..ddbc";
	s6[4] = "bc..aa";
	s6[5] = "bc..dd";
	s7[0] = "aabbcc.";
	s7[1] = "dd.dd.a";
	s7[2] = "..d..da";
	s7[3] = "..d..db";
	s7[4] = "dd.dd.b";
	s7[5] = "..d..dc";
	s7[6] = "..d..dc";
}

void fill(int a) {
	if (a == 4) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				s[x+i][y+j] = s4[i][j];
			}
		}
	} else if (a == 5) {
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < a; j++) {
				s[x+i][y+j] = s5[i][j];
			}
		}
	} else if (a == 6) {
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < a; j++) {
				s[x+i][y+j] = s6[i][j];
			}
		}
	} else if (a == 7) {
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < a; j++) {
				s[x+i][y+j] = s7[i][j];
			}
		}
	}
	x += a;
	y += a;
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	init();
	std::cin >> n;
	if (n == 2) {
		std::cout << "-1\n";
	} else if (n == 3) {
		std::cout << "aa.\n..a\n..a\n";
	} else {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				s[i][j] = '.';
			}
		}
		int a = n%4+4; 
		x = 0, y = 0;
		fill(a);
		for (int i = 0; i < (n-a)/4; i++) {
			fill(4);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				std::cout << s[i][j];
			}
			std::cout << '\n';
		}
	}
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n;
	cin >> n;
	bool f = true;
	int cnt = 0;
	REP(i, n)
	{
		string s; cin >> s;
		if (s == "A") cnt++;
		else cnt--;
		if (cnt < 0) f = false;
	}
	if (cnt != 0) f = false;
	cout << (f ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 3224
n = int(input())
d = {}
for _ in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 0
        
m = max(d.values())
ans = []
for t in d:
    if d[t] == m:
        ans.append(t)
ans.sort()
for u in ans:
    print(u)

Measured memory_bytes: 92120
var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
    input += chunk;
});
process.stdin.on('end', function() {
    main(input)
});

function main(input){
    var n = parseInt(input.trim());
    var dept = 100000;
    for(var i = 0; i < n; i += 1){
        dept = increaseDept(dept);
    }
    console.log(dept);
}

function increaseDept(dept){
    dept *= 1.05;
    dept = Math.ceil(dept / 1000) * 1000;
    return dept;
}

Measured memory_bytes: 15280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

ll a[100010],b[100010];
int main() {
	ll n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		b[i]=a[i]-a[i-1];
	}
	for(int i=1;i<n;i++){
		b[i]=b[i]+b[i-1];
	}
	ll ans=INF;
	for(int i=0;i<=n-k;i++){
		ll sum=0;
		sum=b[i+k-1]-b[i];
		ans=min({ans,sum+abs(a[i]),sum+abs(a[i+k-1])});
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 10000000;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

int main()
{
	ll X, Y;
	scanf("%lld%lld", &X, &Y);
	if( X%Y == 0 ) printf("-1\n");
	else printf("%lld\n", X*(Y-1));
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <array>
#include <stack>
#include <cstring>

enum PassageType{
	FREE, WALL, SEARCHED, GOAL,
};

bool isSearched[50][50][50][50] = {false};

struct Point {
	Point() { x = 0; y = 0; };
	Point(char x, char y) {
		this->x = x;
		this->y = y;
	};
	char x, y;
};

int main() {
	int w, h;

	while (std::cin >> w >> h && w && h) {
		std::memset(isSearched, false, sizeof(bool) * 50 * 50 * 50 * 50);
		std::array<std::vector<std::vector<int>>, 2> room;
		Point start[2];
		for (int i = 0; i < h; i++) {
			std::array<std::string, 2> str;
			for (int j = 0; j < str.size(); j++) {
				std::cin >> str[j];
				room[j].push_back(std::vector<int>());
				for (int k = 0; k < str[j].size(); k++) {
					int type = 0;
					if (str[j][k] == '.') type = FREE;
					else if (str[j][k] == '#') type = WALL;
					else if (str[j][k] == '%') type = GOAL;
					else if (str[j][k] == 'L' || str[j][k] == 'R') {
						start[j].x = k;
						start[j].y = i;
						type = SEARCHED;
					}
					room[j].back().push_back(type);
				}
			}
		}

		std::stack<std::pair<Point, Point>> s;
		s.push(std::make_pair(start[0], start[1]));
		int dx[] = {1, 0, -1, 0};
		int dy[] = {0, 1, 0, -1};

		bool isOk = false;
		while (!s.empty() && !isOk) {
			auto node = s.top(); s.pop();

			//?¬???????????????´????????¢???
			for (int i = 0; i < 4; i++) {
				auto next = node;
				next.first.x += dx[i];
				next.first.y += dy[i];
				next.second.x -= dx[i];
				next.second.y += dy[i];

				//??´????£???£
				next.first.x = std::min(std::max((char)0, next.first.x), (char)(w - 1));
				next.first.y = std::min(std::max((char)0, next.first.y), (char)(h - 1));
				next.second.x = std::min(std::max((char)0, next.second.x), (char)(w - 1));
				next.second.y = std::min(std::max((char)0, next.second.y), (char)(h - 1));
				//??????????????´????????????OK
				if (room[0][next.first.y][next.first.x] == GOAL && room[1][next.second.y][next.second.x] == GOAL) {
					isOk = true;
				}
				else {
					//?£???????????????????????????????
					if (room[0][next.first.y][next.first.x] == WALL) {
						next.first = node.first;
					}
					if (room[1][next.second.y][next.second.x] == WALL) {
						next.second = node.second;
					}
					if (!isSearched[next.first.y][next.first.x][next.second.y][next.second.x] && room[0][next.first.y][next.first.x] != GOAL && room[1][next.second.y][next.second.x] != GOAL) {
						s.push(next);
						isSearched[next.first.y][next.first.x][next.second.y][next.second.x] = true;
					}
				}
			}
		}

		std::cout << (isOk ? "Yes" : "No") << std::endl;
	}
	return 0;
}

Measured memory_bytes: 9796
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int dist[200][200];
int N,M,R;

void warshall_floyd(){
	REP(k,N)
		REP(i,N)
			REP(j,N)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main(){
	cin >> N >> M >> R;
	int r[R];
	REP(i,R){
		cin >> r[i];
		r[i]--;
	}
	int a[M],b[M],c[M];
	REP(i,M){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;b[i]--;
	}
	REP(i,N){
		REP(j,N){
			dist[i][j] = INF;
		}
	}
	REP(i,M){
		dist[a[i]][b[i]] = c[i];
		dist[b[i]][a[i]] = c[i];
	}
	warshall_floyd();
	sort(r, r + R);
	int ans = INF;
	do{
		int num = 0;
		REP(i,R - 1) num += dist[r[i]][r[i + 1]];
		ans = min(ans, num);
	}while(next_permutation(r, r + R));
	cout << ans << endl;
}

Measured memory_bytes: 640
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>=0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#include <bits/stdc++.h>
using namespace std;

//------------------------------typedef集
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
//---------------------------------
struct SegmentTree {
private:
    int n;
    vector<int> node;

public:
    SegmentTree(vi v) {

        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, INT_MAX);

        REP(i,sz) node[i+n-1] = v[i];
        REPN(i,n-2) node[i] = node[2*i+1] + node[2*i+2];
    }

    void update(int k, int x){
        k += n-1;
        node[k] = x;
        while(k){
            k = (k-1)/2;
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
    int getsum(int a, int b, int k=0, int l=0, int r=-1){
        if(r<0) r=n;
        if(r<=a || b<=l) return 0;
        if(a<=l && r<=b) return node[k];
        return getsum(a,b,2*k+1,l,(l+r)/2)+getsum(a,b,2*k+2,(l+r)/2,r) ;
    }
};

vi prime,pseudo;
int q,l,r;

int main(){
    prime.resize(100001,1);
    prime[0] = 0;
    prime[1] = 0;
    REP(i,318){
        if (prime[i]) {
            int itr = i*2;
            while(itr <= 100000){
                prime[itr] = 0;
                itr += i;
            }
        }
    }
    pseudo.resize(50001);
    REP(i,50001){
        pseudo[i] = prime[2*i+1] & prime[i+1];
    }

    SegmentTree ps2017 = SegmentTree(pseudo);

    I(q);
    REP(i,q){
        I(l); I(r);
        l /= 2; r /= 2;
        printf("%d\n",ps2017.getsum(l,r+1));
    }

}


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

int main() {
    int N; cin >> N;
    int ret = N;
    for (int i = 0; i <= N; i++) {
        int cc = 0;
        int t = i;
        while (0 < t) {
            cc += t%6;
            t /= 6;
        }
        t = N-i;
        while (0 < t) {
            cc += t%9;
            t /= 9;
        }
        if (cc < ret) {
            ret = cc;
        }
    }
    cout << ret << endl;
    return 0;
}


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

int main(){
  string s,t;
  cin >> s;
  cin >> t;
  if(t.substr(s.size()).size()==1&&equal(begin(s),end(s),begin(t))){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}     

Measured memory_bytes: 3588
import java.util.*

class Scanner(`in`: java.io.InputStream) {
    private val reader = java.io.BufferedReader(java.io.InputStreamReader(`in`))
    private var tokenizer: StringTokenizer? = null

    fun next(): String {
        if (tokenizer?.hasMoreTokens() != true) {
            tokenizer = StringTokenizer(reader.readLine())
        }
        return tokenizer!!.nextToken()
    }

    fun nextLine(): String {
        return if (tokenizer?.hasMoreTokens() != true) {
            reader.readLine()
        } else tokenizer!!.nextToken("\n")
    }
}

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

////////////////////////////////////////////////////////////////////////

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val K = sc.next().toInt()
        val H = IntArray(N) { sc.next().toInt() }
        val d = IntArray(N) { Int.MAX_VALUE }
        d[0] = 0
        for (i in 0 until N - 1) {
            for (k in 1..K) {
                if (i + k < N) d[i + k] = arrayOf(d[i + k], d[i] + Math.abs(H[i] - H[i + k])).min()!!
            }
        }
        pw.println(d[N - 1])
    }
}


Measured memory_bytes: 108664
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
using P = pair<int,int>;
using ivec = vector<int>;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const int MOD=1000000007;
int INF=100100100100100;
int add(int a,int b){
  return (a+b)%MOD;
}
int prod(int a,int b){
  return (a*b)%MOD;
}

int beki(int a,int b)
{
	if(b==0)return 1;
	int x=beki(a,b/2);
	if(b%2==0)return (x*x)%MOD;
	else return (((a*x)%MOD)*x)%MOD;
}

int inv(int a)
{
	return beki(a,MOD-2);
}

int kaijou(int a)
{
	int ans=1;
	for(int i=1;i<=a;i++)
	{
		ans=(ans*i)%MOD;
	}			
	return ans;
}

/*int combi(int a,int b)
{
	int ret=1;
	for(int i=1;i<=b;i++)
	{
		ret=(((ret*(a+1-i))%MOD)*inv(i))%MOD;
	}
	return ret;
}*/
/*
const int MAX_a=200010;
int cb[MAX_a+1]
void combi(int a,int b)
{
    int ret=1;
    cb[0]=1;
    for(int i=1;i<=b;i++)
    {
	ret=(((ret*(a+1-i))%MOD)*inv(i))%MOD;
        cb[i]=ret;
    }
	
}*/

vector<P> prime_factorize(int N)
{
	vector<P> res;
	for(int a=2;a*a<=N;a++)
	{
		if(N%a!=0)continue;
		int ex=0;
		while(N%a==0)
		{
			ex++;N/=a;
		}
		res.push_back(P(a,ex));
	}
	if(N!=1)res.push_back(P(N,1));
	return res;
}

//ここから書く
signed main(){
  int n;cin>>n;
  int ans=0;
  while(n){
    if(n%10==2)ans++;
    n/=10;
  }
  cout<<ans<<endl;
  return 0;
}

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

int main(void)
{
        int n;
        char a[2],b[2];
        scanf("%s%s",a,b);
        n=strcmp(a,b);
        if(n>0)printf(">\n");
        else if(n==0)printf("=\n");
        else printf("<\n");
        return 0;
}


Measured memory_bytes: 1644
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf3 = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;




void main() {
    int n;
    scan(n);

    int ans;

    foreach (i ; 1 .. n + 1) {
        ans += isOdd(i);
    }

    writeln(ans);
}

bool isOdd(int x) {
    return x.to!string.length % 2;
}


















int[][] readGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new int[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v;
        scan(u, v);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= v;
        if (isUndirected) {
            adj[v] ~= u;
        }
    }

    return adj;
}

alias Edge = Tuple!(int, "to", int, "cost");

Edge[][] readWeightedGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new Edge[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v, c;
        scan(u, v, c);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= Edge(v, c);
        if (isUndirected) {
            adj[v] ~= Edge(u, c);
        }
    }

    return adj;
}

void yes(bool b) {
    writeln(b ? "Yes" : "No");
}

void YES(bool b) {
    writeln(b ? "YES" : "NO");
}

T[] readArr(T)() {
    return readln.split.to!(T[]);
}

T[] readArrByLines(T)(int n) {
    return iota(n).map!(i => readln.chomp.to!T).array;
}

void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a+b > c+d)
        cout << "Left" << endl;
    else if (a+b == c+d)
        cout << "Balanced" << endl;
    else
        cout << "Right" << endl;
    return 0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 2e5 + 10;
main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	queue < int > q;
	vector < int > lun;
	map < int, bool > mp;
	for(int i = 1; i <= 9; i++)q.push(i);
	while(lun.size() < n){
		int x = q.front();
		q.pop();
		if(mp[x])continue;
		mp[x] = 1;
		lun.push_back(x);
		for(int i = 0; i <= 9; i++){
			if(abs(i - x % 10) <= 1)q.push(x * 10 + i);
		}
	}
	sort(lun.begin(), lun.end());
	cout << lun[n - 1] << endl;
}

Measured memory_bytes: 8948
#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// int calculatedValue(int a, int b, int c);

int calc(int a, int b, int c);

int gcd(int a, int b);

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

    vector<vector<vector<int> > > table(K + 1, vector<vector<int> >(K + 1, vector<int>(K + 1, -1)));

    int ans = 0;

    for (int a = 1; a <= K; a++)
    {

        for (int b = 1; b <= K; b++)
        {
            for (int c = 1; c <= K; c++)
            {
                //3つの数字は、a,b,c
                ans = ans + calc(a, b, c);
            }
        }
    }

    cout << ans << endl;
}

int calc(int a, int b, int c)
{
    //aとbの最大公約数を求めて、それとcの最大公約数を求める
    int temp = gcd(a, b);
    return gcd(temp, c);
}

int gcd(int a, int b)
{
    //小さい数をbにする
    if(a < b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    while(1)
    {
        //aとbの最大公約数を求めるのは、aをbで割ったあまりと、bの最大公約数を求めれば良い
        int temp = a%b; //このtempとbの最大公約数を求めればよくなった (tempはbより小さい)

        if(temp == 0)
        {
            return b;
        }

        a = b;
        b = temp;
    }
}



Measured memory_bytes: 36504
a, b, c, x, y = map(int, input().split())
print(min(a*x + b*y, 2*c*max(x,y), 2*c*y + a*(x-y) +(10**10 if y > x else 0), 2*c*x + b*abs(y-x)+(10**10 if x > y else 0)))


Measured memory_bytes: 2940
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long _MOD = 1000000007;
const long long MOD = 998244353;

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

	int n, m;
	cin >> n >> m;
	int sum = 0, a;
	rep(i, m) {
		cin >> a;
		sum += a;
	}

	cout << max(-1, n - sum) << "\n";

	return 0;
}


Measured memory_bytes: 3660
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
int cmp(const void *a, const void *b);
//your code here!

int main(void){
    ll n, m;
    scanf("%lld %lld", &n, &m);
    printf("%lld\n", (n-1)*(m-1));
    return 0;
}

int cmp(const void *a, const void *b){
    ll A=*(ll *)a, B=*(ll *)b;
    if(A==B)return 0;
    else return A>B ? 1:-1;//昇順ソート
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y,z,ans;
  cin>>x>>y;
  if(x>=y) 1;
  else {
    z=x;
    x=y;
    y=z;
  }
  z=x%y;
  if(z==0) ans=y;
  for(int i=1;i<=z;i++){
    if(z%i==0 && y%i==0) ans=i;
  }
  cout<<ans<<endl;
  
 
  return 0;
}



Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> v;
int N,K;
int c[200000];

int main(){
    for(int i=0;i<200000;i++) c[i] = 0;
    int b;
    cin >> N >> K;
    for(int i=0;i<N;i++){
        cin >> b;
        c[b]++;
    }
    for(int i=0;i<200000;i++){
        if(c[i] != 0) v.push_back(c[i]);
    }
    if(v.size() <= K){
        cout << 0 << endl;
        return 0;
    }
    sort(v.begin(),v.end());
    long long count = 0;
    for(int i=0;i<v.size()-K;i++){
        count += v[i];
    }
    cout << count << endl;
    return 0;
}

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

using namespace std ;

int main()

{

long long a, b, c, d, e, f, g, h, i, j, k;

cin>>a>>b>>c>>d;

e=max(max(a*c, a*d), max(b*d, b*c)) ;

cout <<e<<endl;

} 

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define pb push_back
const ll mod = 1e9+7;
ll inv[2005];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,k;
	while(cin >> n >> k){
		f1(2000){
			inv[i] = 1;
			ll rem = mod-2;
			ll now = i;
			while(rem){
				if(rem&1){
					inv[i] *= now;
					inv[i] %= mod;
				}
				now *= now;
				now %= mod;
				rem >>= 1;
			}
		}
		int a=k,b=n-k;
		fr(z,1,k+1){
			if(a<z||b<z-1){
				cout<<0<<'\n';
			}
			else{
				ll ret = 1,ret2 = 1;
				//cout<<a-1<<' '<<z-1<<' '<<b+1<<' '<<z<<endl;
				for(int i=1;i<=min(z-1,a-z);i++){
					ret *= a-i;
					ret %= mod;
					ret *= inv[i];
					ret %= mod;
				}
				for(int i=1;i<=min(z,b+1-z);i++){
					ret2 *= b+2-i;
					ret2 %= mod;
					ret2 *= inv[i];
					ret2 %= mod;
				}
				cout<<ret*ret2%mod<<endl;
				//cout<<ret*ret2%mod<<endl;
			}
		}
	}
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>

#define ll long long
#define ld long double
#define ull unsigned ll
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  Inf = 2 * 1000 * 1000 * 1000;
ll LINF = (ll)4e18;
using namespace std;
#define M_PI       3.14159265358979323846   // pi


int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	vector<ll>a(5);
	ll mx = -1;
	for (auto &x : a) {
		cin >> x;
		mx = max(mx, (n + x - 1) / x);
	}
	cout << mx + 4;
 	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace  std;
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rep(n) for (int i = 0; i < n; ++i)

const int md = 1e9 + 7; //998244353 ;
void addto(int &x, int y) { x = x + y; if (x >= md) x -= md; }
int add(int x, int y) { int z = x + y; return z >= md? z -= md : z;}
void updmin(auto&x, auto y ) { if (y < x) x = y;}
void updmax(auto&x, auto y ) { if (y > x) x = y;}
long long pw(auto x, auto y) {	
	long long s = 1;
	while(y) {
		if (y & 1) s = s * x % md;
		x= 1LL * x * x % md; y /= 2;
	}
	return s;
}


const int maxn = 1e6 + 10;

int T, n, m;
bool dfs(int a, int b, int c, int k) {
	if (c > b && b > a) return true;
	if (k == 0) return false;
	return dfs(a * 2, b, c, k - 1) || 
	dfs(a, b * 2, c, k - 1) ||
	dfs(a, b, c * 2, k - 1);
}
void task() {
	int n, a, b, c, k;
	cin >> a >> b >> c;
	cin >> k;
	cout << (dfs(a, b , c, k)?"Yes":"No") << endl ;
	
	// you should actually read the stuff at the bottom
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout<<fixed<<setprecision(20);
  T = 1;
  for (int ti = 1; ti <= T; ++ti) {
    task();
  }
  return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* write down
*/


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
#define T int t = 0; cin >> t; while(t--)
#define b_e(a) a.begin(), a.end()
typedef long long ll;
typedef  long double lld;
const ll mod = 1e9 + 7;
const ll mx = 2e3 + 1;

void input(){
    int n;
    cin >> n;
    set<int>s;
    int ans = 0;
    f(i, n){
        int x; cin >> x;
        if(i == 0){
            ++ans;
            s.insert(x);
        }
        else if(s.upper_bound(x) == s.begin()){
            ++ans;
            s.insert(x);
        }else s.insert(x);
    }
    cout << ans << endl;
}
int main(){
    input();
    return 0;
}


Measured memory_bytes: 9728
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <set>
using namespace std;

int main(){
    int n;
    string s;
    string sub1, sub2;
    set<char> set;
    int i = 1;
    int j = 0;
    int max = 0;
    cin >> n >> s;
    for(i = 1; i <= n - 1; i++){
        sub1 = s.substr(0, i);
        sub2 = s.substr(i, n-i);
        //cout << sub1 << " " << sub2 << endl;
        j = 0;
        while(j < i){
            if(sub2.find(sub1[j]) != std::string::npos){
                set.insert(sub1[j]);
            }
            j++;
        }
        if(max < set.size()){
            max = set.size();
            //cout << sub1 <<  "\n" << sub2 << endl;
        }
        set.clear();
    }
    cout << max << endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 100000 + 10
#define ll long long int
ll N[MAXN];
ll dp[MAXN];
#define INF 0x3f3f3f3f;
int main()
{
    ll n,k;
    cin>>n>>k;
    for(int i = 0;i < n;++i)
        cin>>N[i],dp[i] = INF;
    dp[0] = 0;
    for(int i = 0;i < n;++i)
        for(int j = i - k;j <= i;++j)
            if(j >= 0)
            dp[i] = min(dp[i] ,dp[j]+ abs(N[i] - N[j]));
    cout<<dp[n - 1]<<endl;
    return 0;
}
//

Measured memory_bytes: 1792
#pragma comment (linker, "/STACK:256000000")
#define  _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()
void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(100);
}

#define int ll
int go[10][10] = {};
void solve() {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		string s = to_string(i);
		go[s[0] - '0'][s.back() - '0']++;
	}
	for (int i = 1; i <= n; ++i) {
		string s = to_string(i);
		ans += go[s.back() - '0'][s[0] - '0'];
	}
	cout << ans << endl;
}

#undef int
int main() {
	init();
	solve();
}


Measured memory_bytes: 384
#include <stdio.h>
int main(void){
    // Your code here!
    int a,b,c,min;
    
    scanf("%d %d %d",&a,&b,&c);
    
    min = (a+b);
    
    if((b+c)<min) min = (b+c);
    if((a+c)<min) min = (a+c);
    
    printf("%d",min);
}


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

int lcs(string X,string Y)
{
    int x=X.size(),y=Y.size();
    int dp[y+1][x+1];

    for(int i=0;i<x+1;i++)dp[0][i]=0;
    for(int i=1;i<y+1;i++)dp[i][0]=0;
    int maxl=0;
    
    for (int j = 1; j <= y; j++){
        for (int k = 1; k <= x ; k++){
            if (Y[j-1]==X[k-1]) dp[j][k]=dp[j-1][k-1]+1;
            else dp[j][k]=max(dp[j][k-1],dp[j-1][k]);
            maxl=max(maxl,dp[j][k]);
        }
    }
    return maxl;
}

int main()
{
    int q;
    cin>>q;
    string X,Y;
    for (int i = 0; i < q; i++) {
        cin>>X>>Y;
        cout<<lcs(X,Y)<<endl;
    }
}
/*
3
abcbdab
bdcaba
abc
abc
abc
bc
*/


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

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int n,q; cin >> n >> q;
    string s; cin >> s;
    int l[n], r[n]; for(int i = 0; i<q; ++i)cin >> l[i] >> r[i];
    vector <int> exsist(n,0);
    for(int i = 1; i<n; ++i) if(s[i-1] == 'A' && s[i] == 'C')exsist[i] = 1;
    vector <int> sum(n+1,0);
    for(int i = 0; i<n; ++i) sum[i+1] = sum[i] + exsist[i];
    cout << endl;
    for(int i = 0; i<q; ++i){
        cout << sum[r[i]] - sum[l[i]] <<endl;
    }
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define ll long long
#define llu unsigned long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAX = 1e5 + 10;
const int mod = 1e9;
int N, M, Q, K;
vector<int> vec[2];
int dp[16100][4010], dest[2];
bool dflag[2];

int rec(int pos, int vi, int init, int dir){
    if(vi == vec[dir].size()){
        if(pos == dest[dir]) dflag[dir] = true;
        return 1;
    }
    int &ret = dp[pos][vi];
    if(ret != -1) return 1;
    ret = 1;

    rec(pos + vec[dir][vi], vi + 1, 0, dir);
    if(!init) rec(pos - vec[dir][vi], vi + 1, 0, dir);
    return 1;
}

int main()
{
    int i, j, k;
    string s;
    cin >> s >> dest[0] >> dest[1];

    int pos = 0;
    int dir = 0;
    int n= s.size();
    while(pos < n){
        int cnt = 0;
        while(pos < n && s[pos] == 'F') {cnt++; pos++;}
        vec[dir].push_back(cnt);
        pos++;
        dir = !dir;
    }
    dest[0] += 8000; dest[1]+= 8000;
    memset(dp, -1, sizeof(dp));
    rec(8000, 0, 1, 0);
    if(!dflag[0]){
        printf("No\n");
        return 0;
    }
    memset(dp, -1, sizeof(dp));
    rec(8000, 0, 0, 1);
    if(!dflag[1]){
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
}


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

int main() {
  int k, n, d;
  cin >> k >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  d = k - (a[n - 1] - a[0]);
  for (int i = 1; i < n; i++) {
    d = max(d, a[i] - a[i - 1]);
  }
  cout << k - d << endl;
}


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

int N;
long long A[100000];

long long solve() {
	
//	cout << "Solve()" << endl;
	
	bool loop=true;
	long long aa;
	int mi;
	while (loop) {
		long long  min_A =1000000001;
		for(int i=0; i<N; i++) 
			if ((min_A>A[i])&&(A[i]>0)) {
				min_A=A[i];
				mi=i;
			}	

//		cout << "min_A=" << min_A << endl;

		for(int i=0; i<N; i++) {
			if (i!=mi && A[i]>0)  {
				A[i] = A[i] % min_A;
			}
		}
		//終了判定
		for(int i=0; i<N; i++) {
		}
		
		int cnt=0;
		for(int i=0; i<N; i++) {
			if (A[i] == 0)  cnt++;
			else            aa = A[i];
		}
		if (cnt==N-1 || aa==1) { 
			loop = false; 	
		}
	}
	
	return aa;
}

int main() {
	cin >> N;

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

	long long ans = solve();
	cout << ans << endl;
	return 0;
}

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

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
    return 0;
}


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

int main(int argc, const char * argv[]) {
    while(1){
        int n; cin >> n;
        if(!n) break;
        
        int big = -1, small = 1001;
        int sum = 0;
        for(int i = 0; i < n; i++){
            int point; cin >> point;
            big = max(big, point);
            small = min(small, point);
            sum += point;
        }
        cout << (sum - big - small) / (n - 2) << endl;
    }
}

Measured memory_bytes: 1160
k = int(input())
queue = [1,2,3,4,5,6,7,8,9]
count = 0
for i in range(0,k-1):
    x = queue[i]
    if x % 10 != 0:
        queue.append( 10*x + pow(x,1,10) - 1)
    queue.append(10*x + pow(x,1,10))
    if x %10 != 9:
        queue.append(10*x + pow(x,1,10) + 1)
print(queue[k-1])



Measured memory_bytes: 15764
import java.util.Scanner;

public class Main {
    final double EPS = 1.0e-10;
    final int INF = 1 << 28;

    void run() {
        Scanner sc = new Scanner(System.in);
        int cns[] = new int[101];
        int tns[] = new int[101];
        for (int i = 0; i < 101; i++) {
            cns[i] = i * i * i;
            tns[i] = i * (i + 1) * (i + 2) / 6;
        }
        while (true) {
            int f = sc.nextInt();
            if (f == 0)
                break;
            int lb = 0;
            int ub = 100;
            while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                if (cns[mid] < f) {
                    lb = mid;
                } else {
                    ub = mid;
                }
            }
            int cn = cns[lb];
            lb = 0;
            ub = 100;
            while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                if (tns[mid] < f) {
                    lb = mid;
                } else {
                    ub = mid;
                }
            }
            int tn = tns[lb];
            int max = Math.max(tn, cn);
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    if (tns[i] + cns[j] <= f)
                        max = Math.max(max, cns[j] + tns[i]);
                    else
                        break;
                }
            }
            System.out.println(max);
        }
    }

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

Measured memory_bytes: 12000
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

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

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

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

  if(y == NIL){ 
    root = z; 
  } 
  else if(z->key < y->key){ 
    y->left = z; 
  }else { 
    y->right = z;
  }  

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

void inorder(Node u){
if(u->left!=NULL) inorder(u->left);
printf(" %d",u->key);
if(u->right!=NULL) inorder(u->right);
}

void preorder(Node u){ 
printf(" %d",u->key);
if(u->left!=NULL) preorder(u->left);
if(u->right!=NULL) preorder(u->right);
 } 


int main(){
  int n, i, x, k;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com); 
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } 
    else if ( com[0] == 'i' ){
      scanf("%d", &k);
      insert(k);
    }
    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } 
  }
  return 0;
}

Measured memory_bytes: 19364
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int read()
{
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = 0; c = getchar(); }
	while(isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	return f ? x : -x;
}

typedef long long LL;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
int inv[maxn], a[maxn];

int main()
{

	int n = read();
	inv[0] = inv[1] = 1;
	for(int i = 2; i <= n; ++i) inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 2; i <= n; ++i) (inv[i] += inv[i - 1]) %= mod;
	int ans = 0;
	for(int i = 1; i <= n; ++i) (ans += (LL)a[i] * (inv[i] - 1 + inv[n - i + 1]) % mod) %= mod;
	for(int i = 1; i <= n; ++i) ans = (LL)ans * i % mod;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  string s;cin>>s;
  int n=(int)s.length();
  rep(i,n){
    cout<<"x";
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } } _io;
typedef long long ll; typedef long double db;

int exgcd(int a, int b, int& x, int& y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}
int getInv(int a, int mod)
{
    int x, y;
    return exgcd(a, mod, x, y) == 1 ? (x % mod + mod) % mod : -1;
}

int main()
{
    string s, t;
    cin >> s >> t;
    ll ans = 0x3f3f3f3f;
    for (int i = 0; i <= (int)s.size() - (int)t.size(); ++i)
    {
        string tt = s.substr(i, (int)t.size());
        ll cnt = 0;
        for (int j = 0; j < (int)t.size(); ++j)
        {
            if (tt[j] != t[j]) ++cnt;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

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

typedef std::pair<int, int> ipair;
#define pb push_back
#define ff first
#define ss second
#define fr(i, j, k) for (int i = j; i < k; i++)
#define rf(i, j, k) for (int i = j; i >= k;i--)
#define int long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair

const int mod = 1000000007;
const ld pi = acos(-1);
const int maxn = 200006;

template<class T> ostream& operator <<(ostream &out,vector<T> &A){for(auto x:A) out<<x<<" ";return out;}
template <class T1,class T2>T1 powr(T1 a,T2 b){T1 res = 1;fr(i,1,b+1)res = res*a;return res;}
#define IOS  std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

bool intdis(vector<vector<int>> A, int d, int i, int j){
  int ans = 0;
  fr(k,0,d) ans += powr(A[i][k]-A[j][k],2);
  return ((double)sqrt(ans) == (int)sqrt(ans)); 
}
int32_t main(){
  int n,d,cnt=0; cin>>n>>d;
  vector<vector<int>> A(n,vector<int>(d));
  fr(i,0,n) fr(j,0,d) cin>>A[i][j];
  fr(i,0,n) fr(j,i+1,n)
  if(intdis(A,d,i,j)) cnt++;
  cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>



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

using namespace std;
int n,m,x;
int a,b;
int main(){
  cin >> n >> m >> x;
  REP(i,m){
    int k;
    cin >> k;
    if(k<x) a++;
    else b++;
  }
  cout << min(a,b) << endl;
  return 0;
}


Measured memory_bytes: 256
import numpy as np
n, d = map(int, input().split())

vector = [[0 for i in range(d)] for j in range(n)]

for i in range(n):
    vector[i] = list(map(int, input().split()))

cnt = 0
for i in range(n - 1):
    for j in range(i + 1,n):
        
        num = 0
        for k in range(d):
            num += (vector[i][k] - vector[j][k])**2 * 1.0
        
        if np.sqrt(num).is_integer():
            cnt += 1

print(cnt)

Measured memory_bytes: 12452
#4問目
N = int(input())
a = list(map(int, input().split()))
#足していった配列を用意する
Sum = 0
Min = float("inf")
SumArray = [0] * N
for i in range(N):
    Sum += a[i]
    SumArray[i] = Sum
#仕切りを用意して，左側をすぬけくん，右側をアライグマのカードとして差分を計算する
if N == 2:
    print(abs(a[0] - a[1]))
else:
    for i in range(N-1):
        temp = abs(SumArray[i] - (SumArray[N-1] - SumArray[i]))
        if temp < Min:
            Min = temp

    print(int(Min))

Measured memory_bytes: 24832
/*
  -> ossan
  -> Do Good Die Great
*/
#include <bits/stdc++.h>
#define int long long int
#define pii pair<int, int>
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define MOD 1000000007
#define Hiraishin                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr);
#define tests \
    int t;    \
    cin >> t; \
    while (t--)
using namespace std;

// global

void solve()
{
    char s;
    cin >> s;
    if (isupper(s))
        cout << 'A';
    else
        cout << 'a';
}

signed main()
{
    Hiraishin
    // tests
    solve();
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <map>
using namespace std;
#define ll long long

const int MAX_N = 200009;

int N, A[MAX_N];

ll s[MAX_N];
map<ll, ll> M;

int main() {
    s[0] = 0;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        s[i+1] = s[i] + A[i];
    }

    for (int i = 0; i <= N; i++) {
        M[s[i]]++;
    }

    ll ans = 0;
    for (auto it : M) {
        ll n = it.second;
        ans += n * (n-1) / 2;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 15104