akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int r;
    cin >> r;
    println(r * r)
    return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,A[100001],B[100001];
	ll Asum[100001]={0},Bsum[100001]={0};
	vpint ABsort;
	scan(N);
	rep(i,N){
		scan(A[i]);scan(B[i]);
		ABsort.push_back(mp(A[i],2*i));
		ABsort.push_back(mp(B[i],2*i+1));
	}
	sort(ABsort.begin(),ABsort.end());
	int type=0;
	ll sum=0;
	rep(i,N){
		type+=ABsort[i].second%2;
		sum+=ABsort[i].first;
	}
	if(type%N==0) prin(sum);
	else{
		int kosu[100001]={0};
		rep(i,N){
			kosu[ABsort[i].second/2]++;
		}
		int flag=1;
		rep(i,N){
			if(kosu[i]==0) flag=0;
		}
		if(flag){
			//printf("sum:%lld\n",sum);
			//rep(i,2*N) printf("%d(%d) ",ABsort[i].first,ABsort[i].second/2);
			ll ans=INFl;
			rep(i,N){
				ans=min(ans,sum-ABsort[i].first+(ABsort[i].second/2==ABsort[N].second/2 ? ABsort[N+1].first : ABsort[N].first));
			}
			prin(ans);
		}
		else prin(sum);
	}
	return 0;
}


Measured memory_bytes: 3056
n=int(input())
L=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int, input().split())
    u-=1
    v-=1
    L[u].append([v,w])
    L[v].append([u,w])
ans=[-1]*n
ans[0]=0
from collections import deque
que=deque([])
que.append(0)
while que:
    v=que.popleft()
    for u, w in L[v]:
        if ans[u]!=-1:
            continue
        ans[u]=(ans[v]+w)%2
        que.append(u)
for a in ans:
    print(a)

Measured memory_bytes: 45396
#include<stdio.h>
#include<iostream>
using namespace std;
long long a,b,c,k,ans;
int main()
{
    cin>>a>>b>>c>>k;
	if(k<a)
	{
		cout<<k;
		return 0;
	}
	else
	{
		if(k<a+b)
		{
			cout<<a;
			return 0;
		}
		else
		{
           ans=k-a-b;
           cout<<a+(-1*ans);
		   return 0;
		}
	}
	return 0;
}

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

int main() {
  string s;
  cin>>s;
  cout<<s[0]<<s.size()-2<<s[s.size()-1]<<endl;
}

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

int main(){

 LL N,D; cin>>N>>D;
 int ans=0;
 rep(i,N){
  LL x,y; cin>>x>>y;
  if(x*x+y*y<=D*D) ans++;
 }
 cout<<ans<<endl;
 
 return 0;
}


Measured memory_bytes: 3596
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N;
        int[] V = new int[20];
        int[] U = new int[20];
        N=sc.nextInt();
        for(int i=0;i<N;i++){
            V[i]=sc.nextInt();
        }
        for(int i=0;i<N;i++){
            U[i]=sc.nextInt();
        }
        int sum=0;
        for(int i=0;i<N;i++){
            if(V[i]-U[i]>0) sum=sum+V[i]-U[i];
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  cout << fixed << setprecision(10);
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i,n) cin >> d.at(i);
  int ans = 0;
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      ans += d.at(i)*d.at(j);
    }
  }
  cout << ans << endl;
}


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

int main() {
  char a;
  cin >> a;
  if(a == 'A'){
    cout << 'T';
  }
  if(a == 'T'){
    cout << 'A';
  }
  if(a == 'G'){
    cout << 'C';
  }
  if(a == 'C'){
    cout << 'G';
  }
  return 0;
}

Measured memory_bytes: 256
from collections import deque

K = int(input())

q = deque([i for i in range(1, 10)])

for _ in range(K):
    x = q.popleft()
    y = x % 10
    if y > 0:
        q.append(10 * x + y - 1)
    q.append(x * 10 + y)
    if y < 9:
        q.append(10 * x + y + 1)

print(x)


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

bool cmp(char a, char b){ 
    return a > b;
}

int main()
{ 
    string s, t;

    cin >> s;
    cin >> t;

    sort(s.begin(), s.end()); 
	sort(t.begin(), t.end(), cmp);

    if (s < t)
       cout << "Yes" << endl; 
	else
       cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m;
int p[maxn],fst[maxn<<1],lst[maxn<<1],to[maxn<<1],e;
int f[maxn],vis[maxn],vist[maxn],cnt;
inline void add(int x,int y){
	to[++e]=y,lst[e]=fst[x],fst[x]=e;
}
inline void bfs(int x){
	queue<int>q;
	q.push(x);
	vis[x]=1;
	f[++cnt]=x;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(register int i=fst[u];i;i=lst[i]){
			int v=to[i];
			if(!vis[v]){
				vis[v]=1;
				f[++cnt]=v;
				q.push(v);
			}
		}
	}
}
inline int work(int x){
	memset(vis,0,sizeof(vis));
	cnt=0;
	bfs(x);
	int ans=0;
//	for(register int i=1;i<=cnt;++i)printf("%d ",f[i]);
//	cout<<endl;
	for(register int i=1;i<=cnt;++i){
		if(vis[p[f[i]]])++ans;
		vist[f[i]]=1;
	}return ans;
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i)scanf("%d",&p[i]);
	for(register int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}int ans=0;
	for(register int i=1;i<=n;++i){
		if(vist[i])continue;
		ans+=work(i);
	}printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 3712
