akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define fish        push_front
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Deque       std::deque
#define PQueue      std::priority_queue
#define Set         std::set
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define HashMap     std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    template<class A, class B, class C> A power ( A x, B n, C mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    template<class A, class B> A power ( A x, B n ) { return power( x, n, 1000000007 ); }
    template<class A> A gcd ( A x, A y ) { return x % y ? gcd( y, x % y ) : y; }
    template<class A> A lcm ( A x, A y ) { return ( x / gcd(x, y) * y ); }
    template<class A> inline A abs ( A n ) { return ( n < 0 ) ? -n : n; }
    template<class A> inline boolean chmax ( A &a, const A &b ) { return b > a ? a = b, true : false; }
    template<class A> inline boolean chmin ( A &a, const A &b ) { return b < a ? a = b, true : false; }
    inline boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    int n;
    int s[110];
    int dp[110][10100];

    int dfs ( int pos, int sum ) {
        if ( pos == n ) {
            if ( sum % 10 == 0 ) return 0;
            return sum;
        }
        if ( ~dp[pos][sum] ) return dp[pos][sum];
        return dp[pos][sum] = std::max(dfs(pos+1,sum),dfs(pos+1,sum+s[pos]));
    }

    signed call_of_Cthulhu( signed datum ) {

        memset(dp, -1, sizeof(dp));

        read n;
        for ( int i = 0; i < n; i++ ) read s[i];
        echo dfs ( 0, 0 ) fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


Measured memory_bytes: 4608
#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 x;
  cin >> x;
  if (x == 1) {
    cout << 1 << endl;
    return 0;
  }

  int ans = 1;
  for (int b = 2; b < x; b++) {
    int p = 2;
    while (pow(b, p) <= x) p++;
    if (2 <= p - 1) ans = max(ans, int(pow(b, p - 1)));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
long long int dp[101][100001];
struct node{
  int w,v;
};
long long int knapsack(int n,int w,vector<node> v)
{
  if(n==0)
    return 0;
  if(w==0)
    return 0;
  long long int o1,o2;
  if(dp[n-1][w]!=-1)
    o1=dp[n-1][w];
  else
    o1=knapsack(n-1,w,v);
  if(w<v[n].w)
  	{
  		dp[n][w]=o1;
  		return o1;
	  }
  if(dp[n-1][w-v[n].w]!=-1)
    o2=dp[n-1][w-v[n].w]+v[n].v;
  else
    o2=knapsack(n-1,w-v[n].w,v)+v[n].v;
  if(o1>o2)
    dp[n][w]=o1;
  else
    dp[n][w]=o2;
  return dp[n][w];
}
int main()
{
  for(int i=0;i<101;i++)
    for(int j=0;j<100001;j++)
      dp[i][j]=-1;
  int n,w;cin>>n>>w;
  vector<node> v(n+1);
  v[0].v=v[0].w=0;
  for(int i=1;i<=n;i++)
    cin>>v[i].w>>v[i].v;
  cout<<knapsack(n,w,v)<<endl;
  return 0;
}
  

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

int main()
{
    int k,n;
    int a[200005];
    cin>>n>>k;
   // ll sum=0;
    for(int i=0;i<n;i++)
        {cin>>a[i];}
        sort(a,a+n);
        ll sum=0;
        for(int i=0;i<n-k;i++){
            sum+=a[i];
        }
        cout<<sum;
    return 0;
}


Measured memory_bytes: 1024
from sys import stdin


def main():
    N, M = map(int, input().split())
    *AB, = map(int, stdin.read().split())
    A = AB[::2]
    B = AB[1::2]
    Z = zip(A, B)
    Z = sorted(Z)
    num = 0
    yen = 0
    for a, b in Z:
        if M < num + b:
            yen += a * (M - num)
            break
        else:
            yen += a * b
            num += b
    print(yen)
    return


main()


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

int main() {
	int a[3], t[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	for (int i = 0;; i++) {
		if (a[0] % 2 || a[1] % 2 || a[2] % 2) {
			cout << i << endl;
			break;
		}
		t[0] = (a[1] + a[2]) / 2;
		t[1] = (a[2] + a[0]) / 2;
		t[2] = (a[0] + a[1]) / 2;
		sort(t, t + 3);
		if (t[0] == a[0] && t[1] == a[1] && t[2] == a[2]) {
			cout << -1 << endl;
			break;
		}
		a[0] = t[0];
		a[1] = t[1];
		a[2] = t[2];
	}
	return 0;
}


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



int main(){
    cout<<fixed<<setprecision(10);

    
    const double PI = acos(-1);
    
    double r; cin>>r;
    double s,p;
    s = PI*r*r;
    p = PI*r*2;
    cout<< s << " " << p;

    return 0;
}


Measured memory_bytes: 3280
def bubble_sort(card_list):
    cards = [i for i in card_list]
    list_length = len(cards)

    for i in range(list_length):
        for j in range(list_length-1,i,-1):
            if int(cards[j][1:]) < int(cards[j-1][1:]):
                cards[j],cards[j-1] = cards[j-1],cards[j]
    return cards

def selection_sort(card_list):
    cards = [i for i in card_list]

    list_length = len(cards)

    for i in range(list_length):
        min_element = i
        for j in range(i+1,list_length):
            if int(cards[j][1:]) < int(cards[min_element][1:]):
                min_element = j
        cards[i],cards[min_element] = cards[min_element],cards[i]
    return cards

n = int(input())
cards = input().split()
bubble_cards = bubble_sort(cards)
selection_cards = selection_sort(cards)

print(' '.join(bubble_cards))
print('Stable')
print(' '.join(selection_cards))
if bubble_cards == selection_cards:
    print('Stable')
else:
    print('Not stable')


Measured memory_bytes: 5612
n, k  = list(map(int, input().split()))
h = list(map(int, input().split()))

c = [0]
for i in range(1, n):
  tmp = 10**100
  for j in range(1, min(i, k)+1):
    tmp = min(abs(h[i] - h[i - j]) + c[i - j], tmp)
  c.append(tmp)
  
print(c[-1])


Measured memory_bytes: 57952
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int A, V, B, W, T;
	cin >> A >> V >> B >> W >> T;
	if (W >= V) {
		cout << "NO" << endl;
		return 0;
	}
	int diff = V - W;
	int time = (abs(B - A) + diff - 1) / diff;
	if (time <= T) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 3632
class UnionFind:
    def __init__(self, n):
        self.d = []
        for i in range(n):
            self.d.append(-1)
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] = self.d[x] + self.d[y]
        self.d[y] = x
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.d[self.find(x)]
    
n, m, k = map(int, input().split())
uf = UnionFind(n)
dame = [set() for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)
    dame[a].add(b)
    dame[b].add(a)
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not uf.same(c, d):
        continue
    dame[c].add(d)
    dame[d].add(c)

for i in range(n):
    ans = uf.size(i) - 1
    #print(uf.size(i))
    ans -= len(dame[i])
    print(ans, end=" ")
print()

Measured memory_bytes: 62212
n=int(input())
l=len(str(n))
top=int(str(n)[0])
bottom=int(str(n)[-1])
ans=0
for i in range(1,n+1):
  first=int(str(i)[0])
  last=int(str(i)[-1])
  if last==0:
    continue
  if first==last:
    ans+=1
  if last*10+first<=n:
    ans+=1
  for i in range(1,l-2):
    ans+=10**i
  if l>=3:
    if last>top:
      continue
    elif last<top:
      ans+=10**(l-2)
    else:
      if first<=bottom:
        ans+=int(str(n)[1:-1])+1
      else:
        ans+=int(str(n)[1:-1])
print(ans)

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/11/11  Problem: ABC 085 C / Link: http://arc085.contest.atcoder.jp/tasks/arc085_c  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL N;

LL ans = 0LL;


/* 最大流 Dinic Ｏ(EV^2)よりかなりはやい */
struct DINIC {
#define  MAX_V 305
	const LL INF = 1LL<<60LL;
	struct edge {
		int to; LL cap, rev;
		edge() {}
		edge(int to, LL cap, LL rev) :to(to), cap(cap), rev(rev) {}
	};

	vector<edge> G[MAX_V];
	LL level[MAX_V], iter[MAX_V];

	void add_edge(int from, int to, LL cap) {
		G[from].push_back(edge(to, cap, G[to].size()));
		G[to].push_back(edge(from, 0, G[from].size() - 1));
	}

	void bfs(int s) {
		memset(level, -1, sizeof(level));
		queue<int> q;
		level[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int v = q.front(); q.pop();
			FOR(i, 0, (int)G[v].size()) {
				edge &e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}

	LL dfs(int v, int t, LL f) {
		if (v == t) return f;
		for (LL &i = iter[v]; i < (int)G[v].size(); ++i) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				LL d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	LL max_flow(int s, int t) {
		LL flow = 0;
		while (true) {
			bfs(s);
			if (level[t] < 0) return flow;
			memset(iter, 0, sizeof(iter));
			LL f;
			while ((f = dfs(s, t, INF)) > 0)
				flow += f;
		}
	}

#undef  MAX_V 
};


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

	scanf("%lld", &N);
	VL a(N);
	LL sum = 0;
	FOR(i, 0, N) {
		scanf("%lld", &a[i]);
		if(a[i]>0)sum += a[i];
	}
	DINIC F;
	int s = 0;
	int t = N + 4;
	FOR(i, 0, N) {
		if (a[i] < 0)
			F.add_edge(s, i + 1, -a[i]);
		else F.add_edge(i+1, t, a[i]);
	}
	FOR(i, 1, N + 1) {
		FOR(j, i+1, N + 1) {
			if (j%i == 0) {
				F.add_edge(i, j, 1LL<<50LL);
			}
		}
	}

	ans = sum-F.max_flow(s,t);



	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int inf=1e18;
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,m,x;
    cin >> n >> m >> x;
    int c[n],a[n][m];
    for(int i=0;i<n;i++){
    	cin >> c[i];
    	for(int j=0;j<m;j++)
    		cin >> a[i][j];
    }
    int ans=inf;
    for(int mask=0;mask<(1ll<<n);mask++){
    	int s[m]={0},cost=0;
    	for(int i=0;i<n;i++){
    		if(((1ll<<i)&mask)==0)continue;
    		cost+=c[i];
    		for(int j=0;j<m;j++){
    			s[j]+=a[i][j];
    		}
    	}
    	int ok=1;
    	for(int i=0;i<m;i++){
    		if(s[i]<x)ok=0;
    	}
    	if(ok)ans=min(ans,cost);
    }
    if(ans==inf)ans=-1;
    cout << ans;
}

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

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

    map<long long int, int> num;
    for(int i=0; i<n; i++){
        long long int a;
        cin >> a;
        
        if(num.find(a) == num.end()) num[a] = 1;
        else num[a] += 1;
    }

    if(num.size() <= 3){
        vector<pair<long long int, int>> y;
        for(auto x : num){
            y.push_back(x);
        }

        if((int)y.size() == 3 
        && y[0].second == y[1].second
        && y[1].second == y[2].second
        && ((y[0].first ^ y[1].first) == y[2].first)){
            cout << "Yes" << endl;
            return 0;
        }
        if((int)y.size() == 2
        && y[0].first == 0
        && y[1].second == 2 * y[0].second){
            cout << "Yes" << endl;
            return 0;
        }
        if((int)y.size() == 1
        && y[0].first == 0){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 8380
#include<stdio.h>
void judge(int *);
int main(void)
{
	int i,n,a,b,c,jud=0;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d %d %d",&a,&b,&c);
		if(a > b && a > c){
			if(a*a==b*b+c*c)
				jud=1;
		}
		else if(b > c){
			if(b*b==a*a+c*c)
				jud=1;
		}
		else{
			if(c*c==a*a+b*b)
				jud=1;
		}
		judge(&jud);
	}
	return 0;
}
void judge(int *p)
{
	if(*p==1)
		printf("YES\n");
	else
		printf("NO\n");
	*p=0;
}

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

int h;
int w;

int cou = 0;
int main()
{
	cin >> h >> w;

	for(int i = 1;i <= h;i++){
		string s;
		cin >> s;
		for(int j = 1;j <= w;j++)
		{
			if(s[j - 1] == '#')
			{
				cou++;
			}
		}
	}


	if(cou == h + w - 1)
	{
		cout << "Possible" << endl;
	}
	else
	{
		cout << "Impossible" << endl;
	}
	return 0;
}



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

s = input()
print("Yes" if re.search('C.*F', s) else "No")


Measured memory_bytes: 10612
#include <string>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;

int main()
{
    string s;
    cin >> s;
    rep(i, s.size()){
        cout << "x";
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e15;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	rep(i,n) cin >> v[i];
	ll x = 0;
	rep(i,n) x ^= v[i];
	rep(i,n) {
		if (i != 0) cout << " ";
		cout << (x ^ v[i]);
	}
	cout << endl;
}

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

vector<pair<long long, int>> factorize(long long N)
{
  vector<pair<long long, int>> res;
  for (long long i = 2; i * i <= N; i++)
  {
    if (N % i != 0)
      continue;
    res.emplace_back(i, 0);
    while (N % i == 0)
    {
      N /= i;
      res.back().second++;
    }
  }
  if (N != 1)
    res.emplace_back(N, 1);
  return res;
}

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

  ll N;
  cin >> N;
  ll ans = 1;
  vector<ll> cnt(N + 1, 0LL);
  for (int i = 1; i <= N; i++)
  {
    vector<pair<ll, int>> tmp = factorize(i);
    for (auto a : tmp)
    {
      cnt[a.first] += a.second;
    }
  }
  for (int i = 2; i <= N; i++)
  {
    cerr << cnt[i] << endl;
    ans *= (cnt[i] + 1);
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const int mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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


// ll memo[2020][2020];
// int pascal_triangle(){
//   for(int i = 0; i < 2020; i++){
//     for(int j = 0; j < i+1; j++){
//       if(j == 0 || j == i) memo[i][j] = 1;
//       else{
// 	memo[i][j] = (memo[i-1][j-1]+memo[i-1][j]);
//       }
//     }
//   }
//   return 0;
// }


int factorial(int n){
  if(n == 0) return 1;
  return n*factorial(n-1);
}

int divisor(int a){
  int cnt = 0;
  for(int i=1; i <= a; i++) if(a%i == 0) cnt++;
  return cnt;
}

int comb(int n, int k){
  return factorial(n) / (factorial(n-k)*factorial(k));
}

int answer(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

int N;
int a;
int b;
int c;


int main(){
  cin >> N;
  int ans = inf;
  for(int i = 0; i <=N; i++){ // i = A yen
    int A = i;
    int B = N - i;
    int cnt = 0;
    while(A){
      cnt += A % 6;
      A/=6;
    }
    while(B){
      cnt += B%9;
      B/=9;
    }
    ans = min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}







Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <boost/lexical_cast.hpp>

int main(){
    long long n;
    std::cin >> n;

    std::vector<long long> vec;
    std::string a, b;
    long aDigit, bDigit;
    for(long i = 1; i <= std::sqrt(n); ++i){
        if(0 == n % i){
            a = boost::lexical_cast<std::string>(i);
            b = boost::lexical_cast<std::string>(n / i);
//            std::cout << "a: " << a << std::endl;
//            std::cout << "b: " << b << std::endl;
            
            if(a.size() < b.size()){
                vec.push_back(b.size());
            }else{
                vec.push_back(a.size());
            }
        }
    }

    std::cout << *min_element(vec.begin(), vec.end()) << std::endl;

    return 0;
}


Measured memory_bytes: 888
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// std::ios::sync_with_stdio(false);

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    LL N,A,B;
    while (cin >> N >> A >> B) {
        LL ans = 0;
        if (N == 1) 
            ans = (A == B);
        else if (A <= B) {
            const LL lo = A+B + A*(N-2);
            const LL hi = A+B + B*(N-2);
            ans = hi-lo+1;
        }
        cout << ans << endl;
    }
    return 0;
}


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

int main() {
	int D, G;
	cin >> D >> G;

	vector<int> p(D), c(D);
	for (int i = 0; i < D; i++) {
		cin >> p[i] >> c[i];
	}

	int ans = 10000;
	for (int i = 0; i < (1<<D); i++) {
		int sum = 0;
		int n = 0;
		for (int j = 0; j < D; j++) {
			if (!(i & (1 << j))) continue;
			sum += 100 * (j + 1) * p[j] + c[j];
			n += p[j];
		}

		for (int j = D - 1; j >= 0; j--) {
			if ((i & (1 << j))) continue;
			if (G - sum <= 0) continue; 

			int cnt = min((G - sum) / (100 * (j + 1)), p[j]);
			n += cnt;
			sum += cnt * 100 * (j + 1);
		}
		ans = min(ans, n);
	}
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
/*saidaiti*/
#include<stdio.h>
int main(void)
{
  int a,b;
  scanf("%d",&a);
  scanf("%d",&b);
  if(a+b>=a-b&&a+b>=a*b){
         printf("%d\n",a+b);
  }
  else if(a-b>=a+b&&a-b>=a*b){
         printf("%d\n",a-b);
  }
  else{
         printf("%d\n",a*b);
  }
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,ans1=1,ans2=1,ans3=1,ans4=1,ans,mod=1e9+7;
    cin>>n;
    for(int i=0;i<n;i++){
        ans1*=10;
        ans2*=9;
        ans3*=9;
        ans4*=8;
        ans1%=mod;
        ans2%=mod;
        ans3%=mod;
        ans4%=mod;
    }
    ans=(ans1-ans2-ans3+ans4)%mod;
    if(ans<0){
        ans+=mod;
    }
    cout<<ans<<endl;
    return (0);
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;
  int A = S[0] -'0';
  int B = S[1] -'0';
  int C = S[2] -'0';
  int D = S[3] -'0';
  if(A+B+C+D == 7) cout << A << '+' << B << '+' << C<< '+' << D <<'=' << 7 << endl;
  else if(A-B+C+D == 7) cout << A << '-' << B << '+' << C<< '+' << D <<'=' << 7 << endl;
  else if(A+B-C+D == 7) cout << A << '+' << B << '-' << C<< '+' << D <<'=' << 7 << endl;
  else if(A+B+C-D == 7) cout << A << '+' << B << '+' << C<< '-' << D <<'=' << 7 << endl;
  else if(A-B-C+D == 7) cout << A << '-' << B << '-' << C<< '+' << D <<'=' << 7 << endl;
  else if(A+B-C-D == 7) cout << A << '+' << B << '-' << C<< '-' << D <<'=' << 7 << endl;
  else if(A-B+C-D == 7) cout << A << '-' << B << '+' << C<< '-' << D <<'=' << 7 << endl;
  else if(A-B-C-D == 7) cout << A << '-' << B << '-' << C<< '-' << D <<'=' << 7 << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
  char s[4];
  int i, j;
  int a[4], b[4];
  int f = 0, sum = 0;
  for(i = 0; i < 4; i++){
    cin >> s[i];
  }

  for(i = 0; i < 3; i++){
    for(j = i + 1; j < 4; j++){
      if(s[i] == s[j]){
        f++;
      }
    }
    if(f == 1){
      sum++;
    }
    f = 0;
  }
  if(sum == 2){
    cout << "Yes";
  }
  else{
    cout << "No";
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int x,y;
  while(1){
    cin >> x >> y;
    if(x==0 && y==0) break;


    if(x<y){
      cout <<x<<" "<<y<<endl;
    }
    else if(y<x){
      cout <<y<<" "<<x<<endl;
    }
    else if(x==y){
      cout <<x<<" "<<y<<endl;
    }
  }
  
}
  



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

int main()
{
	string s;
	cin >> s;
	int n = s.size();
  	int st=200000,ed=0;
	for(int i = 0;i < n; i++) {
		if(s[i] == 'A') {
          st = i;
          break;
        }
    }
          
	for(int i = n-1; i >= 0; i--) {
      if(s[i] == 'Z') {
          ed = i;
          break;
        }
	}
	cout << ed - st + 1 << endl;
}






Measured memory_bytes: 640
program main
   integer(8) N, Time, total, i
   integer(8), allocatable :: t(:)
   read(*, *) N, Time
   allocate(t(1: N+1))
   read(*, *) t(1: N)
   t(N+1) = t(N) + Time
   total = 0
   do i = 1, N
       if( t(i+1)-t(i) <= Time) then
	       total = total + (t(i+1)-t(i))
	   else 
	       total = total + Time
	   end if
   end do
   write(*, *) total 
end program main

Measured memory_bytes: 2304
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <map>
#include <queue>
#define N 1010
#define ll long long
#define mo ((ll)1e9+7)
//10000000000037ll
//21993833369ll
#define db double
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
bool cmp(int a, int b) {return a > b;}
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}
int main() {
	ll x, k, d;
	scanf("%lld%lld%lld", &x, &k, &d);
	if (x < 0)x *= -1ll;
	ll tmp = min(k, x / d);
	k -= tmp, x -= tmp * 1ll * d;
	if (k & 1)x -= d;
	printf("%lld\n", (ll)fabs(x));
	return 0;
}

Measured memory_bytes: 3828
//shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 

const ll inf = (ll)(1e17 + 17);
const ll mod = (ll)(1e9 + 7);
ll k;
ll todo1(ll xx) {
	ll ct = 0;
	for(ll i = 2; i*i <= xx; i++) {
		if(xx%i == 0) {
			ll pp = xx;
			while(pp%i == 0) pp/=i;
			if(pp%i == 1) ct++;
			pp = xx;
			if(xx/i != i) {
				ll ii = xx/i;
				while(pp%ii == 0) pp/=ii;
				if(pp%ii == 1) ct++;
			}
		}
	}
	return ct;
}
ll todo2(ll xx){
	ll ct = 0;
	for(ll i = 2; i*i <= xx; i++) {
		if(xx%i == 0) {
			ct++;
			if(xx/i != i) ct++;
		}
	}
	return ct;
}

int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  cin >> k;
  if(k == 2) {
  	cout << 1 << endl;
  	return 0;
  }
  cout << todo1(k) + todo2(k-1) + 2 << endl;
  return 0;
} //good night.

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

int main() {
    int n,k;
    cin >> n >>k;
    vector<ll>a(n);
    rep(i,n) cin >> a[i];
    vector<ll>init_a(n);
    rep(i,n) init_a[i] = a[i];
    ll ans = 1e18;
    for(int bit = 0;bit < (1<<n);bit++) {
        ll tmp = 0;
        ll cnt = 0;
        for(int i = 0;i<n;i++) {
            if(bit & (1<<i)) {
                ll maxh = 0;
                for(int j = 0;j<i;j++) {
                    maxh = max(maxh,a[j]);
                }
                if(maxh >= a[i]) {
                    tmp = tmp + maxh - a[i] + 1;
                    a[i] += maxh - a[i] + 1;
                }
                cnt++;
            }
        }
        if(cnt == k) {
            ans = min(ans,tmp);
        }
        rep(i,n) a[i] = init_a[i];
    }
    cout << ans << endl;
}

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

int main() {
  string s; cin>>s;
  int n = s.size(),c=0;
  for(int i=0; i<n; i++) {
    s.erase(s.size()-1);
    if(s.size()%2==0) {
      string t1 = s.substr(0,s.size()/2);
      string t2 = s.substr(s.size()/2);
      if(t1==t2) break;
    }
  }
  cout<<s.size();
}

Measured memory_bytes: 256
x,y = gets.chomp.split.map(&:to_i)
mod = 1000000007
ans = 0
max_num = 1000010

class Combination_mod_p
  def initialize(mod,max_num)
    @max_num = max_num
    @mod = mod

    @fac = Array.new(@max_num,0)
    @finv = Array.new(@max_num,0)
    @inv = Array.new(@max_num,0)

    @fac[0] = @fac[1] = 1
    @finv[0] = @finv[1] = 1
    @inv[1] = 1
    (2..@max_num-1).each do |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 
    end
  end

  def com(n,k)
    return 0 if n < k || (n < 0 || k < 0)

    return @fac[n] * (@finv[k] * @finv[n-k] % @mod) % @mod
  end
end

if (-x + 2*y) % 3 == 0 && (2*x - y) % 3 == 0
  combination = Combination_mod_p.new(mod,max_num)
  r_n = (-x + 2*y)/3
  u_n = (2*x - y)/3
  sum = r_n + u_n
  if r_n > u_n
    ans = combination.com(sum,u_n)
  else
    ans = combination.com(sum,r_n)
  end
end

puts ans

Measured memory_bytes: 25212
#include<bits/stdc++.h>
using namespace std;
int dp[100001],k;
/*int ans(int a[],int n)
{if(n==0) return dp[0];
 if(n==1) return dp[1];
 if(dp[n]!=-1) return dp[n];
 int min=1000000;
 for(int i=n;i>n-k&&i>0;i--)
 {   int temp=ans(a,i-1)+abs(a[n]-a[i-1]);
     if(temp<min) min=temp;
 }
 dp[n]=min;
 return dp[n];
}*/
int main()
{   ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int n;
    cin>>n>>k;
    int a[n];
    int i,j;
    for(i=0;i<n;i++) cin>>a[i];
    memset(dp,1000000, sizeof(dp));
    dp[0]=0;dp[1]=abs(a[1]-a[0]);
    n--;
 for(j=0;j<=n;j++)
{   
     for(i=1;i<=min(j,k);i++)
 {  
			dp[j]=min(dp[j],abs(a[j]-a[j-i])+dp[j-i]);
 }
} 
    cout<<dp[n]<<endl;
    return 0;
} 

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline
import math

def combnations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

INF = 10 ** 9 + 7
N, K = map(int, input().split())
for i in range(1, K + 1):
    if N - K + 1 < i:
        print(0)
        continue
    ans = combnations(N - K + 1, i) * combnations(K - 1, i - 1)
    ans %= INF
    print(ans)

Measured memory_bytes: 3316
N = int(input())
H = list(map(int, input().split()))

H_max = 0
flag = True
for i in range(N):
    if H_max < H[i]:
        H_max = H[i]
    if H_max - H[i] >= 2:
        flag = False
        break

if flag == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 14252
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007

using namespace std;

struct UnionFind{
  vector<int> par,num;

  UnionFind(int N) : par(N),num(N){
    for(int i=0;i<N;i++){
      par[i] = i;
      num[i] = 1;
    }
  }

  int root(int x){
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry) return;
    par[rx] = ry;
    num[ry] = num[ry]+num[rx]; 
  }

  int get_num(int x){
    int rx = root(x);
    return num[rx];
  }

  bool same(int x, int y){
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

ll modpow(ll a, ll n, ll p){
  if(n == 0){
    return 1;
  }
  if(n%2 == 0){
    ll root = modpow(a,n/2,p);
    return root * root %p;
  }
  else{
    return a*modpow(a,n-1,p)%p;
  }
}


int main(void){
  ll n,a,b;
  cin >> n >> a >> b;
  
  ll ans = (modpow(2,n,MAX)-1)%MAX;

  //cout << ans << endl;
  ll work = 1, work2 = 1;
  rep(i,a){
    work *= n-i;
    work %= MAX;
    work2 *= i+1;
    work2 %= MAX;
  }
  ans -= (work*modpow(work2,MAX-2,MAX))%MAX;
  if(ans < 0){
    ans += MAX;
  }
  work = 1; work2 = 1;
  rep(i,b){
    work *= n-i;
    work %= MAX;
    work2 *= i+1;
    work2 %= MAX;
  }
  ans -= (work*modpow(work2,MAX-2,MAX))%MAX;
  if(ans < 0){
    ans += MAX;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using Graph = vector<vector<pii>>;
const int MOD = 1e9 + 7;

struct UnionFind {
    vector<int> par, rnk;
    int cnt;

    UnionFind(int N) : par(N), rnk(N), cnt(N) {
        for (int i = 0; i < N; ++i)
            par[i] = i;
    }

    int root(int x) {
        return (par[x] == x ? x : par[x] = root(par[x]));
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y)
            return;
        if (rnk[x] < rnk[y])
            swap(x, y);
        par[y] = x;
        if (rnk[x] == rnk[y])
            rnk[x]++;
        cnt--;
    }
};

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

    int N, M;
    cin >> N >> M;

    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        X--, Y--;
        uf.unite(X, Y);
    }

    cout << uf.cnt << endl;

    return 0;
}


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

#define MAXN 100100

int value[4][MAXN], dp[4][MAXN];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> value[1][i] >> value[2][i] >> value[3][i];
    }
    fill(dp[1], dp[1]+n+1, -1);
    fill(dp[2], dp[2]+n+1, -1);
    fill(dp[3], dp[3]+n+1, -1);
    dp[1][1] = 0;
    dp[2][1] = 0;
    dp[3][1] = 0;
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= 3; j++){
            for(int k = 1; k <= 3; k++){
                if(j == k) continue;
                dp[k][i+1] = max(dp[k][i+1], dp[j][i] + value[k][i]);
            }
        }
    }
    dp[1][n] += max(value[2][n], value[3][n]);
    dp[2][n] += max(value[1][n], value[3][n]);
    dp[3][n] += max(value[2][n], value[1][n]);
    cout << max(dp[1][n], max(dp[2][n], dp[3][n])) << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <iomanip>
#include <algorithm>

typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for(ll i=init;i<(n);i++)

int main() {
    int n, l;
    cin >> n >> l;
    ll total = 0;
    repi(i, n, 0) {
        total += l + i;
    }
    ll diff = INF;
    ll ans = 0;
    repi(i, n, 0) {
        if(diff > abs(total - (total - (l + i)))){
            ans = total - (l + i);
            diff = abs(total - (total - (l + i)));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
n = list(map(int, list(input()[::-1])))
l = len(n)

ans = dec = 0
for i in range(1<<l):
        cnt = 0
        for j in range(l):
                if j==l-1:
                        cnt += n[j] - dec
                        break
                if((i>>j)&1):
                        cnt += 9
                        dec = True
                else:
                        cnt += n[j] - dec
                        dec = False
        ans = max(ans, cnt)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
const ll ATCODER_AMARI = 1000000007; //10^9 + 7
const ll INF = 10000000000000;

//階乗関数　ATCODER_AMARIに注意
ll factorial(ll k){
  ll sum = 1;
  for(int i = 1 ; i < k + 1; i++) {
    sum *= i;
    //sum = sum % ATCODER_AMARI;
  }
  return sum;
}

int main() {
  ll sum = 0;
  string nnn;
  cin >> nnn;
  rep(i,nnn.size()) {
    int kkk = nnn.at(i) - '0';
    sum += kkk;
    sum %= 9;
  }

  if(sum == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}



Measured memory_bytes: 3652
PROGRAM-ID.                      ABC_045_B.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 SA1.
        03 SA PIC X(1) OCCURS 100.

    01 SB1.
        03 SB PIC X(1) OCCURS 100.

    01 SC1.
        03 SC PIC X(1) OCCURS 100.

    01 now     PIC X(1) VALUE SPACE.
    01 winner  PIC X(1).

    01 aidx    PIC 9(3) VALUE ZERO.
    01 bidx    PIC 9(3) VALUE ZERO.
    01 cidx    PIC 9(3) VALUE ZERO.

    01 alen    PIC 9(3).
    01 blen    PIC 9(3).
    01 clen    PIC 9(3).

    01 flg     PIC X(1) VALUE ZERO.

PROCEDURE                        DIVISION.
    ACCEPT SA1.
    ACCEPT SB1.
    ACCEPT SC1.

    MOVE 'a' TO now.

    COMPUTE alen = FUNCTION STORED-CHAR-LENGTH(SA1).
    COMPUTE blen = FUNCTION STORED-CHAR-LENGTH(SB1).
    COMPUTE clen = FUNCTION STORED-CHAR-LENGTH(SC1).

    PERFORM UNTIL flg = 1
        IF now = 'a' THEN
            ADD 1 TO aidx
            MOVE SA(aidx) TO now
            IF alen < aidx THEN
                MOVE 'A' TO winner
                EXIT PERFORM
            END-IF
        ELSE
            IF now = 'b' THEN
                ADD 1 TO bidx
                MOVE SB(bidx) TO now
                IF blen < bidx THEN
                    MOVE 'B' TO winner
                    EXIT PERFORM
                END-IF
            ELSE
                ADD 1 TO cidx
                MOVE SC(cidx) TO now
                IF clen < cidx THEN
                    MOVE 'C' TO winner
                    EXIT PERFORM
                END-IF
        END-IF
    END-PERFORM.

    DISPLAY winner.

    STOP RUN.


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



int main() {
	
	int A,A2,B,B2;
	cin >>A>> A2>>B>>B2;
	
	if (A == 12) {
		if (B == 1) {
			cout << 1 << endl;
			return 0;
		}
	}
	else {
		if (A + 1 == B) {
			cout << 1 << endl;
			return 0;
		}
	}

	cout<<0 << endl;
	
}

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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod (int)(1e9 +7);

const double pi = acos(-1.0);

typedef vector<int> vi;
typedef string ss;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

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

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}

int main()
{
    ll n,k;
    cin >> n >> k;

    vll h(n),dp(n,0);
    rep(i,n)cin >> h[i];

    if(n <= k  + 1){
        cout << abs(h[0] - h[n-1]) << endl;
        return 0;
    }

    dp[0] = 0;

    REP(i,1,k+1)dp[i] = abs(h[i] - h[0]);

    REP(i,k+1,n){
        ll min = M;
        ll tmp;
        REP(j,1,k+1){
            tmp = abs(h[i] - h[i-j]) + dp[i-j];
            
            if(min >= tmp)min = tmp;
            //cout << tmp << endl;
        }

        dp[i] = min;
    }

    /*cout << endl;
    rep(i,n)cout << dp[i] << endl;
    cout << endl;*/

    cout << dp[n-1] << endl;

    return 0;
} 

Measured memory_bytes: 1792
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 1

typedef long long ll;

const double PI = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

int main(){
    int N;
    cin >> N;
    string a = to_string(N);
    ll ans = 0;
    for(int i = 1; i <= a.size() - 1; i++){
        if(i % 2 == 1){
            ll temp = 1;
            for(int j = 1; j <= i; j++){
                if(j == 1) temp *= 9;
                else temp *= 10;
            }
            ans += temp;
        }
    }
    if(a.size() % 2 == 1){
        ll temp = 1;
        for(int i = 1; i <= a.size() - 1; i++) temp *= 10;
        ans += N - temp + 1; 
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3684
def main():
    X, K, D = map(int, input().split())

    if X == 0:
        minCount = 0
    else:
        minCount = abs(X) // D
    
    if minCount >= K:
        print(min(abs(X - D * K), abs(X + D * K)))
        return

    absplusD = abs(X + D * minCount)
    absminusD = abs(X - D * minCount)
    if(min(absplusD, absminusD) == absminusD):
        X = X - D * minCount
    else:
        X = X + D * minCount
        
    K = K - minCount

    plusX = X + D
    minusX = X - D

    if min(abs(X), abs(plusX), abs(minusX)) == abs(X):
        if K % 2 == 0:
            print(abs(X))
        else:
            print(min(abs(plusX), abs(minusX)))

    else:
        if (K - 1) % 2 == 0:
            print(min(abs(plusX), abs(minusX)))
        else:
            print(abs(X))

if __name__ == "__main__":
    main()

Measured memory_bytes: 9164
import fractions
n,x=map(int,input().split())
pl=sorted(list(map(int,input().split()))+[x])
ans=abs(pl[1]-pl[0])
if len(pl)>1:
    for i in range(len(pl)-2):
        ans=fractions.gcd(ans,abs(pl[i+2]-pl[i+1]))
print(ans)

Measured memory_bytes: 16244
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vll = vector<ll> ;
#define all(v) v.begin(),v.end()

int main(){
  ll N;cin>>N;
  int cnt[100000];
  fill(cnt,cnt+100000,0);
  for(int i=1;i<=100;++i){
    for(int j=1;j<=100;++j){
      for(int k=1;k<=100;++k){
        cnt[i*i+j*j+k*k+i*j+j*k+k*i]++;
      }
    }
  }
  rep(i,N+1){
    if(i==0)continue;
    cout<<cnt[i]<<endl;
  }
}

Measured memory_bytes: 3912
#include<bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,j,n) for(int i=j;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)

int ctoi(char c) {
	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

int main() {
    string s;
	cin >> s;
    int n=s.length();
    long mod = 1000000007;
    long dp[n][13];
    fr(i,n){
      fr(j,13){
        dp[i][j]=0;
      }
    }
    fr(i,n){
      if(s[i]=='?'){
        if(i==0){
          fr(j,10){
            dp[0][j]=1;
          }
        }
        else{
          fr(j,13){
            fr(k,10){
              dp[i][(j*10+k)%13]+=dp[i-1][j];
              dp[i][(j*10+k)%13]%=mod;
            }
          }
        }
      }
      else{
        int a = ctoi(s[i]);
        if(i==0){
          dp[0][a]=1;
        }
        else{
          fr(j,13){
            dp[i][(j*10+a)%13]=dp[i-1][j];
            dp[i][(j*10+a)%13]%=mod;
          }
        }
      }
    }
    
    cout << dp[n-1][5] << endl;
}


Measured memory_bytes: 10624
#include<stdio.h>
using namespace std;
int main()
{
   int w,a,b;
   scanf("%d %d %d",&w,&a,&b);

  if(a+w<b)
   {
    printf("%d\n",b-(a+w));
   }

    else if(a>b+w)
    {
      printf("%d\n",a-(b+w));
    }

  else
    {
     printf("0\n");
    }
return 0;
}



Measured memory_bytes: 504
#include <iostream>
#include <algorithm>
#define MAX_N 1000000
#define L 1000
using namespace std;
struct cave{
	int num;
	int pnum;	//探索した素数洞穴の総数
	int lastp;	//最後に通った素数の値
};

struct cave hole[L+1][L+1];
bool prime[MAX_N+1];

int main(){
	for(int i = 0; i < MAX_N+1; i++){
		prime[i] = true;
	}
	prime[0] = prime[1] = false;	//prime[1]:1
	for(int i = 2; i <= MAX_N; i++){
		if(prime[i] == true){
			for(int j = 2*i; j < MAX_N; j += i){
				prime[j] = false;
			}
		}
	}	//素数判定
	for(int i = 0; i < L/2; i++){
		for(int j = 0; j < 2*i+1; j++){
			hole[-i-1+L/2][-i+j+L/2-1].num = (2*i+2)*(2*i+2)-j;
			hole[-i-1+j+L/2][i+1+L/2-1].num = (2*i+1)*(2*i+2)+1-j;
			hole[i+L/2][i+1-j+L/2-1].num = (2*i+1)*(2*i+1)+1-j;
			hole[i-j+L/2][-i+L/2-1].num = 2*i*(2*i+1)+1-j;
		}
	}	//mapping
	int m,n;
	while(cin >> m >> n,m){
		int sy = -1,sx = -1;
		for(int i = 0; i < L; i++){
			for(int j = 0; j < L; j++){
				if(hole[i][j].num == n){
					sy = i;
					sx = j;
					break;
				}
				if(sy!=-1&&sx!=-1){break;}
			}
		}
		for(int i = 0; i < L; i++){
			for(int j = 0; j < L; j++){
				hole[i][j].pnum = 0;
				hole[i][j].lastp = 0;
			}
		}	//hole初期化


		if(prime[hole[sy][sx].num] == true){
			hole[sy][sx].pnum = 1;
			hole[sy][sx].lastp = hole[sy][sx].num;
		}
		for(int i = sy+1; i < L; i++){	//syのあった段から下に見ていく
			for(int j = max(0,sx-(i-sy)); j <= min(sx+(i-sy),L-1); j++){
				if(hole[i][j].num <= m){	//洞穴の個数以上の場所は見ない
					int tmp = 0,maxtmp = 0;
					for(int k = -1; k <= 1; k++){
						if(max(0,sx-(i-sy)) <= j+k && j+k <= min(sx+(i-sy),L-1) && maxtmp < hole[i-1][j+k].pnum){
							maxtmp = hole[i-1][j+k].pnum;
							tmp = hole[i-1][j+k].lastp;
						}
					}
					hole[i][j].pnum = maxtmp;
					hole[i][j].lastp = tmp;
					if(prime[hole[i][j].num] == true){
						hole[i][j].pnum ++;
						hole[i][j].lastp = hole[i][j].num;
					}
				}
			}
		}

		int maxtmp = -1;
		int last = 0;
		for(int i = 0; i < L; i++){
			for(int j = 0; j < L; j++){
				if(hole[i][j].num <= m){
					if(hole[i][j].pnum == maxtmp && hole[i][j].lastp > last){
						last = hole[i][j].lastp;
					}else if(hole[i][j].pnum > maxtmp){
						maxtmp = hole[i][j].pnum;
						last = hole[i][j].lastp;
					}
				}
			}
		}
		cout << maxtmp << " " << last << endl;
	}
	return 0;
}

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

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める

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

    ll K;
    string S;
    cin >> K >> S;
    if(S.length() <= K){
        cout << S << endl;
    }else{
        S = S.substr(0,K);
        S += "...";
        cout << S << endl;
    }

    return 0;
}


Measured memory_bytes: 3656