akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MAXN=100005;
const ll INF=0x3f3f3f3f;

ll n,K,tot;
ll sum[MAXN];
ll f[MAXN],l[MAXN],r[MAXN];
ll num[MAXN*2];

struct node{
    ll val,tag;
    node *ch[2];
    void PushDown(){
        if(!tag) return;
        if(ch[0]) ch[0]->val=ch[0]->tag=tag;
        if(ch[1]) ch[1]->val=ch[1]->tag=tag;
        val=tag;
        tag=0;
    }
}tree[MAXN*4];
node *root,*ncnt;

void Init(){ncnt=&tree[0];}

node *newnode(ll val=0){
    node *p=++ncnt;
    p->val=val,p->tag=0;
    p->ch[0]=p->ch[1]=NULL;
    return p;
}

void Update(node *&rt,ll l,ll r,ll st,ll ed,ll val){
    if(st>ed) return;
    if(!rt) rt=newnode();
    if(st<=l&&r<=ed){
        rt->val=rt->tag=val;
        return;
    }
    if(!rt->ch[0]) rt->ch[0]=newnode();
    if(!rt->ch[1]) rt->ch[1]=newnode();
    rt->PushDown();
    ll mid=(l+r)>>1;
    if(st<=mid) Update(rt->ch[0],l,mid,st,ed,val);
    if(ed>mid) Update(rt->ch[1],mid+1,r,st,ed,val);
}

ll Query(node *rt,ll l,ll r,ll pos){
    if(!rt) return 0;
    if(l==r) return rt->val;
    ll mid=(l+r)>>1;
    if(!rt->ch[0]) rt->ch[0]=newnode();
    if(!rt->ch[1]) rt->ch[1]=newnode();
    rt->PushDown();
    if(pos<=mid) return Query(rt->ch[0],l,mid,pos);
    return Query(rt->ch[1],mid+1,r,pos);
}

ll Ask(ll k){
    ll pos=Query(root,1,tot,k);
    return pos?f[pos]+(num[l[pos]]-num[k]+K)%K:0;
}

int main(){
    Init();
    scanf("%lld%lld",&n,&K);
    for(ll i=1;i<=n;i++){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        sum[i]=sum[i-1]+a;
        if(b==2) l[i]=0,r[i]=K-1;
        else l[i]=(K-2ll*sum[i-1]%K)%K,r[i]=(K-2ll*sum[i]%K)%K;
        if(b==1&&a*2ll>K) return puts("-1"),0;
        num[++tot]=l[i];
        num[++tot]=r[i];
    }
    sort(num+1,num+tot+1);
    tot=unique(num+1,num+tot+1)-num-1;
    for(ll i=1;i<=n;i++){
        l[i]=lower_bound(num+1,num+tot+1,l[i])-num;
        r[i]=lower_bound(num+1,num+tot+1,r[i])-num;
    }
    for(ll i=n;i>=1;i--){
        f[i]=Ask(l[i]);
        if(l[i]>r[i]) Update(root,1,tot,r[i]+1,l[i]-1,i);
        else Update(root,1,tot,1,l[i]-1,i),Update(root,1,tot,r[i]+1,tot,i);
    }
    ll ans=f[1];
    for(ll i=tot;i>0;i--) ans=min(ans,Ask(i));
    printf("%lld\n",ans+2ll*sum[n]);
}


Measured memory_bytes: 13312
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String s = sc.next();
    char[] c1 = s.toCharArray();
    for(int i = 0; i < s.length(); i++) {
      int r = c1[i] - 'A';
      r = (r + n) % 26;
      c1[i] = (char)('A' + r);
    }
    System.out.println(new String(c1));
  }
}

Measured memory_bytes: 22356
from collections import deque

def main():
    H, W = map(int, input().split())
    N = int(input())
    A = list(map(int, input().split()))
    d = deque()
    for i in range(N):
        for a in range(A[i]):
            d.append(i+1)
    C = [[0] * W for _ in range(H)]

    for h in range(H):
        if h % 2 == 0:
            for w in range(W):
                C[h][w] = d.popleft()
        else:
            for w in range(W-1,-1,-1):
                C[h][w] = d.popleft()
    
    for h in range(H):
        print(*C[h])


if __name__ == "__main__":
    main()

Measured memory_bytes: 42864
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a<b?b:a)
#define abs(x) (x<0?(-x):x)
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define RF(i,L,R) for (int i = L; i > R; i--)
#define RFE(i,L,R) for (int i = L; i >= R; i--)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define ll long long
#define INF 2000000000
#define nINF -2000000000
#define MOD 1e9+7
#define PI 3.1415926535897932384626
int main(){
	int n;
	while(~getI(n)) printf("%d\n",n/3);
}


Measured memory_bytes: 256
import random

def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum += c[i]*(d-last_d[i])
        
    return (score - sum)

