akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

bool isSquare(int n) {
    for (int i = 1; i * i <= n; i++) {
        if (i * i == n) {
            return true;
        }
    }
    return false;
}

int main() {
    int n, d;
    int x[10][10];
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> x[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int disdis = 0;
            for (int k = 0; k < d; k++) {
                disdis += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);    
            }
            if (isSquare(disdis)) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
def main():
    H, W = map(int, input().split())
    MP = [input() for i in range(H)]
    for i in range(H):
        mi = MP[i]
        for j in range(W):
            c = mi[j]
            if c == 's':
                sx = j; sy = i
            elif c == 'g':
                gx = j; gy = i
    S = input()
    L = len(S)
    X = [-1]*len(S)
    st = []
    for i, c in enumerate(S):
        if c in "[{":
            st.append(i)
        elif c in "]}":
            k = st.pop()
            X[k] = i
            X[i] = k
    ds = "WNES"
    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
    U = set()
    ans = 0
    d = 1
    cur = 0
    def check(c, x, y, d):
        if c == "T":
            return 1
        if c in ds:
            return (d == ds.index(c))
        dx, dy = dd[d]
        return MP[y+dy][x+dx] == "#"
    x = sx; y = sy
    ok = 0
    while 1:
        if x == gx and y == gy:
            ok = 1
            break
        br = 0
        while cur < L:
            key = (x, y, d, cur)
            if key in U:
                br = 1
                break
            U.add(key)

            c = S[cur]
            if c in "[{":
                c = S[cur+1]
                if c == '~':
                    if not check(S[cur+2], x, y, d):
                        cur += 3
                    else:
                        cur = X[cur]+1
                else:
                    if check(c, x, y, d):
                        cur += 2
                    else:
                        cur = X[cur]+1
            elif c == "]":
                cur += 1
            elif c == "}":
                cur = X[cur]
            else:
                break
        if cur == L or br:
            break
        c = S[cur]
        dx, dy = dd[d]
        assert c in "<>^v"
        if c == "^":
            if MP[y+dy][x+dx] != '#':
                x += dx; y += dy
        elif c == "v":
            if MP[y-dy][x-dx] != '#':
                x -= dx; y -= dy
        elif c == "<":
            d = (d - 1) % 4
        else: # c == ">"
            d = (d + 1) % 4
        cur += 1
        ans += 1
    if ok:
        print(ans)
    else:
        print(-1)
main()


Measured memory_bytes: 163956
N = gets.chomp.to_i
S = gets.chomp.split.map(&:to_i)
Q = gets.chomp.to_i
T = gets.chomp.split.map(&:to_i)
ans = 0
T.each do |i|
  S.push(i)
  j = 0
  until S[j] == i
    j += 1
  end
  if j == S.length - 1
    ans += 0
  else
    ans += 1
  end
  S.pop
end
puts ans



Measured memory_bytes: 7172
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int i,j;
		
		i=in.nextInt();
		j=in.nextInt();
		while(i!=0 || j!=0){
			if(i<j){
				System.out.println(i+" "+j);
			}else if(i>j){
				System.out.println(j+" "+i);	
			}else{
				System.out.println(i+" "+j);
			}
			i=in.nextInt();
			j=in.nextInt();
		}
		
		in.close();
	}
}

Measured memory_bytes: 27136
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <string.h>
#include <map>
#include <bitset>

#define Z class
#define ln cout<<'\n'
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (n); ++i)
//ASCII a=97, A=65
// int H[N]; rep(i,N) scanf("%d", &H[i]);
// int max_x = *std::max_element(x.begin(), x.end());
// int min_y = *std::min_element(y.begin(), y.end());
// sort(vec.begin(), vec.end()); std::greater<>()
// reverse(vec.begin(), vec.end());
// scanf("%s",s);
// printf("%d\n",end-start+1);
// ceil (a + (b - 1)) / b

//===== グラフ受け取り =====//
/*
    int N, M; cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);

        // 無向グラフの場合は以下を追加
        // G[b].push_back(a);
    }
    
    // == 重み付きグラフ == //
    
    struct Edge {
        int to; 
        int weight; 
        Edge(int t, int w) : to(t), weight(w) { }
    };
    using Graph = vector<vector<Edge>>;
    int main() {
        int N, M; cin >> N >> M;
        Graph G(N);
        for (int i = 0; i < M; ++i) {
            int from, to, weight;
            cin >> from >> to >> weight;
            G[from].push_back(Edge(to, weight));
        }
    }
*/    

using namespace std;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
using pll = pair<long long, long long>;

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;}
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
const long long INF = 1LL << 60;

