akhauriyash/Code-Regression huggingface dataset:
s = input()
k = int(input())
li = []
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if j-i<=6:
            li += [s[i:j]]
li2 = set(li)
li3 = sorted(li2)
print(li3[k-1])

Measured memory_bytes: 13164
N,K = map(int,input().split())
A = list(map(int,input().split()))

move_dic = {1:0}
move_list = [1]
pre = A[0]
counter = 0
while True:
    if pre in move_dic:
        loopstart = move_dic[pre]
        loop = move_list[loopstart:]
        init_len = len(move_list)
        loop_len = len(loop)
        break
    else:
        counter += 1
        move_dic[pre] = counter
        move_list.append(pre)
        pre = A[pre - 1]

if K >= init_len:
    ans = (K - init_len) % loop_len
    print(loop[ans])
else:
    print(move_list[K])

Measured memory_bytes: 38976
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
#define inf 2123456789
#define maxn 100005
ll a[212345] = { 0 };
ll b[412345] = { 0 };
ll c[412345] = { 0 };
int main() {
	ll n, i, t, ans = 0;
	cin >> n;
	for (i = 1; i <= n; i++) {
		cin >> t;
		if (t > 200000)a[i] = -1;
		else a[i] = t;
	}
	for (i = 1; i <= n; i++) {
		if (a[i] == -1)continue;
		else {
			t = i - a[i] + 200002;
			b[t]++;
			t = i + a[i] + 200002;
			c[t]++;
		}
	}
	for (i = 0; i < 412345; i++) {
		ans += c[i] * b[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 9944
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<iomanip>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007
#define MAXS(x,y) (x = max(x,y))
#define MINS(x,y) (x = min(x,y))

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int N;
double dp[301][301][302];

int main(){
  cin >> N;

  vector<int> a(N);
  REP(i,N) cin >> a[i];

  dp[0][0][0] = 0.0;
  map<int, int> m;
  REP(i,N){
    m[a[i]] += 1;
  }


  REP(i,N+1)REP(j,N+1)REP(k,N+1){
    if(i == 0 && j == 0 && k ==0)continue;

    int res = N;
    double p = 1.0;

    if(i > 0){
      p += dp[i-1][j+1][k] * i / N;
      res -= i;
    }

    if(j > 0){
      p += dp[i][j-1][k+1] * j / N;
      res -= j;
    }

    if(k > 0){
      p += dp[i][j][k-1] * k / N;
      res -= k;
    }

    dp[i][j][k] = p * N / (N-res);
  }


  cout << setprecision(10) << dp[m[3]][m[2]][m[1]] << endl;
}

Measured memory_bytes: 214144
N = int(input())
L= sorted(list(map(int, input().split())))

count = 0
for i in range(N):
  z = 0
  for j in range(i + 1, N):
    x = L[i] + L[j]
    if z < N:
      while L[z] < x:
        z += 1
        if z == N:
          break
    count += z - j - 1
    #print(count)
print(count)


Measured memory_bytes: 42732
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
typedef long long lint;
const int N=1e5+5;
int n;
struct _pair{
	int id,x,y;
}pnt[N];

namespace utils{
	template <class T> inline void apn(T &x,const T y){x>y?x=y:0;}
	template <class T> inline void apx(T &x,const T y){x<y?x=y:0;}
	template <class T> inline T cabs(const T &x){return x<0?-x:x;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=(c=='-')&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

bool cmp_x(const _pair &a,const _pair &b){
	return a.x<b.x;
}

bool cmp_y(const _pair &a,const _pair &b){
	return a.y<b.y;
}

namespace G{
	int cnt,fa[N];
	struct edge{
		int x,y,v;
		friend bool operator < (const edge &a,const edge &b){
			return a.v<b.v;
		}
	}eg[N<<2];

	inline void add(const int a,const int b,const int v){
		eg[++cnt]=(edge){a,b,v};
	}

	int find_rt(const int x){
		return fa[x]?fa[x]=find_rt(fa[x]):x;
	}

	int kruskal(){
		std::sort(eg+1,eg+cnt+1);
		int ans=0;
		for(int i=1; i<=cnt; ++i){
			int x=find_rt(eg[i].x),y=find_rt(eg[i].y);
			if(x==y) continue;
			fa[x]=y;
			ans+=eg[i].v;
		}
		return ans;
	}
}

int main(){
	n=nxi();
	for(int i=1; i<=n; ++i){
		pnt[i].id=i;
		pnt[i].x=nxi(),pnt[i].y=nxi();
	}
	std::sort(pnt+1,pnt+n+1,cmp_x);
	for(int i=1; i<n; ++i){
		int res=std::min(pnt[i+1].x-pnt[i].x,cabs(pnt[i+1].y-pnt[i].y));
		G::add(pnt[i].id,pnt[i+1].id,res);
	}
	std::sort(pnt+1,pnt+n+1,cmp_y);
	for(int i=1; i<n; ++i){
		int res=std::min(pnt[i+1].y-pnt[i].y,cabs(pnt[i+1].x-pnt[i].x));
		G::add(pnt[i].id,pnt[i+1].id,res);
	}
	printf("%d\n",G::kruskal());
	return 0;
}


Measured memory_bytes: 6528
N,M=map(int,input().split())
A=[[int(i) for i in input().split()] for i in range(N)]
r=0
mod=998244353
for j in range(M):
  flag=False
  for i in range(r,N):
    if not flag:
      if A[i][j]:
        flag=True
        A[i],A[r]=A[r],A[i]
        r+=1
    else:
      if A[i][j]:
        for k in range(M):
          A[i][k]^=A[r-1][k]

Factorial=[1]*(r+1)
for i in range(1,r+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
  
inverseFactorial=[1]*(r+1)
inverseFactorial[r]=power(Factorial[r],mod-2)
for i in range(0,r)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

ans=0
a=1
while a<=r:
  ans=(ans+comb(r,a)*power(3,r-a)*power(4,min(N,M)-r)*power(2,max(N,M)-min(N,M)))%mod
  a+=2
print(ans)
  
  
        

Measured memory_bytes: 43740
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int Z = sc.nextInt();

		int x = X;
		int y = Y;
		int z = Z;

		X = y;
		Y = x;
		X = z;
		Z = y;

		System.out.print(X);
		System.out.print(" ");
		System.out.print(Y);
		System.out.print(" ");
		System.out.print(Z);
		
	}
}

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

int main(){
	string s;
	cin >> s;
	int len = s.length();
	
	int count = 0;
	for(int i=0;i<len;i++)
		if(s[i]=='o')
			count++;
	if(count>=8)
		cout << "YES" << endl;
	else{
		if((8-count)>15-len)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
	
	
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    struct Node* parent;
    struct Node* left;
    struct Node* right;
    int id;
};

static struct Node* CreateNode(int id) {
    struct Node* p_node = malloc(sizeof(struct Node));

    p_node->parent = p_node->left = p_node->right = NULL;
    p_node->id = id;

    return p_node;
}

static void DestroyNode(struct Node* p_node) {
    free(p_node);

    return;
}

static int FindRoot(const int pre[], int n, const int in[], int l, int r) {
    int i, j;

    for ( i = 0; i < n; i++ ) {
        for ( j = l; j < r; j++ ) {
            if ( pre[i] == in[j] ) {
                return pre[i];
            }
        }
    }
    
    return -1;
}

static int GetRootPos(int root, const int in[], int s, int e) {
    int i;
    
    for ( i = s; i < e; i++ ) {
        if ( in[i] == root ) {
            return i;
        }
    }
    assert( 0 );
    
    return -1;
}

static struct Node* Reconstruction(struct Node* p_parent, const int pre[], int n, const int in[], int l, int r) {
    int root;
    int in_index;
    struct Node* p_root;
    
    if ( l >= r ) {
        return NULL;
    }

    root = FindRoot(pre, n, in, l, r);
    in_index = GetRootPos(root, in, l, r);
    
    p_root = CreateNode(root);
    p_root->parent = p_parent;

    p_root->left = Reconstruction(p_root, pre, n, in, l, in_index);
    p_root->right = Reconstruction(p_root, pre, n, in, in_index + 1, r);

    return p_root;
}

static void PrintPostorder(const struct Node* p_root) {

    if ( p_root == NULL ){
        return;
    }

    PrintPostorder(p_root->left);
    PrintPostorder(p_root->right);
    printf("%d", p_root->id);

    if ( p_root->parent ) {
        printf(" ");
    }

    return;
}

static void DestroyTree(struct Node *p_root) {
    if ( !p_root ) {
        return;
    }

    DestroyTree(p_root->left);
    DestroyTree(p_root->right);
    DestroyNode(p_root);

    return;
}

int main(void) {
    int n;
    int i;
    int *pre, *in;
    struct Node* p_root;

    scanf("%d\n", &n);
    pre = malloc(sizeof(int) * n);
    in  = malloc(sizeof(int) * n);

    for ( i = 0; i < n; i++ ) {
        int d;
        scanf("%d", &d);
        pre[i] = d;
    }
    for ( i = 0; i < n; i++ ) {
        int d;
        scanf("%d", &d);
        in[i] = d;
    }

    p_root = Reconstruction(NULL, pre, n, in, 0, n);

    PrintPostorder(p_root);
    printf("\n");

    DestroyTree(p_root);
    free(pre);
    free(in);    

    return 0;
}
            
        



Measured memory_bytes: 2100
def exec(input)
  stack = []

  input.split.each do |i|
    case i
    when ?+
      lhs, rhs = stack.slice!(-2..-1)
      stack << lhs + rhs
    when ?-
      lhs, rhs = stack.slice!(-2..-1)
      stack << lhs - rhs
    when ?/
      lhs, rhs = stack.slice!(-2..-1)
      stack << lhs / rhs
    when ?*
      lhs, rhs = stack.slice!(-2..-1)
      stack << lhs * rhs
    else
      stack << i.to_i
    end
  end

  stack[-1]
end

p exec(gets)



Measured memory_bytes: 8876
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   def Find_Root(self, x):
       if(self.root[x] < 0):
           return x
       else:
           # ここで代入しておくことで、後の繰り返しを避ける
           self.root[x] = self.Find_Root(self.root[x])
           return self.root[x]
   # 木の併合、入力は併合したい各ノード
   def Unite(self, x, y):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]

n,m,k=map(int,input().split())
f=[set() for i in range(n)]
h=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    f[a].add(b)
    f[b].add(a)
    h.Unite(a,b)
ans=[h.Count(i)-len(f[i])-1 for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    if h.isSameGroup(a,b):
        ans[a]-=1
        ans[b]-=1
print(*ans)


Measured memory_bytes: 44932
n = int(input())
A = list(map(int, input().split()))
q = int(input())

from sys import stdin
input = stdin.readline

cnt = [0]*(10**5 + 1)
total = 0
for i in range(n):
  cnt[A[i]] += 1
  total += A[i]
  
for i in range(q):
  b,c = map(int, input().split())
  cnt[c] += cnt[b]
  total -= cnt[b]*b
  total += cnt[b]*c
  cnt[b] = 0
  print(total)
  

Measured memory_bytes: 84336
#include <iostream>
using namespace std;
int main(){
	int cras;
	for(int i = 0; i < 10000; i++){
		cin >> cras;
		if(cras){
			cout << "Case " << i+1 << ": " << cras << endl;
		}else{
			break;
		}
	}
	return 0;
}



Measured memory_bytes: 3016
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));

            return;
        }

        public void Solve(ConsoleInput cin)
        {
            var s = cin.Read;
            var c = s.ToCharArray();

            for (int i = 0; i < s.Length; i = i + 2)
            {
                Write(s[i]);
            }
            Write("\n");

        }
    }

    public static class Extensions
    {
        public static string Reverse(this string sourse)
        {
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

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

using namespace std;

int main(){
  int N,M;cin>>N>>M;
  vector<int> city(60,0);
  int a,b;
  for(int i=0; i<M;i++){
    cin>>a>>b;
    city[a-1]++;
    city[b-1]++;
  }
  
  for(int i =0 ;i < N;i++){
    cout<<city[i]<<endl;
  }
}

Measured memory_bytes: 256
// I need some holiday
// But I don't wish that everyday is holiday
// Because I didn't bear the pain
// Because it wasn't a true freedom
//         ——『イヤホンと蝉時雨』·Orangestar

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair<int, int> pii;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define MP make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline int chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline int chkmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> inline T sqr(const T &val) { return val * val; }

namespace fastIO
{
	const int MAX_BUFFER_SIZE = 1 << 16;

	char buffer[MAX_BUFFER_SIZE], *cur = buffer, *ed = buffer;

	inline char getc() { return cur == ed && (ed = (cur = buffer) + fread(buffer, 1, MAX_BUFFER_SIZE, stdin), cur == ed) ? EOF : *cur++; }
}
using fastIO::getc;

template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getc());
	for(; !isdigit(ch); ch = getc()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

inline char *read_str(char *s)
{
	register char ch(getc());
	while(!isgraph(ch)) ch = getc();
	for(; isgraph(ch); ch = getc()) *s++ = ch;
	*s = '\0';
	return s;
}

// END tpl.

const int MAXN = (int) 1e5;

int n, m;

vector<pii> adj[MAXN + 5];

inline void input()
{
	n = read<int>(), m = read<int>();
	for(int i = 1; i <= m; ++i)
	{
		int u = read<int>(), v = read<int>();
		adj[u].emplace_back(v, +1);
		adj[v].emplace_back(u, -1);
	}
}

int vis[MAXN + 5];
vector<int> V;
int E;

inline void dfs(int u, int d)
{
	V.push_back(u), E += SZ(adj[u]);
	vis[u] = d;
	for(auto it : adj[u])
	{
		int v = it.fst;
		if(vis[v] == -1) dfs(v, (d + it.snd + 3) % 3);
	}
}

inline int check()
{
	for(auto u : V) for(auto it : adj[u])
	{
		int v = it.fst;
		if(vis[v] != (vis[u] + it.snd + 3) % 3) return 0;
	}
	return 1;
}

inline void solve()
{
	memset(vis, -1, sizeof vis);
	LL ans = 0;
	for(int i = 1; i <= n; ++i) if(vis[i] == -1)
	{
		V.clear(), E = 0, dfs(i, 0), E /= 2;

		if(!check()) ans += (LL) SZ(V) * SZ(V);
		else
		{
			int mx = 0, cnt[3] = {0, 0, 0};
			for(auto j : V) chkmax(mx, vis[j]), ++cnt[vis[j]];
			if(cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) for(int j = 0; j < 3; ++j) ans += (LL) cnt[j] * cnt[(j + 1) % 3];
			else ans += E;
		}
	}
	printf("%lld\n", ans);
}

int main()
{
#ifdef K_ON
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	input();
	solve();

	return 0;
}




Measured memory_bytes: 9336
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int (i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int (i) = (int)(initial); (i) < (int)(n); ++(i))
#define repeat(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int (i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int (i) = (int)(initial); (i) > (int)(n); (i)--)
#define repeat_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define variable
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;
const double EPS = numeric_limits<double>::epsilon();
// 最大公約数
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n) {
	vector< pair<ll, ll> > p;
	for(ll i = 2; i*i <= n; i++) {
		if ((n % i) != 0) continue;
		p.push_back(make_pair(i, 0));
		while((n % i) == 0) {
			n /= i;
			p[i].second += 1;
		}
		p.push_back(make_pair(n, 0));
	}

	if (n != 1) p.push_back(make_pair(n, 1));
	return p;
}
string alphabet() { return "abcdefghijklmnopqrstuvwxyz"; }

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

	ll result = 0;
	for(int i = 1; i <= K; i++) {
		for(int j = 1; j <= K; j++) {
			for(int k = 1; k <= K; k++) {
				int n1 = gcd(i, j);
				int n2 = gcd(n1, k);
				result += n2;
			}
		}
	}

	cout << result << endl;
	return 0;
}

Measured memory_bytes: 3628
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")

count = 0


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    A = [[0]*N for _ in range(N)]

    def dfs(curr, visited):
        global count
        visited[curr] = True
        if all(visited):
            count += 1
            return

        for t in edges[curr]:
            if visited[t] == False:
                dfs(t, visited[:])
        return

    edges = defaultdict(list)
    for aa, bb in zip(a, b):
        edges[aa-1].append(bb-1)
        edges[bb-1].append(aa-1)
    dfs(0, [False]*N)
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>;
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int cnt;
int n;
int p[20];


bool judge(int x, int y, int z) {
	if (x > z)swap(x, z);
	if (y > x && z > y)return true;
	return false;
}

int main() {

	cin >> n;
	rep(i, n)cin >> p[i];

	REP(i, 1, n - 1) {
		if (judge(p[i - 1],p[i],p[i + 1]))cnt++;
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

main()
{
	int n;
	int i;
	int S[13]={};
	int H[13]={};
	int C[13]={};
	int D[13]={};
	
	scanf("%d",&n);
	
	char m;
	int num;
	
	for(i=0;i<n;i++){
		scanf(" %c %d",&m,&num);
		if(m == 'S'){
			S[num-1]=1;
		} else if(m == 'H'){
			H[num-1]=1;
		} else if(m == 'C'){
			C[num-1]=1;
		} else if(m == 'D'){
			D[num-1]=1;
		}
	}
	
	for(i=0;i<13;i++){
		if(S[i]==0){
			printf("S %d\n",i+1);
		}
	}
	
	for(i=0;i<13;i++){
		if(H[i]==0){
			printf("H %d\n",i+1);
		}
	}
	
	for(i=0;i<13;i++){
		if(C[i]==0){
			printf("C %d\n",i+1);
		}
	}
	
	for(i=0;i<13;i++){
		if(D[i]==0){
			printf("D %d\n",i+1);
		}
	}
	
	return 0;
}
	

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

using namespace std;

int main() {
	
	string s1;
	string s2("CODEFESTIVAL2016");
	int ans = 0; 
	cin >> s1;
	for (int i = 0; i < 16; ++i) {
		if (s1[i] != s2[i]) {
			++ans;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  set<int> A;
  A.insert(a);
  A.insert(b);
  A.insert(c);
  if (A.size() == 2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

class RangeSumQuery {
private:
	vector<int> num;
	vector<int> st;
	vector<int> rangeSum;
public:
	RangeSumQuery(vector<int> v) {
		num = v;
		double root = sqrt(num.size());

		double cnt = 0;
		for (int i = 0; i < root; i++, cnt += root) {
			st.push_back((int)floor(cnt));
		}
		st.push_back(num.size() + 1);

		for (int i = 0; i < st.size() - 1; i++) {
			int now = st[i];
			int next = st[i + 1];
			int sum = 0;
			for (int j = now; j < next; j++) {
				sum += num[j];
			}
			rangeSum.push_back(sum);
		}
	}

	void add(int x, int y) {
		num[x] += y;
		
		int low = 0;
		int high = st.size() - 1;
		int mid = (high + low) / 2;
		while (high - low > 1) {
			if (x < st[mid]) {
				high = mid;
			} else {
				low = mid;
			}
			mid = (high + low) / 2;
		}

		rangeSum[mid] += y;
	}

	int getSum(int s, int t) {
		int sum = 0;
		for (int i = 0; i < st.size() - 1; i++) {
			int now = st[i];
			int next = st[i + 1];

			if (next <= s) continue;

			if (t < now) break;

			if (s <= now && next <= t) {
				sum += rangeSum[i];
				continue;
			}

			int a = max(now, s);
			int b = min(next - 1, t);
			for (int j = a; j <= b; j++) {
				sum += num[j];
			}
		}

		return sum;
	}
};

signed main() {
	int n, q;
	cin >> n >> q;

	auto rsq = RangeSumQuery(vector<int>(n, 0));

	rep(i, q) {
		int com, x, y;
		cin >> com >> x >> y;

		if (com == 0) {
			x--;
			rsq.add(x, y);
		} else {
			x--; y--;
			cout << rsq.getSum(x, y) << endl;
		}
	}

    return 0;
}

Measured memory_bytes: 4464
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct UnionFind{
  int n,num;
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int sz):n(sz),num(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
    num--;
  }
  int size(int x){
    return r[find(x)];
  }
  int count() const{
    return num;
  }
};
//END CUT HERE

struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE

signed DSL_1_A(){
  int n,q;
  cin>>n>>q;
  UnionFind uf(n);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c) cout<<uf.same(x,y)<<"\n";
    else uf.unite(x,y);
  }
  cout<<flush;
  return 0;
}
/*
  verified on 2019/03/03
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp
*/

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

  UnionFind uf(n);
  vector<Int> ans(m+1,0);
  ans[m]=(Int)n*(n-1)/2;
  for(int i=m-1;i>=0;i--){
    a[i]--;b[i]--;
    ans[i]=ans[i+1];
    if(uf.same(a[i],b[i])) continue;
    
    Int x=uf.size(a[i]),y=uf.size(b[i]);
    ans[i]-=x*y;
    
    uf.unite(a[i],b[i]);
  }
  ans.erase(ans.begin());
  for(Int x:ans) cout<<x<<"\n";
  cout<<flush;
  return 0;
}

/*
  verified on 2019/03/03
  https://atcoder.jp/contests/abc120/tasks/abc120_d
*/

signed ABC126_E(){
  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--;
    z%=2;    
    uf.unite(x,y);
  }
  cout<<uf.count()<<endl;
  return 0;
}
/*
  verified on 2019/05/19
  https://atcoder.jp/contests/abc120/tasks/abc126_E
*/


signed main(){
  //DSL_1_A();
  //ABC120_D();
  ABC126_E();
  return 0; 
}


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

namespace B
{
	class Program
	{
		static void Main()
		{
			var line1 = Console.ReadLine();
			var line2 = Console.ReadLine();

			var N = Int32.Parse(line1);
			
			var splited = line2.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
			var L = new List<int>();
			foreach (var token in splited) {
				L.Add(Int32.Parse(token));
			}

			if (L.Max() < L.Sum() - L.Max()) {
				Console.WriteLine("Yes");
			} else {
				Console.WriteLine("No");
			}
		}
	}
}

Measured memory_bytes: 13268
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

const int INF = 1 << 29;

int N, M;

vector<int> g[202020];

int main() {
    cin >> N >> M;
    for (int j = 0; j < M; ++j) {
        int a, b;
        cin >> a >> b; --a; --b;
        g[a].push_back(b);
    }

    int dist[202020];
    fill(dist, dist+N, INF);

    dist[0] = 0;
    for (int v : g[0]) {
        dist[v] = 1;
    }
    for (int j = 0; j < N; ++j) {
        if (dist[j] == 1) {
            for (int v : g[j]) {
                dist[v] = min(dist[v], 2);
            }
        }
    }

    cout << (dist[N-1] == 2 ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return 0;
}


Measured memory_bytes: 9344
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
		long a = long.Parse(input[0]);
		long b = long.Parse(input[1]);
    if(0 < a) Console.WriteLine("Positive");
    else
    {
      if(0 <= b) Console.WriteLine("Zero");
      else
      {
        long c = b-a;
        if(c % 2 == 0) Console.WriteLine("Negative");
        else Console.WriteLine("Positive");
      }
    }

	}
}

Measured memory_bytes: 13140
import java.util.*;

class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      
	  int n = sc.nextInt();
      int d = sc.nextInt();
      int cnt = 0;
      
      while(n > 0){
      	n -= d*2 + 1;
        cnt++;
      }
      
      System.out.println(cnt);
    }
}

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

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b)
{ if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b)
{ if(b < a) { a = b; return true; } else { return false; } }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
ostream& operator<<(ostream &os, const string& s)
{ FOR(v, s) os << *v; return os; }
template<typename T> auto operator<<(ostream& os, const T& t)
    -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }

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

    ll X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    vector<int> pv(A), qv(B);
    REP(i, A) {
        cin >> pv[i];
    }
    REP(i, B) {
        cin >> qv[i];
    }
    priority_queue<int> r;
    REP(i, C) {
        int v;
        cin >> v;
        r.push(v);
    }

    RSORT(pv);
    RSORT(qv);

    priority_queue<int, vector<int>, greater<int>> p, q;
    REP(i, X) {
        p.push(pv[i]);
    }
    REP(i, Y) {
        q.push(qv[i]);
    }

    ll ans = 0;
    while(0 != X || 0 != Y) {
        auto fetch = [&](auto& pq) {
                         if(pq.top() < r.top() && !r.empty()) {
                             ans += r.top();
                             r.pop();
                         }
                         else {
                             ans += pq.top();
                         }
                         pq.pop();
                     };
        if((p.top() < q.top() && 0 != X) || Y == 0) {
            fetch(p);
            X--;
        }
        else {
            fetch(q);
            Y--;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2552
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int32_t main(){
    int k,n,i;
    cin>>k>>n;
    int a[n];
    vector<int>v;
    for(i=0;i<n;i++){
        cin>>a[i];
        if(i!=0){
            v.pb(a[i]-a[i-1]);
        }
    }
    v.pb(k-a[n-1]+a[0]);
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    cout<<k-v[0];
    return 0;
}


Measured memory_bytes: 3572
def ruined_square(x1, y1, x2, y2):
    x = x2
    y = y2
    dx = x2 - x1
    dy = y2 - y1

    dx, dy = -dy, dx
    x += dx
    y += dy
    print("{} {} ".format(x, y), end = "")

    dx, dy = -dy, dx
    x += dx
    y += dy
    print("{} {}".format(x, y))

x1, y1, x2, y2 = map(int, input().split())
ruined_square(x1, y1, x2, y2)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=998244353;
const LL LINF=1LL<<60;
const int INF=1<<30;





int main(){
    int H,W,h,w;cin >> H >> W >> h >> w;
    if(H%h==0&&W%w==0){
        puts("No");
        return 0;
    }
    puts("Yes");
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if(i%h==0&&j%w==0){
                cout << - (int)1e9;
            }
            else{
                cout << (int)(1e9 - 1)/(h*w - 1);
            }
            cout << (j==W?"\n":" ");
        }
    }
    return 0;
}



Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
int dp[3010][6010];
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, T;
    cin >> N >> T;
    vector<pair<int, int> > AB(N);
    for (auto &ab : AB) cin >> ab.first >> ab.second;
    sort(AB.begin(), AB.end());
    for (int i = 0; i < N; ++i) {
        int a = AB[i].first, b = AB[i].second;
        for (int j = 0; j < T+a; ++j) {
            dp[i+1][j] = dp[i][j];
            if (j >= a) dp[i+1][j] = max(dp[i+1][j], dp[i][j-a]+b);
        }
    }
    int ans = 0;
    for (int j = 0; j < T+AB[N-1].first; ++j) {
        ans = max(ans, dp[N][j]);
    }
    printf("%d\n", ans);
    return 0;
}


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