def main():
    D = int(input())

    c = list(map(int, input().split()))

    s = [list(map(int, input().split())) for i in range(D)]

    #print(c)

    #print(s)

    last_d = [0 for i in range(26)]
    
    ans = []
    
    score = 0
    
    for i in range(D):
        max = 0
        idx = 0
        for j in range(26):
            if max < (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] != 0:
                max = s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2
                idx = j
            elif max == (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] * (i-last_d[j])*(i-last_d[j]+1)/2 > c[idx]* (i-last_d[idx])*(i-last_d[idx]+1)/2 and i-last_d[j]>i-last_d[idx]:
                idx = j
        last_d[idx] = i+1
        score += s[i][j]
        down_score(i+1,c,last_d,score)
        
        ans.append(idx)

    for i in range(D):
        print(ans[i]+1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9800
#include <iostream>
#include <limits>
#include <map>
#include <string>

using namespace std;

int main() {
    map<string, int> dict;
    int n;
    cin >> n;
    for (size_t i = 0; i < n; ++i) {
        string s;
        cin >> s;
        if (dict.count(s)) {
            ++dict[s];
        }
        else {
            dict[s] = 1;
        }
    }
    int m;
    cin >> m;
    for (size_t i = 0; i < m; ++i) {
        string s;
        cin >> s;
        if (dict.count(s)) {
            --dict[s];
        }
        else {
            dict[s] = -1;
        }
    }
    int max_num = numeric_limits<int>::min();
    for(const auto& item : dict) {
        if (item.second > max_num) max_num = item.second;
    }
    cout << ((max_num > 0) ? max_num : 0) << endl;
    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_s()

if '7'in N:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9044
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int a = 0;
    int b = 0;
    int c = 0;
    for(int i = 0;i < s.length();i++){
      char x = s.charAt(i);
      if(x=='a')a++;
      else if(x=='b')b++;
      else c++;
    }
    int max = Math.max(a,Math.max(b,c));
    if(max-a<=1&&max-b<=1&&max-c<=1)System.out.println("YES");
    else System.out.println("NO");
  }
}

Measured memory_bytes: 23852
#include <iostream>
#include <string>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

int main(){
	int a;
	string s;
	cin >> a ;
	cin >> s;
	if(a>=3200){
		cout<<s;
	}else{
		cout<<"red";
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n];
        for (int i = 0 ; i < n ; i++) {
            p[i] = sc.nextInt();
        }
        int count = 0;
        for (int i = 1 ; i < n - 1 ; i++) {
            int a = p[i - 1];
            int b = p[i];
            int c = p[i + 1];
            if ((a < b && b < c) || (c < b && b < a)) {
                count++;
            }
        }
        System.out.println(count);

    }

}

Measured memory_bytes: 23764
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define INT(x) int x; scanf("%d",&x)
#define INPUT(x) scanf("%d",&x)
#define REP1(x,n) for(int x = 0; x < n; x++)
#define REP2(x,s,e) for(int x = s; x <= e; x++)
#define RREP1(x,n) for(int x = n-1; x >= 0; x--)
#define RREP2(x,s,e) for(int x = s; x >= e; x--)
#define BR printf("\n")
#define INF 2000000000

typedef long long ll;

int main(){
    char S[15];
    cin >> S;
    string SS;
    int len = strlen(S);
    REP1(i,4) SS += S[i];
    SS += " ";
    REP1(i,len-4) SS += S[i+4];
    cout << SS << endl;
    return 0;
}

Measured memory_bytes: 256
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors


n = int(input())

ans = 0
for i in range(1, n+1):
    if i % 2 == 1 and len(make_divisors(i)) == 8:
        ans += 1
print(ans)


Measured memory_bytes: 62412
using System;
using System.Linq;
using System.Text;

public class Test
{
	static public void Main( )
	{
		String w = "";
		for( var i=0; i<152; i++ ) {
			w += "#.";
		}

		while( true ) { 
			String[] data = Console.ReadLine().Split( ' ' );
			var H = Int32.Parse( data[0] );
			var W = Int32.Parse( data[1] );
			if( 0 == H && 0 == W ) break;
			
			StringBuilder output = new StringBuilder();
			for( var i=0; i<H; i++ ) {
				output.Append( w.Substring( (i&1), W ) ).Append( "\n" );
			}
			output.Append( "\n" );
			Console.Write( output );
		}
	}
}

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

int main()
{
  int A,B,sum=0;
  cin >> A >> B;
  if(A==1){
    sum=300000;
    if(B==1) sum+=700000;
    else if(B==2) sum+=200000;
    else if(B==3) sum+=100000;
  }
  else if(A==2){
    sum=200000;
    if(B==1) sum+=300000;
    else if(B==2) sum+=200000;
    else if(B==3) sum+=100000;
  }
  else if(A==3){
    sum=100000;
    if(B==1) sum+=300000;
    else if(B==2) sum+=200000;
    else if(B==3) sum+=100000;
  }
  else{
    if(B==1) sum+=300000;
    else if(B==2) sum+=200000;
    else if(B==3) sum+=100000;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
s = input()

c = 0
for i in range(n):
    if s[i] == 'L' and i > 0 and s[i-1] == 'L':
        c += 1
    if s[i] == 'R' and i < n-1 and s[i+1] == 'R':
        c += 1
print(min(c + 2* k, n-1))

Measured memory_bytes: 3316
#include<iostream>
using namespace std;
int main(){
  int ma[100005]={};
  int n;
  cin >> n;
  int i,j,k;
  int a,b;
  for(i=0;i<n;i++){
    cin >> a >> b;
    for(j=a;j<=b;j++) ma[j]++;
  }
  int m=0;
  for(i=0;i<100005;i++){
    //if(i<10)
    //cout << i <<":" << ma[i]<<endl;
    if(i<=ma[i]+1)
      m=max(m,i-1);
  }
  cout << m << endl;
  return 0;
}

Measured memory_bytes: 1560
#include <iostream>
#include <vector>
using namespace std;
//
struct segtree{
	//
	int n;
	vector<long long> dat,laz;
	//
	segtree(int n_){
		init(n_);
	}
	//
	void init(int n_){
		n=1;
		while(n<n_){
			n*=2;
		}
		dat.resize(2*n-1,0);
		laz.resize(2*n-1,0);
	}
	//
	void eval(long long l,long long k){
		if(k*2+1<n*2-1){
			laz[k*2+1]+=laz[k];
			laz[k*2+2]+=laz[k];
		}
		dat[k]+=laz[k]*l;
		laz[k]=0;
	}
	//[a,b)
	long long update(int a,int b,int x,int k=0,int l=0,int r=-1){
		if(r==-1){
			r=n;
		}
		eval(r-l,k);
		if(r<=a||b<=l){
			return dat[k]+laz[k]*(r-l);
		}else if(a<=l&&r<=b){
			return dat[k]+(laz[k]+=x)*(r-l);
		}else{
			eval(r-l,k);
			long long va=update(a,b,x,k*2+1,l,(l+r)/2);
			long long vb=update(a,b,x,k*2+2,(l+r)/2,r);
			return dat[k]=va+vb;
		}
	}
	//[a,b)
	long long query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1){
			r=n;
		}
		eval(r-l,k);
		if(r<=a||b<=l){
			return 0;
		}else if(a<=l&&r<=b){
			return dat[k];
		}else{
			long long va=query(a,b,k*2+1,l,(l+r)/2);
			long long vb=query(a,b,k*2+2,(l+r)/2,r);
			return va+vb;
		}
	}
	//
};
int main(){
	int N,Q;
	cin>>N>>Q;
	segtree seg(N);
	while(Q--){
		int C;
		cin>>C;
		if(C==1){
			int S,T;
			cin>>S>>T;
			S--;T--;
			cout<<seg.query(S,T+1)<<endl;
		}else{
			int S,T,X;
			cin>>S>>T>>X;
			S--;T--;
			seg.update(S,T+1,X);
		}
	}
	return 0;
}