int main(){
   int N, M; cin >> N >> M;
   vector<vector<int>> switches(M);
   rep (i, M) {
       int k; cin >> k;
       rep(j, k) {
           // why is a decremented??
           // => change 1-origin to 0-origin?? 
            int a; cin >> a; a--;
            switches[i].push_back(a);
       }
   }
   //the number of switches to turn on right
   //p[i] = {0 or 1}
   vector<int> p(M);
   rep(i, M) cin >> p[i];
   
   ll res = 0;
   for (int bit = 0; bit < (1 << N); ++bit ) {
       bool valid = true;
       rep (i, M) {
           int con = 0;
           for (auto v : switches[i]) {
               if (bit & (1<<v)) ++con;
           }
           //lamp check { on / off }
           if (con % 2 != p[i]) valid = false;
       }
       if(valid) ++res;
   }
   cout << res << endl;
}






Measured memory_bytes: 256
from fractions import gcd

d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    if d % i == 0:
        d //= i
        r += 1
    while d % i == 0:
        d //= i
    i += 1
print(r + (d > 1))


Measured memory_bytes: 5176
from collections import defaultdict
from collections import deque


def main():
    N, M = map(int, input().split())
    A = [0] * M
    B = [0] * M

    for i in range(M):
        a, b = map(int, input().split())
        A[i] = a - 1
        B[i] = b - 1

    friends = defaultdict(set)

    for i in range(M):
        a, b = A[i], B[i]
        friends[a].add(b)
        friends[b].add(a)

    seen = [False] * N

    # print(friends)

    def dfs(start):
        cnt = 0
        nodes = []

        todo = deque([start])
        while len(todo) > 0:
            v = todo.pop()
            cnt += 1
            nodes.append(v)

            for next_v in friends[v]:
                if seen[next_v]:
                    continue
                else:
                    todo.append(next_v)
                    seen[next_v] = True

        return cnt, nodes

    trees = []
    counts = []
    for v in range(N):
        if seen[v]:
            continue
        else:
            seen[v] = True
            c, nodes = dfs(v)
            counts.append(c)
            trees.append(nodes)

    # print(counts)
    # print(trees)
    print(max(counts))


if __name__ == '__main__':
    main()


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

int main() {
  int k, x;
  cin >> k >> x;
  bool first = true;
  for (int i = x - k + 1; i <= x + k - 1; ++i) {
    if (!first)
      cout << " ";
    cout << i;
    first = false;
  }
  cout << "\n";
  return 0;
}


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

using namespace std;

typedef long long ll;

struct drink {
		ll a;
		ll b;
};

