akhauriyash/Code-Regression huggingface dataset:
a, b, m = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
M = min(A) + min(B)
for i in range(m):
  x, y, c = map(int, input().split())
  x, y = x - 1, y - 1
  M = min(A[x] + B[y] - c, M)
print(M)

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

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int a;

	scanf("%d", &a);

	for (size_t i = 1; i <= 9; i++)
	{
		if (!(a % i) && a / i <= 9)
		{
			printf("Yes");
			return 0;
		}
	}
	printf("No");
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string N;
    cin >> N;
    
    if(N.at(0) == N.at(1) && N.at(1) == N.at(2)){
        cout << "Yes" << endl;
    }else if(N.at(1) == N.at(2) && N.at(2) == N.at(3)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void){
    // Your code here!
    int a,b,k;
    bool flag=true;
    scanf("%d",&k);
    scanf("%d %d",&a,&b);
    for(int i=a;i<=b;i++){
        if(i%k==0){
            flag=false;
            printf("OK");
            break;
        }
    }
    if(flag){
        printf("NG");
    }
}


Measured memory_bytes: 3824
using System;

class Program
{
    static void Main(string[] args)
    {
        int i, j;
        int ii, jj;

        string[] strInput = Console.ReadLine().Split(' ');
        int h = int.Parse(strInput[0]);
        int w = int.Parse(strInput[1]);
        int k = int.Parse(strInput[2]);
        int[,] c = new int[h, w];

        int blkTotal = 0;
        string strInput2 = "";

        num2choice n2c_h = new num2choice(h);
        num2choice n2c_w = new num2choice(w);


        for (i = 0; i < h; i++)
        {
            strInput2 = Console.ReadLine();
            for (j = 0; j < w; j++)
            {
                if(strInput2[j] == '#') {
                    c[i, j] = 1;
                    blkTotal++;
                }
            }
        }

        int result = 0;

        if (k > blkTotal)
        {
            Console.WriteLine(0);
            return;
        }

        int hpat = (int)Math.Pow(2, h);
        int wpat = (int)Math.Pow(2, w);

        int cnt;

        for (i = 0; i < hpat; i++)
        {
            n2c_h.Convert(i);
            for(j = 0; j < wpat; j++)
            {
                n2c_w.Convert(j);

                cnt = 0;
                for(ii = 0; ii < h; ii++)
                {
                    for(jj = 0; jj < w; jj++)
                    {
                        if(n2c_h.choice[ii] != 0 && n2c_w.choice[jj] != 0 && c[ii,jj] == 1)
                        {
                            cnt++;
                        }
                    }
                }
                if(cnt == k)
                {
                    result++;
                }
            }

        }

        Console.WriteLine(result);

        return;
    }


}

class num2choice
{
    public int[] choice;
    public int choiceCnt;   //選択された個数
    private int m_n;

    public num2choice(int n)
    {
        choice = new int[n];
        m_n = n;
    }

    public void Convert(int num)
    {
        int i;
        choiceCnt = 0;

        for (i = 0; i < m_n; i++)
        {
            if ((num & 0x1) != 0)
            {
                choice[i] = 1;
                choiceCnt++;
            }
            else
            {
                choice[i] = 0;
            }
            num = num >> 1;
        }
    }

}

Measured memory_bytes: 27872
#include <bits/stdc++.h>
using namespace std;
vector <int> a;

bool check(int n){
  int S=a.size();
  for(int i=0;i<S;i++){
    int sum=a[i],j=i+1;
    while(j<S&&sum<n)sum=sum*10+a[j++];
    if(sum==n) return 0;
  }
  return 1;
}

int main(){
  int n;
  cin>>n;
  a.resize(n);
  for(int i=0;i<n;i++) cin>>a[i];
  int i=0;
  while(!check(i++));
  cout <<i-1<<endl;
  return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>
#include <string.h>

#define M 1000000
#define L 14

char H[M][L]; /* Hash Table */


int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key) { return key % M; }

int h2(int key) { return 1 + (key % (M - 1)); }

int find(char str[]){
  long long key, i , h;

  key = getKey(str);

  for(i = 0; ; i++){
    h = (h1(key) + i * h2(key)) % M;

    if(strcmp(H[h], str) == 0) return 1;
    else if(strlen(H[h]) == 0) return 0;
  }
}

int insert(char str[]){
  long long key, i, h;

  key = getKey(str);

  for(i = 0; ; i++){
    h = (h1(key) + i * h2(key)) % M;
    if(strcmp(H[h], str) == 0) return 1;
    else if(strlen(H[h]) == 0){
      strcpy(H[h], str);
      return 0;
    }
  }
}


int main(){
    int i, n, h;
    char str[L], com[9];
    
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}





Measured memory_bytes: 15388
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        Set<Integer> ac = new HashSet<>();
        Map<Integer, Integer> wa = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int p = Integer.parseInt(sc.next());
            String s = sc.next();
            if("AC".equals(s)) {
                ac.add(p);
            }else {
                if(!ac.contains(p)) {
                    int w = wa.getOrDefault(p, 0);
                    w++;
                    wa.put(p, w);
                }
            }
        }
        int res = 0;
        for(int i:ac) {
            res += wa.getOrDefault(i, 0);
        }
        System.out.println(ac.size() + " " + res);
    }
}


Measured memory_bytes: 63984
using System;
using System.Linq;