Measured memory_bytes: 7072
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <climits>
#include <cassert>
#include <numeric>
using namespace std;

typedef long long LL;

constexpr char minch = 'A';
constexpr char maxch = 'Z';

struct transition{
	vector<int> to;
	vector<LL> delta;
	void init(int len){
		to.assign(len, 0);
		delta.assign(len, 0);
	}
};

struct solver{
	transition unit;
	transition trs[maxch - minch + 1];
	const char *p;

	transition mul(transition lt, transition rt){
		int len = lt.to.size();
		transition res = unit;
		for(int i = 0; i < len; ++i){
			int x = lt.to[i];
			res.to[i] = rt.to[x];
			res.delta[i] += lt.delta[i] + rt.delta[x];
		}
		return res;
	}

	transition pow(transition x, LL y){
		transition a = unit;
		while(y){
			if(y & 1){ a = mul(a, x); }
			x = mul(x, x);
			y >>= 1;
		}
		return a;
	}

	transition parse(){
		transition res = unit;
		bool empty = true;
		while(1){
			transition nxt;
			if('1' <= *p && *p <= '9'){
				char *endp;
				LL rep = strtoll(p, &endp, 10);
				assert(rep != LLONG_MAX);
				p = endp;

				transition tr;
				if(*p == '('){
					++p;
					tr = parse();
					assert(*p == ')');
					++p;
				}
				else{
					assert(minch <= *p && *p <= maxch);
					tr = trs[*p - minch];
					++p;
				}

				nxt = pow(tr, rep);
			}
			else if(minch <= *p && *p <= maxch){
				nxt = trs[*p - minch];
				++p;
			}
			else{ break; }
			res = mul(res, nxt);
			empty = false;
		}
		assert(!empty);
		return res;
	}

	LL solve(string h, string n){
		int nlen = n.size();
		unit.init(nlen + 1);
		iota(unit.to.begin(), unit.to.end(), 0);
		for(transition &tr : trs){ tr.init(nlen + 1); }

		vector<int> mp(nlen + 1, -1);
		int fail = -1;
		for(int i = 0; i < nlen; ++i){
			while(fail >= 0 && n[fail] != n[i]){
				fail = mp[fail];
			}
			++fail;
			mp[i + 1] = fail;
		}

		for(int i = 0; i <= nlen; ++i){
			if(i > 0){
				for(int j = 0; j <= maxch - minch; ++j){
					trs[j].to[i] = trs[j].to[mp[i]];
				}
			}
			if(i < nlen){
				trs[n[i] - minch].to[i] = i + 1;
			}
			for(int j = 0; j <= maxch - minch; ++j){
				if(trs[j].to[i] == nlen){ trs[j].delta[i] = 1; }
			}
		}

		p = h.c_str();
		transition ret = parse();
		assert(*p == '\0');
		return ret.delta[0];
	}
};

int main(){
	string h, n;
	while(cin >> h >> n){
		LL ans = solver().solve(h, n);
		cout << ans << endl;
	}
}



Measured memory_bytes: 6176
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 102;

int n;
int sum;

int z;
vector<int> a[N];

int main()
{
    cin >> n;
    if (n % 2 == 1)
    {
        a[++z].push_back(n);
        for (int i = 1; i <= n / 2; ++i)
        {
            a[++z].push_back(i);
            a[z].push_back(n - i);
        }
    }
    else
    {
        for (int i = 1; i <= n / 2; ++i)
        {
            a[++z].push_back(i);
            a[z].push_back(n - i + 1);
        }
    }
    vector<pair<int, int> > ans;
    for (int i = 1; i <= z; ++i)
    {
        for (int j = i + 1; j <= z; ++j)
        {
            for (int ii = 0; ii < a[i].size(); ++ii)
            {
                for (int jj = 0; jj < a[j].size(); ++jj)
                {
                    ans.push_back(m_p(a[i][ii], a[j][jj]));
                }
            }
        }
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i].first << ' ' << ans[i].second << endl;
    return 0;
}


Measured memory_bytes: 384
# -*- coding: utf-8 -*-
L, R = map(int, input().split(' '))
if R - L >= 2020:
    print(0)
    exit()