int main() {
		int N, M;
		cin >> N >> M;
		vector<drink> v(N);
		for (int i = 0; i < N; i++) cin >> v[i].a >> v[i].b;

		sort(v.begin(), v.end(), [](const drink &x, const drink &y) {
				return x.a < y.a;
		});

		ll bought = 0, ans = 0;
		for (int i = 0; bought < M; i++) {
				if (v[i].b <= (M-bought)) {
						ans += (v[i].a * v[i].b);
						bought += v[i].b;
				} else if (v[i].b > (M-bought)) {
						ans += (v[i].a * (M-bought));
						bought += (M-bought);
				}
		}

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


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric> 
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	if(abs(n - m) >= 2) 
	{
		cout << 0 << endl;
		return 0;
	}
	ll a = max(n, m);
	ll b = min(n, m);
	if(a == b)
	{
		for(int i = a - 1; i >= 1; i--)
		{
			a = (a * i) % MOD;
		}
		cout << (2 * a * a) % MOD << endl;
	}
	else
	{
		for(int i = a - 1; i >= 1; i--)
		{
			a = (a * i) % MOD;
		}
		for(int i = b - 1; i >= 1; i--)
		{
			b = (b * i) % MOD;
		}
		cout << (a * b) % MOD << endl;;
	}
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string s,t;
  cin>>s>>t;
  bool ok=true;
  if(s.size()==t.size()-1){
    for(int i=0; i<s.size(); i++){
      if(s[i]!=t[i]){
        ok=false;
      }
    }
    if(ok){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
  }
}

Measured memory_bytes: 3628
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, m = LI()
G = [set() for _ in range(n)]
RG = [set() for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = LI()
    G[a - 1].add(b - 1)
    RG[b - 1].add(a - 1)

r = 0
while RG[r]:
    for v in RG[r]:
        r = v
        break

def topological_sort():
    in_degree = [0] * n
    D = {}
    for u in range(n):
        in_degree[u] += len(RG[u])
    dq = deque([r])
    cnt = 0
    while dq:
        u = dq.pop()
        D[u] = cnt
        cnt += 1
        for v in G[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                dq += [v]
    return D

D = topological_sort()
for u in range(n):
    par = 0
    ret = -1
    for v in RG[u]:
        if D[v] > ret:
            ret = D[v]
            par = v + 1
    print(par)








Measured memory_bytes: 106156
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int n, m;
    cin >> n >> m;
    vector< pair<ll, ll> > V(n, make_pair(0LL,0LL));
    REP(i, n) cin >> V[i].first >> V[i].second;
    sort(ALL(V));
    // REP(i,n) cout <<i << " "<< V[i].first << " " << V[i].second << endl;
    ll ans=0;
    REP(i,n){
        // cout << i << "にいて，もう " << m << "個かいたい．お金はまだ"<<ans << endl;
        if(m >= V[i].second ) {
            ans += V[i].first * V[i].second;
            m -= V[i].second;
        }
        else {
            ans+= V[i].first * m;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define MAXN 100005

typedef pair<long long, long long> pll;

const long long m = 1000000007;

map <int, pll> cs;
vector <int> g [MAXN];
int v [MAXN];

void calc(int n){
    v[n]=-1;
    vector<int> vv= g[n];
    long long x =1, y =1,a,b;
    pll p,q;
    for(auto e:vv){
        if(v[e]==0){
            calc(e);
        }
        if(v[e]==1){
            p = cs[e];
            a = p.first, b = p.second;
            x=(x*((a+b)%m))%m;
            y = (y*a)%m;
        }
        
    }
    q = make_pair(x,y);
    cs[n] = q;
    v[n]=1;
}
int main(){
    int n,a,b;
    cin>>n;
    for(int i=0; i<n-1; i++){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    memset(v, 0, sizeof(v));
    calc(1);
    long long rta = (cs[1].first+cs[1].second)%m;
    cout<<rta<<"\n";
}

Measured memory_bytes: 23552
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,b;
    cin>>n>>m>>b;
     if(m+b>=n)
     {
         printf("%d %d\n",min(m,b),m+b-n);
     }
     else
     {
         printf("%d %d\n",min(m,b),0);
     }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();

		int max = 0;
		for (int i = 0; i < s.length() -  t.length() + 1; i++) {
			String a = s.substring(i, t.length() + i);
			int cnt = 0;
			for (int j = 0; j < t.length(); j++) {
				if (a.charAt(j) == t.charAt(j)) cnt++;
			}
			max = Math.max(max, cnt);
		}

		System.out.println(t.length() - max);

		sc.close();

	}

}

Measured memory_bytes: 36476
#include<iostream>
using namespace std;
int main(){
  int i = 0;
  while(1){
    int x;
    
    cin >> x;
    i = i + 1 ;   
    if (x==0) break;
    cout << "Case " << i << ": " << x << endl;
  }
  return 0;
}


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

bool vector_finder(std::vector<ll>& vec, ll number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
    if (index != vec.size())
    {
        vec.erase(itr);
        return true;
    }
    else 
    {
        return false;
    }
}

int main()
{
    ll n, k;
    cin >> n >> k;
    ll r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;

    map<char, ll> points_map;
    points_map['r'] = p;
    points_map['s'] = r;
    points_map['p'] = s;

    ll sum_point = 0;
    vector<ll> no_points;

    for (ll i=0; i < n; i++)
    {
        if(i < k)
        {
            sum_point += points_map[t[i]];
        }
        else if (t[i] != t[i-k])
        {
            sum_point += points_map[t[i]];
        }
        else if (vector_finder(no_points, i-k))
        {
            sum_point += points_map[t[i]];
        }
        else
        {
            no_points.push_back(i);
        }
    }

    cout << sum_point << endl;

    return 0;
}


Measured memory_bytes: 768
import java.util.*;

public class Main {
    private static final Scanner scn = new Scanner(System.in);
    
    public static void main(String[] args) {
        int x = scn.nextInt(), y = scn.nextInt();
        System.out.println(euclid(x > y ? x : y, x < y ? x : y));
    }
    
    private static int euclid(int x, int y) {
        if(y > 0) {
            return euclid(y, x % y);
        } else {
            return x;
        }
    }
}

Measured memory_bytes: 26168
def func():
    pass


def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))

    m = a[0]
    for i in range(n + 100):
        if m == 2:
            print(i + 1)
            return
        m = a[m - 1]
    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 7084
#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))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define lint long long

const int INF = 1e9;
const int MOD = 1e9+7;
const lint LINF = 1e18;



using namespace std;
int a,b,c,d;

int main(){
  cin >> a >> b >> c >> d;
  cout << max(0,min(b,d)-max(a,c)) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#define rep(i,n) for(int i = 0;i<(n);i++);
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 100100100100;
typedef pair<ll, ll> P;
ll gcd(ll a, ll b) {//a>b
	if (a < b)swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
int main(){
  ll n,m;
  cin >> n >> m;
  cout << n - m + 1 << endl;
}

Measured memory_bytes: 256
# 連想配列
from collections import deque
N = int(input())
ab = {}
abl = []
path = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
    abl.append((a-1,b-1))
    ab[(a-1,b-1)] = 0
color = [0]*N
color[0] = -1
q = deque([])
q.append(0)
max = 0

while len(q)>0:
    cn = q.popleft()
    ccolor = color[cn]
    ncolor = 1
    for i in path[cn]:
        if color[i] == 0:
            if ccolor != ncolor:
                color[i] = ncolor
                ab[(cn,i)] = ncolor
                ncolor += 1
            else:
                color[i] = ncolor+1
                ab[(cn,i)] = ncolor+1
                ncolor += 2
            if color[i] > max:
                max = color[i]
            q.append(i)
print(max)
for i in abl:
    print(ab[i])

Measured memory_bytes: 91296
#include "bits/stdc++.h"
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define ri register int
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
#define ls (cur << 1)
#define rs (cur << 1 | 1)
#define mid ((l + r) >> 1)
const int maxn = 5e5 + 10;
inline int Max(int a, int b) { return a > b ? a : b; }
inline int Min(int a, int b) { return a > b ? b : a; }
namespace FastIO {
inline int read()
{
    int f = 1, r = 0;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (isdigit(c)) {
        r = 10 * r + c - '0';
        c = getchar();
    }
    return f * r;
}
inline void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void writesp(int x) { write(x), putchar(' '); }
inline void writeln(int x) { write(x), puts(""); }
};
using namespace FastIO;
int N, seg[maxn << 2], pos[maxn], K, tot, ver[maxn << 2], next[maxn << 2], head[maxn], du[maxn];
struct Node {
    int weight, pos;
} nodes[maxn];
inline void add(int u, int v)
{
    ver[++tot] = v, next[tot] = head[u], head[u] = tot;
}
void update(int l, int r, int pos, int val, int cur)
{
    if (l == r) {
        seg[cur] = val;
        return;
    }
    if (mid >= pos)
        update(l, mid, pos, val, ls);
    else
        update(mid + 1, r, pos, val, rs);
    seg[cur] = Min(seg[ls], seg[rs]);
}
int query(int l, int r, int L, int R, int cur)
{
    if (l >= L && r <= R) {
        return seg[cur];
    }
    int ans = inf;
    if (mid >= L) {
        ans = query(l, mid, L, R, ls);
    }
    if (mid < R) {
        ans = Min(ans, query(mid + 1, r, L, R, rs));
    }
    return ans;
}
std::priority_queue<int, std::vector<int>, std::greater<int>> q;
inline int cmp(const Node& a, const Node& b) { return a.pos < b.pos; }
signed main()
{
    //freopen("C:\Users\hjw\Downloads\testdata (4).in", "r", stdin);
    N = read(), K = read();
    for (ri i = 1; i <= N; ++i) {
        pos[read()] = i;
    }
    memset(seg, 0x3f, sizeof(seg));
    for (ri i = N; i >= 1; --i) {
        int now = pos[i];
        int low = query(1, N, now, Min(N, now + K - 1), 1);
        if (low != inf) {
            du[pos[low]]++, add(now, pos[low]);
        }
        low = query(1, N, Max(1, now - K + 1), now, 1);
        if (low != inf) {
            du[pos[low]]++, add(now, pos[low]);
        }
        update(1, N, pos[i], i, 1);
    }
    for (ri i = 1; i <= N; ++i) {
        if (!du[i])
            q.push(i);
    }
    int cnt = 0;
    while (!q.empty()) {
        int top = q.top();
        nodes[++cnt].weight = cnt, nodes[cnt].pos = top;
        q.pop();
        for (ri i = head[top]; i; i = next[i]) {
            du[ver[i]]--;
            if (du[ver[i]] == 0) {
                q.push(ver[i]);
            }
        }
    }
    std::sort(nodes + 1, nodes + 1 + N, cmp);
    for (ri i = 1; i <= N; ++i) {
        writeln(nodes[i].weight);
    }
    return 0;
}

Measured memory_bytes: 33020
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long int ll;
typedef long double ld;


int main(){
    ll a,b,h,ans;
    cin >> a >> b >> h;
    ans=(a+b)*h/2;
    cout << ans << endl;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp.split(' ').map(&:to_i)

a = a.unshift(0).push(0)

s = 0
(n + 1).times{|i| s += (a[i + 1] - a[i]).abs}

n.times do |i|
  s_i = s + (a[i] - a[i + 2]).abs - (a[i] - a[i + 1]).abs - (a[i + 1] - a[i + 2]).abs
  puts s_i.to_s
end

Measured memory_bytes: 12548
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <numeric>
#include <ctype.h>
#include <cstdlib>
#include <string.h>
#include <cmath>
#include <cstdio>


#define N 1000000


using namespace std;

bool isPrime(int x)
{
	if (x == 2)
		return true;
	if (x % 2 == 0)
		return false;

	for (int i = 3; i * i <= x; i += 2)
	{
		if (x % i == 0)
			return false;
	}

	return true;
}

int main()
{
	int n, cnt = 0, input;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input;

		if (isPrime(input))
			cnt++;
	}

	cout << cnt << endl;
	

}

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

#define ll            long long
#define pb            push_back
#define si            set <int>
#define F             first
#define S             second
#define mii           map<int ,int >
#define msi           map<string,int >
#define mis           map<int , string>
#define fr(i,a,b)     for(int  i=a;i<=b;i++)
#define loop(i,n)     for(int i=0;i<n;i++)
#define all(v)        v.begin(),v.end()
#define vi            vector<int >
#define vii           vector<pair<int , int >>
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define mp            make_pair
#define input(arr,n)  loop(i,n) cin>>arr[i]
#define output(arr,n) loop(i,n) cout<<arr[i]<<" "
#define mod           998244353
#define sof           sizeof
using namespace std;
int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}

bool isPrime(int num){
    
    if(num==2) return true;
    if(num<2 || num%2==0) return false;
    for(int i = 3; i*i <=num; i+=2) {
       if(num % i == 0) {
          
          return false;
       }
    }
    return true;
   
}

bool comp(const pair<int,int> &a,const pair<int,int> &b){
  return a.F>b.F;
}

vector<vector<int>> L(3005,vector<int>(3005,-1));
string a,b;

const int N=1e5+5;
int dp[3][N];

void solve(){
  //cout<<"gadbad";
  
  int n;
  cin>>n;
  int  a[n],b[n],c[n];
  loop(i,n) cin>>a[i]>>b[i]>>c[i];
  dp[0][0]=a[0];
  dp[1][0]=b[0];
  dp[2][0]=c[0];  
  
  fr(i,1,n-1){
    dp[0][i]=max(dp[1][i-1],dp[2][i-1])+a[i];
    dp[1][i]=max(dp[2][i-1],dp[0][i-1])+b[i];
    dp[2][i]=max(dp[0][i-1],dp[1][i-1])+c[i];
  }
  cout<<max(max(dp[0][n-1],dp[1][n-1]),dp[2][n-1]);
}




signed main()   
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout); 
  #endif  

  int t;
  t=1;
  //cin>>t;
  loop(i,t){

      solve();
      if(i<t-1) cout<<"\n";
  }

  
  
  //directed graph
    



}
  


  



Measured memory_bytes: 41332
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt
  val red :List[List[Int]] = List.fill(n, 2)(sc.nextInt)
  val blue :List[List[Int]] = List.fill(n, 2)(sc.nextInt)
  val sortedRed :List[List[Int]] = red.sortWith((a, b) => a(1) > b(1))
  val sortedBlue :List[List[Int]] = blue.sortBy(_(0))

  var cnt = 0
  var usedList :List[Int] = Nil

  sortedBlue.foreach(b => {
    var loop = true
    var index = 0
    sortedRed.foreach(r => {
      if (loop & !usedList.contains(index) & b(0) > r(0) & b(1) > r(1)) {
        cnt += 1
        loop = false
        usedList = index :: usedList
      }
      index += 1
    })
  })

  println(cnt)
}

