akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define bit(k) (1LL<<(k))
typedef long long ll;

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);

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

/*------------------------------------/
for library*/

/*------------------------------------*/

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

    int N,M;
    cin>>N>>M;
    vector<ll> x(N),y(N),z(N);
    rep(i,N){
        cin>>x[i]>>y[i]>>z[i];
    }
    /*
    ケーキN個中M個を食べて、
    |\sigma(x)| + |\sigma(y)| + |\sigma(z)|
    を最大化したい

    +と-で分けて考える？
    |x|の最大化と|y|の最大化を同時にやるのは、無理だろ
    最終的に+にしたいとき、そのままの符号で扱う
    最終的に-にしたいとき、-をかけて扱う
    こうすれば、x + y + zの大きいものから貪欲に選んでもいいんじゃない？

    */
    ll ans = 0;
    for(int i = 0; i < bit(3); i++){
        vector<ll> tmps;
        rep(j,N){
            ll tmp = 0;
            tmp += ((i & bit(0)) ? x[j]:-x[j]);
            tmp += ((i & bit(1)) ? y[j]:-y[j]);
            tmp += ((i & bit(2)) ? z[j]:-z[j]);
            tmps.push_back(tmp);
        }
        sort(all(tmps));
        reverse(all(tmps));
        //print(tmps);
        ll summ = 0;
        rep(j,M){
            summ += tmps[j];
        }
        chmax(ans,summ);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            char[] s = in.next().toCharArray();
            int[] count = new int[26];
            for (char c : s) {
                count[c - 'a']++;
            }
            char i = 0;
            while (i < 26 && count[i] != 0) {
                i++;
            }
            if (i == 26) {
                out.println("None");
            } else {
                out.println("" + (char)(i + 'a'));
            }
        }

    }

    static class InputReader {
        public BufferedReader  reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextFloat() {
            return Double.parseDouble(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

    }
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
                    
                    
int main(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    string ans = "No";

    for(int i = 0; i < K; i++) {
        if(A >= B) {
            B *= 2;
        } else if(B >= C) {
            C *= 2;
        }
    }

    if(A < B && B < C) {
        ans = "Yes";
    }

    cout << ans << endl;
            
}

Measured memory_bytes: 3624
package main

import (
	"fmt"
	//"sort"
	//"strconv"
	//"strings"
)

func main() {
	var n, k, q int
	fmt.Scan(&n, &k, &q)
	var p [100000]int
	var a int
	for i := 0; i < q; i++ {
		fmt.Scan(&a)
		p[a-1]++
	}
	for i := 0; i < n; i++ {
		if k-q+p[i] > 0 {
			fmt.Println("Yes")
		} else {
			fmt.Println("No")
		}
	}
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef long double ld;
const ld pi = 4*atan((ld)1);
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll nax = 0;

ll n;
ll a[105];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	ll cek = 0;
	for(ll i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	for(ll i = 1; i <= n; i++){
		for(ll j = i + 1; j <= n; j++){
			for(ll k = j + 1; k <= n; k++){
				if(i == j || i == k || j == k){
					continue;
				}
				if(a[i] == a[j] || a[i] == a[k] || a[j] == a[k]){
					continue;
				}
				vector<ll> v;
				if(a[i] + a[j] > a[k]){
					if(a[i] < a[j] && a[j] < a[k]){
						cek++;
					}
				}
			}
		}
	}
	cout << cek << '\n';
}



Measured memory_bytes: 3656
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(abs(a-c)<=d)cout<<"Yes";
    else if(abs(a-b)<=d&&abs(b-c)<=d)cout<<"Yes";
    else cout<<"No";
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;

int solve1(int A[]){//この方法だとメモリを圧迫しすぎてしまうのでアウト
    vector<int> L[100001];
    bool small;

    L[0].push_back(A[0]);
    for(int i=1;i<N;i++){
        small=false;
        for(int j=0;j<L[i-1].size();j++){
            if(!small && L[i-1][j]>=A[i]){
                small=true;
                L[i].push_back(A[i]);
            }
            else L[i].push_back(L[i-1][j]);
        }
        if(!small) L[i].push_back(A[i]);
    }
    return L[N-1].size();
}
int solve2(int A[]){
    int L[100001];
    L[0]=A[0];
    int length=1;

    for(int i=0;i<N;i++){
        if(L[length-1]<A[i]) L[length++]=A[i];
        else *lower_bound(L,L+length,A[i]) = A[i];//この処理で、Lの中でA[i]より大きいい中で一番小さい奴がA[i]に置き換わる
        }
        return length;
}

int main(){
    int A[100001];
    cin>>N;
    for(int i=0;i<N;i++) cin>>A[i];
    cout<<solve2(A)<<endl;
}


Measured memory_bytes: 3800
#include <bits/stdc++.h>
#include <boost/format.hpp>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, ans = 0;
    string s;
    cin >> n >> s;
    REP(num, 1000) {
        int i1 = (num / 100) % 10;
        int i2 = (num / 10) % 10;
        int i3 = num % 10;

        auto pos1 = s.find(to_string(i1));
        if (pos1 != string::npos) {
            auto pos2 = s.find(to_string(i2), pos1 + 1);
            if (pos2 != string::npos) {
                auto pos3 = s.find(to_string(i3), pos2 + 1);
                if (pos3 != string::npos) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3744
import java.util.*;

public class Main {

    static int mod = 1_000_000_007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        long[] dp = new long[s+1];
        dp[0] = 1;
        for (int i = 0; i < s; i++) {
            for (int j = 3; j <= s; j++) {
                if(s < i + j) break;
                dp[i+j] = (dp[i+j] + dp[i]) %mod;
            }
        }
        System.out.println(dp[s]);
        sc.close();

    }

}


Measured memory_bytes: 35692
# import sys
# input = sys.stdin.readline
inf = 10 ** 18
P = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))

d_x = {}
for idx, Ai in enumerate(A):
    if str(Ai) not in d_x.keys():
        d_x[str(Ai)] = [idx]
    else:
        d_x[str(Ai)].append(idx)

tab_jump = [None] * N
for key in d_x.keys():
    for i in range(len(d_x[key]) - 1):
        tab_jump[d_x[key][i]] = d_x[key][i + 1]
    tab_jump[d_x[key][-1]] = d_x[key][0]

ans = []
pos = 0
while True:
    # print("#", pos)
    if pos >= N * K: break
    pos_src = pos % N
    pos_dst = tab_jump[pos_src]
    if pos_src < pos_dst:
        pos_nxt = pos + (pos_dst - pos_src) + 1
    else:
        pos_nxt = pos + (pos_dst - pos_src) + N + 1
    #
    if pos_nxt > N * K:
        ans.append(A[pos_src])
        pos += 1
    else:
        if pos_nxt % N == 0:
            K_iter = pos_nxt // N
            pos = N * ((K // K_iter) * K_iter)
        else:
            pos = pos_nxt

if len(ans) > 0:
    print(' '.join(map(str, ans)))

Measured memory_bytes: 76588
s = list(str(input()))
q = int(input())
f = []
b = []
cnt = 0
for i in range (q):
    t = list(str(input()))
    if t[0] == '2':
        if t[2] == '1':
            f.append(t[4])
        else:
            b.append(t[4])
    else:
        x = f
        y = b
        f = y
        b = x
        cnt += 1
f.reverse()
if cnt%2 != 0:
    s.reverse()
    
print(''.join(f) + ''.join(s) + ''.join(b))

Measured memory_bytes: 6428
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int h[n];
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        while(h[i] != 0){
            for(int j = i; j < n; j++){
                if(h[j] > 0){
                    h[j]--;
                }else{
                    break;
                }
            }
            ans++;
        }
    }
    cout << ans;
}

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

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define V vector<int>
#define VLL vector<long long>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
	int N, M, K;  cin >> N >> M >> K;

	bool ans = false;
	for(int n = 0 ; n <= N ; n++){
			for(int m = 0 ; m <= M ; m++){
					if(n * (M - 2 * m) + m * N == K){
							ans = true;
							break;
					}
			}
	}
  
	if(ans)	cout << "Yes" << endl;
	else	cout << "No"  << endl;

	return 0;
}


Measured memory_bytes: 256
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr int MOD_TYPE = 1;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

#pragma endregion

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);
  int h, w;
  cin >> h >> w;
  int di = 0;
  vector<pii> v;
  rep(i, h)
  {
    if (di == 0)
    {
      rep(j, w) v.push_back(MP(i, j));
    }
    else
    {
      for (int j = w - 1; j >= 0; --j)
        v.push_back(MP(i, j));
    }
    di ^= 1;
  }
  int i = 0;
  int ans[110][110];
  int n;
  cin >> n;
  rep(color, n)
  {
    int a;
    cin >> a;
    rep(j, a)
    {
      ans[v[i].first][v[i].second] = color + 1;
      i++;
    }
  }
  rep(i, h)
  {
    rep(j, w) cout << ans[i][j] << (j == w - 1 ? "\n" : " ");
  }
  return 0;
}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define pb(a) push_back(a)