int main() {
    int n, p;
    cin >> n >> p;
    string s;
    cin >> s;
    if (10%p == 0) {
        long long ans = 0;
        rep(r, n) {
            if ((s[r]-'0') % p == 0){
                ans += r+1;
            }
        }
        cout << ans << endl;
        return 0;
    }

    vector<int> d(n+1);
    int ten = 1;
    for (int i = n-1; i >=0; --i){
        int a = (s[i]-'0') * ten % p;
        d[i] = (d[i+1]+a) % p;
        ten *= 10; ten %= p;
    }
    vector<int> cnt(p);
    long long ans = 0;
    for (int i = n; i >= 0; --i){
        ans += cnt[d[i]];
        cnt[d[i]]++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1412
import java.util.*;


public class Main {

    private static final int INF = Integer.MAX_VALUE;

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

        List<Integer> list = new ArrayList<>();
        for(int tmp= 0; tmp < n;tmp++){
            int l = sc.nextInt();
            list.add(l);
        }

        int height = 0;
        int result = 1;
        int i = 0;
        while(height <= x && i < n){
            height += list.get(i);
            if(height <= x){
                result++;
            }
            i++;
        }

        System.out.println(result);
    }
}


Measured memory_bytes: 22996
///
// File:  1295.cpp
// Author: ymiyamoto
//
// Created on Sun Dec 10 10:50:36 2017
//

#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int32_t main()
{
  while (true) {
    uint32_t w, d;
    cin >> w >> d;
    if (w == 0 && d == 0) break;

    vector<uint32_t> front(w);
    for (uint32_t i = 0; i < w; i++) {
      cin >> front[i];
    }
    vector<uint32_t> side(d);
    for (uint32_t i = 0; i < d; i++) {
      cin >> side[i];
    }

    vector<uint32_t> blocks;
    for (uint32_t i = 0; i < front.size(); i++) {
      blocks.push_back(front[i]);
    }

    for (uint32_t s : side) {
      bool found = false;
      for (auto iter = front.begin(); iter < front.end(); iter++) {
        if (*iter == s) {
          front.erase(iter);
          found = true;
          break;
        }
      }
      if (!found) {
        blocks.push_back(s);
      }
    }

    uint32_t sum = 0;
    for (auto v : blocks) {
      sum += v;
    }
    cout << sum << endl;
  }

  return 0;
}

Measured memory_bytes: 3136
/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/

/+---test
axyb
abyxb
---+/
/+---test
aa
xayaz
---+/
/+---test
a
z
---+/
/+---test
abracadabra
avadakedavra
---+/

void main(string[] args) {
  const S = readln.chomp;
  const T = readln.chomp;

  auto dp = new size_t[][](S.length+1, T.length+1);
  foreach (si, s; S) foreach (ti, t; T) {
    size_t p1;
    if (s == t) {
      p1 = dp[si][ti] + 1;
    }
    const p2 = dp[si][ti+1];
    const p3 = dp[si+1][ti];

    dp[si+1][ti+1] = max(p1, p2, p3);
  }

  size_t si = S.length, ti = T.length;
  string ans;
  while (si && ti) {
    if (si && dp[si][ti] == dp[si-1][ti]) {
      --si;
    } else if (ti && dp[si][ti] == dp[si][ti-1]) {
      --ti;
    } else {
      ans ~= S[si-1];
      --si; --ti;
    }
  }
  ans.retro.writeln;
}


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


void solve(std::vector<long long> x, std::vector<long long> y){
    int xd = x[1] - x[0];
    int yd = y[1] - y[0];
    int x3 = x[1] - yd;
    int y3 = y[1] + xd;
    int x4 = x3 - xd;
    int y4 = y3 - yd;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}

int main(){
    std::vector<long long> x(2);
    std::vector<long long> y(2);
    for(int i = 0 ; i < 2 ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
    }
    solve(std::move(x), std::move(y));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll n; cin >> n;
    ll k; cin >> k;
    vector <ll> hs;
    REP(i, n){
        ll h; cin >> h;
        hs.push_back(h);
    }
    vector <ll> dp(n, 1e18);
    dp[0] = 0;
    for(int i=1; i<n; i++){
        for (int j=i-1; (j>=0) && (j>=i-k); j--){
            dp[i] = min(dp[i], abs(hs[i] - hs[j]) + dp[j]);
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1908
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

void main_()
{
    ll N, K;
    cin >> N >> K;
    vector<ll> hs;
    hs.reserve(N);
    copy_n(istream_iterator<ll>(cin), N, back_inserter(hs));

    vector<ll> dp(N, numeric_limits<ll>::max());
    dp[0] = 0;
    for (ll i = 1; i < N; ++i) {
        for (ll j = 1; j <= K && i - j >= 0; ++j) {
            auto c = dp[i - j] + abs(hs[i] - hs[i - j]);
            dp[i] = min(dp[i], c);
        }
    }

    cout << dp[N - 1] << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <tuple>
#include <cstring>
#include <map>
#include <iomanip>
#include <ctime>
#include <complex>
#include <cassert>
#include <climits>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _ << " " <<
#define all(X) (X).begin(), (X).end()
#define len(X) (X).size()
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define Tiii tuple<int, int, int>
#define Tlll tuple<ll, ll, ll>

constexpr ll mod = 1000000007;

ll pw(ll x, ll y, ll mod) {
    if (y == 0) return 1;
    else if (y == 1) return x % mod;
    else if (y % 2 == 0) {
        ll p = pw(x, y / 2, mod);
        return p * p % mod;
    }
    else {
        ll p = pw(x, y / 2, mod);
        return p * p % mod * x % mod;
    }
}

ll dv(ll x, ll y, ll mod) {
    x %= mod;
    y %= mod;
    return x * pw(y, mod - 2, mod) % mod;
}
 
ll comb(ll n, ll r, ll mod) {
    ll v = 1;
    if (n < r || n < 0 || r < 0) return 0;
    for (int i = 1; i <= r; i++) {
        v = v * dv(n - i + 1, i, mod) % mod;
    }
    return v;
}

int main() {
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;

    ll v1 = comb(c1 + r2 + 1, r2, mod), ans = 0;
    ll v2 = comb(c1 + r1, r1 - 1, mod);
    
    for (int i = c1; i <= c2; i++) {
        ans = (ans + v1 - v2 + mod) % mod;
        v1 = v1 * dv(i + r2 + 2, i + 2, mod) % mod;
        v2 = v2 * dv(i + r1 + 1, i + 2, mod) % mod;
    }
    cout << ans << endl;
    


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N; cin >> N;
    string s; cin >> s;

    vector<int> d(N, 0);
    d[0] = (s[0] == '(')? 1:-1;

    for(int i=1; i<N; i++){
        if(s[i] == '(') d[i] = d[i-1]+1;
        else d[i] = d[i-1]-1;
    }

    int x = 100000;
    for(int i=0; i<N; i++) x = min(x, d[i]);

    if(x >= 0){
        for(int i=0; i<d[N-1]; i++) s += ')';
    }
    else{
        for(int i=0; i<-x; i++) s = '('+s;
        for(int i=0; i<d[N-1]-x; i++) s += ')';
    }

    cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define loop(i,x,z) for (int i=x;i<z;i++)
using ll = long long;
int n, A[200002], cnt = 0;
ll k;
bool vis[200002];
int main()
{
	cin >> n >> k;
	if (!k)
	{
		cout << 1;
		return 0;
	}
	loop(i, 1, n+1)
	{
		cin >> A[i];
	}
	int cur = 1;
	while (!vis[cur])
	{
		vis[cur] = 1;
		cur = A[cur];
		cnt++;
		if (cnt == k)
		{
			cout << cur;
			return 0;
		}
	}
	k -= (ll)cnt;
	memset(vis, 0, sizeof(vis));
	cnt = 0;
	while (!vis[cur])
	{
		vis[cur] = 1;
		cur = A[cur];
		cnt++;
	}
	k %= cnt;
	while (k--)
	{
		cur = A[cur];
	}
	cout << cur;
}

Measured memory_bytes: 4584
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll unsigned long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const ll mod = 1e9 + 7;

ll nC2(ll a) 
{
	return (a)*(a-1)/2;
} 
ll nC3(ll a) 
{
 	return (a)*(a-1)*(a-2)/6;
}

int main()
{
	SPEED
	ll n;
	cin >> n;
	string s;
	cin >> s;
	ll nR = 0, nG = 0, nB = 0;
	for (ll i = 0; i < n; ++i)
	{
		if (s[i]=='R')
		{
			nR++;
		}
		else if (s[i]=='G')
		{
			nG++;
		}
		else
		{
			nB++;
		}
	}

	ll result = nC3(n) - nC3(nR) - nC3(nG) - nC3(nB);
	result = result - nC2(nR)*(nB+nG) - nC2(nG)*(nB+nR) - nC2(nB)*(nR+nG);

	for (ll len = 1; len <= n; len++) 
	{
	    for (ll i = 0; i + 2*len < n; i++) 
	    {
		    if (s[i] == s[i + len] || s[i + len] == s[i + 2*len] || s[i] == s[i + 2*len]) 
		    {
		    	continue;
		    }
		    else 
		    	result--;
	    }
  	}

  	cout << result;
	return 0;
}

Measured memory_bytes: 3676
#include<stdio.h>
int main(void){
  int S,h,m,s;
  scanf("%d",&S);

  h=S/3600;
  m=S%3600/60;
  s=S-h*3600-m*60;

  
  
  printf("%d:%d:%d\n",h,m,s);
  return 0;
}

Measured memory_bytes: 592
def bellmanford(s, n, es):
    # 負の経路の検出
    # n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    neg = [False]*n
    d[s] = 0

    for i in range(n):
        for p, q, r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    neg[q] = True
    return d, neg


n, w = map(int, input().split())  # n:頂点数　w:辺の数
es = []

for _ in range(w):
    x, y, z = map(int, input().split())
    es.append([x-1, y-1, -z])

d, neg = bellmanford(0, n, es)
if neg[-1]:
    print("inf")
else:
    print(-d[-1])


Measured memory_bytes: 45528