Measured memory_bytes: 25784
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <tuple>
#include <stack>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
typedef long long ll;
using namespace std;
ll mod = pow(10,9) + 7;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
char upper(char c){
	return c-0x20;
}
char lower(char c){
	return c+0x20;
}
int main() {
	int a,b;
	cin >> a >> b;
	if(a==1) a+=13;
	if(b==1) b+=13;
	if(a>b)
		cout << "Alice" << endl;
	else if(a<b)
		cout << "Bob" << endl;
	else
		cout << "Draw" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		System.out.println((long) N * (N - 1) / 2);

	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

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


Measured memory_bytes: 23252
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
#define PI             acos(-1.0)
#define IOS            ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ms(a,b)         memset(a, b, sizeof(a))
#define filein      freopen("input.txt", "r", stdin);
#define fileout     freopen("output.txt", "w", stdout);
#define debug       cout<<"Hello, i am in here."<<endl;
#define bit_cnt(mask) __builtin_popcountll(mask)
#define ll long long int
#define dst(u,v,x,y) sqrt((x*1.0-u*1.0)*(x*1.0-u*1.0)+(y*1.0-v*1.0)*(y*1.0-v*1.0))
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}
template <class T> inline T bpow(T p,T e){ll ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p);p = (p * p);}return (T)ret;}
using namespace std;
const int MOD = (int)1e9+7;
void solve()
{
  ll sum=0;
  ll n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      for(int k=1;k<=n;k++)
      {
        sum+=__gcd(i,__gcd(j,k));
      }
    }
  }
  cout<<sum<<endl;
}
int  main()
{
    IOS
    solve();
    return 0;
}



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