typedef long long ll;
using namespace std;

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 int dy[] = { 0, 0, 1, -1 };
//const int dx[] = { 1, -1, 0, 0 };
const int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
ll gcd(ll a, ll b);
ll lcm(ll x, ll y);

vector<ll> h;

int main()
{
	ll a,b,c,d;
	ll ans = 0;
	cin >> a >> b >> c >>d;
	ans += min(a, b);
	ans += min(c, d);

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

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

    int N, R;
    cin >> N >> R;

    if (N >= 10)
    {
        cout << R;
    }
    else
    {
        cout << (10 - N) * 100 + R;
    }

    return 0;
}

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

int main() {
    double A, B, deg;
    cin >> A >> B >> deg;
    double rad = deg * M_PI / 180.0;
    double S = 0.5 * A * B * sin(rad);
    double C = sqrt(pow(A, 2) + pow(B, 2) - 2.0 * A * B * cos(rad));
    double L = A + B + C;
    double H = 2.0 * S / A;
    cout << fixed << setprecision(6) << S << endl;
    cout << fixed << setprecision(6) << L << endl;
    cout << fixed << setprecision(6) << H << endl;
}


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

int N;
vector<ll> let(5);
const char letter[5] = {'M', 'A', 'R', 'C', 'H'};

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        string temp; cin >> temp;
        for (int j = 0; j < 5; j++) {
            if (temp[0] == letter[j]) {
                let[j]++;
            }
        }
    }
    ll res = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = i+1; j < 4; j++) {
            for (int k = j+1; k < 5; k++) {
                res += let[i]*let[j]*let[k];
            }
        }
    }
    cout << res << endl;
    return 0;

}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split(' ')))