n, m = map(int, input().split())
a = [1]*n
ans_box = [False]*n
ans_box[0] = True
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    a[x] -= 1
    a[y] += 1
    if ans_box[x]:
        if a[x] == 0:
            ans_box[x] = False
        ans_box[y] = True
print(ans_box.count(True))






Measured memory_bytes: 10336
#bottom-up query
class SegmentTree():
    def __init__(self, num, segfunc, ide_ele):
        length = 2 ** (num-1).bit_length()
        self.n = num
        self.func = segfunc
        self.seg = [ide_ele] * 2 * length
        self.ide_ele = ide_ele
    
    def update(self, index, target):
        index += self.n - 1
        self.seg[index] = target
        while (index > 0):
            index = (index - 1) // 2
            self.seg[index] = self.func(self.seg[index*2 + 1], self.seg[index*2 + 2])
    
    # [l, r)
    def quary(self, l, r):
        l += self.n - 1
        r += self.n - 1
        res = self.ide_ele
        while l < r :
            if l & 1 == 0:
                res = self.func(res, self.seg[l])
            if r & 1 == 0:
                res = self.func(res, self.seg[r-1])
            l = l // 2
            r = (r-1) // 2
        return res

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    anss = []
    ide_ele = 10 ** 9
    segs = [SegmentTree(N, min, ide_ele) for i in range(26)]
    for index, c in enumerate(S):
        segs[ord(c) - ord('a')].update(index, index)
    
    for _ in range(Q):
        query = input().split()
        if query[0] == "1":
            index = int(query[1]) - 1
            target = query[2]
            if S[index] == target:
                continue
            else:
                segs[ord(S[index])-ord('a')].update(index, ide_ele)
                S[index] = target
                segs[ord(target)-ord('a')].update(index, index)
        else:
            l, r = map(int, query[1:])
            l-= 1; r-= 1
            ans = 0
            for i in range(26):
                if segs[i].quary(l, r+1) <= r:
                    ans += 1
            anss.append(ans)
    print(*anss, sep="\n")

if __name__ == "__main__":
    main()


Measured memory_bytes: 290088
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

const string YES = "Yes";
const string NO = "No";

void solve(long long N){
  for (int i=1;i<=9;i++){
    for (int j=1;j<=9;j++){
      if (i*j==N){
	cout<<"Yes"<<endl;
	return;
      }
    }
  }
  cout<<"No"<<endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  solve(N);
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int i, N, M, L, R, count=0, max_L, min_R;
  
  scanf("%d %d", &N, &M);
  scanf("%d %d", &L, &R);

  max_L = L;
  min_R = R;
  for (i = 0; i < M-1; i++){
	  scanf("%d %d", &L, &R);
	  if (L>max_L)
		  max_L=L;
	  if (R<min_R)
		  min_R=R;
  }
  count = min_R - max_L+1;
  if (count < 0)
	  count = 0;
  printf("%d\n", count);

}
    

Measured memory_bytes: 128
n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for _ in range(m):
    b, c = map(int, input().split())
    bc.append((b, c))

a = sorted(a)
bc = sorted(bc, key = lambda x: x[1], reverse = True)
i_bc = 0
for i, aa in enumerate(a):
    b, c = bc[i_bc]
    if aa < c:
        a[i] = c
        b -= 1
        bc[i_bc] = (b, c)
        if b == 0:
            i_bc += 1
    if i_bc >= m:
        break
print(sum(a))


Measured memory_bytes: 23272
using System;
using System.Collections.Generic;

namespace abc148_d
{
  class Program
  {
    static void Main(string[] args)
    {
      var n = CIn.ReadInt();
      var a = CIn.ReadIntArray(n);

      var ans = 0;
      var current = 1;

      for (var i = 0; i < n; i++)
      {
        if (a[i] == current)
        {
          current++;
        }
        else
        {
          ans++;
        }
      }

      Console.WriteLine(ans == n ? -1 : ans);
    }
  }

  class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(long n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(long n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(long n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(long n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }
  }
}

Measured memory_bytes: 35036
import java.util.*;

public class Main{  

    public static void main(String args[]){    
        Scanner console = new Scanner(System.in);
        int N = console.nextInt();
        int M = console.nextInt();
        if(N == M){
         System.out.println("Yes");
        }else{
         System.out.println("No");
        }
    }
       
}

Measured memory_bytes: 22740
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n, m;
	cin >> n >> m;
	
	vector<int> L(m), R(m);
	for(int i = 0; i < m; ++i) {
		cin >> L[i] >> R[i];
		L[i]--;
		R[i]--;
	}
	
	int maxL = *max_element(L.begin(), L.end());
	int minR = *min_element(R.begin(), R.end());
	
	int ans = 0;
	for(int i = 0; i < n; ++i) {
		if( i >= maxL && i <= minR ) ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1024
//Reference : https://atcoder.jp/contests/abc168/submissions/13354853
#include<bits/stdc++.h>
//macros
using namespace std;
typedef long long ll;
typedef pair<int, int > Pii;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef vector<ll> Vll;
#define pb push_back
#define rs resize 
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repll(i, a, b) for(ll i=(a); i<(b); i++)
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define COUT(a) cout << a << endl
#define ALL(a) (a).begin(),(a).end()
const long long int mod = 1e9 + 7;
const long long int INF = 1001001001;
vector<int> to[200001];

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false); 
    ll N,M;
    cin >> N >> M;
    rep(i,0,M){
        int A, B;
        cin >> A >> B;
        A--; B--;
        to[A].pb(B); to[B].pb(A);
    }
    queue<int> q;
    vector<int> dist(N,INF);
    vector<int> pre(N,-1);
    dist[0]=0; q.push(0);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u : to[v]){
            if(dist[u] != INF) continue;
            q.push(u);
            dist[u] = dist[v] + 1;
            pre[u] = v;
        }
    }
    COUT("Yes");
    rep(i,0,N){
        if(i == 0) continue;
        int ans = pre[i];
        ans++;
        COUT(ans); 
    }
    return 0;
}