ret = float('inf')
for i1 in range(L, R+1):
    for i2 in range(i1+1, R+1):
        ret = min(ret, (i1*i2)%2019)

print(ret)




Measured memory_bytes: 40684
package main
import (
  "fmt"
  "sort"
)
func main() {
  var n,a,b int
  var v []float64
  var ave float64
  fmt.Scan(&n,&a,&b)
  v = make([]float64,n)
  for i:=0;i<n;i++ {
    fmt.Scan(&v[i])
  }
  sort.Sort(sort.Reverse(sort.Float64Slice(v)))
  ave = 0
  for i:=0;i<a;i++ {
    ave += v[i]
  }
  ave /= float64(a)
  fmt.Printf("%.8f\n",ave)
  var x,y int64
  for i:=0;i<n;i++ {
    if v[i] == v[a-1] { x++ }
  }
  if v[0] == v[a-1] {
    for i:=a;i<b+1;i++ {
      y += comb(x,int64(i))
    }
    fmt.Println(y)
  } else {
    for i:=0;i<a;i++ {
      if v[i] == v[a-1] { y++ }
    }
    fmt.Println(comb(x,y))
  }
}
func comb(n int64,k int64) int64 {
  if k > n { return 0 }
  if 2*k > n { return comb(n,n-k) }
  var num,den,g int64 = 1,1,1
  for i:=k;i>0;i-- {
    num *= n-k+i
    den *= i
    g = gcd(num,den)
    num /= g
    den /= g
  }
  return num/den
}
func gcd(x int64,y int64) int64 {
  if x < y { return gcd(y,x) }
  if x%y == 0 { return y }
  return gcd(y,x%y)
}

Measured memory_bytes: 512
from collections import deque
S = deque(input())
Q = int(input())
cnt = 0
for i in range(Q):
  x = list(input().split())
  if(int(x[0]) == 1):
    cnt += 1
  else:
    if((cnt+int(x[1])) % 2 == 1):
      S.appendleft(x[2])
    else:
      S.append(x[2])

S = list(S)
if(cnt % 2 == 1):
  S = S[::-1]
print("".join(S))

Measured memory_bytes: 71640
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            Integer[] a = new Integer[3 * n];
            for (int i = 0; i < 3 * n; i++) {
                a[i] = Integer.parseInt(in.next());
            }
            long ans = 0;

            Arrays.sort(a, Comparator.reverseOrder());

            int pos = 1;
            for (int i = 0; i < n; i++) {
                ans += a[pos];
                pos += 2;
            }

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 66192
from itertools import permutations

a, b, c, d, e = [int(input()) for _ in range(5)]

result = 10 ** 9

p = permutations([a, b, c, d, e])
for case in p:
  t = 0
  for i, dish in enumerate(case):
    if i != 4 and dish % 10 != 0:
      dish += 10 - dish % 10
    t += dish
  
  result = min(result, t)
  
print(result)