print(*A)
for i in range(1, n):
    t = A[i]
    k = i - 1
    while k >= 0 and t < A[k]:
        A[k + 1] = A[k]
        k -= 1
    A[k + 1] = t
    print(*A)



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

namespace AtCoder
{
    class Abc165A
    {
        public static void Main()
        {
            var k = int.Parse(Console.ReadLine());
            var ab = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

            if (ab[1] / k > ab[0] / k || ab[0] % k == 0 || ab[1] % k == 0)
                Console.WriteLine("OK");
            else
                Console.WriteLine("NG");
        }
    }
}


Measured memory_bytes: 28292
#include <bits/stdc++.h>
using namespace std;
typedef signed long long lint;

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  lint h, w, n;
  cin >> h >> w >> n;
  set< lint > p;
  vector< tuple< lint, lint > > c;
  for (lint i=0; i<n; ++i) {
    lint a, b;
    cin >> a >> b;
    a--; b--;
    p.insert(a*w+b);
    for (lint x=-1; x<=1; ++x) {
      for (lint y=-1; y<=1; ++y) {
	c.push_back(make_tuple(a+x, b+y));
      }
    }
  }
  sort(c.begin(), c.end());
  vector< lint > cnt(10, 0);
  for (lint i=0; i<c.size(); ++i) {
    lint ai=get<0>(c[i]), bi=get<1>(c[i]);
    if (i>0 && c[i]==c[i-1]) continue;
    if (ai-1 < 0 || h <= ai+1) continue;
    if (bi-1 < 0 || w <= bi+1) continue;
    lint ans = 0;
    for (lint x=-1; x<=1; ++x) {
      for (lint y=-1; y<=1; ++y) {
	lint px=ai+x, py=bi+y;
	if (p.find(px*w+py) != p.end()) ans++;
      }
    }
    //cerr << ai << "," << bi << " " << ans << endl;
    cnt[ans]++;
  }
  lint sum = 0;
  for (lint i=1; i<=9; ++i) sum += cnt[i];
  cout << (h-2)*(w-2)-sum << endl;
  for (lint i=1; i<=9; ++i) cout << cnt[i] << endl;
  return 0;
}


Measured memory_bytes: 21480
import math
import fractions

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

x = int(input())
while 1:
    if is_prime(x):
        break
    x += 1
print(x)

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