Measured memory_bytes: 13016
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
int a[N];
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	int n; cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	int mx=0;
	int cnt=0;
	for(int i=1; i<=n; i++) {
		while(i+1<=n&&a[i+1]<=a[i]) {
			i++;
			cnt++;
		}
		mx=max(cnt,mx);
		cnt=0;
	}
	mx=max(cnt,mx);

	cout<<mx<<endl;
	return 0;
}


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

int gcd(int m, int n){
  if(n==0)return m;
  return gcd(n,m%n);
}

int main(){
  int W,H,C;
  cin >> W >> H >> C;

  int g=gcd(W,H);
  cout << W/g*H/g*C << endl;

  return 0;
}



Measured memory_bytes: 3084
#include <iostream>
#include <algorithm>

using namespace std;
 
int main(){
    int z;
 
    while(cin >> z,z){
	long long ans = -1,z3 = z*z*z,res=9999999;    
 
	for(long long i = z-1 ; i >= 0 ; i--){
	    for(long long j = z-1 ; j >= 0 ; j--){
		ans = max(ans,i*i*i+j*j*j);
		if(ans <= z3){
		    res = min(res,z3-ans);
		}
		else ans = -1;
	    }
	}
	cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
#define rep(i, l, r) for(register int i = l; i < r; i++)
#define hrp(i, l, r) for(register int i = l; i <= r; i++)
#define rev(i, r, l) for(register int i = r; i >= l; i--)
#ifdef LOCAL
#define D(x) cout<<"D: "<<#x<<'='<<x<<endl;
#define R(x, l) cout<<"R: Array "<<#x<<endl; rep(i, 0, l) cout<<' '<<i<<':'<<*(x+i)<<endl;
#else
#define D(x)
#define R(X, l)
#endif
#define pb push_back
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<typename tn> inline tn next(void);
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v);
inline int _max(int cnt, ...);
inline int _min(int cnt, ...);
signed main(void)
{
	#ifdef LOCAL
//		freopen("C:\\Users\\Joeon\\Desktop\\IN.txt", "r", stdin);
//		freopen("C:\\Users\\Joeon\\Desktop\\OUT.txt", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n = next<int>(), ans = 0;
	hrp(i, 1, n) if(!(i%3 == 0 || i%5 == 0)) ans += i;
	cout<<ans<<endl;
	return 0;
}
template<typename tn> inline tn next(void)
{
	tn k;
	cin>>k;
	return k;
}
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v)
{
	rep(i, 0, v.size()) os<<v[i]<<' ';
	return os;
}
inline int _max(int cnt, ...)
{
	int mx = -1e18;
	va_list l;
	va_start(l, cnt);
	while(cnt--) mx = max(mx, va_arg(l, int));
	va_end(l);
	return mx;
}
inline int _min(int cnt, ...)
{
	int mn = 1e18;
	va_list l;
	va_start(l, cnt);
	while(cnt--) mn = min(mn, va_arg(l, int));
	va_end(l);
	return mn;
}


Measured memory_bytes: 3652
#pragma GCC optimize(2)
#pragma warning(disable:4996)
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include<cstring>
#include <stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include <string>
#include<iomanip>
#include<assert.h>
#define itn int
#define endl "\n"
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
const int maxn = 100 + 6;
const int maxa = 1000 * 1000 * 1000 + 7;
typedef long long ll;
const int mod = 1000 * 1000 * 1000 + 7;
using namespace std;
int t, n, m, T;
int main()
{
#ifdef _DEBUG
	freopen("D:\\input.txt", "r", stdin);
	//	freopen("E:\\output.txt", "w", stdout);
#endif
	std::ios::sync_with_stdio(false); cin.tie(0);	cout.tie(0);
	int n, weight;
	cin >> n;
	cin >> weight;
	vector<ll>w(n);
	vector <ll > v(n);
	for (int i = 0; i < n; i++) {
		cin >> w[i] >> v[i];
	}
	vector<ll>dp(weight+1);
	for (int i = 0; i <n; i++)
		for (int j = weight; j >=0; j--) {
			if (j - w[i] >= 0)
				dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
		}

	cout << dp[weight]<<endl;
	return 0;
}

Measured memory_bytes: 3648
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort(reverse=True)

MOD = 10**9+7

dp = [[0]*(X+1) for i in range(N+1)]
dp[0][X] = 1

for i,a in enumerate(S):
    for j in range(1,X+1):
        if dp[i][j] == 0: continue
        dp[i+1][j] += dp[i][j] * (N-1-i)
        dp[i+1][j] %= MOD
        dp[i+1][j%a] += dp[i][j]
        dp[i+1][j%a] %= MOD

ans = sum(i*a for i,a in enumerate(dp[-1]))
print(ans % MOD)

Measured memory_bytes: 191896
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;