Measured memory_bytes: 9124
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100010;
#define clr(x) memset(x,0,sizeof(x))
int alnk[N],blnk[N];
int acnt[N],bcnt[N];
namespace T{
	const int E=N<<1;
	int to[E],bro[E],ahead[N],bhead[N],e=0;
	inline void init(){
		memset(ahead,-1,sizeof(ahead));
		memset(bhead,-1,sizeof(bhead));
	}
	inline void ae(int u,int v,int head[]){
		to[e]=v,bro[e]=head[u],head[u]=e++;
	}
	int dfs(int x,int head[],int lnk[],int cnt[]){
		int u=cnt[x]&1?0:x;
		for(int i=head[x];~i;i=bro[i]){
			int v=dfs(to[i],head,lnk,cnt);
			u=u?lnk[u]=v,lnk[v]=u,0:v;
		}
		assert(u);
		return u;
	}
}
int col[N];
void dfs(int x){
	if(alnk[x]&&col[alnk[x]]==0){
		col[alnk[x]]=-col[x];
		dfs(alnk[x]);
	}
	if(blnk[x]&&col[blnk[x]]==0){
		col[blnk[x]]=-col[x];
		dfs(blnk[x]);
	}
}
int main(){
	int n=ni,art,brt;
	T::init(),clr(alnk),clr(blnk),clr(acnt),clr(bcnt);
	for(int i=1;i<=n;i++){
		int fa=ni;
		if(fa==-1){
			art=i;
		}else{
			acnt[fa]++;
			T::ae(fa,i,T::ahead);
		}
	}
	for(int i=1;i<=n;i++){
		int fa=ni;
		if(fa==-1){
			brt=i;
		}else{
			bcnt[fa]++;
			T::ae(fa,i,T::bhead);
		}
	}
	for(int i=1;i<=n;i++){
		if((acnt[i]&1)!=(bcnt[i]&1)){
			puts("IMPOSSIBLE");
			return 0;
		}
	}
	puts("POSSIBLE");
	T::dfs(art,T::ahead,alnk,acnt);
	T::dfs(brt,T::bhead,blnk,bcnt);
	for(int i=1;i<=n;i++){
		if(!(acnt[i]&1)&&col[i]==0){
			col[i]=1;
			dfs(i);
		}
		printf("%d ",col[i]);
	}
	putchar('\n');
	return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000007
long long  f[1000001];
ll pow(ll a, ll b, ll MOD)
{
 ll x=1,y=a;
 while(b > 0)
 	{
 		if(b%2 == 1)
 	{
 		x=(x*y);
 		if(x>MOD) x%=MOD;
 	}
 	y = (y*y);
 	if(y>MOD) y%=MOD;
 	b /= 2;
 	}
 return x;
}
/* Modular Multiplicative Inverse
 Using Euler's Theorem
 a^(phi(m)) = 1 (mod m)
 a^(-1) = a^(m-2) (mod m) */
ll InverseEuler(ll n, ll MOD)
{
 return pow(n,MOD-2,MOD);
}
ll C(ll n, ll r, ll MOD)
{
 return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}
int main(){
	/*f[0] = 1;
	for(int i = 1 ; i <= 1000000 ; i++)
		f[i] = (f[i-1]*i)%INF;*/
 	//cout << C(5,2,INF) << endl;
 	ll a,b;
 	cin>>a>>b;
 	if((a+b)%3!=0)
    {
        cout<<"0"<<endl;
        return 0;
    }
 	ll A,B;
 	A = (a+b)/3;
 	B = (2*A)-a;
 	if(B>A || B<0)
    {
        cout<<"0"<<endl;
        return 0;
    }
    f[0] = 1;
	for(int i = 1 ; i <= 1000000; i++)
		f[i] = (f[i-1]*i)%INF;
 	cout << C(A,B,INF) << endl;
 	return 0;
}


Measured memory_bytes: 8064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;

const int mod = 1e9 + 7;
const int N = 1e4 + 10;
int spf[N];

void sieve(){
    for (int i = 1; i < N; i += 2)
        spf[i] = i;
    for (int i = 2; i < N; i += 2)
        spf[i] = 2;
    for (int i = 3; i * i < N; i += 2){
        if (spf[i] == i)
            for (int j = i * i; j < N; j += i << 1)
                if (spf[j] == j)
                    spf[j] = i;
    }
}

map<int, int> get_factorization(int n){
    map<int, int> ret;
    while (n != 1){
        ++ret[spf[n]];
        n /= spf[n];
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
    sieve();
    int n;
    cin >> n;
    vector<map<int, int>> prime_factorization(n + 1);
    for (int i = 2; i <= n; ++i){
        prime_factorization[i] = get_factorization(i);
    }
    map<int, int> mp;
    for (int i = 2; i <= n; ++i){
        for (auto &it : prime_factorization[i]){
            mp[it.first] += it.second;
        }
    }
    int ans = 1;
    for (auto &it : mp){
        ans = 1LL * ans * (it.second + 1) % mod;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int a,b,c,d;
string s;
signed main()
{
	cin>>a;
	if(a%100>a/100*5){
		cout<<0;
	}else{
		cout<<1;
	}
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <iostream>
#include <algorithm>
#include <unordered_map> 
using namespace std;

const int maxn = 200000 + 200;

struct US{
	int ki, val;
}a[maxn];
priority_queue<US> q;
int T, n, K[maxn], L[maxn], R[maxn], tot;
long long ans;

bool operator < (US x, US y)
{
	return x.val > y.val;
}

inline bool cmp(US x, US y)
{
	return x.ki < y.ki;
}

inline bool cmp1(US x, US y)
{
	return x.ki > y.ki;
}

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		ans = tot = 0;
		scanf("%d", &n);
		for(int i = 1;i <= n;++i)
			scanf("%d%d%d", &K[i], &L[i], &R[i]);

		for(int i = 1;i <= n;++i)
		{
			if(L[i] >= R[i])
			{
				ans += R[i];
				++tot;
				a[tot].val = L[i] - R[i];
				a[tot].ki = K[i];
			}
		}
		sort(a + 1, a + tot + 1, cmp);
		for(int i = 1;i <= tot;++i)
		{
			q.push(a[i]);
			if(q.size() > a[i].ki)
				q.pop();
		}
		while(!q.empty())
		{
			ans += q.top().val;
			q.pop();
		}

		tot = 0;

		for(int i = 1;i <= n;++i)
		{
			if(L[i] < R[i])
			{
				ans += L[i];
				++tot;
				a[tot].val = R[i] - L[i];
				a[tot].ki = K[i];
			}
		}
		sort(a + 1, a + tot + 1, cmp1);
		for(int i = 1;i <= tot;++i)
		{
			q.push(a[i]);
			if(q.size() > n - a[i].ki)
				q.pop();
		}
		while(!q.empty())
		{
			ans += q.top().val;
			q.pop();
		}

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

	return 0;
}


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

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> X(M), A(M - 1);
    rep(i, M) cin >> X.at(i);
    sort(all(X));
    rep(i, M-1) A.at(i) = X.at(i+1) - X.at(i);
    sort(all(A));
    int ans = 0;
    if(N >= M) cout << 0 << endl;
    else{
        rep(i, M-N) ans += A.at(i);
        cout << ans << endl;
    }
}

Measured memory_bytes: 1024
x, y = map(int,input().split())
#ls = list(map(int,input().split()))
#n = int(input())
#s = input()
#x, y = input().split()

if (x == 1 and y != 1):
  print("Alice")
elif (x != 1 and y == 1):
  print("Bob")
elif x == y:
  print("Draw")
elif x > y:
  print("Alice")
elif y > x:
  print("Bob")

Measured memory_bytes: 3060
import sys

input = sys.stdin.readline
N = int(input())
musics = []
for _ in range(N):
    s, t = input().split()
    musics.append((s.strip(), int(t)))

X = input().strip()
ans = 0
flag = False
for s, t in musics:
    if flag:
        ans += t
    if s == X:
        flag = True

print(ans)

Measured memory_bytes: 9168
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

from itertools import combinations
from functools import reduce
from operator import mul

N = int(input())
p = prime_factorize(N)
ans = len(str(N))
for i in range(1,len(p)//2+1):
    for x in combinations(p,i):
        t1 = reduce(mul,x)
        t2 = N // t1
        ans = min(ans,max(len(str(t1)),len(str(t2))))
print(ans)

Measured memory_bytes: 41820
n,l=map(int,input().split())
aji = []
m = 100000
flg = 0
for i in range(n):
  aji.append((l+i))
  if abs(aji[i]) <= m:
    m = abs(aji[i])
    if aji[i] <= 0:
      flg = 1
    else:
      flg = 0
print(sum(aji)- m if flg==0 else sum(aji) +m)


Measured memory_bytes: 9084
n = int(input())
H = list(map(int, input().split()))
dp = [0] * n
dp[1] = abs(H[1] - H[0])
for i in range(2, n):
    dp[i] = min(dp[i - 2] + abs(H[i - 2] - H[i]), dp[i - 1] + abs(H[i - 1] - H[i]))
print(dp[n - 1])

Measured memory_bytes: 13928
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      String s = sc.next();
      int cnt1 = 0;
      int cnt2 = 0;
      for(int i = 0;i<s.length();i++){
         if(s.charAt(i)=='A'){
            cnt1++;
         }
         if(s.charAt(i)=='B'){
            cnt2++;
         }
      }
      if(cnt1>=1&&cnt2>=1){
          System.out.println("Yes");
       }else{
           System.out.println("No");
       }         
	}
}


Measured memory_bytes: 35536
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int n,m;
  cin >> n >> m;
  vector<int> a(m),b(m);
  vector<vector<int>> c(m);
  rep(i,m){
    cin >> a[i] >> b[i];
    c[i].resize(b[i]);
    rep(j,b[i]) {
      cin >> c[i][j];
      c[i][j]--;
    }
  }

  int inf = 1e+9;
  vector<vector<int>> dp(1<<n);
  rep(i,(1<<n)) dp[i].assign(m+1,inf);

  rep(i,m+1) dp[0][i] = 0;

  rep(i,m){
    rep(S,(1<<n)){
      dp[S][i+1] = min(dp[S][i],dp[S][i+1]);
    }
    rep(S,(1<<n)){
      int temp = S;

      rep(j,b[i]){
	// if(!((S>>c[i][j])&1)){
	//   f = true;
	// }
	temp = temp|(1<<c[i][j]);
      }

      dp[temp][i+1] = min(dp[temp][i+1],min(dp[S][i]+a[i],dp[temp][i]));

    }
  }

  if(dp[(1<<n)-1][m]==inf) cout << -1 << "\n";
  else cout << dp[(1<<n)-1][m] << "\n";

  // rep(i,(1<<n)){
  //   rep(j,m+1){
  //     cout << dp[i][j] << " ";
  //   }
  //   cout  << "\n";
  // }

  // int x = 5;
  // x = x|3;
  // cout << x << "\n";
  
  return 0;
}


Measured memory_bytes: 16512
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<stdio.h>
#include<cmath>
#include<limits>
#include<iomanip>

using namespace std;

template <class T> using V = vector<T>;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

using ll = long long;
using db = long double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
using graph = V<V<int>>;
using pq = priority_queue<ll>;



#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define pb(a) push_back(a);



ll Sum(ll n) {
ll m=0;
  while(n){
    m+=n%10;
    n/=10;
  }
  return m;
}



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


#define comuse Comuse()

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

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


ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}