int main() {
  vector<char> N;
  char c;
  bool flag = false;
  
  while(cin >> c) {
    N.push_back(c);
  }

  switch (N.size()) {
  case 3 : if(N[0] == N[2]) flag = true; break;
  case 2 : if(N[0] == N[1]) flag = true; break;
  case 1 : flag = true; break;
  }

  if(flag) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

void print(long A[], long n) {
	for (long i = 0; i < n; i++) {
		cout << A[i] << endl;
	}
}

long insertionSort(long A[], long n, long g) {
	long cnt = 0;
	for (long i = g; i < n; i++) {
		long v = A[i];
		long j = i - g;
		for (; j >= 0 && A[j] > v; j -= g) {
			A[j + g] = A[j];
			cnt++;
		}
		A[j + g] = v;
	}
	return cnt;
}

void shellSort(long A[], long n) {
	long cnt = 0;
	long m;
	long G[13];
	G[0] = 1;
	for (m = 0; G[m] <= n; m++) {
		G[m + 1] = ((G[m] * 2 + 1) * 3 - 1) / 2;
	}
	cout << m << endl;
	for (long i = m - 1; i >= 0; i--) {
		cnt += insertionSort(A, n, G[i]);
		if  (i != m - 1) {
			cout << " ";
		}
		cout << G[i];
	}
	cout << endl << cnt << endl;
}

int main() {
	long n;
	cin >> n;
	long A[n];
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

	shellSort(A, n);
	print(A, n);

	return 0;

}

Measured memory_bytes: 8972
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, l, r, a = 0; cin >> n >> l >> r;
	while(n--){
		int x; cin >> x;
		if(l <= x && x < r);
		else a++;
	}
	cout << a << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <sstream>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define SORT(x) sort((x).begin(), (x).end())
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

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

int main(){
	int h, w;
	while(scanf("%d%d", &h, &w),h||w){
		vector<string> d(h);
		map<int,map<string,int> > m;
		rep(i,h) cin >> d[i];
		rep(i,h) rep(j,w){
			rep(k,8){
				int y = i, x = j;
				string str;
				str.pb(d[y][x]);
				while(true){
					y += dy[k];
					x += dx[k];
					if(y < 0) y = h+y;
					if(y >= h) y = y-h;
					if(x < 0) x = w+x;
					if(x >= w) x = x-w;
					if(y == i && x == j) break;
					str.pb(d[y][x]);
					m[-1*str.size()][str]++;
				}
			}
		}
		map<int,map<string,int> >::iterator ite;
		bool ok = false;
		for(ite = m.begin(); ite != m.end(); ite++){
			map<string,int> tmp = ite->sec;
			map<string,int>::iterator it;
			for(it = tmp.begin(); it != tmp.end(); it++){
				if(it->sec >= 2){
					cout << it->fi << endl;
					ok = true;
					break;
				}
			}
			if(ok) break;
		}
		if(!ok) cout << "0" << endl;
	}
}

Measured memory_bytes: 36008
#include<bits/stdc++.h>
using namespace std;
vector<int> d[100];
bool visited[100];
int dist;
int max_dist;
void dfs(int s){
	dist++;
	if(dist > max_dist) max_dist = dist;
	visited[s] = true;
	for(int i = 0; i < d[s].size(); i++){
		int t = d[s][i];
		if(visited[t] == false){
			dfs(t);
			dist--;
			visited[t] = false;
		}
	}
	visited[s] = false;
	return;
}
int main(){
	int N, a, b;
	for(;;){
		scanf("%d", &N);
		if(N == 0) break;
		max_dist = 0;
		for(int i = 0; i < 100; i++) d[i].clear();
		for(int i = 0; i < N; i++){
			scanf("%d %d", &a, &b);
			a--; b--;
			d[a].push_back(b);
			d[b].push_back(a);
		}
		for(int i = 0; i < 100; i++){
			fill(visited, visited + 100, false);
			dist = 0;
			dfs(i);
		}
		printf("%d\n", max_dist);
	}
	return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
#define fst first
#define snd second
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> inline int Log2(T& x) {int k; for(k=0; (T(1)<<k)<=x; ++k); return k;} // number of binary digits


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

  VV to(N), ot(N);
  for (int i = 0; i < M; ++i) {
    int u, v; cin >> u >> v;
    u--; v--;
    to[u].push_back(v);
    ot[v].push_back(u);
  }

  Vld E(N);
  drep(u, N-1) {
    ld x = 0;
    for (auto v : to[u]) x += E[v];
    E[u] = x / to[u].size() + 1;
  }

  Vld p(N);
  p[0] = 1;
  rep(u, N-1) for (auto v : to[u]) p[v] += p[u] / to[u].size();

  ld cmax = 0;
  rep(u, N-1) {
    int d = to[u].size();
    if (d <= 1) continue;
    for (auto v : to[u]) chmax(cmax, p[u] / (d - 1) * (E[v] - E[u] + 1));
  }

  ld ans = E[0] - cmax;
  cout << setprecision(12);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
N = int(input())
A = list(map(int, input().split()))
inf = 10**18

x = N % 2 + 1
dp = [[-inf] * 4 for _ in range(N + 10)]
dp[0][0] = 0
for i, a in enumerate(A):
    for j in range(x + 1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += a
        dp[i + 1][j] = max(dp[i + 1][j], now)

print(dp[N][x])

Measured memory_bytes: 58496
import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)


Measured memory_bytes: 57688
#include<bits/stdc++.h>
using namespace std;
  
int main(){
  
  int K,S;
  cin >> K >> S;
  
 int ans = 0;
  
  for(int x = 0; x<=K; ++x){
    for(int y =0; y<=K; ++y){
      int z = S - x - y;
      if(0 <= z and z <=K) ans++;
    }
  }

  
  cout << ans << endl;

}

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

#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>

#define rep(i,n)         for(int i=(int)0; i<(int)n; i++)
#define REP(i,m,n)       for(int i=(int)m; i<(int)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define prt(var)         cout << var << endl
#define prtd(n, var)     cout << fixed << setprecision(n) << var << endl
#define prt2(var1, var2) cout << var1 << " " << var2 << endl
#define prtseq(var, n)   rep(i,n){cout << var[i] << " ";} cout << endl
#define prtseql(var, n)  rep(i,n){cout << var[i] << " " << endl;}

//----------------------------------------------------------------

int main(void) {
  int n, k;
  cin >> n >> k;
   string s;
   cin >> s;

   char tg=s[0];
   bool change=false;
   rep(i,n-1){
     if(tg!=s[i+1]){
       if(change){
         s[i+1]=tg;
       } else if(!change && k>0){
         change=true;
         k--;
         s[i+1]=tg;
       }
     } else {
       change=false;
     }
   }

   //prt("--->modified"); prt(s);

   int ans=0;
   char tmp=s[0];
   int ct=1;
   rep(i,n-1){
     if(tmp==s[i+1]){
       ct++;
     } else {
       ans+=ct-1;
       ct=1;
       tmp=s[i+1];
     }
   }
   ans+=ct-1;
   ct=1;
   prt(ans);

}


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

void show(vector<ll>& vc)
{
    for(auto it:vc)cout<<it<<" ";
    cout<<endl;
}
#define M 10
bool p[M+2];
vector<ll>prime;
void seive(void)
{
    memset(p,0,sizeof p);
    p[1]=1;
    p[0]=1;

    for(int i=4; i<=M; i+=2)
    {
        p[i]=1;

    }

    for(ll i=3; i*i<=M; i+=2)
    {

        if(!p[i])
        {

            for(ll j=i*i; j<=M; j+=2*i)
            {
                p[j]=1;

            }
        }
    }

    prime.push_back(2);
    for(int i=3; i<=M; i+=2)prime.push_back(i);
}
ll dx[] = {-1,-1,0,-1,1,0,1,1};
ll dy[] = {-1,0,-1,1,-1,1,0,1};

typedef pair<ll, ll> pii;
#define x first
#define y second


pii extendedEuclid(ll a, ll b)   // returns x, y | ax + by = gcd(a,b)
{
    if(b == 0) return pii(1, 0);
    else
    {
        pii d = extendedEuclid(b, a % b);
        return pii(d.y, d.x - d.y * (a / b));
    }
}

ll modularInverse(ll a, ll n)
{
    pii ret = extendedEuclid(a, n);
    return ((ret.x % n) + n) % n;
}

vector<vector<ll> >vc(100005);
vector<ll>in_degree(100005,0);
vector<bool>visited(100005,0);
vector<ll>dis(100005,0);
void dfs(ll n)
{
    assert(!visited[n]);
    visited[n] = true;
    for(auto b: vc[n])
    {
        dis[b] = max ( dis[b] , dis[n ] + 1);
        in_degree[b]--;
        if(in_degree[b]== 0)dfs(b);
    }
}

void solve(ll t)
{
    ll n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        ll a,b;
        cin>>a>>b;

        vc[a].push_back(b);
        in_degree[b]++;
    }

    for(int i=1;i<=n;i++)
    {
        if(!visited[i] && in_degree[i]==0)dfs(i);
    }

     ll ans=  0;
    for(int i=1;i<=n;i++)
    {
        ans = max(ans , dis[i]);
    }

    cout<<ans<<endl;



}


int main()
{

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

    //seive();


    ll t=1;
    //cin>>t;
    ll T=t;



    while(t--)
    {


        solve(T-t);

    }
}


Measured memory_bytes: 10496
#include <iostream>
using namespace std;
using ll = long long;

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

  if( S == T.erase(T.length()-1)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
	int x, a, b;
  cin >> x >> a >> b;
  if(abs(x-a)>abs(x-b)) cout << 'B' << endl;
  else cout << 'A' << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int count = 0;
		for(int i = 0; i < n; i++){
			if(sc.nextInt() >= k){
				count++;
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 42944
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>

int N;
int64_t a[3001];
int64_t dp[3001][3001];

int main() {
  std::cin >> N;
  for (int i = 0; i < N; ++i)
    std::cin >> a[i];
  for (int i = 0; i < N; ++i) {
    for (int j = i; j >= 0; --j) {
      if (i == j) {
        dp[j][i] = a[i];
      } else {
        dp[j][i] = std::max(a[j] - dp[j+1][i], a[i] - dp[j][i-1]);
      }
    }
  }
  std::cout << dp[0][N-1] << '\n';
}


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

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		double x1,y1,x2,y2,x3,y3;
		scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);

		double x,y;
		double ax,ay,am,bx,by,bm;


		if(y1==y2){
			x = (x1+x2)/2;
			bx = (x2+x3)/2;
			by = (y2+y3)/2;
			bm = -(x2-x3)/(y2-y3);
			y = bm*(x-bx)+by;
		}else if(y2==y3){
			x = (x2+x3)/2;
			ax = (x1+x2)/2;
			ay = (y1+y2)/2;
			am = -(x1-x2)/(y1-y2);
			y = am*(x-ax)+ay;
		}else{
			ax = (x1+x2)/2;
			ay = (y1+y2)/2;
			am = -(x1-x2)/(y1-y2);	
			bx = (x2+x3)/2;
			by = (y2+y3)/2;
			bm = -(x2-x3)/(y2-y3);

			x = (am*ax-bm*bx-ay+by)/(am-bm);
			y = am*(x-ax)+ay;
		}
		
		printf("%.3lf %.3lf %.3lf\n", x, y, sqrt(pow(x1-x, 2)+pow(y1-y,2)));
	}
}

Measured memory_bytes: 0
from collections import deque
a = list(input())
b = list(input())
c = list(input())

a = deque(a)
b = deque(b)
c = deque(c)

x = 'a'
while True:
    if x == 'a':
        if a:
            x = a.popleft()
        else:
            print('A')
            exit()
    elif x == 'b':
        if b:
            x = b.popleft()
        else:
            print('B')
            exit()
    else:
        if c:
            x = c.popleft()
        else:
            print('C')
            exit()


Measured memory_bytes: 9168
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint int
using namespace std;
     
typedef long long lo;
     
template<typename tp> inline void read(tp &x) {
	x = 0; char c = getchar(); int f = 0;
	for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
	for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
	if (f) x = -x;
}

const int N = 3e5 + 233;
lo ans;
int n;
char str[N];

inline void doit(vector <int> c) {
	int s = 0;
	for (int i = (int) c.size() - 1; i >= 0; i--) {
		s += c[i] == 3;
		ans += (c[i] == 1) * s;
	}
}

int main(void) {
	scanf("%s", str + 1);
	n = strlen(str + 1);
	vector <int> cur;
	rep (i, n) {
		int ban = 0;
		if (str[i] == 'A') {
			if (!cur.empty() && cur.back() == 2) {
				cur.pop_back();
				doit(cur);
				cur.clear();
			}
			cur.push_back(1);
		} else if (str[i] == 'B') {
			if (cur.empty() || cur.back() == 2) {
				ban = 1;
			} else {
				cur.push_back(2);
			}
		} else if (str[i] == 'C') {
			if (cur.empty() || cur.back() != 2) {
				ban = 1;
			} else {
				cur.pop_back();
				cur.push_back(3);
			}
		}
		if (ban) {
			// cout << "i = " << i << "\n";
			// for (int i : cur) cout << i << " "; cout << "\n";
			doit(cur);
			cur.clear();
		}
	}
	doit(cur);
	cout << ans << "\n";
}


Measured memory_bytes: 2164
#include<stdio.h>
  #define MAX 100
#define INF 1000000
#define white 0
#define gray 1
#define black 2
  
int n, u;
int M[MAX][MAX];
 
 
void MST(void);
 
 
 
int main(){
   
  int i,j,k;
  int v,c;
  
  scanf("%d",&n);
  
  for(i = 0 ;i < n;i++){
    for(j = 0;j < n;j++){
      M[i][j] = INF;
    }
  }
  
  for(i = 0;i < n;i++){
    scanf("%d %d",&u,&k);
    for(j = 0;j < k;j++){
      scanf("%d %d",&v,&c);
      M[u][v] = c;
    }
  }
  
  MST();
  
  return 0;
}
  
void MST(){
   
  int i;
  int min;
  int d[MAX];
  int color[MAX] = {white};
  
  for(i = 0;i < n;i++){
    d[i] = INF;
  }
  
  d[0] = 0;
  color[0] = gray;
  
  while(1){
 
    min = INF;
    u = -1;
 
    for(i = 0;i < n;i++)
      if(min > d[i] && color[i] != black){
    u = i;
    min = d[i];
      }
    if(u == -1)break;
    color[u] = black;
    for(i = 0;i < n;i++)
      if(color[i] != black && M[u][i] != INF){
    if(d[i] > d[u] + M[u][i]){
      d[i] = d[u] + M[u][i];
      color[i] = gray;
    }
      }
  }
   
  for(i = 0;i < n;i++){
    if(d[i] == INF)printf("%d -1\n",i);
    else printf("%d %d\n",i,d[i]);
  }
  
}

Measured memory_bytes: 636
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cstring>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

using namespace std;

const int N_MAX = 1000001;
int dp[20][N_MAX];
int money[N_MAX];

int return_pow_max(int n, int d){
  int ret = 0;
  while(pow(d, ret) <= n){
    ret++;
  }
  ret--;
  return ret;
}

int main(){
  int n;
  cin >> n;
  
  int nine_max_ix = return_pow_max(n, 9);
  int six_max_ix = return_pow_max(n, 6);

  int money_ix = 0;
  money[money_ix] = 1;
  money_ix++;
  
  rep(i, 1, six_max_ix+1){
    money[money_ix] = pow(6, i);
    money_ix++;
  }
  
  rep(i, 1, nine_max_ix+1){
    money[money_ix] = pow(9, i);
    money_ix++;
  }
  
  // dp[i][j] ... using up to i-th index
  
  rep(row, 0, money_ix+1){
    dp[row][0] = 0;
  }
  
  rep(col, 1, n+1){
    dp[0][col] = 0;
    dp[1][col] = col;
  }
  
  rep(row, 1, money_ix){
    rep(col, 0, n+1){
      dp[row+1][col] = INT_MAX;
      if(col - money[row] >= 0){
	int max_k = col/money[row];
	dp[row+1][col] = min(dp[row][col]+1,
			     min(dp[row][col-money[row]]+1,
				 dp[row+1][col-money[row]]+1));
	dp[row+1][col] = min(dp[row][col], dp[row+1][col]);
	//rep(k, 0, max_k+1){
	  //dp[row+1][col] = min(dp[row][col]+1,
	  //		       min(dp[row][col-money[row]]+1, dp[row][col])); // use or not use
	//dp[row+1][col] = min(dp[row][col-k*money[row]]+k, min(dp[row][col], dp[row+1][col]));
	//}
      }
      else{
	dp[row+1][col] = dp[row][col]; // not use
      }
    }
  }
  /*
  rep(row, 0, money_ix+1){
    rep(col, 0, n+1){
      cout << dp[row][col] << " ";
    }
    cout << endl;
    }*/
 
  cout << dp[money_ix][n] << endl;
  
  return 0;
}


Measured memory_bytes: 35072
import java.util.*;class Main{public static void main(String[]z){int[]n=new int[100];int x=0,y,i,j;for(Scanner s=new Scanner(System.in);s.hasNext();x=y)for(z=s.next().split(","),i=0;i<(y=z.length);n[j+(x<y?1:0)]=Math.max(n[j],n[j+1])+new Integer(z[j-(x>y?1:0)]),i++)j=x<y?y-1-i:i+1;Arrays.sort(n);System.out.println(n[99]);}}

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

int main() {
  long long X,Y,res;
  cin >> X >> Y;
  bool flag = true;
  res = 0;
  
  while(flag){
      if(X > Y){
        flag = false;
      }else{
        res ++;
        X *= 2; 
      }
  }
  cout << res << endl;
}

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

using namespace std;

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

int main()
{
	for(int n;cin>>n,n;){
		vector<string> ss(n);
		rep(i,n) cin>>ss[i];
		
		{
			sort(begin(ss),end(ss));
			ss.erase(unique(begin(ss),end(ss)),end(ss));
			n=ss.size();
			vector<int> flg(n);
			rep(i,n) rep(j,n) if(i!=j && ss[i].find(ss[j])!=-1)
				flg[j]=1;
			per(i,n) if(flg[i])
				ss.erase(begin(ss)+i);
			n=ss.size();
		}
		
		vector<vector<int>> d(n,vector<int>(n));
		rep(i,n) rep(j,n){
			d[i][j]=ss[j].size();
			if(ss[i].size()<ss[j].size()){
				per(k,ss[i].size())
					if(ss[i].substr(k)==ss[j].substr(0,ss[i].size()-k))
						d[i][j]=ss[j].size()-(ss[i].size()-k);
			}
			else{
				rep(k,ss[j].size())
					if(ss[i].substr(ss[i].size()-(k+1))==ss[j].substr(0,(k+1)))
						d[i][j]=ss[j].size()-(k+1);
			}
		}
		
		vector<int> p(n);
		iota(begin(p),end(p),0);
		string res(101,'z');
		do{
			int len=ss[p[0]].size();
			rep(i,n-1) len+=d[p[i]][p[i+1]];
			if(res.size()>=len){
				string tmp=ss[p[0]];
				rep(i,n-1) tmp+=ss[p[i+1]].substr(ss[p[i+1]].size()-d[p[i]][p[i+1]]);
				if(res.size()>tmp.size() || res.size()==tmp.size() && res>tmp)
					res=tmp;
			}
		}while(next_permutation(begin(p),end(p)));
		
		cout<<res<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	int c=0;
	getline(cin,s);
	for(int i=0;i<s.size();++i){
	if(s[i]=='C')
	c++;
	if(s[i]=='F'&&c){
		printf("Yes");
		return 0;
	}
	}
	printf("No");
	return 0;
}

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

int main(){
  int a,b,c;
  int i=1;
  int flag = -1;
  cin >> a >> b >> c;
  int tmp;
  
  tmp = a%b;
  bool roop=true;
  while(roop==true){
    if(c == (tmp*i)%b){
      flag = 1;
      roop = false;
    }
    else if(tmp == (tmp*i)%b && i > 1) roop = false;
    i++;
  }
  if(flag==1) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt(), ans = 0;
        for (int i = 0, max = 0, h; i < n; i++) {
            if (max <= (h = scanner.nextInt())) {
                ans++;
                max = h;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
h,k=list(map(int,input().split()))
def bupdp(l,h,k):
    dp=[0]*(h+1)
    dp[0] = 0
    for i in range(0,h):
        if i>k:
            mini = min([dp[i-j]+abs(l[i]-l[i-j]) for j in range(1,k+1)])             
            dp[i] = mini
        if i<=k and i!=0:
            minim = min([dp[i-j]+abs(l[i]-l[i-j]) for j in range(1,i+1)])
            dp[i] = minim
        if i<1:
            dp[i] = 0
    return dp[-2]

l = list(map(int,input().split()))
print(bupdp(l,h,k))

Measured memory_bytes: 20688
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/


int main() {
	
	int t, a, b;
	scanf("%d%d%d", &t, &a, &b);
	printf("%d\n", min(t * a, b));
	
	Please AC;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
   public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);
     int  N = sc.nextInt();
     int i=0,j,ans=0;
     int Nhold=N;
     while(N>0){
       N=N/10;
       i++;
     }
     if(i%2==1){
       ans+=Nhold-Math.pow(10,i-1)+1;
       i--;
     }
     for(j=1;j<i;j+=2){
       ans+=Math.pow(10,j)-Math.pow(10,j-1);
     }
     System.out.println(ans);
   }
}


Measured memory_bytes: 21588
A, B, C, K = [int(_) for _ in input().split()]

l = A + B + C - K

def solve(A, B, C, K):
    result = 0
    n = min(A, K)
    result += n
    K -= n
    A -= n
    if K == 0:
        return result
    n = min(B, K)
    K -= n
    B -= n
    if K == 0:
        return result
    n = min(C, K)
    result -= n
    K -= n
    C -= n
    return result

print(solve(A, B, C, K))

Measured memory_bytes: 9196
#include "stdio.h"
 
int main(void){
	int N, V[50], C[50], res = 0;
	scanf("%d\n", &N);
	for(int i = 0;i < N - 1;i++){
		scanf("%d ", &V[i]);
	}
	scanf("%d\n", &V[N - 1]);
	for(int i = 0;i < N - 1;i++){
		scanf("%d ", &C[i]);
	}
	scanf("%d", &C[N - 1]);
	for(int i = 0;i < N;i++){
		if(V[i] - C[i] > 0){
        	res += V[i] - C[i];
        }
	}
	printf("%d", res);
}

Measured memory_bytes: 128
gakuen_list = [[[0 for i in range(10)]for j in range(3)]for n in range(4)]
y = int(input())
l = 0
for i in range(y):
    a,b,c,x = input().split(" ")
    a = int(a)
    b = int(b)
    c = int(c)
    c -= 1
    q = gakuen_list[a - 1][b - 1][c]
    q = int(q)
    if q != 0:
        q += int(x)
        gakuen_list[a - 1][b- 1][c] = q
    else:
        gakuen_list[a - 1][b- 1][c] = x
        continue
for img in gakuen_list:
    for line in img:
        for dot in line:
            print(" " + str(dot),end="")
        print()
    if l == 3:
        break
    else:
        l += 1
        for n in range(20):
            print("#",end="")
    print()
    


Measured memory_bytes: 5632
#include<iostream>
#include<string>
using namespace std;
int main() {
  int n, ans=0;
  string s;
  cin>>n>>s;
  
  for(int i=0; i<n-2; i++){
    if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C'){
      ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
#define reps(i,s,n) for(int (i) = (s); (i) < (n); ++(i))
#define rep(i,n) reps(i,0,n)
using ll = long long;

int main(){
    int n ,T;
    ll ans = 0;
    cin >> n >> T;
    vector<int> t(n,0);
    
    for(int i = 0; i < n; i++) cin >> t[i];
    ans = T;
    for(int j = 0; j < n - 1; j++){
        if(t[j] + T > t[j+1]) {
            ans += (T - (t[j] + T -t[j+1]));
        }else{
            ans += T;
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t x,t;
    cin >> x >> t;
    cout << (x>t?x-t:0) << endl;
}


Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

std::string S;

int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);

    in >> S;
    for (size_t i = 0; i < S.size(); i++)
    {
        out << 'x';
    }
    out << endl;

    return 0;
}
#endif


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int H,W,i,j;
    
    3 <= H;
    W <= 300;
    
    while(1){
        scanf("%d %d", &H,&W);
        if (H == 0 && W == 0){
            break;
        }
    for (i = 1; i <= H; i++)
    {
        for (j = 1; j <= W; j++)
    {
        if (i > 1 && i < H && j < W && j > 1)
         printf(".");
        else
         printf("#");
    }    
        printf("\n");
    }
    printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2056