int main(){
  int n,k,h;
  cin >> n >> k;
  int r;
  for(int i;i<n;i++){
    cin >> h;
    if(h>=k){
      r++;
    }
  }
  cout << r;
  return 0;
}

Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

def same(x,y): # xとyが同じ集合に属するか判定
    return find(x)==find(y)

def main():
    n,m=inpm()
    ab=[]
    for _ in range(m):
        a,b=inpm()
        ab.append((a-1,b-1))
    ans=0
    global par,rank
    for i in range(m):
        par=[k for k in range(n)]  # 親
        rank=[0 for _ in range(n)] # 木の深さ
        for j in range(m):
            if i==j:
                continue
            unite(ab[j][0],ab[j][1])
        for j in range(n-1):
            if not same(j,j+1):
                ans+=1
                break
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 44012
#include<stdio.h>
#include<iostream>
using namespace std;
struct Card{char suit,value;};

void bubble(struct Card A[], int n){
  int i,j;
  bool flag=1;
  for ( i = 0; flag; i++ ){
      flag=0;
      for ( j = n-1; i < j; j-- ){
        if(A[j].value < A[j-1].value){
        swap(A[j],A[j-1]);
        flag=1;
        }
      }
  }
}

void selectinsert(struct Card A[], int n){
  int i,j,minv;
    for ( i = 0;i<n-1;i++){
      minv=i;
      for (j=i;n>j;j++){
        if(A[minv].value>A[j].value){
        minv=j;
        }
      }
      swap(A[i],A[minv]);
  }
}
void print(struct Card A[],int n){
int i;
  for ( i = 0; i < n; i++ ){
    if ( i > 0 ) cout << " ";
    cout << A[i].suit << A[i].value;
  }
  cout << endl;
}
bool isStable(struct Card A1[],struct Card A2[],int n){
int i;
  for ( i = 0; i < n; i++ ){
  if (A1[i].suit != A2[i].suit){
  return false;
  }

 }
 return true;
}