int main(){
    int h, w;
    cin >> h >> w;

    vector<vector<char>> c(h, vector<char>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> c[i][j];
        }
    }

    vector<vector<long long int>> dp(h, vector<long long int>(w));
    dp[0][0] = 1;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(c[i][j] == '.'){
                if(i >= 1) dp[i][j] += dp[i-1][j];
                if(j >= 1) dp[i][j] += dp[i][j-1];
            }
            dp[i][j] %= MOD;
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}

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

int main() {
    int h[2], m[2];
    int k;

    cin >> h[0] >> m[0] >> h[1] >> m[1] >> k;

    int tot = (h[1] - h[0]) * 60;

    if (m[0] <= m[1]) {
        tot += m[1] - m[0];
    } else {
        tot -= 60;
        tot += (60 - m[0]) + m[1];
    }

    cout << tot - k;

    return 0;
}


Measured memory_bytes: 3620
def test(n,t,x,y):
	for i in range(n-1):
		t1=abs(x[i+1]-x[i])+abs(y[i+1]-y[i])
		t2=t[i+1]-t[i]
		if (t1>t2 or (t2-t1)%2): return 0
	return 1
def main():
	n=int(input())
	n+=1
	t=[0]*n
	x=[0]*n
	y=[0]*n
	for i in range(1,n):
		t[i],x[i],y[i]=map(int,input().split())
	if (test(n,t,x,y)): print("Yes")
	else: print("No")
main()

Measured memory_bytes: 11636
#include<bits/stdc++.h>
#define f(i,n) for(ll i=0;i<n;i++)
#define fe(i,a,b) for(ll i=a;i<=b;i++)
#define ll long long
#define endl "\n"
#define pb push_back
#define mp make_pair
using namespace std;
ll dp[100005];
ll mincost(vector<int>&a, ll n, ll k)
{
	if(dp[n]!=-1)
		return dp[n];
	if(n==1)
		return dp[n]=0;
	if(n<1)
		return INT_MAX;
	dp[n]=INT_MAX;
	for(int i=1;i<=k;i++)
	{
		if(n-i<=0)
			break;
		dp[n]=min(abs(a[n-i-1]-a[n-1])+mincost(a,n-i,k),dp[n]);
	}
	return dp[n];
}
void solve()
{
	memset(dp,-1,sizeof(dp));
	ll n, k;
	cin>>n>>k;
	vector<int>a(n);
	f(i,n)
		cin>>a[i];
	cout<<mincost(a,n,k)<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll t=1;
	// cin>>t;
	while(t--)
		solve();
    return 0;
}


Measured memory_bytes: 12228
#include <stdio.h>

typedef struct {
	int permit;
	char from_addr[12];
	char to_addr[12];
} rule_t;

typedef struct {
	char from_addr[12];
	char to_addr[12];
	char message[52];
	int allowed;
} packet_t;

int rule_num;
rule_t rules[1024];
int packet_num;
packet_t packets[1024];

int is_match(const char* addr,const char* rule) {
	int i;
	for(i=0;i<8;i++) {
		if(rule[i]!='?' && addr[i]!=rule[i])return 0;
	}
	return 1;
}