public class AtCoderA
{
    static void Main()
    {
        {
            var line = Console.ReadLine();
            int before = 0;
            for (int i = 0; i < 4; i++)
            {
                int num = int.Parse(line.Substring(i, 1));
                if (i != 0 && num == before)
                {
                    Console.WriteLine("Bad");
                    return;
                }
                before = num;
            }
        }
        Console.WriteLine("Good");
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, l; cin >> n >> l;
    vector<int> apple(n);
    for(int i = 1; i <= n; i++) apple[i - 1] = l + i - 1;
    int d = INF, ans = 0, sum = 0;
    for(int i = 0; i < n; i++) sum += apple[i];
    for(int k = 0; k < n; k++)
    {
        int num = 0;
        for(int i = 0; i < n; i++)
        {
            if(i == k) continue;
            num += apple[i];
        }
        if(abs(sum - num) < d)
        {
            d = abs(sum - num);
            ans = num;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
using namespace std;

int main() {
  int a,b;
  while(scanf("%d %d",&a,&b) != EOF) {
    int num = a + b;
    int digit = 1;
    while(num >= 10) {
      digit++;
      num /= 10;
    }
    printf("%d\n",digit);
  }
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[100010];
int main(){
    int n, k;
    while(cin>>n>>k){
        ll ans=0;
        for(int i=0; i<n; ++i){
            scanf("%d",a+i);
        }
        sort(a, a+n);
        for(int i=0; i<k; ++i){
        	ans+=a[i];
        }
        cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 3764
using System;
class Program{
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		long[] a=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
		string ans="YES";
		long o=a[n-1],t=n;
		long[] h=new long[n];
		for(int i=0;i<n-1;i++){
			t+=i+1;
			o+=a[i];
			h[i]=a[i+1]-a[i];
		}
		h[n-1]=a[0]-a[n-1];
		if(o%t!=0){ans="NO";}
		else{
			o/=t;
			t=0;
			for(int i=0;i<n;i++){
				if(h[i]>o){ans="NO";break;}
				h[i]=Math.Abs(h[i]-o);
				if(h[i]%n!=0){ans="NO";break;}
				t+=h[i]/n;
			}
			if(o!=t){ans="NO";}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 21564
n = int(input())
judge = [0,0,0,0]
for _ in range(n):
    a = input()
    if a == 'AC':
        judge[0] += 1
    elif a == 'WA':
        judge[1] += 1
    elif a == 'TLE':
        judge[2] += 1
    else:
        judge[3] += 1
print('AC x '+str(judge[0])+'\nWA x '+str(judge[1])+'\nTLE x '+str(judge[2])+'\nRE x '+str(judge[3]))

Measured memory_bytes: 9204
#include <bits/stdc++.h>
 
using namespace std;
 
#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define For(I,N)   for(int I=1;I<=(N);I++)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
#define SZ(X) ((int)(X.size()))
#define LG(X) ((int)(X.length()))
#define CL(X) (X).clear()
#define MAXEL(A,B) (*max_element(A,B))
#define MINEL(A,B) (*min_element(A,B))
#define ROPEN(X) freopen(X,"r",stdin)
#define WOPEN(X) freopen(X,"w",stdout)
#define BG(X) (X.begin())
#define EN(X) (X.end())
#define VI vector<int>
#define PII pair<int,int>
 
//cout << fixed << setprecision(20) << p << endl;
 
template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int ans=0;
	int ret=0;
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='A' || s[i]=='C' || s[i]=='G' || s[i]=='T')ret++;
		else ret=0; 
		ans=max(ans,ret);
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
    string a;   cin>>a;
    string b;   cin>>b;
    
    if (a.length() > b.length())
        cout<<"GREATER";
    else if (a.length() < b.length())
        cout<<"LESS";
    else if (a == b) {
        cout<<"EQUAL";
    } else {
        int len = a.length();
        for (int i = 0; i < len; ++i) {
            if (a[i] > b[i]) {
                cout<<"GREATER";
                break;
            } else if (a[i] < b[i]) {
                cout<<"LESS";
                break;
            }
        }
    }
    
    return 0;
}

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bug( x ,y) cerr << #x << '=' << x<<','<<#y<<'='<< y << '\n' ;


int n ,a,b;


int main(){

	IOS

	cin >> n >> a >>b;

	string s ;

	cin >> s;


	for (int i = 0; i < n; ++i)
	{
		if(s[i]=='a' && (a>0 || b>0) ){

			cout << "Yes" << '\n';
			
			if(a>=0)a--;

            if(a==-1)b--;
            

		}

		else if(s[i] =='b' && b>0){

			cout << "Yes\n";

			if(b>0)b--;

		}

		else{
			cout << "No\n";
		}
	
	}




	
 
}

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

int main() {
  int N, M, A[300010];
  cin >> N; M = 3 * N;
  for (int i = 0; i < M; i++) cin >> A[i];
  sort(A, A+M);
  long sum = 0;
  int j = M-2;
  for (int i = 0; i < N; i++) {
    sum += A[j]; j -= 2;
  }
  cout << sum << endl;
}

Measured memory_bytes: 4772
while True:
    H, W = map(int, input().split())
    if H == 0 and W == 0: break
    for i in range(H):
        for j in range(W):
            if (i + j) % 2 ==0:
                print("#", end = '')
            else:
                print('.',end = '')
        print()
    print()


Measured memory_bytes: 7000
#include<stdio.h>
#include <iomanip>
#include <iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include <random>
#include <chrono>

#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
int main() {
	long long n, k, q,tmp;
	cin >> n >> k >> q;
	vector<int> a(n+1);
	vector<string> ans(n,"Yes");
	rep(i, q) {
		cin >> tmp;
		a[tmp]++;
	}
	rep(i, n) {
		tmp = k - q + a[i+1];
		if (tmp <= 0) {
			ans[i] = "No";
		}
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,temp = 1,ans = 0,tem;
  cin>>N;
  vector <int> num(N+1);
  for(int i = 1;i<=N;i++){
    cin >> num.at(i);
  }
  for(int i = 0;i<=N;i++){
    if(temp == 2){break;}
    tem = num.at(temp);
    temp = tem;
    ans++;
  }
  if(ans > N){cout << "-1" << endl;}
  else{cout << ans << endl;}
  return 0;
}


Measured memory_bytes: 640
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#else
#define NDEBUG
#include <bits/stdc++.h>
#endif

using namespace std;
using large = long long;

int N, K;
static vector<int> A;

static large solve() {
    auto divisor = set<int, greater<int>>();
    {
        auto Asum = accumulate(A.begin(), A.end(), 0LL);
        for (auto x = 1; x * x <= Asum; ++x) {
            if (Asum % x != 0)
                continue;
            divisor.insert(x);
            divisor.insert(Asum / x);
        }
    }
    auto rem1 = vector<int>(N + 1);
    auto rem2 = vector<int>(N + 1);
    for (auto d : divisor) {
        rem1.clear();
        for (auto i = 0; i < N; ++i) {
            auto tmp = A[i] % d;
            if (tmp < 0)
                tmp += d;
            if (tmp != 0) {
                rem1.push_back(tmp);
            }
        }
        if (rem1.empty())
            return d;

        sort(rem1.begin(), rem1.end());
        rem2.clear();
        auto rightsum = 0LL;
        for (auto i = 0; i < rem1.size(); ++i) {
            rightsum += (d - rem1[i]);
            rem2.push_back(d - rem1[i]);
        }

        auto leftsum = 0LL;
        for (auto leftcnt = 0; leftcnt < rem1.size(); ++leftcnt) {
            leftsum += rem1[leftcnt];
            rightsum -= rem2[leftcnt];
            if (leftsum == rightsum && leftsum <= K)
                return d;
        }
    }

    return 1;
}

int main() {
    cin >> N >> K;
    A.resize(N);
    for (auto& Ai : A)
        cin >> Ai;
    sort(A.begin(), A.end());
    cout << solve() << endl;
    return 0;
}


Measured memory_bytes: 3648
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func stringsFiledsToint64s() []int64 {
	sc.Scan()
	r := []int64{}
	ss := strings.Fields(sc.Text())
	for _, s := range ss {
		i, e := strconv.ParseInt(s, 10, 64)
		if e != nil {
			panic(e)
		}
		r = append(r, int64(i))
	}
	return r
}

func nextint64() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	// _ = nextint64()
	// inputs := stringsFiledsToint64s()
	// result := int64(1)
	// isZero := false
	// for _, i := range inputs {
	// 	if i == 0 {
	// 		isZero = true
	// 	}
	// }

	// if isZero {
	// 	fmt.Print(0)
	// } else {
	// 	for _, i := range inputs {
	// 		result *= i
	// 		if result > 1e18 || result < i {
	// 			result = -1
	// 			break
	// 		}
	// 	}
	// 	fmt.Print(result)
	// }
	sc.Split(bufio.ScanWords)

	n := int(nextint64())
	a := make([]int64, n)

	for i := 0; i < n; i++ {
		a[i] = nextint64()
		if a[i] == 0 {
			fmt.Println("0")
			return
		}
	}

	var ans int64 = 1
	for i := 0; i < n; i++ {
		ans *= a[i]
		if ans > 1e18 || ans < a[i] {
			fmt.Println("-1")
			return
		}
	}
	fmt.Println(ans)
}


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

const ll INF = 1LL << 60;

ll A, B, C, D;

// 最小公倍数
ll lcm(ll a, ll b) {
    return a / __gcd(a, b) * b;
}
int main() {
    cin >> A >> B >> C >> D;

    ll width = B - A + 1;
    // Cの倍数
    ll c = B / C - (A - 1) / C;

    // Dの倍数
    ll d = B / D - (A - 1) / D;

    // gcd(C, D)の倍数
    ll tmp = lcm(C, D);
    ll gcd_cd = B / tmp - (A - 1) / tmp;  

    // cout << width << " " << c << " " << d << " " << gcd_cd << endl;
    cout << width - (c + d - gcd_cd) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <iomanip>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstdlib>
#include <ctime>

using namespace std;

//#define HOME
void jakos() {
#ifdef HOME
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

#define endl '\n'
#define int long long
typedef long long ll;

const int mod = 1e9 + 7;
const int base = 179;
const int INF = 1e18;
const int N = 1e5 + 7;

signed main() {
    jakos();

    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    if (s == u) {
        a--;
    }
    else if (t == u) {
        b--;
    }
    cout << a << " " << b << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define int ll
const ll inf=1744174417441744;
const ll mod=1e9+7;
ll dist_s[100005]={0},dist_t[100005]={0},num_s[100005]={0},num_t[100005]={0};
vector<P> node[100005];
void dijkstra_s(ll s){
  priority_queue<P,vector<P>,greater<P>> pque;
  pque.push(P(0,s));
  num_s[s]=1;
  for(int i=1;i<100005;i++) dist_s[i]=inf;
  dist_s[s]=0;
  while(!pque.empty()){
    P p=pque.top();
    pque.pop();
    ll cos=p.first,pos=p.second;
    if(dist_s[pos]<cos) continue;
    for(int i=0;i<node[pos].size();i++){
      ll to=node[pos][i].first,ncos=node[pos][i].second;
      ncos+=cos;
      if(dist_s[to]>ncos){
        dist_s[to]=ncos;
        num_s[to]=num_s[pos];
        num_s[to]%=mod;
        pque.push(P(ncos,to));
      }
      else if(dist_s[to]==ncos){
        num_s[to]+=num_s[pos];
        num_s[to]%=mod;
      }
    }
  }
}
void dijkstra_t(ll t){
  priority_queue<P,vector<P>,greater<P>> pque;
  pque.push(P(0,t));
  num_t[t]=1;
  for(int i=1;i<100005;i++) dist_t[i]=inf;
  dist_t[t]=0;
  while(!pque.empty()){
    P p=pque.top();
    pque.pop();
    ll cos=p.first,pos=p.second;
    if(dist_t[pos]<cos) continue;
    for(int i=0;i<node[pos].size();i++){
      ll to=node[pos][i].first,ncos=node[pos][i].second;
      ncos+=cos;
      if(dist_t[to]>ncos){
        dist_t[to]=ncos;
        num_t[to]=num_t[pos];
        num_t[to]%=mod;
        pque.push(P(ncos,to));
      }
      else if(dist_t[to]==ncos){
        num_t[to]+=num_t[pos];
        num_t[to]%=mod;
      }
    }
  }
}
signed main(){
  ll n,m,s,t;
  cin>>n>>m>>s>>t;
  for(int i=0;i<m;i++){
    ll u,v,d;
    cin>>u>>v>>d;
    node[u].push_back(P(v,d));
    node[v].push_back(P(u,d));
  }
  dijkstra_s(s);
  dijkstra_t(t);
  for(int i=1;i<=n;i++){
    num_s[i]%=mod;
    num_t[i]%=mod;
  }
  ll L=dist_s[t];
  ll ans=(num_s[t]*(num_s[t]-1))%mod;
  if(L%2==0){
    for(int i=1;i<=n;i++){
      if(dist_s[i]*2==L&&dist_t[i]*2==L){
        ll path_num=(num_s[i]*num_t[i])%mod;
        path_num*=(path_num-1);
        path_num%=mod;

        ans-=path_num;
        ans+=mod;
        ans%=mod;
      }
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=0;j<node[i].size();j++){
      ll u=i,v=node[i][j].first;
      if(dist_s[u]*2<L&&dist_t[v]*2<L&&dist_s[u]+dist_t[v]+node[i][j].second==L){
        ll path_num=(num_s[u]*num_t[v])%mod;
        path_num*=(path_num-1);
        path_num%=mod;

        ans-=path_num;
        ans+=mod;
        ans%=mod;
      }
    }
  }
  cout<<ans%mod<<endl;
}


Measured memory_bytes: 18772
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

double sumn[1005];

int main() {
	for (int i = 1; i <= 1000; ++i) sumn[i] = sumn[i - 1] + i;
	int n, k; cin >> n >> k;
	vector<double> pi(n);
	for (int i = 0; i < n; ++i) {
		int p; cin >> p;
		pi[i] = sumn[p] / p;
	}
	double ans = 0;
	for (int i = 0; i < k; ++i) ans += pi[i];
	double tmp = ans;
	for (int i = k; i < n; ++i) {
		tmp = tmp - pi[i - k] + pi[i];
		ans = max(ans, tmp);
	}
	printf("%.10f\n", ans);

	return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

int main() {
    string S;
    cin >> S;

    vector<int> cnt(2, 0);
    rep(i, S.size()) {
        cnt[S[i] - '0']++;
    }

    int ans = min(cnt[0], cnt[1]) * 2;
    cout << ans << endl;
}

Measured memory_bytes: 512
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto abx = readln.split.to!(real[]);
    auto a = abx[0];
    auto b = abx[1];
    auto x = abx[2];

    real min_r = 0, max_r = 90;
    foreach (_; 0..10000) {
        auto r = (min_r + max_r) / 2;
        auto t = r * (PI / 180);
        real y;
        if (sin(t)*b > cos(t)*a) {
            y = (a*b - a*a/(2*tan(t))) * a;
        } else {
            y = (tan(t)*b*b/2) * a;
        }
        if (x <= y) {
            max_r = r;
        } else {
            min_r = r;
        }
    }
    writefln("%2.10f", 90 - max_r);
}

Measured memory_bytes: 256
import fractions
N = int(input())
T =  list(map(int, input().split()))
ans = T[0]
for i in range(1, N):
    ans = ans * T[i] // fractions.gcd(ans, T[i])
a = 0
for i in range(N):
    a += ans // T[i]

print(a % (10 ** 9 + 7))

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

using namespace std;

typedef long long ll;
ll N, M, R, L, D, path[100000], loc[100000];

int main() {
  cin >> N >> M;

  vector<vector<pair<ll, ll> > > vec(N);
  memset(path, 0, sizeof(path));
  for (int i = 0; i < M; i++) {
    cin >> L >> R >> D;
    L--;
    R--;
    vec[L].push_back(make_pair(R ,D));
    vec[R].push_back(make_pair(L ,-D));
  }

  for (int i  = 0; i < N; i++) {
    if (!path[i]) {
      path[i]++;
      queue<ll> que;
      que.push(i);

      while(!que.empty()) {
        ll q = que.front();
        que.pop();

        for (auto x : vec[q]) {
          if (!path[x.first]) {
            loc[x.first] = loc[q] + x.second;
            path[x.first]++;
            que.push(x.first);
          } else {
            if (loc[x.first] != loc[q] + x.second) {
              cout << "No" << endl;
              return 0;
            }
          }
        }
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 14848
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
int gcd(int a, int b) { return a ? gcd(b%a, a) : b; }
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N, M, A[11];
int need[] = { 0, 2,5,5,4,5,6,3,7,6 };
using vi = vector<int>;
#define init vi(10, 0)
//---------------------------------------------------------------------------------------------------
bool comp(vi a, vi b) {
    int sm1 = 0;
    fore(i, a) sm1 += i;

    int sm2 = 0;
    fore(i, b) sm2 += i;

    if (sm1 != sm2) return sm1 < sm2;

    rrep(i, 9, 0) if (a[i] != b[i]) return a[i] < b[i];

    return false;
}
//---------------------------------------------------------------------------------------------------
string solve() {
    vector<int> ans = init;

    rep(a1, 0, 10) rep(a2, 0, 10) rep(a3, 0, 10) rep(a4, 0, 10) rep(a5, 0, 10) rep(a6, 0, 10) rep(r, 1, 10) {
        int cst = need[a1] + need[a2] + need[a3] + need[a4] + need[a5] + need[a6];
        int d = N - cst;

        if (d < 0) continue;

        if (A[a1] == 0) continue;
        if (A[a2] == 0) continue;
        if (A[a3] == 0) continue;
        if (A[a4] == 0) continue;
        if (A[a5] == 0) continue;
        if (A[a6] == 0) continue;
        if (A[r] == 0) continue;

        vi cand(10, 0);
        if(0 < a1) cand[a1]++;
        if (0 < a2) cand[a2]++;
        if (0 < a3) cand[a3]++;
        if (0 < a4) cand[a4]++;
        if (0 < a5) cand[a5]++;
        if (0 < a6) cand[a6]++;

        if (0 < d % need[r]) continue;
        cand[r] += d / need[r];

        if (comp(ans, cand)) {
            ans = cand;
        }
    }

    string res = "";
    rrep(i, 9, 1) {
        rep(j, 0, ans[i]) res += char('0' + i);
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    A[0] = 1;
    rep(i, 0, M) {
        int a; cin >> a;
        A[a] = 1;
    }
    cout << solve() << endl;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(1, n):
    m = 10**10
    index = i-1
    num = k
    while index >= 0 and num:
        m = min(m, dp[index]+abs(h[index]-h[i]))
        index-=1
        num-=1
    dp[i] = m
print(dp[n-1])

Measured memory_bytes: 56544
#include <stdio.h>
#include <math.h>
int main(){
	double input,sa,max,min;
    scanf("%lf",&input);
    max=input;
    min=input;
    while(scanf("%lf",&input)!=EOF){
        if(max<input){
            max=input;
        }else if(min>input){
            min = input;
        }
    }
    sa = max-min;
    printf("%.1f",sa);
	return 0;
}

Measured memory_bytes: 652
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a,b,c,d;
char s[N];
int main()
{
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    scanf("%s",s+1);
    bool flag=true;
    for(int i=a;i<max(c,d);i++)
        if(s[i]=='#'&&s[i+1]=='#') flag=false;
    if(c>d)
    {
        int tot=0;
        for(int i=max(a,b-1);i<=d-1;i++)
            if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.') tot++;
        if(tot==0&&!(b-1==a&&s[b+1]=='.')) flag=false;
    }
    printf(flag?"Yes":"No");
}


Measured memory_bytes: 384
#include<stdio.h>

int main (){
    int K,A,B;
    int sum=0;
    
    scanf("%d",&K);
    scanf("%d %d", &A, &B);
    
    while (sum < B){
        sum += K;
        if (sum >= A){
            break;
        }
    }
    sum > B ? printf("NG\n") : printf("OK\n");
    //condition ? statement T : statement F   
        
    
    return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x,y;cin>>x>>y;
    int ans = 0;
    ans += 100000*max(0,4-x);
    ans += 100000*max(0,4-y);
    if(x==1&&y==1)ans+=400000;
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

bool cmp(int x,int y) {
	return x>y;
}

int main () {
	int n,k;
	cin >> n >> k;
	int a[55];
	for (int i=1;i<=n;i++) {
		cin >> a[i];
	}
	sort (a+1,a+n+1,cmp);
	int ans=0;
	for (int i=1;i<=k;i++) {
		ans+=a[i];
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

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

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

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

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

const int inf = 1e9;

int main()
{
    int n;
    while (cin >> n) {
        VI A(n,inf);
        FOR(i,0,n-1) {
            int b; cin >> b;
            A[i] = min(b,A[i]);
            A[i+1] = b;
        }
        LL ans = 0;
        FOR(i,0,A.size())
            ans += A[i];
        cout << ans << endl;
    }
    return 0;
}   


Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
total = 0
if n == 1:
    pass
else:
    for i in factorization(n):
        t = 1
        while 1:
            if i[1]-t < 0:
                break
            else:
                total += 1
                i[1] -= t
                t += 1
print(total)

Measured memory_bytes: 63376
N = int(input())
A_array = list(map(int, input().split()))

A_array.sort()

ans_array = []
if A_array[0] >= 0:
    m = A_array[0]
    for i in range(1, N - 1):
        ans_array.append((m, A_array[i]))
        m = m - A_array[i]
    ans_array.append((A_array[-1], m))
    m = A_array[-1] - m
    print(m)
    for ans in ans_array:
        print(ans[0], ans[1])
    exit()

elif A_array[-1] <= 0:
    m = A_array[-1]
    for i in range(N - 2, -1, -1):
        ans_array.append((m, A_array[i]))
        m = m - A_array[i]
    print(m)
    for ans in ans_array:
        print(ans[0], ans[1])
    exit()

else:
    change_index = 0
    m = A_array[-1]
    for i in range(N - 1):
        if A_array[i + 1] < 0:
            ans_array.append((m, A_array[i]))
            m -= A_array[i]
        else:
            change_index = i
            break
    n = A_array[change_index]

    for i in range(change_index + 1, N - 1):
        ans_array.append((n, A_array[i]))
        n -= A_array[i]

    ans_array.append((m, n))
    m = m - n
    print(m)
    for ans in ans_array:
        print(ans[0], ans[1])
    exit()


Measured memory_bytes: 61908
#include <stdio.h>

int main(){
  int i,j,n,q,S[10000],T[10000],sum = 0;

  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%d",&S[i]);
  }
  
  
  scanf("%d",&q);
  for(i = 0; i < q; i++){
    scanf("%d",&T[i]);
  }
  
  
  for(i = 0; i < q; i++){
    for(j = 0; j < n; j++){
      if(T[i] == S[j]){
	sum++;
	break;
      }
    }
  }
  
  printf("%d\n",sum);

  return 0;
}



Measured memory_bytes: 2052
n = int(input())
ans = 0
lst_v = list(map(int,input().split()))
lst_c = list(map(int,input().split()))
for i in range(n):
  if lst_v[i] > lst_c[i]:
    ans += (lst_v[i] - lst_c[i])
  else:
    continue

print(ans)
  	
  

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define re register
inline int read(){
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0'){
		t=(t<<3)+(t<<1)+v-48;
		v=getchar();
	}
	return t;
}
using namespace std;
char s[88];
int main(){
	scanf("%s",s+1);
	if(s[4]==s[3]&&s[6]==s[5])puts("Yes");
	else puts("No");
}

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

int main(){
   double n,m;
   cin>>n>>m;
   vector<double> a(n);
   double sum = 0;
   for(int i = 0; i < n; i++){
         cin>>a[i];
         sum += a[i];
   }
   double limit = sum/(4*m);
   for(int i = 0; i < n; i++){
        if(a[i] >= limit) m--;
   }
   if( m <= 0 ) cout<<"Yes"<<endl;
   else cout<<"No"<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >>n;
  string s;
  cin >>s;
  int p;
  p=n;
  for (int i=0;i<n-1;i++){
  if (s.at(i)==s.at(i+1)){
  	p-=1;
  }
  }
  cout <<p<<endl;
}
      

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a==1||a==2)
		if(b==2||b==1)
			cout<<3<<endl;
	if(a==1||a==3)
		if(b==1||b==3)
			cout<<2<<endl;
	if(a==2||a==3)
		if(b==2||b==3)
			cout<<1<<endl;
}

Measured memory_bytes: 256
################# <-----------------  Quicksilver_ -----------------> ##################
from itertools import combinations

n,m,k=[int(i) for i in input().split()]

glob=[]

for i in range(n):
    arr=[int(i) for i in input().split()]
    glob.append(arr)

l=list(range(0,n))

mino=1000000000000000

for i in range(1,n+1):

    comb = combinations(l,i)

    r=[]
    for ijk in range(m+1):
        r.append(0)

    for z in comb:
        for fg in range(m+1):
            r[fg]=0
        for y in z:
            for yu in range(m+1):
                r[yu]+=glob[y][yu]
        if min(r[1:])>=k:
            mino=min(mino,r[0])
if mino==1000000000000000:
    print(-1)
else:
    print(mino)


Measured memory_bytes: 9240
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define v first
#define x second
using namespace std;
const int nmax=200005;
const int mod=1000*1000*1000+7;
pair<int,int> a[nmax];
vector<int> lst[nmax];
int dp[nmax],sum[nmax],mx[nmax],mn[nmax],l[nmax],r[nmax];
int n,i,j,p,add;
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].v;
    }
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++)
    {
        mx[i]=max(mx[i-1],a[i].x);l[i]=i;
        for(p=17;p>=0;p--)
            if(l[i]-(1<<p)>0&&mx[l[i]-(1<<p)]>=a[i].x)
               l[i]-=(1<<p);
    }
    mn[n+1]=(1<<30);
    for(i=n;i>=1;i--)
    {
        mn[i]=min(mn[i+1],a[i].x);r[i]=i;
        for(p=17;p>=0;p--)
            if(r[i]+(1<<p)<=n&&mn[r[i]+(1<<p)]<=a[i].x)
              r[i]+=(1<<p);
    }
    for(i=1;i<=n;i++)
    {
        lst[r[i]].push_back(l[i]-1);
    }
    dp[0]=1;sum[0]=1;
    for(i=1;i<=n;i++)
    {
        sum[i]=sum[i-1];sort(lst[i].begin(),lst[i].end());
        for(j=0;j<lst[i].size();j++)
        {
            add=sum[i];
            if(lst[i][j])
                add-=sum[lst[i][j]-1];
            add%=mod;
            if(add<0) add+=mod;
            dp[i]+=add;if(dp[i]>=mod) dp[i]-=mod;
            sum[i]+=add;if(sum[i]>=mod) sum[i]-=mod;
        }
    }
    cout<<dp[n];
    return 0;
}

Measured memory_bytes: 17408
N, M = map(int, input().split())

mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]

        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
        self.invs[n] = pow(self.facts[n], mod-2, mod)
        for i in range(1, n+1):
            self.invs[n-i] = self.invs[n-i+1] * (n-i+1) % mod

    def ncr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def npr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return self.facts[n] * self.invs[n-r] % mod

ans = 0
comb = Combination(M)
for i in range(N+1):
    ans = (ans + (-1) ** i * comb.npr(M-i, N-i) * comb.ncr(N, i)) % mod

ans = ans * comb.npr(M, N) % mod
print(ans)


Measured memory_bytes: 153144
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int>a(n+1),b(n+1),c(n+1);
	for(int i=1; i<=n; i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	int table[100001][3];
	table[1][0]=a[1];
	table[1][1]=b[1];
	table[1][2]=c[1];
	for(int i=2; i<=n; i++){
		table[i][0]=a[i]+max(table[i-1][1],table[i-1][2]);
		table[i][1]=b[i]+max(table[i-1][0],table[i-1][2]);
		table[i][2]=c[i]+max(table[i-1][0],table[i-1][1]);
	}
	int ans=max(table[n][0],max(table[n][1],table[n][2]));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5620
#include <stdio.h>

int main(){
    int H, W;
    int i, j;
    while(1){
        scanf("%d %d", &H, &W);
        if(H == 0)break;

        for(i = 0; i < H; i++){
            for(j = 0; j < W; j++){
                printf("%c%s", (i == 0 || i == H - 1 || j == 0 || j == W -1) ? '#' : '.', (j == W - 1) ? "\n" : "");
            }
            if(i == H - 1)printf("\n");
        }
    }
}


Measured memory_bytes: 2060
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Graph{
	private:
	int n;
	vvi g;
	public:
	vi match,used;
	bool BM_dfs(int v){
		used[v]=1;
		for(auto u:g[v]){
			int w=match[u];
			if(w<0||!used[w]&&BM_dfs(w)){
				match[v]=u;
				match[u]=v;
				return 1;
			}
		}
		return 0;
	}
	int BM(){
		int res=0;
		match=vi(n,-1);
		for(int i=0;i<n;i++) if(match[i]<0){
			used=vi(n);
			if(BM_dfs(i)) res++;
		}
		return res;
	}
	Graph(int v){
		n=v;
		g=vvi(v);
	}
	void add_edge(int s,int t){
		g[s].push_back(t);
		g[t].push_back(s);
	}
};


ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0) break;
		Graph g(n+m);
		vi a(n),b(m);
		for(int i=0;i<n;i++) cin>>a[i];
		for(int i=0;i<m;i++) cin>>b[i];
		for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(gcd(a[i],b[j])>1) g.add_edge(i,n+j);
		cout<<g.BM()<<endl;
	}
}


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

int min(int a, int b) {
	if(a < b) return a;
	return b;
}

int abs(int a) {
	if(a < 0) return -a;
	return a;
}

int main() {
	// your code goes here
	int n;
	cin >> n;
	int h[n];
	for(int i=0; i<n; i++) {
		cin >> h[i];
	}
	int dp[n];
	dp[0] = 0;
	dp[1] = dp[0]+abs(h[1]-h[0]);
	for(int i=2; i<n; i++) {
		dp[i] = min(dp[i-2]+abs(h[i]-h[i-2]), dp[i-1]+abs(h[i]-h[i-1]));
	}
	cout << dp[n-1] << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
typedef long long ll;

int main(){
  ll n, t;
  ll a[100000];
  ll cntb=0,cnts=0;
  cin >> n >> t;

  ll min=1000000000,maxdif=0;
  ll cntmin=0,mintmp=1000000000;
  for(ll i =0;i<n;i++){
    cin >> a[i];
    if(min > a[i]){
      cntmin=1;
      min = a[i];
    }else if (min == a[i]){
      cntmin++;
    }else{
      if(a[i]-min > maxdif){
	maxdif=a[i]-min;
	cntb=1;
	cnts=cntmin;
	mintmp=min;
      }else if (a[i]-min == maxdif){
	cntb++;
	if(mintmp!=min){
	  cnts+=cntmin;
	  mintmp=min;
	}
      }
    }
  }
  if(cnts>cntb)
    cout << cntb<<endl;
  else
    cout << cnts<<endl;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	int n;
	int a, b, c, d;
	int kazu = 0;
	int hanbetsu = 0;
	
	while (scanf("%d", &n) != EOF){
		for (a = 0; a != 10; a++){
			for (b = 0; b != 10; b++){
				for (c = 0; c != 10; c++){
					for (d = 0; d != 10; d++){
						if ((a + b+ c + d) == n){
							kazu++;
						}
					}
				}
			}
		}
		
		printf("%d\n", kazu);
		kazu = 0;
	}
	
	return (0);
}

Measured memory_bytes: 1712
#include <iostream>
#include<algorithm>
#include<set>
#include<queue>
#define rep(i,j,n) for(int i=j;i<n;i++)
using namespace std;
#define int long long
int mul[214514];
int divi[214514];
#define inf 1000000007
int bit[114514],n;
struct edge{int u,v,cost;};
edge es[214514];
int zero=0;
string alph("abcdefghijklmnopqrstuvwxyz");
signed main(){
    int n,m;cin>>n>>m;
    rep(i,0,n+1){
        rep(j,0,n-i+1){
            int sum=m-(i*1000+j*5000);
            if(sum==10000*(n-i-j)){
                cout<<n-i-j<<" "<<j<<" "<<i<<endl;
                return 0;
            }
        }
    }
    cout<<-1<<" "<<-1<<" "<<" "<<-1<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;
const int loose = 0;
const int tight = 1;

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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

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

	ll k, q;
	cin >> k >> q;
	Array d(k);
	REP(i, k) cin >> d[i];

	while (q--) {
		ll n, x, m;
		cin >> n >> x >> m;
		ll ans = n - 1;
		Array dm = d;
		REP(i, k) {
			dm[i] %= m;
			if (dm[i] == 0) {
				ans -= (n - 1) / k;
				if ((n - 1) % k > i) ans--;
			}
		}

		ll sum = 0;
		ll an = x;
		REP(i, k) {
			sum += dm[i];
			if((n - 1) % k > i) an += dm[i];
		}
		an += sum * ((n-1)/k);
		ans -= an / m - x / m;
		cout << ans << en;
	}


	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int d=0;
  int a=n;
  int t;
  while(a>0)
  {
    
    d+=1;
    a=a/10;
  }
  int sum=0;
  for(int i=1;i<d;i=i+2)
  {
    sum+=(9*pow(10,i-1));
  }
  
  if((d%2==0)&&(d>0))
  {
  cout<<sum;
  return 0;
}
 else 
 {
 	t=n+1-pow(10,d-1);
 }
 sum+=t;
 cout<<sum<<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;

int main()
{
    const char *ABC = "ABC";
    const char *ARC = "ARC";
    const int ABCRate = 1200;

    int x;
    if (scanf("%d", &x) < 1) return 0;

    printf("%s\n", x < ABCRate ? ABC : ARC);
    return 0;
}


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

bool isSmallAlphabet(char& ch) {
  /* a ~ z(ascii) : 97 ~ 122 */
  if('a' <= ch && ch <= 'z') return true;
  else return false;
}

bool isHit(string& str) {
  if(str.find("the") != str.npos) return true;
  else if(str.find("this") != str.npos) return true;
  else if(str.find("that") != str.npos) return true;
  else return false;
}

char shiftIndex(char ch) {
  if(isSmallAlphabet(ch)) {
    ch += 1;
    /* ???????????????????°?????????§???????????£??????*/
    if(!isSmallAlphabet(ch)) {
      ch -= 26;
    }
  }
  return ch;
}

/* ????????¶??????????§£??? */
void CaesarCipher(string str) {
  
  /* p??????????????¢??????????????????????????????????????? */
  for(int p = 0; p < 26; ++p) {

    transform(str.begin(), str.end(), str.begin(), shiftIndex);

    /* Find "the" or "this" or "that" */
    if(isHit(str)) {
      cout << str << endl;
    }
  }
}

int main() {
  string str;
  while(getline(cin, str)) {
    CaesarCipher(str);
  }
  return 0;
}

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

using namespace std;

#define ff first
#define ss second
#define pb push_back
using ii = pair<long long, long long>;
using ll = long long;
#define oo 1000000000000000000

ll dp[60][60];
int vai[60][60];
int mark[60][60];
int pass;
int a[100];
int b[100];
set<int> s;

ll f(int x, int y){
	if(x == y){
		vai[x][y] = 0;
		return 0;
	}
	if(x < y) return oo;
	if(mark[x][y] == pass) return dp[x][y];
	mark[x][y] = pass;
	ll ret = oo;
	int d = -1;
	for(auto i : s){
		if(i <= x){
			if(f(x % i, y) + (1LL << i) < ret){
				ret = f(x % i, y) + (1LL << i);
				d = i;
			}
		}
	}
	vai[x][y] = d;
	return dp[x][y] = ret;
}

int main (){
	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",a+i);
	for(int i = 0; i < n; i++)
		scanf("%d",b+i);
	for(int i = 1; i <= 49; i++)
		s.insert(i);
	for(int j = 50; j > 0; j--){
		int da = 1;
		s.erase(j);
		pass++;
		memset(vai, -1, sizeof vai);
		for(int i = 0; i < n; i++){
			f(a[i], b[i]);
			if(vai[a[i]][b[i]] == -1){
				da = 0;
				break;
			}
		}
		if(!da) s.insert(j);
		if(!da && j == 50){
			printf("-1\n");
			return 0;
		}
	}
	ll ans = 0;
	for(int i : s){
		ans += 1LL << i;
	}
	printf("%lld\n",ans );
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(n, 0));

  function<void(const vector<int>&, int)> f = [&](const vector<int>& s, int l) {
    for (int i = 0; i < s.size(); i++) {
      for (int j = 0; j < i; j++) {
        if (i % 2 != j % 2) a[s[i]][s[j]] = a[s[j]][s[i]] = l;
      }
    }
    for (int o = 0; o < 2; o++) {
      vector<int> tt;
      for (int i = o; i < s.size(); i += 2) tt.push_back(s[i]);
      if (tt.size() >= 2) f(tt, l + 1);
    }
  };

  vector<int> t(n);
  iota(begin(t), end(t), 0);
  f(t, 1);

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) cout << a[i][j] << ' ';
    cout << endl;
  }
}


Measured memory_bytes: 1536