int main(){
  int n, i, j,sw;
  Card C1[100],C2[100];
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) cin >> C1[i].suit >> C1[i].value ;
  for(i=0;i<n;i++)C2[i]=C1[i];
  bubble(C1,n);
  selectinsert(C2,n);
  print(C1,n);
  cout << "Stable" << endl;
  print(C2,n);
  if (isStable(C1,C2,n)){
  cout << "Stable" << endl;
  }else{
  cout << "Not stable" << endl;
  }

    return 0;
}

Measured memory_bytes: 3208
import sys

S=input()
check=1

if S[0]!="A":
    print("WA")
    sys.exit()

SLIST=list(S)

if SLIST[1]=="C" or SLIST[len(S)-1]=="C":
    print("WA")
    sys.exit()
    


count=0
for x in SLIST:
    if x=="C":
        count+=1

if count==1 and 0<=S[2:].index("C")<=len(S)-4:
    True
else:
    print("WA")
    sys.exit()

for x in SLIST[1:]:
    if 97<=ord(x)<=122 or x=="C":
        True
    else:
        print("WA")
        sys.exit()

print("AC")
    

Measured memory_bytes: 3064
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);
		int n=sc.nextInt();
		for(int k=0; k<n; k++){
			int[] a=new int[3];
			for(int i=0; i<3; i++)
				a[i]=sc.nextInt();
			sort(a);
			if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2])
				println("YES");
			else
				println("NO");
		}
		sc.close();
	}

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

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

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

Measured memory_bytes: 12000
def main():
  t = input().lower()

  r = 0
  while True:
    sentence = input()

    if sentence == 'END_OF_TEXT':
      break

    sentence = sentence.split(' ')
    
    for word in sentence:
      if word.lower() == t:
        r += 1

  print(r)

if __name__ == '__main__':
  main()


Measured memory_bytes: 5556
from collections import deque
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = set()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.add((i, j))

for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = Q.copy()
    Q = set()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

for i in range(N):
    if len(A[i]) > 0:
        print(-1)
        exit()

print(ans)