int main(void) {
	char buffer[8];
	int i,j;
	int allowed_num;
	while(1) {
		scanf("%d%d",&rule_num,&packet_num);
		if(rule_num==0 && packet_num==0)break;
		for(i=0;i<rule_num;i++) {
			scanf("%s%s%s",buffer,rules[i].from_addr,rules[i].to_addr);
			if(buffer[0]=='p')rules[i].permit=1;
			else rules[i].permit=0;
		}
		allowed_num=0;
		for(i=0;i<packet_num;i++) {
			scanf("%s%s%s",packets[i].from_addr,packets[i].to_addr,
				packets[i].message);
			packets[i].allowed=0;
			for(j=0;j<rule_num;j++) {
				if(is_match(packets[i].from_addr,rules[j].from_addr) &&
						is_match(packets[i].to_addr,rules[j].to_addr)) {
					packets[i].allowed=rules[j].permit;
				}
			}
			if(packets[i].allowed)allowed_num++;
		}
		printf("%d\n",allowed_num);
		for(i=0;i<packet_num;i++) {
			if(packets[i].allowed) {
				printf("%s %s %s\n",
					packets[i].from_addr,packets[i].to_addr,
					packets[i].message);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

inline void read(int &T) {
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	T=f?-x:x;
}

long long n,ans;

long long qpow(int a,int b) {
	long long ans=1,base=a;
	while(b) {
		if(b&1) ans*=base;
		base*=base;
		b>>=1;
	}
	return ans;
}

void branch(long long a) {
	for(int i=2;1ll*i*i<=a;++i) {
		int flag=0;
		long long base=qpow(i,flag+1);
		while(a%base==0) {
			a/=base;
			++flag;
			base=qpow(i,flag+1);
			++ans;
		}
		while(a%i==0) a/=i;
	}
	if(a!=1) ++ans;
}

int main() {
	std::cin>>n;
	branch(n);
	std::cout<<ans<<'\n';
	return 0;
}

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

bool isPrime(int n)
{
    if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (int i = 3; i <= sqrtn; i += 2)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int x;
    cin >> x;
    int ans;
    if (x == 2)
        ans = 3;
    else
    {
        while (!isPrime(x))
        {
            x++;
        }
    }
    cout << x << endl;
    return 0;
}

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

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
struct edge{
  int to, d, n;
  edge() {}
  edge(int to, int d, int n) :
    to(to), d(d), n(n) {}
};
struct S{
  int n, p, l;
  S(int n, int p, int l) :
    n(n), p(p), l(l) {}
};
bool operator < (const S& s, const S& t){
  return s.n > t.n;
}
int main(){
  int N, M, L;
  while(cin>>N>>M>>L && N){
    vector<edge> edges[101];
    REP(i, M){
      int A,B,D,E;
      cin>>A>>B>>D>>E;
      A--; B--;
      edges[A].push_back(edge(B, D, E));
      edges[B].push_back(edge(A, D, E));
    }
    priority_queue<S> que;
    que.push(S(0, 0, L));
    int memo[102][102];
    REP(i, N)REP(j, L + 1)memo[i][j] = INF;
    int ans = INF;
    while(!que.empty()){
      S s = que.top(); que.pop();
      if(s.p == N - 1) {
        ans = s.n;
        break;
      }
      if(memo[s.p][s.l] <= s.n) continue;
      memo[s.p][s.l] = s.n;
      REP(i, edges[s.p].size()){
        edge e = edges[s.p][i];
        que.push(S(s.n + e.n, e.to, s.l));
        if(s.l >= e.d) que.push(S(s.n, e.to, s.l - e.d));
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1548
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define deb(x) cout << #x << " is " << x << "\n";

using namespace std;
using namespace __gnu_pbds;

const double PI = 2 * acos(0.0);
const long long INF = 1e18L + 5;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int x, y, z;
	cin >>x >>y >>z;
	vector<int> arr = {x, y, z};
	sort(arr.begin(), arr.end());
	if((arr[0] == arr[1] && arr[1] != arr[2]) || (arr[0] != arr[1] && arr[1] == arr[2])) {
		cout <<"Yes";
	}
	else {
		cout <<"No";
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

//定数
//円周率
const double pi = 3.141592653589793238462643383279;
//天井
const int INF = 1000000000; // = 10^9
const ll LINF = 1000000000000000; // = 10^15
//ABC文字列
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZABC";
const string abc = "abcdefghijklmnopqrstuvwxyzabc";
//よくあるmodくん
const ll MOD = 1000000007; // = 10^9 + 7

//データ構造
//隣接リスト用構造体（有向グラフ向け）
struct edge {
  ll to; // E.toでその辺の終点へアクセスできる
  ll cost; // e.costでその辺の重みにアクセスできる
};
//Union_Find木
struct UnionFind {
  vector<int> UF; // UF.at(i) : iの親の番号
  vector<int> SIZE; // SIZE.at(root(i)) : iと連結されてる要素の数
  UnionFind(int N) : UF(N), SIZE(N, 1) { // 最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) {
      UF.at(i) = i;
    }
  }
  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (UF.at(x) == x) {
      return x;
    }
    return UF.at(x) = root(UF.at(x));
  }
  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); // xの根をrx
    int ry = root(y); // yの根をry
    if (rx == ry) {
      return; // xとyの根が同じ(=同じ木にある)時はそのまま
    }
    // xとyの根が同じでない(=同じ木にない)時：小さい方の根を大きい方の根につける
    if (SIZE.at(rx) < SIZE.at(ry)) {
      UF.at(rx) = ry;
      SIZE.at(ry) += SIZE.at(rx);
      SIZE.at(rx) = 0;
    }
    else {
      UF.at(ry) = rx;
      SIZE.at(rx) += SIZE.at(ry);
      SIZE.at(ry) = 0;
    }
  }
  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
  int size(int x) { // xと連結されてる要素の数を返す
    return SIZE.at(root(x));
  }
};

//関数 (計算量)
//ctoi (O(1))
int ctoi(char c){
  if (c == '0') return 0;
  if (c == '1') return 1;
  if (c == '2') return 2;
  if (c == '3') return 3;
  if (c == '4') return 4;
  if (c == '5') return 5; 
  if (c == '6') return 6;
  if (c == '7') return 7;
  if (c == '8') return 8;
  if (c == '9') return 9;
  return -1;  
}
//to_char (O(1))
char to_char(int i){
  if (i == 0) return '0';
  if (i == 1) return '1';
  if (i == 2) return '2';
  if (i == 3) return '3';
  if (i == 4) return '4';
  if (i == 5) return '5';
  if (i == 6) return '6';
  if (i == 7) return '7';
  if (i == 8) return '8'; 
  if (i == 9) return '9';
  return ' ';  
}
//素数判定 
//一つ一つの判定ではこっちの方が速い(一つ当たりO(√N))
//一方100までに何個あるかなどはEratosthenesの篩の方が良い（O(NlogN))
bool PN(int x) {
  if (x <= 1) return false; // 1や0,-1は素数ではない
  if (x == 2) return true; // √2 + 1 > 2 なので下でやると 2 ％ 2 = 0 となり判定できない
  for (int i = 2; i < sqrt(x) + 1; i++) {
    if (x % i == 0) return false; // 割れたら素数じゃない
  }
  return true;
}
// A^N mod M を計算する。modしたくなかったらM = LINFとかにすればよい。(O(√N))
ll modpow(ll A, ll N, ll M) {
  ll ans = 1;
  while (N > 0) {
    if (N & 1) ans = ans * A % M;
      A = A * A % M;
      N >>= 1;
   }
  return ans;
}
  
//メイン処理
int main() {
  cout << fixed << setprecision(16); //精度向上
  //ここまでテンプレ
  int A, B, C;
  cin >> A >> B >> C;
  if (A == B) {
    cout << C << endl;
  }
  else if (A == C) {
    cout << B << endl;
  }
  else {
    cout << A << endl;
  }
}
    

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

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

class UnionFind{
private:
  vector<ll> Parent; 
 public:
  UnionFind(ll N){
    Parent = vector<ll>(N, -1);
  }
  
  ll root(ll A){
    if(Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }
  
  ll size(ll A){
    return -Parent[root(A)]; 
  }
  
  bool connect(ll A, ll B){
    A = root(A);
    B = root(B);
    if(A == B){
      return false;
    }
    if(size(A) < size(B)) swap(A, B);
    Parent[A] += Parent[B];
    Parent[B] = A;
    return true;
  }
  
  bool isSame(ll A, ll B){
    return root(A) == root(B);
  }
};

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  vpll v(m);
  rep(i,m){
    ll a,b; cin>>a>>b; a--,b--;
    v[i]={a,b};
  }
  reverse(all(v));
  ll sum=n*(n-1)/2;
  vll ans(m);
  ans[0]=sum;
  UnionFind uf(n);
  rep(i,m-1){
    if(!uf.isSame(v[i].first,v[i].second)){
      ans[i+1]=ans[i]-uf.size(v[i].first)*uf.size(v[i].second);
      uf.connect(v[i].first,v[i].second);
    }else ans[i+1]=ans[i];
  }
  rrep(i,m){
    cout<<ans[i]<<endl;
  }
  
}

Measured memory_bytes: 4480
def convert(s): 
  
    # initialization of string to "" 
    new = "" 
  
    # traverse in the string  
    for x in s: 
        new += x  
  
    # return string  
    return new 

h,w,a,b=map(int,input().split())
k=[]
for i in range(a):
  k.append('0')
for i in range(w-a):
  k.append('1')
k=convert(k)
t=[]
for i in range(a):
  t.append('1')
for i in range(w-a):
  t.append('0')
t=convert(t)
for i in range(b):
  print(k)
for i in range(h-b):
  print(t)

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007; // 998244353

#define CLR(a) memset((a), 0, sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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; }

int main(void){
    string S; cin >> S;
    int n[26]; CLR(n);
    for(char c : S){
        n[c-'a']++;
    }

    if(S.size() < 26){
        REP(i,26){
            if(n[i] == 0){
                string ans = S + (char)(i+'a');
                cout << ans << en;
                return 0;
            }
        }
    }
    else{
        RREP(i,26){
            int back = S.back()-'a';
            S.pop_back();
            n[back]--;
            FOR(j,back+1,26){
                if(n[j] == 0){
                    string ans = S + (char)(j+'a');
                    cout << ans << en;
                    return 0;
                }
            }
        }
    }
    cout << -1 << en;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, char const *argv[]) {
  int a, b, c, n;
  n = scanf("%d %d %d", &a, &b, &c);
  if(((a < c) && (c <= b)) || ((b < c) && (c <= a))) {
    printf("Yes");
  } else {
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 128
N = int(input())
A = list(map(int,input().split()))
P = {}
Q = {}
X = {}
for i in range(N):
  p = i+1+A[i]
  q = i+1-A[i]
  if str(p) in P:
    P[str(p)] += 1
  else:
    P[str(p)] = 1
  if str(q) in Q:
    Q[str(q)] += 1
  else:
    Q[str(q)] = 1
  X.setdefault(str(p),i+1+A[i])
  X.setdefault(str(q),i+1-A[i])

#J[a]とI[b]が等しいのが条件
#とりうる値 < 10**9を全て試す
ans = 0

for key in X.keys():
  if (key in P) and (key in Q):
  	ans += P[key] * Q[key]

print(ans)


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	int N = pow(2, n);
	multiset<int> data;
	for (int i = 0; i < N; i++){
		int val;
		cin >> val;
		val = val * -1;
		data.insert(val);
	}
	
	vector<int> v;
	v.push_back(*data.begin());
	data.erase(data.begin());

	for (int i = 1; i <= n; i++) {
		vector<int> newv;
		for (auto it : v) {
			if (data.upper_bound(it) == data.end()) {
				cout << "No" << endl; 
				return 0;
			} 
			newv.push_back(*data.upper_bound(it));
			data.erase(data.upper_bound(it));
		}

		for (auto it : newv) {
			v.push_back(it);
		}
	}

	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 13984
#include <stdio.h>
#include <math.h>

#define PI 3.141592653589793

int main(){
    int a,b,c;
    double s,l,h;
    
    scanf("%d %d %d", &a, &b, &c);
    
    s = sin(c * PI / 180.0)*a*b/2;
    l = a + b + sqrt(a*a + b*b - 2*a*b * cos(c * PI / 180.0));
    h = s/a*2;
    
    printf("%lf %lf %lf\n", s, l, h);
    
    return 0;
}




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

#define ll long long
#define P pair<ll, ll>
#define F first
#define S second

const ll mod = 1000000007LL;
ll n, m;
ll dp[100005];

unordered_map<ll, vector<ll>> G;
void solve() {
  cin >> n >> m;

  unordered_map<ll, ll> inDegree;
  for (ll i = 0; i < m; i++) {
    ll x, y;
    cin >> x >> y;
    G[x].push_back(y);
    inDegree[y]++;
  }

  dp[0] = -10;

  queue<ll> q;
  for (ll i = 1; i <= n; i++) {
    if (inDegree[i] == 0) q.push(i);
  }

  while (!q.empty()) {
    ll u = q.front();
    for (auto v : G[u]) {
      dp[v] = max(dp[v], 1 + dp[u]);
      inDegree[v]--;
      if (inDegree[v] == 0) {
        q.push(v);
      }
    }
    q.pop();
  }

  cout << *max_element(dp, dp + n + 1);
}

int main(int argc, char const *argv[]) {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int T = 1;
  while (T--) {
    solve();
  }

  return 0;
}

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

int main(){
  int t;
  cin >> t;
  vector<ll> ans(t);
  rep(x,t) {
    ll n, k, l, r;
    cin >> n;
    vector<P> plus, minus; 
    rep(i,n) {
      cin >> k >> l >> r;
      ans[x] += r;
      if(l-r > 0) plus.push_back(P(k,l-r));
      else if(l-r < 0 && k < n) {
        ans[x] += l - r;
        minus.push_back(P(n-k,r-l));
      }
      else ans[x] += l-r;
    }
    sort(plus.begin(),plus.end());
    sort(minus.begin(),minus.end());
    priority_queue<ll,vector<ll>,greater<ll>> que;
    for(P p : plus) {
      que.push(p.second);
      while(que.size() > p.first) {
        que.pop();
      }
    }
    while(que.size()) {
      ans[x] += que.top();
      que.pop();
    }
    for(P m : minus) {
      que.push(m.second);
      while(que.size() > m.first) {
        que.pop();
      }
    }
    while(que.size()) {
      ans[x] += que.top();
      que.pop();
    }
  }
  rep(i,t) cout << ans[i] << endl;
  return 0;
}


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

template<typename T>
struct lca {
  int n, root, l;
  vector<vector<int>> to;
  vector<vector<T>> co;//長さ
  vector<int> dep;
  vector<T> costs;
  vector<vector<int>> par;
  lca(int n):n(n),to(n),co(n),dep(n),costs(n) {
    l = 0;
    while ((1<<l) < n) ++l;
    par = vector<vector<int>>(n+1,vector<int>(l,n));
  }
  void addEdge(int a, int b, T c=0) {
    to[a].push_back(b); co[a].push_back(c);
    to[b].push_back(a); co[b].push_back(c);
  }
  void dfs(int v, int d=0, T c=0, int p=-1) {
    if (p != -1) par[v][0] = p;
    dep[v] = d;
    costs[v] = c;
    for (int i = 0; i < to[v].size(); ++i) {
      int u = to[v][i];
      if (u == p) continue;
      dfs(u, d+1, c+co[v][i], v);
    }
  }

  void init(int _root=0) {
    root = _root;
    dfs(root);
    for (int i = 0; i < l-1; ++i) {
      for (int v = 0; v < n; ++v) {
        par[v][i+1] = par[par[v][i]][i];
      }
    }
  }
  // LCA
  int operator()(int a, int b) {
    if (dep[a] > dep[b]) swap(a,b);
    int gap = dep[b]-dep[a];
    for (int i = l-1; i >= 0; --i) {
      int len = 1<<i;
      if (gap >= len) {
        gap -= len;
        b = par[b][i];
      }
    }
    if (a == b) return a;
    for (int i = l-1; i >= 0; --i) {
      int na = par[a][i];
      int nb = par[b][i];
      if (na != nb) a = na, b = nb;
    }
    return par[a][0];
  }
  int length(int a, int b) {
    int c = lca(a,b);
    return dep[a]+dep[b]-dep[c]*2;
  }
  T dist(int a, int b) {
    int c = lca(a,b);
    return costs[a]+costs[b]-costs[c]*2;
  }
};

struct Edge{
  int to, col, len;
  Edge(int x, int y, int z){
    to=x; col=y; len=z;
  }
};

struct query{
  int col, len, s, id;
  query(int qx, int qy, int qu, int qv){
  col=qx; len=qy; s=qu;id=qv;
  }
};

vector<Edge> es[100005];
vector<query> Q[100005];
vector<ll> ans(100005,0);
vector<ll> sumcol(100005,0);
vector<ll> cntcol(100005,0);



void dfs2(ll v, ll p){
  for(auto q:Q[v]){

    ll x=-sumcol[q.col];
    x+=(ll)q.len*cntcol[q.col];
    ans[q.id]+=x*q.s;

  }

  for(auto e:es[v]){
    if(e.to==p)continue;
    sumcol[e.col]+=e.len;
    cntcol[e.col]++;
    dfs2(e.to,v);
    cntcol[e.col]--;
    sumcol[e.col]-=e.len;
  }

}

int main() {
  int n,q;
  cin>>n>>q;
  lca<ll> lc(n);
  rep(i,n-1){
    int a1,b1,c1,d1;
    cin>>a1>>b1>>c1>>d1;
    a1--;b1--;
    es[a1].emplace_back(b1,c1,d1);
    es[b1].emplace_back(a1,c1,d1);
    lc.addEdge(a1,b1,d1);
  }
  lc.init();

  rep(i,q){
    int x1,y1,u1,v1;
    cin>>x1>>y1>>u1>>v1;
    u1--;v1--;
    int anc=lc(u1,v1);
    ans[i]=lc.costs[u1]+lc.costs[v1]-lc.costs[anc]*2;
    Q[u1].emplace_back(x1, y1, 1, i);
    Q[v1].emplace_back(x1, y1, 1, i);
    Q[anc].emplace_back(x1, y1, -2, i);
  }

  dfs2(0,-1);

  rep(i,q){
    cout<<ans[i]<<endl;
  }




}


Measured memory_bytes: 45044
x1,y1,x2,y2 = map(int,input().split())
d1 = x2-x1
d2 = y2-y1
x3 = x2 - d2
y3 = y2 + d1
x4 = x1 - d2
y4 = y1 + d1
print(x3,y3,x4,y4)


Measured memory_bytes: 2940
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF (1LL<<60)
#define MOD1 1000000007

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}/*swap 交換*/
ll max2(ll a,ll b){return a>=b?a:b;}/*2つのうち大きい数を返す*/ 
ll min2(ll a,ll b){return a>=b?b:a;}/*2つのうち小さい数を返す*/ 
ll ABS(ll a){return a>=0?a:(-a);}/*絶対値*/ 
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{
    ll aa;
    ll bb;
}frequent;

int main(void){
    ll a,b,m,ans=0;
    scanf("%lld%lld%lld",&a,&b,&m);
    ll ref[a],mic[b],cou[m],x[m],y[m],sum[m];
    ll refm=INF,micm=INF,summ=INF;
    rep(i,0,a){
        scanf("%lld",&ref[i]);
        refm=min2(refm,ref[i]);
    } 
    rep(i,0,b){
        scanf("%lld",&mic[i]);
        micm=min2(micm,mic[i]);
    }
    ans=refm+micm;
    rep(i,0,m){
        scanf("%lld%lld%lld",&x[i],&y[i],&cou[i]);
        sum[i]=ref[x[i]-1] + mic[y[i]-1] - cou[i];
        summ=min2(summ,sum[i]);
    }
    ans=min2(ans,summ);
    printf("%lld\n",ans);
    return 0;
}


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

int main() {
  int N,M,X=0.;
  cin >> N >> M;
  vector<int>L(M);
  vector<int>R(M);
  for(int i=0; i<M; i++){
    cin >> L[i] >> R[i];
  }
  sort(L.begin(),L.end());
  sort(R.begin(),R.end());
  if(R[0]-L[M-1] >= 0){
    cout << R[0]-L[M-1]+1 << endl;
    return 0;
  }
  cout << 0 << endl;
}


Measured memory_bytes: 3976
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  int n;
  cin>>n;
  
  vector<int> p(n);
  vector<int> pwa(n);
  vector<int> q(n);
  vector<int> qwa(n);
  
  int wa = 0;
  rep(i,n){
  cin>>p[i];
  wa+=p[i];
  pwa[i]=wa;
  }
  
  wa = 0;
  rep(i,n){
  cin>>q[i];
  wa+=q[i];
  qwa[i]=wa;
  }
  
  int ans=p[0]+wa;
  repo(i,n){
  ans=max(ans,pwa[i]+wa-qwa[i-1]);
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 256
/*
 * atcoder/abc130/a.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

int N;
int L[101];

void input() {
  cin >> N;
  int max_ = 0;
  int total = 0;
  loop(n,0,N) {
    cin >> L[n];
    total += L[n];
    chmax(max_, L[n]);
  }
  if (total > 2 * max_) cout << "Yes";
  else cout << "No";
  cout << endl;
}

int main() {
  // cout.precision(15);
  input();
  return 0;
}


Measured memory_bytes: 256
import sys
inputs = sys.stdin.readlines()

from itertools import groupby
S = inputs[0].strip()
K = int(inputs[1])

if len(set(S)) == 1:
    print(len(S)*K // 2)
else:
    counts = [len(list(g)) for k, g in groupby(S)]
    if S[0] != S[-1]:
        t = 0
    else:
        t = 1 if counts[0] % 2 == counts[-1] % 2 == 1 else 0
        counts[0] += counts.pop()
    print(K*sum(map(lambda x: x//2, counts)) - t)

Measured memory_bytes: 3064
#include <stdio.h>
int main(void){
	int a,b,c, i , x,n,y=0;
	scanf("%d %d %d", &a,&b,&c);
	if (a < b){
		n = a;
		a = b;
		b = n;
	}
		
	for (i = a; 1 <= i; i=i-1){
		if (a%i == 0 && b%i == 0){
			x = i;
			y++;
			if (y == c)
				break;
		}
	}
	printf("%d\n", x);
	return 0;
}

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

using ll=long long;
using namespace std;

#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vll(v) sort((v).begin(), (v).end(), greater<long long>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

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;}

const int IINF=(1<<30);
const ll LLINF = 1LL<<60;

char BigAlphaToSmall(char a){
    if (a >= 65 && a <= 90){
        return a + 32;
    }
    return a;
}

char SmallAlphaToBig(char a){
    if (a >= 97 && a <= 122){
        return a - 32;
    }
    return a;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;cin >> n;
    vector<int> hoge(n);
    vector<int> fuga(n);

    rep_i(i,n){
        cin >> hoge[i];
    }

    rep_i(i,n){
        cin >> fuga[i];
    }

    double p1, p2, p3, p;

    rep_i(i, n){
        p1 += abs(hoge[i] - fuga[i]);
    }
    
    rep_i(i, n){
        p2 += pow(abs(hoge[i] - fuga[i]), 2.0);
    }
    p2 = pow(p2, 0.5);


    rep_i(i, n){
        p3 += pow(abs(hoge[i] - fuga[i]), 3.0);
    }
    p3 = pow(p3, 1/3.0);

    p = -1000000;
    rep_i(i, n){
        if(abs(hoge[i] - fuga[i]) >= p){
            p = abs(hoge[i] - fuga[i]);
        }
    }

    cout << fixed << setprecision(10);
    cout << p1 << endl;
    cout << p2 << endl;
    cout << p3 << endl;
    cout << p << endl;
}


Measured memory_bytes: 3448