vll div(ll n){
  vll ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      ret.push_back(i);
      if(i*i!=n){
        ret.push_back(n/i);
      }
    }
  }
  SORT(ret);
  return (ret);
}

ll modpow(ll a,ll n,ll mod){
  ll ans=1;
  while(n>0){
    if(n&1){
      ans=ans*a%mod;
    }

    a=a*a%mod;
    
    n>>=1;
  }

  return ans;
}

void Solve();


const int MAX_N = 131072;
//segment tree 
int NN;
int seg[MAX_N*2-1];
void seguse(){
  for(int i=0;i<2*NN-1;i++){
    seg[i]=INT_MAX;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
//segtreeの葉の先頭の添え字はn-1
void Solve(){
  //vll segtree(524287);
  //ll N=262144;
  ll n,m;
    cin>>n>>m;
  cout<<lcm(n,m)<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <tuple>
using namespace std;

int main(){

    int n, m;
    cin >> n >> m;

    tuple<int, int, int> tp[m];
    for(int i=0; i<m; i++){
        int p, y;
        cin >> p >> y;

        tp[i] = make_tuple(y, p, i);
    }

    sort(tp, tp+m);

    // for(int i=0; i<m; i++){
    //     cout << get<1>(tp[i]) << endl;
    // }

    int cnt[n+1] = {};
    tuple<int, int, int> ans[m];

    for(int i=0; i<m; i++){
        int ptemp = get<1>(tp[i]);
        cnt[ptemp]++;
        ans[i] = make_tuple(get<2>(tp[i]), get<1>(tp[i]), cnt[ptemp]);
    }

    sort(ans, ans+m);

    for(int i=0; i<m; i++){
        cout << setw(6) << setfill('0') << get<1>(ans[i]) << setw(6) << setfill('0') << get<2>(ans[i]) << "\n";
    }

    return 0;
}

Measured memory_bytes: 4224
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


n = iinput()
a = iarr()
b = iarr()

ans = 0
for i in range(n):
    tmp = min(a[i],b[i])
    a[i] -= tmp
    b[i] -= tmp
    ans += tmp
    tmp = min(a[i+1],b[i])
    a[i+1] -= tmp
    ans += tmp
print(ans)



Measured memory_bytes: 30988
fn main(){
    let abc: Vec<usize> = read_vec();
    let a = abc[0];
    let mut b = abc[1];
    let mut c = abc[2];
    let k: usize = read();
    let mut k2 : usize = 0;
    
    while a >= b {
        b *= 2;
        k2 += 1;
    }

    while b >= c {
        c *= 2;
        k2 += 1;
    }

    let ans = if k >= k2 {"Yes"} else {"No"};
    
    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T>() -> T
where T: std::str::FromStr,
      T::Err: std::fmt::Debug
{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    buf.trim().parse().unwrap()
}

#[allow(dead_code)]
fn read_vec<T>() -> Vec<T>
where T: std::str::FromStr,
      T::Err: std::fmt::Debug
{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    buf.split_whitespace().map(|e| e.parse().unwrap()).collect()
}


Measured memory_bytes: 2124
<?php

while (fscanf(STDIN, "%d", $N) && $N) {
  $P = array();
  for ($i = 0; $i < $N; $i++) {
    $tmp = explode(' ', trim(fgets(STDIN)));
    array_shift($tmp);
    $P[] = $tmp;
  }
  $tmp = explode(' ', trim(fgets(STDIN))); 
  array_shift($tmp);
  $L = $tmp;
 
  $id = -1;
  for ($i = 0; $i < count($P); $i++) {
    $flg = true;
    foreach ($L as $v1) {
      $found = false;
      foreach ($P[$i] as $v2) {
        if ($v1 == $v2) {
          $found = true;
          break;
        }
      }
      if (!$found) {
        $flg = false;
        break;
      }
    }
    if ($flg) {
      if ($id != -1) {
        $id = -1;
        break;
      }
      $id = $i + 1;
    }
  }
  
  print $id . "\n";
}

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

typedef long long ll;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const ll MOD = 1e9 + 7 ;
const double PI = 2 * acos(0.0) ;


int main()
{
    ll n, m, flag = 0 ;
    ll arr[3] ;
    arr[0] = 0, arr[1] = 0, arr[2] = 0 ;
    cin >> n >> m ;
    map <ll, ll> mp ;
    while (m--) {
        ll x, y ;
        cin >> x >> y ;
        if (x == 1 and y == 0 and n > 1)    flag = 1 ;
        else if (arr[x - 1] != 0 and arr[x - 1] != y)  flag = 1 ;
        else {
            arr[x - 1] = y ;
        }
    }
    if (flag)   cout << -1 << endl ;
    else {
        if (n > 1 and arr[0] == 0)  arr[0] = 1 ;
        for (int i = 0; i < n; i++) {
            cout << arr[i] ;
        }
    }

}


Measured memory_bytes: 256
from collections import deque
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]

d = deque()
for i in range(N):
    p = bisect.bisect_left(d, A[i])
    if p==0:
        d.appendleft(A[i])
    else:
        d[p-1] = A[i]
ans = len(d)
print(ans)


Measured memory_bytes: 8188
#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 r;
  cin >> r;
  int ans = r * r;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3536
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

long long gcd(long long a, long long b){
    while(b != 0){
        long long tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

long long lcm(long long a, long long b){
    return a / gcd(a, b) * b;
}

int main()
{
    long long a, b;
    cin >> a >> b;

    long long ans = lcm(a, b);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int a,b; cin>>a >>b;
    if((a+b)%2 == 0) cout << (a+b)/2 << endl;
    else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc085/tasks/abc085_c

N, Y = map(int, input().split())


def calc(n, y):
    for i in range(n + 1):
        rest = y - i * 10000
        for j in range(n - i + 1):
            if rest - (j * 5000) == (n - i - j) * 1000:
                return i, j, n - i - j
    return -1, -1, -1

result = calc(N, Y)
print('%d  %d %d' % (result[0], result[1], result[2]))


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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> flog(n);
    
  
  for (int i = 0; i < n; i++){
    cin >> flog.at(i);
  }
  
  int dp[n], tmp;
  dp[0] = 0;
  dp[1] = abs(flog.at(0)-flog.at(1));
  if (k == 1){
    int sum = 0;
    for (int i = 0; i < (n-1); i++){
      sum += abs(flog.at(i)-flog.at(i+1));
    }
    cout << sum << endl;
  }else {
    if (k > n){
      k = n-1;
    }
    for (int i = 1; i < k; i++){
      tmp = min(dp[i]+abs(flog.at(i+1)-flog.at(i)),dp[i-1]+abs(flog.at(i+1)-flog.at(i-1)));
      for (int j = 2; j <= i; j++){
        tmp = min(dp[i-j]+abs(flog.at(i+1)-flog.at(i-j)),tmp);
      }
      dp[i+1] = tmp;
    }
  	for (int i = k; i < (n-1); i++){
   	  tmp = min(dp[i]+abs(flog.at(i+1)-flog.at(i)),dp[i-1]+abs(flog.at(i+1)-flog.at(i-1)));
      for (int j = 2; j < k; j++){
      	tmp = min(dp[i-j]+abs(flog.at(i+1)-flog.at(i-j)),tmp);
      }
      dp[i+1] = tmp;
    }
    cout << dp[n-1] << endl;
  }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll                    long long int
#define loop(i,a,b)           for(int i=(int)a;i<(int)b;++i)
#define rloop(i,a,b)          for(int i=(int)a;i<=(int)b;++i)
#define loopl(i,a,b)          for(ll i=(ll)a;i<(ll)b;++i)
#define loopr(i,a,b)          for(int i=(int)a;i>=(int)b;--i)
#define count_1(n)            __builtin_popcountll(n)
#define pb                    push_back
#define eb                    emplace_back
#define ab(a)                 (a<0)?(-1*a):a
#define pc                    putchar_unlocked
#define gc                    getchar_unlocked
#define mset(a,b,c)           loop(i,0,b) a[i]=c
#define F                     first
#define S                     second
#define mp                    make_pair
#define clr(x)                x.clear()
#define MOD                   1000000007
#define MAX                   1e9
#define MIN                   -1e9
#define itoc(c)               ((char)(((int)'0')+c))
#define vi                    vector<int>
#define vvi                   vector<vi>
#define pll                   pair<ll,ll>
#define pii                   pair<int,int>
#define all(p)                p.begin(),p.end()
#define mid(s,e)              (s+(e-s)/2)
#define mini                  INT_MIN
#define vloop(i,v)            for(auto i:v)
const int MX=10010896;
const int lmt=3164;
const int N=10000001;
int flag[MX>>6];
#define ifc(i)                (flag[i>>6]&(1<<((i>>1)&31)))
#define isc(i)                (flag[i>>6]|=(1<<((i>>1)&31)))
#define chk(n)                (n==2||(n>2&&(n&1)&&!ifc(n)))
#define sv()                  int t; scanf("%d",&t); while(t--)
using namespace std;
ll extgcd(ll a,ll b,ll& x,ll& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}}
ll modpow(ll a,ll b) {ll res=1;a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
void sieve(){ int i,j,k; for(i=3;i<lmt;i+=2) if(!ifc(i)) for(j=i*i,k=i<<1;j<MX;j+=k) isc(j);}

int n, m, vis[100009], dis[100009];
vi adj[100009];

vi tt(100005);
void init()
{
    memset(vis,0,sizeof(vis));
}
int dfs(int s)
{
    if(vis[s])
        return dis[s];
    vis[s]=1;
    int ret=0;
    for(auto u:adj[s])
        ret=max(ret,dfs(u)+1);
    dis[s]=ret;
    return dis[s];
}

int main()
{
    int n,m;
    cin>>n>>m;
    loop(i,0,m)
    {
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
    }
    int ans=0;
    loop(i,1,n+1)
    {
        if(!vis[i])
        ans=max(ans,dfs(i));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 8960
n,a,b = map(int, input().split())
diff = abs(a-b)
if diff % 2:
  c = n - max(a,b) + (diff + 1) // 2
  d = min(a,b) - 1 + (diff+1) // 2
  print(min(c,d))
else:
  print(diff // 2)

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

int main() {

    int N=0;
    cin >> N;

    string answer = "No";
    for(int i=1; i<10; i++){
        for(int j=1; j<10; j++){
            if(N == i*j){
                answer = "Yes";
                break;
            }
        }
    }

    cout << answer << endl;

}


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

template<typename T> vector<T> tensor(int n, T v){ return vector<T>(n, v); }
template<typename... Ts> auto tensor(int n, Ts... ts) {
    return vector<decltype(tensor(ts...))>(n, tensor(ts...));
}

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

    auto table = tensor<lint>(n, n, -1);

    for(lint i=0; i<n; i++) {
        lint a;
        cin >> a;
        for(lint k=0; k<a; k++) {
            lint x, y;
            cin >> x >> y;
            table[i][--x] = y;
        }
    }

    lint base = 2;
    lint exp = n;
    lint ans = -1e18;
    for(lint poly = 0; poly < pow(base, exp); poly++) {
        lint tmp = poly;
        vector<lint> coef;
        for(lint i=0; i<exp; i++) {
            coef.push_back(tmp % base);
            tmp /= base;
        }

        bool ok = true;
        vector<lint> expected(n, -1);
        for(lint i=0; i<exp; i++) {
            if(coef[i] == 0)  continue;

            for(lint j=0; j<exp; j++) {
                // 発言: table[i][j]
                if(table[i][j] == -1)  continue;

                if(expected[j] == -1) {
                    expected[j] = table[i][j];
                } else if(expected[j] != table[i][j]) {
                    ok = false;
                }
            }
        }

        for(lint i=0; i<exp; i++) {
            if(expected[i] == -1)  continue;
            ok &= (coef[i] == expected[i]);
        }

        lint cand = 0;
        for(lint i=0; i<exp; i++) {
            cand += (coef[i] == 1);
        }
        if(ok) ans = max(ans, cand);
    }

    cout << ans << endl;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ld ans = 0;
  ll N;
  cin >> N;
  rep(i, N){
    string x;
    string u;
    cin >> x >> u;
    if(u=="BTC"){
      ll len = x.size();
      auto pos = x.find(".");
      ll tail = stoi(x.substr(pos+1, len-pos-1));
      ll head = stoi(x.substr(0, pos));
      ans += (tail+head*100000000)*380000.0/100000000.0;
    }else{
      ans += stoi(x);
    }
  }
  cout << ans;
  return 0;
}


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

int main()
{
    string s,t;cin>>s>>t;
    int sum=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=t[i])
            sum++;
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 3928
#include <iostream>
#include <vector>

using namespace std;

#define int long long

signed main()
{
    int N, K;
    cin >> N >> K;
    vector<int> va(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> va[i];
        va[i]--;
    }

    vector<int> loop;
    vector<bool> visited(N, false);
    int loop_start = 0;
    int offset = 0;
    loop.push_back(0);
    int current = 0;
    while (true)
    {
        visited[current] = true;
        int next = va[current];
        if (visited[next])
        {
            loop_start = next;
            break;
        }
        loop.push_back(next);
        current = next;
    }

    for (int x : loop)
    {
        if (x == loop_start)
            break;
        offset++;
    }

    // cout << loop.size() << endl;
    if (K <= offset - 1)
    {
        cout << loop[K] + 1 << endl;
    }
    else
    {
        cout << loop[(K - offset) % (loop.size() - offset) + offset] + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 6900