Measured memory_bytes: 36076
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define  show for(int j=0;j<v.size();j++) cout<<v[j]<<" ";
#define ld long double
#define e endl
#define bc __builtin_popcount
#define MOD 1000000007
#define INT_SIZE 32
#define me(x) memset(x,0,sizeof(x))
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
int main()
{int k,x;
cin>>k>>x;

for(int i=-k+1;i<=k-1;i++)
{
    cout<<x+i<<" ";
}
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9



int main() {
	int N, A, B;
	cin >> N >> A >> B;
	if (abs(A - B) % 2 == 1) cout << "Borys" << endl;
	else cout << "Alice" << endl;


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
#define MAXN (100000+10)
int n;
vi e[MAXN];
ll dep=0;
int ss[MAXN]={};
void dfs(int x,int fa,ll l) {
	int s=0;
	for(int v:e[x]) if (v!=fa) {
		++s;dfs(v,x,l+1);
	}
	dep=max(dep,l);
	gmax(ss[l],s);
}
vector<pi > pa;
int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	For(i,n-1) {
		int u=read(),v=read();
		e[u].pb(v);
		e[v].pb(u);
		pa.pb(mp(u,v));
	}
	pair<ll,ll> ans;
	For(i,n) {
		For(i,n) ss[i]=0;
		dep=0;
		dfs(i,0,1);
		ll c=1;
		For(i,dep-1) c*=ss[i];
//		cout<<i<<':';
//		PRi(ss,dep-1)
		if(i==1) ans=mp(dep,c);
		else ans=min(ans,mp(dep,c));
	}	
//	cout<<ans.fi<<' '<<ans.se<<endl;
	
	Rep(i,n-1) {
		For(i,n) ss[i]=0;
		dep=0;
		int x=pa[i].fi,y=pa[i].se;
//		cout<<x<<' '<<y<<":";
		dfs(x,y,1);dfs(y,x,1);
		ll c=1;
////		PRi(ss,dep-1)
		For(i,dep-1) c*=ss[i];
		c*=2;
		ans=min(ans,mp(dep,c));
	}
	cout<<ans.fi<<' '<<ans.se<<endl;
	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
using namespace std;
int n,t,x,y;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&t,&x,&y);
		if (t<x+y||(t-x-y)%2==1)
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def d_num(num):
    ret = 0
    s = str(num)
    d = len(s)
    if d == 1:
        return num
    for i in range(d - 1):
        ret += (i + 1) * 9 * 10 ** i
    return ret + d * (num - 10 ** (d - 1) + 1)

def search(num, l, r):
    if r - l <= 1:
        return l, num - d_num(l)
    mid = (l + r) / 2
    if d_num(mid) > num:
        r = mid
    else:
        l = mid
    return search(num, l, r)

while True:
    K, N = map(int, raw_input().split())
    if K == 0:
        break
    '''
    S = ''
    for i in range(10000):
        S += str(i)
    print S[K:K + N]
    '''
    p = search(K - 1, 0, 10 ** 18)

    S = ''
    for i in range(p[0] + 1, p[0] + 101):
        S += str(i)
    print S[p[1]:p[1] + N]



Measured memory_bytes: 5020
class Integer
  
  attr_accessor :mod
  @@mod = 10 ** 9 + 7
  @@h = Hash.new
  
  alias_method :primitive_add, :+
  def +(other)
    res = self.primitive_add(other)
    res %= @@mod if res < 0 || res >= @@mod
    res
  end
  
  alias_method :primitive_minus, :-
  def -(other)
    res = self.primitive_minus(other)
    res %= @@mod if res < 0 || res >= @@mod
    res
  end
  
  alias_method :primitive_times, :*
  def *(other)
    self.primitive_times(other) % @@mod
  end
  
  def /(other)
    @@h[other] ||= other.pow(@@mod-2, @@mod)
    self * @@h[other] % @@mod
  end
end

n, k = gets.to_s.split.map{|e|e.to_i}

ans = (k..n+1).map{|i| i * (n + n - i + 1) / 2 - i * ( i - 1 ) / 2 + 1 }.reduce(:+)

puts ans

Measured memory_bytes: 16132
#include<iostream>
#include<vector>
#define REP(i,N) for(int i=0;i<(N);++i)
using namespace std;
bool check(vector<vector<int> >&map, vector<char> &used,int place,int bplace){
  bool res = true;
  REP(i,map[place].size()){
    if(map[place][i] == bplace)continue;
    if(used[map[place][i]])return false;
    used[map[place][i]] = true;
    res &= check(map,used,map[place][i],place);
  }
  return res;
}
int main(){
  int n,m;
  while(cin>>n>>m&&n!=0){
    vector<vector<int> > count(n,vector<int>());
    vector<char> used(n,false);
    REP(i,m){
      int a,b;
      cin>>a>>b;
      --a;--b;
      count[a].push_back(b);
      count[b].push_back(a);
    }
    bool flag = true;
    REP(i,n){
      if(count[i].size()>=3){
        flag=false;
        continue;
      }
    }
    if(!flag){
      cout << "no" << endl;
      continue;
    }
    REP(i,count.size()){
      if(used[i])continue;
      flag &= check(count,used,i,-1);
    }
    cout << (flag?"yes":"no") << endl;
  }
  return 0;
}



Measured memory_bytes: 6408
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,k;
  cin>>a>>b>>k;
  int count=0;
  for(int i=min(a,b);0<i;i--){
    if(a%(i)==0&&b%(i)==0)count++;
    if(count==k){
      cout<<i<<endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef unsigned long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
	ll n, m;
	scanf("%lld %lld", &n, &m);
	if(n > m/2) cout << m/2 << endl;
	else {
		ll y = n+n;
		ll t = m-y;
		ll k = ceil(t/4);
		cout << k + n << endl;
	}
    return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
constexpr long INF = 1L << 62;
long MOD = 1e9 + 7;

constexpr int MAX = 4000;
long fac[MAX], inv[MAX], finv[MAX];
void CombInit(){
    fac[0] = inv[0] = finv[0] = 1;
    fac[1] = inv[1] = finv[1] = 1;
    for(int i=2; i<MAX; ++i){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}

long Comb(int n,int k){
    if(n < 0 || k < 0 || n < k) return 0;
    return (fac[n] * finv[n-k] % MOD) * finv[k] % MOD;
}

long mod_pow(long x, long e) {
    long y = 1;
    while(e) {
        if(e&1) y = y*x%MOD;
        x = x*x%MOD;
        e >>= 1;
    }
    return y;
}


int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    long p; cin >> p;
    MOD = p;
    vector<int> a(p); REP(i,p) cin >> a[i];

    CombInit();
    // f(i) = a[i] (mod p)
    // fermat's little theorem
    // x^(p-1) mod p
    // | x == 0    = 0
    // | otherwise = 1
    // 
    // a[i] = 1 => f(i) = 1 (mod p)
    //
    // f(x) += (1 - (x - i)^(p-1))
    // it is because
    // (x-i)^(p-1) mod p
    // | x == i    = 0
    // | otherwise = 1
    //
    // finally
    // f(x) = (1 - (x - i)^(p-1)) + (1 - (x - j)^(p-1)) + ...
    // where a[i] = 1, a[j] = 1, ...
    // i != j(+ all other)なので、 x == iのとき上の第一項は1, それ以外は0。
    // 同様に、a[i](i = 0 ~ p-1) = 1のとき、上記のようにf(x)を構築することでそれぞれの条件を独立にf(x)に反映できる。

    // (x- i) ^ (p-1) = x^(p-1) + p-1C1*(-i)*x^(p-2) + 
    vector<long> b(p);
    REP(i,p) {
        if(a[i]) {
            (b[0] += 1) %= MOD;

            long prod = 1;
            for(int j = p-1; j >= 0; --j) {
                b[j] = (b[j] - Comb(p-1, j) * prod % MOD + MOD) % MOD;
                prod = (prod * (-i) + MOD) % MOD;
            }
        }
    }

    REP(i,p) cout << b[i] << (i == p-1 ? '\n' : ' ');

    return 0;
}

Measured memory_bytes: 512
import java.util.*;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			int n=in.nextInt();
			int m=in.nextInt();
			int ans=0;
			if((n|m)==0)
				return;
			String a[][]=new String[n][2];
			String b[]=new String[m];
			for(int i=0;i<n;i++)
			{
				a[i][0]=in.next();
				a[i][1]=in.next();
			}
			for(int i=0;i<m;i++)
				b[i]=in.next();
		
			for(int i=0;i<m;i++)
			{
				char ch[]=b[i].toCharArray();
				int cnt=0;
				for(int j=0;j<n;j++)
				{
					char re[]=a[j][0].toCharArray();
					boolean match=true;
					for(int k=0;k<re.length;k++)
					{
						if(re[k]=='*')
							continue;
						if(re[k]!=ch[k])
							match=false;
					}
					if(match)
						cnt=Math.max(cnt,Integer.valueOf(a[j][1]));
				}
				ans+=cnt;
			}
			System.out.println(ans);
		}
	}
	
	static public void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}
}

Measured memory_bytes: 63844
k=int(input())
unta=[[],[],[],[],[],[],[],[],[],[],[],[]]
unta[1]=["1","2","3","4","5","6","7","8","9"]
for keta in range(2,12):
	for i in range(len(unta[keta-1])):
		if unta[keta-1][i][keta-2]=="0":
			unta[keta].append(unta[keta-1][i]+"0")
			unta[keta].append(unta[keta-1][i]+"1")
		elif unta[keta-1][i][keta-2]=="9":
			unta[keta].append(unta[keta-1][i]+"8")
			unta[keta].append(unta[keta-1][i]+"9")
		else:
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])-1))
			unta[keta].append(unta[keta-1][i]+unta[keta-1][i][keta-2])
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])+1))
unchi=[]
for i in range(11):
	unchi+=unta[i]
print(unchi[k-1])

Measured memory_bytes: 46060
ans = []
while True:
    n,s  = map(int, input().split())
    if n==0 and s==0:
        break
    cnt = 0
    for x in range(1,n+1):
        for y in range(x+1,n+1):
            z = s - x - y 
            if y < z <= n:
                cnt += 1
    ans.append(cnt)

for a in ans:
    print(a)


Measured memory_bytes: 5600