akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

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

	void run() {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();
		char[][] A = new char[H][W];
		for (int i = 0; i < H; ++i) {
			A[i] = sc.next().toCharArray();
		}
		int sh = -1, sw = -1;
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if (A[i][j] == 'S') {
					sh = i;
					sw = j;
				}
			}
		}

		int[][] d = new int[H][W];
		for (int i = 0; i < d.length; ++i) {
			for (int j = 0; j < d[i].length; ++j) {
				d[i][j] = Integer.MAX_VALUE / 16;
			}
		}
		d[sh][sw] = 0;
		class P {
			int h, w;

			public P(int h, int w) {
				this.h = h;
				this.w = w;
			}
		}

		ArrayDeque<P> que = new ArrayDeque<>();
		que.add(new P(sh, sw));
		while (!que.isEmpty()) {
			P p = que.poll();
			for (int i = 0; i < 4; ++i) {
				P np = new P(p.h + dy[i], p.w + dx[i]);
				if (!movable(np.h, np.w, A))
					continue;
				if (d[np.h][np.w] > d[p.h][p.w] + 1 && d[p.h][p.w] + 1 <= K) {
					d[np.h][np.w] = d[p.h][p.w] + 1;
					que.add(np);
				}
			}
		}

		int ans = Integer.MAX_VALUE / 16;
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if (d[i][j] > K)
					continue;
				ans = Math.min(ans, 1 + (f(i, j, H, W) + K - 1) / K);
			}
		}
		System.out.println(ans);
	}

	int f(int h, int w, int H, int W) {
		int ret = Integer.MAX_VALUE / 16;
		ret = Math.min(ret, h);
		ret = Math.min(ret, H - 1 - h);
		ret = Math.min(ret, w);
		ret = Math.min(ret, W - 1 - w);
		return ret;
	}

	boolean movable(int h, int w, char[][] map) {
		if (h < 0 || w < 0 || h >= map.length || w >= map[0].length) {
			return false;
		}
		if (map[h][w] == '#') {
			return false;
		}
		return true;
	}

	private static void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
}


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

using namespace std;

int main(void){
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a,a+3);
  if((a[0]==a[1]&&a[0]!=a[2])||(a[1]==a[2]&&a[0]!=a[2]))
    cout << "Yes";
  else
    cout << "No";
  return 0;
}


Measured memory_bytes: 256
#include <stdlib.h>

int happ(int money);
int main(void);

int happ(int money){
   int new, p, q;
   p = money/500;
   new = money%500;
   q = new/5;
   return (1000*p + 5*q);
}

int main(void){
   int money, r;
   scanf("%d", &money);
   r = happ(money);
   printf("%d", r);
   return 0;
}


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

using namespace std;

typedef pair< int, int >	pii;

vector< pii > v[1000];
string s;
int n, k;

bool compar(pii a, pii b){
	if((a.first == 0 || a.second == n - 1) && (b.first != 0 && b.second != n - 1)){
		return false;
	}

	if((b.first == 0 || b.second == n - 1) && (a.first != 0 && a.second != n - 1)){
		return true;
	}

	return a.first < b.first;
}

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

	cin >> n >> k;

	cin >> s;

	int n = int(s.length());

	int st = 0;
	char c = s[0];

	for(int i = 0 ; i < n ; i++){
		if(s[i] != c){
			v[c].push_back({st, i - 1});
			st = i;	
		}

		c = s[i];
	}

	v[c].push_back({st, n - 1});

	sort(v['L'].begin(), v['L'].end(), compar);
	sort(v['R'].begin(), v['R'].end(), compar);

	if(v['L'].size() < v['R'].size()){
		int mn = min(int(v['L'].size()), k);

		for(int d = 0 ; d < mn ; d++){
			for(int e = v['L'][d].first ; e <= v['L'][d].second ; e++){
				s[e] = 'R';
			}
		}
	}else{
		int mn = min(int(v['R'].size()), k);

		for(int d = 0 ; d < mn ; d++){
			for(int e = v['R'][d].first ; e <= v['R'][d].second ; e++){
				s[e] = 'L';
				// printf("e: %d\n", e);
			}
		}
	}

	int cnt = 0;

	for(int i = 1 ; i < n ; i++){
		if(s[i] == s[i - 1]){
			cnt++;
		}
	}

	printf("%d\n", cnt);

	return 0;
}

Measured memory_bytes: 1356
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000009
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define rollcall cout<<"I'm Sucu."<<endl
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define int ll

signed main(void){
   int N;
   int Ans=0;
   int A[104];
   cin >> N;
   REP(i,N){cin >> A[i];}
   REP(i,N){REP(j,N){
       Ans=max(Ans,abs(A[i]-A[j]));
   }}
   cout << Ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using namespace std;
using ll = long long;
using Edge = pair<int,long long>;
using Graph = vector<vector<Edge>>;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
    int N,W;
    cin >> N >> W;
    vector<int> w(N),v(N);
    rep(i,N) cin >> w[i] >> v[i];
    ll DP[N+10][W+10];
    rep(i,N+1) rep(j,W+1) DP[i][j] = 0;
    
    rep(j,W+1) if(j >= w[0]) DP[0][j] = v[0];
    
    rep1(i,N-1) rep1(j,W){
        if(j-w[i] >= 0) DP[i][j] = max(DP[i-1][j], DP[i-1][j-w[i]]+v[i]);
        else DP[i][j] = DP[i-1][j];
    }    

    pr(DP[N-1][W]);
}


Measured memory_bytes: 80768
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define pi 4*atan(1.0)
#define rep(i,n) for(int i=0;i<n;i++)

double a,b,c,d;

int main(){
	while(cin>>a>>b>>c>>d&&!(a==-1&&b==-1&&c==-1&&d==-1)){
		a*=pi/180;b*=pi/180;c*=pi/180;d*=pi/180;
		double x1=cos(a)*cos(b),Y1=cos(a)*sin(b),z1=sin(a),x2=cos(c)*cos(d),y2=cos(c)*sin(d),z2=sin(c);
		double dist=sqrt((x1-x2)*(x1-x2)+(Y1-y2)*(Y1-y2)+(z1-z2)*(z1-z2));
		printf("%.0f\n",2*asin(dist/2.0)*6378.1);
	}
}

Measured memory_bytes: 0
/*
* @Author: key
* @Date:   2016-03-04 11:52:34
* @Last Modified by:   key
* @Last Modified time: 2016-03-04 12:49:05
*/

#include <iostream>

using namespace std;

int c[10];

int a[10],b[10];

bool flag;

void dfs(int x,int y,int z){
    if(x > 9){
        flag = true;
        return;
    }

    if(flag)
        return;

    if(y < 0 || c[x] > a[y]){
        a[y+1] = c[x];
        dfs(x+1,y+1,z);
    }

    if(z < 0 || c[x] > b[z]){
        b[z+1] = c[x];
        dfs(x+1,y,z+1);
    }

}

int main(){

    int n;

    cin >> n;

    while(n--){
        flag = false;
        for(int i = 0; i < 10; i++){
            cin >> c[i];
            a[i] = 0;
            b[i] = 0;
        }
        dfs(0,-1,-1);
        if(flag)
            cout << "YES" <<endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

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

int N, M, ans;
vector<int> G[8];

void dfs(int v, int p, int b) {
	if(b == (1 << N) - 1) {
		ans++;
		return;
	}
	for(auto c : G[v]) {
		if(~b >> c & 1) {
			dfs(c, v, b ^ (1 << c));
		}
	}
}

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

	cin >> N >> M;

	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	dfs(0, -1, 1);
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Map<String, Integer> map = new HashMap<>();
    for(int i = 0; i < n; i++) {
      String str = sc.next();
      if(map.containsKey(str)) {
        map.put(str, map.get(str) + 1);
      } else {
        map.put(str, 1);
      }
    }
    int m = sc.nextInt();
    for(int i = 0; i < m; i++) {
      String str = sc.next();
      if(map.containsKey(str)) {
        map.put(str, map.get(str) - 1);
      }
    }
    int ans = 0;
    for(Map.Entry<String, Integer> entry : map.entrySet()) {
      if(ans < entry.getValue()) ans = entry.getValue();
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
N, M = map(int, input().split())
H = list(map(int, input().split()))
check = [1]*N
for m in range(M):
  ab =  list(map(int, input().split()))
  if H[ab[0]-1] > H[ab[1]-1]:
    check[ab[1]-1] = 0
  elif H[ab[1]-1] > H[ab[0]-1]:
    check[ab[0]-1] = 0
  elif H[ab[1]-1] == H[ab[0]-1]:
    check[ab[0]-1] = 0
    check[ab[1]-1] = 0
print(sum(check))

Measured memory_bytes: 20136
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,n,m) for(int i=n;i<int(m);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
 
int vx[]={0,0,-1,1};
int vy[]={1,-1,0,0};
int dx[]={1,0,-1,1,-1,1,0,-1};
int dy[]={1,1,1,0,0,-1,-1,-1};
 
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}	
 
const ll mod=1e9+7;
const int INF=INT_MAX/2;

int main(){
    int N;
    cin>>N;
    if(N%2==0)cout<<N/2<<endl;
    else cout<<N/2+1<<endl;
}
 

Measured memory_bytes: 256
#include <iostream>
long gcm(long a,long b){
	if (b==0) return a;
	return gcm(b,a%b);
}
 
int main(void){
	long a,b,x;
	while (std::cin>>a>>b){
		x=gcm(a,b);
		std::cout<<x<<" "<<a/x*b<<"\n";
	}
}

Measured memory_bytes: 1160
use std::io::*;
use std::str::FromStr;

fn mod_pow(x: usize, n: usize, mod_: usize) -> usize {
    if n > 0 {
        mod_pow(x * x % mod_, n >> 1, mod_) * if n & 1 == 1 { x } else { 1_usize } % mod_
    } else {
        1_usize
    }
}

fn main() {
    let n: usize = read();
    let a: Vec<usize> = (0..n).map(|_| read()).collect();

    let mo = 10_usize.pow(9) + 7;

    let mut f: Vec<usize> = vec![1; n+1];
    let mut k_i: Vec<usize> = vec![0; n+1];
    for i in 1..n+1 {
        f[i] = (f[i-1] * i) % mo;
        k_i[i] = k_i[i-1] + mod_pow(i, mo - 2, mo);
        k_i[i] %= mo;
    }

    let mut ans = 0;
    for i in 0..n {
        ans += (a[i] * (k_i[i+1] + k_i[n-i] - 1)) % mo;
        ans %= mo;
    }
    ans *= f[n];
    ans %= mo;
    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 6524
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func f(a int) int {
	if a > 0 {
		return 1
	} else if a < 0 {
		return -1
	}
	return 0
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
	sc.Split(bufio.ScanWords)

	n := getInt()
	a := make([]int, n)

	for i := 0; i < n; i++ {
		a[i] = getInt()
	}

	sign := -1
	ans := [2]int{0, 0}
	for k := 0; k < 2; k++ {
		if k == 0 {
			sign = -1
		} else {
			sign = 1
		}
		sum := 0
		for i := 0; i < n; i++ {
			sum += a[i]
			if sign == 1 {
				if sum >= 0 {
					ans[k] += 1 + sum
					sum = -1
				}
			} else {
				if sum <= 0 {
					ans[k] += 1 - sum
					sum = 1
				}
			}
			sign = -sign
		}
	}

	fmt.Println(min(ans[0], ans[1]))
}


Measured memory_bytes: 3072
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する


int main() {
    int N;
    cin >> N;
    int cnt[101] = {};
    int ma = -1;
    int mi = 114514;
    rep(i,0,N){
        int tmp;
        cin >> tmp;
        cnt[tmp]++;
        ma = max(ma,tmp);
        mi = min(mi,tmp);
    }
    if(ma % 2){
        if(mi == (ma+1) / 2){
            if(cnt[mi] != 2){
                cout << "Impossible" << endl;
                return 0;
            }
            rep(i,mi+1,ma+1){
                if(cnt[i] < 2){
                    cout << "Impossible" << endl;
                    return 0;
                }
            }
            cout << "Possible" << endl;
        }else{
            cout << "Impossible" << endl;
            return 0;
        }
    }else{
        if(mi == ma/2){
            if(cnt[mi] != 1){
                cout << "Impossible" << endl;
                return 0;
            }
            rep(i,mi+1,ma+1){
                if(cnt[i] < 2){
                    cout << "Impossible" << endl;
                    return 0;
                }
            }
            cout << "Possible" << endl;
        }else{
            cout << "Impossible" << endl;
            return 0;
        }
    }


    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		short[] ab = {sc.nextShort(),sc.nextShort()};
		if(ab[0] > ab[1]){
			System.out.println("a > b");
		}else if(ab[0] == ab[1]){
			System.out.println("a == b");
		}else{
			System.out.println("a < b");
		}
	}
}


Measured memory_bytes: 26220
def sum(n):
    str_n = str(n)
    ans = 0
    for i in range(len(str_n)):
        ans += int(str_n[i])
    return ans

N,A,B = map(int,input().split())

ans1 = 0
for i in range(N+1):
    if A <= sum(i) <= B:
        ans1 += i
    else:
        continue
print(ans1)


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

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

    long long ans = 0;
    for (int i = 0; i < 1 << (S.size() - 1); ++i) {
        long long sum = 0, a = S[0] - '0';
        for (int j = 0; j < S.size() - 1; ++j) {
            if (i & (1 << j)) {
                sum += a;
                a = 0;
            }
            a = a * 10 + (S[j + 1] - '0');
        }
        sum += a;
        ans += sum;
    }

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

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

const int MAX_N=2e5+10;

deque <int> Q1,Q2;
int N,K,P[MAX_N],cnt[MAX_N],ans=0;

int main(){
	scanf("%d%d",&N,&K);
	for(int i=0;i<N;i++) scanf("%d",&P[i]);
	cnt[0]=0;
	for(int i=1;i<N;i++){
		if(P[i]>P[i-1]) cnt[i]=cnt[i-1]+1;
		else cnt[i]=0;
		if(cnt[i]>=K-1) ans=1;
	}
	if(cnt[K-1]!=K-1) ans++;
	for(int i=0;i<N;i++){
		while(Q1.size()&&P[Q1.back()]>P[i]) Q1.pop_back();
		Q1.push_back(i);
		while(Q2.size()&&P[Q2.back()]<P[i]) Q2.pop_back();
		Q2.push_back(i);
		if(i>=K){
			if(Q1.front()!=i-K||Q2.front()!=i)
				if(cnt[i]<K-1) ans++;
			if(Q1.front()==i-K) Q1.pop_front();
			if(Q2.front()==i-K) Q2.pop_front();
		}	
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;

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

using ll = long long;

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

class Radix {
  private:
    const char* s;
    int a[128];
  public:
    Radix(const char* s = "abcdefghijklmnopqrstuvwxyz") : s(s) {
      int i;
      for(i = 0; s[i]; ++i)
        a[(int)s[i]] = i;
    }
    std::string to(long long p, int q) {
      int i;
      if(!p)
        return "0";
      char t[64] = { };
      for(i = 62; p; --i) {
        t[i] = s[(p % q)];
        p /= q;
      }
      return std::string(t + i + 1);
    }
    std::string to(const std::string& t, int p, int q) {
      return to(to(t, p), q);
    }
    long long to(const std::string& t, int p) {
      int i;
      long long sm = a[(int)t[0]];
      for(i = 1; i < (int)t.length(); ++i)
        sm = sm * p + a[(int)t[i]];
      return sm;
    }
};

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  ll N; std::cin >> N;
  
  std::string s;
  for(char c='a'; c<='z'; c++) s += c;

  std::string ans;
  while( N > 0 ) {
    ans += s[ (N-1)%26 ];
    if ( N == 26 ) break;
    if ( N % 26 != 0 ) N /= 26;
    else {
      N = (N-1)/26;
    }
  }
  std::reverse( all(ans) );
  std::cout << ans << std::endl;
  return 0;
}



Measured memory_bytes: 3648
#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

#define MAXN 10012
#define INF 1e+9

typedef struct{
	int exist;
	int none;
}dint;

dint origin[MAXN];
dint buffer[MAXN];
dint *dp = origin;
dint *dpbuf = buffer;
int field[MAXN] = {0};
int length = 0;

int SwapDim1Array(dint **a,dint **b);

int main (void){
	scanf("%d",&length);
	for(int i=0;i<=length;i++){
			dp[i].exist = INF;
			dp[i].none = INF;
			dpbuf[i].exist = INF;
			dpbuf[i].none = INF;
	}
	dp[0].none = 0;
	for(int i=1;i<length;i++){
		scanf("%d",&field[i]);
	}


	for(int i=0;i<length;i++){		//くばるDP
		for(int j=0;j<=i;j++){
			dpbuf[j].exist = INF;
			dpbuf[j].none = INF;
		}
		for(int j=0;j<=i;j++){
			dpbuf[j+1].exist = min(min(dp[j].exist + field[i+1] - field[i] , dp[j].none + field[i] + field[i+1]) , dpbuf[j+1].exist);
			dpbuf[j].none = min(min(dp[j].exist , dp[j].none) , dpbuf[j].none);
			//printf("(%d,%d)\t",dp[j].exist,dp[j].none);
		}//puts("");
		SwapDim1Array(&dp,&dpbuf);
	}
	/*for(int j=0;j<=length;j++){
		printf("(%d,%d)\t",dp[j].exist,dp[j].none);
	}puts("");*/

	int answer = 0;
	answer = min(dp[length/2].exist,dp[length/2].none);
	printf("%d\n",answer);

	return 0;
}

int SwapDim1Array(dint **a,dint **b){
	dint *c;
	c = *a;
	*a = *b;
	*b = c;
	return 0;
}

Measured memory_bytes: 1388
x,n=map(int,input().split())
try:
    p= list(map(int, input().split()))
except:
    print(x)
else:
    for i in range(150):
        if p.count(x)==0:
            print(x)
            exit()
        elif (p.count(x-i)==0):
            print(x-i)
            exit()
        elif(p.count(x+i)==0):
            print(x+i)
            exit()

Measured memory_bytes: 9132
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e10;
const ll MAX_N = 1010;

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
char c[310][310];
ll dp[101];

//long longしか使わない
//素数は1より大きい
//lower_boundは指定したkey以上の要素の一番左のイテレータをかえす
//upper_boundは指定したkeyより大きい要素の一番左のイテレータをかえす
int main() {
	ll n;
	cin >> n;
	vector<ll>a(n);
	ll kabu = 0;
	ll money = 1000;
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n - 1) {
		if (a[i] < a[i + 1]) {
			kabu = money / a[i];
			money -= kabu * a[i];
			money += kabu * a[i + 1];
		}
	}
	cout << money << endl;
	return 0;
}


Measured memory_bytes: 3504
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main() {
	string s;
	cin >> s;
	if (s == "ABC") {
		cout << "ARC" << endl;
		return 0;
	}
	else {
		cout << "ABC" << endl;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 3628
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	char s;
	cin >> s;
		
	if(s == 'a' || s == 'i' || s == 'u' || s == 'e' || s == 'o') cout << "vowel" << endl;
	else cout << "consonant" << endl;
	
	return 0;
}

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

using namespace std;

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    if((n + 1) / 2 >= k) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;

}

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

int main()
{
    double d, t, s;
    double actual_time;

    cin >> d >> t >> s;
    actual_time = 1.0 * d / s;

    if (actual_time <= t)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    //cout << d << " " << t << " " << s << " " << actual_time << endl;

    return 0;
}

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

using namespace std;
using ll =long long;
using db = double;

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

#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(v) SORT(v);(v).erase(unique((v).begin(),(v).end()),(v).end())
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
const int mod = 1e9 + 7;

ll ans;
//ここから書き始める
int main()
{
	//input 
	cout << setprecision(10);
	int n; cin >> n;
	vector<int> leng(n);
	rep(i,n) cin >> leng[i];
	SORT(leng);

	ll ans = 0;
	rep(b,n)rep(a,b){
		int need_leng = leng[a]+leng[b];
		int it  = lower_bound(leng.begin(),leng.end(),need_leng) - leng.begin();
		//			int need_leng_point = upper_bound(leng.begin()+j,leng.end(),need_leng);
		int l = b + 1;
		ans += max(0,it-l) ;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int K; cin >> K;
  int odd = 0, eve = 0;
  for(int i = 1; i <= K; i++){
    if(i%2 == 1){
      odd++;
    }else{
      eve++;
    }
  }
  cout << odd*eve << endl;
}

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

int comp(const int &a, const int &b)
{
	return (a > b);
}

int main()
{
	int n, l[10000];
	int sum = 0;
	
	cin >> n;
	
	for(int i = 0; i < n; i++)
		cin >> l[i];
	sort(l, l + n, comp);
	
	for(int i = 0; i < n - 2; i++)
	{
		int L = i + 1;
		int R = n - 1;
		while(L < R)
		{
			if(l[i] < l[L] + l[R])
			{
				sum += R - L;
				L++;
			}
			else
				R--;
		}
	}
	
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_imports)]
use proconio::input;
use std::cmp::max;
use std::cmp::min;
use std::collections::HashMap;
use std::collections::VecDeque;

fn main() {
    input! {
        mut A: i64,
        mut B: i64,
        mut K: i64,
    }

    if K <= A {
        A -= K;

        println!("{}", A);
        println!("{}", B);
        return;
    }

    K -= A;
    A = 0;
    B -= K;
    B = max(0, B);

    println!("{}", A);
    println!("{}", B);
}


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

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
	string s[3];
	int turn = 0;
	REP(i,3) cin >> s[i];
	while(1){
		if(s[turn].size()==0) break;
		char top = s[turn][0];
		s[turn] = s[turn].substr(1,s[turn].size()-1);
		if(top == 'a') turn = 0;
		else if(top == 'b') turn = 1;
		else turn = 2;
		// cout << top << endl;
	}	
	if(turn == 0) cout << "A" << endl;
	else if(turn == 1) cout << "B" << endl;
	else cout << "C" << endl;
}

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

int dp[300][90000];
int dp2[300][90000];
const int mod = 998244353;

signed main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0; i<N; i++) cin >> a[i];
  int sum = accumulate(a.begin(), a.end(), 0);
  int allcase = 1;
  for (int i=0; i<N; i++)  allcase = (3*allcase) % mod;

  dp[0][a[0]] = 1;
  dp[0][0] = 2;
  for (int i=0; i<N-1; i++) for (int j=0; j<90000-a[i+1]; j++) {
    dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 2) % mod;
    dp[i+1][j+a[i+1]] = (dp[i+1][j+a[i+1]] + dp[i][j]) % mod;
  }

  int count = 0;
  for (int i=(sum+1)/2; i<90000; i++) count = (count + dp[N-1][i]) % mod;

  int ans = (allcase + mod - (count*3)%mod) % mod;

  if(sum % 2 == 0) {
    dp2[0][a[0]] = 1;
    dp2[0][0] = 1;
    for (int i=0; i<N-1; i++) for (int j=0; j<90000-a[i+1]; j++) {
      dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % mod;
      dp2[i+1][j+a[i+1]] = (dp2[i+1][j+a[i+1]] + dp2[i][j]) % mod;
    }
    ans = (ans + mod + (dp2[N-1][sum/2] * 3)%mod) % mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 421376
n=int(input())
a=list(map(int,input().split()))
cnt=0
while True:
    judge=True
    for i in range(n):
        if a[i]%2!=0:
            judge=False
    if judge==False:
        break
    for i in range(n):
        a[i]/=2
    cnt+=1
print(cnt)
        

Measured memory_bytes: 2940
#include <algorithm>
#include <complex>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::cerr;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::stack;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

typedef long long int ll;
const int MOD = 1e9 + 7;

int main() {
    int n, k, x, y;
    cin >> n >> k >> x >> y;

    int ans = 0;
    ans += x * min(k, n);
    ans += y * max(0, n - k);
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 504
n = int(input())
a = list(map(int, input().split()))

data = [0]*(n+1)

for aa in a:
  data[aa] += 1

allans = 0
for d in data:
  if d >= 2:
    allans += (d*(d-1))//2
    
for aa in a:
  if data[aa] == 2:
    print(allans - (data[aa]*(data[aa]-1))//2)
  elif data[aa] > 2:
    print(allans - (data[aa]-1))
  else:
    print(allans)
  

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

int main(){
    vector<vector<int>> a(3, vector<int>(3));
    rep(i,3){
        rep(j,3){
            cin >> a.at(i).at(j);
        }
    }
    int n; cin >> n;
    vector<int> b(n);
    rep(i, n) cin >> b.at(i);
    rep(i, n){
        rep(j, 3){
            rep(k, 3){
                if(b.at(i) == a.at(j).at(k)){
                    a.at(j).at(k) = 0;
                }
            }
        }
    }
    string ans = "No";
    rep(i, 3){
        if((a.at(i).at(0) == 0) &&((a.at(i).at(1) == 0)) && (a.at(i).at(2) == 0)){
            ans = "Yes";
        }else if((a.at(0).at(0) == 0) &&((a.at(1).at(1) == 0)) && (a.at(2).at(2) == 0)){
            ans = "Yes";
        }else if((a.at(2).at(0) == 0) &&((a.at(1).at(1) == 0)) && (a.at(0).at(2) == 0)){
            ans = "Yes";
        }else if((a.at(0).at(i) == 0) &&((a.at(1).at(i) == 0)) && (a.at(2).at(i) == 0)){
            ans = "Yes";
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
int main()
{
    int N,K,num=1;
    scanf("%d %d",&N,&K);
    while(N--)
    {
        if(num*2>num+K)
            num=num+K;
        else
            num=num*2;
    }
    printf("%d\n",num);
    return 0;
}

Measured memory_bytes: 256
import Control.Applicative
import qualified Control.Monad as Monad

main = loop

loop :: IO ()
loop = do
    [h,w] <- map (read :: String -> Int) . words <$> getLine
    Monad.when (h /= 0 || w /= 0) $ do
        printFrame h w
        loop

printFrame :: Int -> Int -> IO ()
printFrame h w = do
    Monad.forM_ [1..h] $ \i -> do
        putStrLn $ frameOrDot h w i
    putStrLn ""

frameOrDot :: Int -> Int -> Int -> String
frameOrDot h w i = if (i == 1 || i == h)
                     then concat . take w $ repeat "#"
                     else "#" ++ (concat . take (w-2) $ repeat ".") ++ "#"


Measured memory_bytes: 4164
// ctrl+shift+b
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    vector<ll> X(3); rep(i, 3){cin >> X.at(i);}
    sort(X.begin(), X.end());
    cout << X.at(0) + X.at(1) + 10 * X.at(2) << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3632
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    a: i64,
    b: i64,
  }
  let d = a - b;
  if d % 2 == 0 {
    puts!("{}\n", b + d / 2);
  } else {
    puts!("IMPOSSIBLE\n");
  }
}


Measured memory_bytes: 4352
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = (1 << 17) + 10;
int fa[N] , v[N] , n;
vi son[N];
vector<pii> evt[N];

void ins(vector<pii>&a,pii x){
    if(sz(a) == 0) a.pb(x);
    else if(x.fi > a.back().fi && a.back().se > x.se) a.pb(x);
    else if(x.fi == a.back().fi) a.back().se = min(a.back().se , x.se);
}

bool check(int lim){
    for(int c=n;c>=1;--c){
        evt[c].clear();
        if(sz(son[c])){
            int lson = son[c][0] , rson = son[c][1];
            if(sz(evt[lson]) > sz(evt[rson])) swap(lson , rson);
            vector<pii> &A = evt[lson] , &B = evt[rson] , C , D;
            for(int i=0,j=0;i<sz(A);++i){
                while(j < sz(B) && A[i].se + B[j].fi + v[lson] + v[rson] <= lim) ++j;
                if(j) C.pb(mp(A[i].fi + v[lson] , B[j-1].se + v[rson]));
            }
            for(int i=0,j=0;i<sz(A);++i){
                while(j < sz(B) && A[i].fi + B[j].se + v[lson] + v[rson] > lim) ++j;
                if(j < sz(B)) D.pb(mp(B[j].fi + v[rson] , A[i].se + v[lson]));
            }
            for(int i=0,j=0;i<sz(C)||j<sz(D);){
                if(j == sz(D) || (i < sz(C) && C[i].fi <= D[j].fi)) ins(evt[c] , C[i++]);
                else ins(evt[c] , D[j++]);
            }
        } else evt[c].pb(mp(0 , 0));
    }
    return sz(evt[1]);
}

int main(){
    scanf("%d",&n);
    rep(i,2,n+1) scanf("%d%d",fa + i , v + i) , son[fa[i]].pb(i);
    int l = -1 , r = N * 34;
    check(6);
    while(l + 1 < r){
        int m = (l + r) >> 1;
        check(m) ? r = m : l = m;
    }
    printf("%d\n",r);
    return 0;
}


Measured memory_bytes: 22628
#include <iostream>

using namespace std;

int main() {
  int a, b, c, d, count;
  cin >> a >> b >> c >> d;

  count = 0;
  while(true){
    if(count%2 == 0){
      c -= b;
      if(c<=0){
        cout << "Yes" << endl;
        break;
      }
    }else{
      a -= d;
      if(a<=0){
        cout << "No" << endl;
        break;
      }
    }
    count += 1;
  }

  return 0;
}


Measured memory_bytes: 3620
#include <iostream>

using namespace std;

int main() {
  char c[3][4];
  for (int i = 0; i < 3; i++)
    cin >> c[i];

  for (int i = 0, j = 0; i < 3; i++, j++) 
      cout << c[i][j];

  cout << endl;

  return 0;
}

    
    

    
    


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>

using namespace std;

void solve()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	bool used[10000];
	memset(used, 0, sizeof(used));
	int n;
	cin >> n;
	vector<char> s(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> s[i];
	}
	for (int i = 0; i < n; ++i)
	{
		int digit = 0;
		for (int j = 0; j < 4 && i + j < n; ++j)
		{
			digit = digit * 10 + s[i + j] - '0';
			used[digit] = true;
		}
	}
	int pos = 0;
	while (true)
	{
		if (used[pos] == 0)
		{
			cout << pos << endl;
			return;
		}
		++pos;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1216
#include <iostream>
//#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}
//void chmin(ll &a,ll b){if(a>b) a = b ;}

int main(){
	string s ; cin >> s ;
	ll n = s.size() ;
	vll dp1(n+1,INF),dp2(n+1,INF) ;
	dp1.at(0) = 0 ;
	dp2.at(0) = 1 ;
	for(int i=1;i<=n;i++){
		ll num = s.at(i-1)-'0' ;
		dp1.at(i) = min(dp1.at(i-1)+num,dp2.at(i-1)+10-num) ;
		dp2.at(i) = min(dp1.at(i-1)+num+1,dp2.at(i-1)+9-num) ;
	}
	cout << dp1.at(n) << endl ;
}


Measured memory_bytes: 17028
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		int n = fs.nextInt();
		if(n == 1) {
			System.out.println("Hello World");
			return;
		}
		
		int a = fs.nextInt();
		int b = fs.nextInt();
		System.out.println(a+b);
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


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

int main() {
  int a;
  cin >> a;
  int result;
  // １００の位の結果を保存
  result = a / 100;
  // 10の位の結果を保存
  a -= (result * 100);
  result += a / 10;
  // 1のくらいの結果を保存
  result += a % 2;

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

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

int main()
{
    ll N; 
    cin >> N;
    ll a[N];
    ll sum = 0;
    for(int i = 0; i < N; i++)
    {
        cin >> a[i];
        sum += a[i] - 1;
    }
    
    cout << sum << endl;
    return 0;
}

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

bool is_match(int i, int *ps) {
    int a = ps[i];
    int b = ps[i + 1];
    int c = ps[i + 2];
    if (b > a && b > c) {
        return false;
    }
    if (b < a && b < c) {
        return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int ps[n];
    for (int i = 0; i < n; i++) {
        cin >> ps[i];
    }
    int count = 0;
    for (int i = 0; i < n - 2; i++) {
        if (is_match(i, ps)) {
            count++;
        }
    }
    cout << count << "\n";
    return 0;
}


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

const int maxn=100010;
int n,m,ans[maxn],f[maxn],head[maxn],tot;
struct node
{
	int nxt,to,id;
}edge[maxn<<1];

void add(int u,int v,int id)
{
	edge[++tot]=(node){head[u],v,id};
	head[u]=tot;
}

void dfs(int u,int fa)
{
	int i,v,j=0;
	for (i=head[u];i;i=edge[i].nxt)
	{
		v=edge[i].to;
		if (v==fa)
			continue;
		++j;
		if (j>m)
			m++;
		if (f[u]==j)
		{
			++j;
			if (j>m)
				m++;
		}
		f[v]=j;
		ans[edge[i].id]=j;
		dfs(v,u);
	}
}

int main()
{
	int i,j,u,v;
	scanf("%d",&n);
	for (i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v,i),add(v,u,i);
	}
	dfs(1,0);
	printf("%d\n",m);
	for (i=1;i<=n-1;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 5120
#include<stdio.h>

int n,A[2000000+1];

void maxHeapify(int);

int main(){
  int i;

  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
}

  for(i=n/2;i>=1;i--){
    maxHeapify(i);
  }
  for(i=1;i<=n;i++){
    
    printf(" %d",A[i]);
    }
  printf("\n");

  return 0;
}

void maxHeapify(int i){
  int l,r,larg,tmp;

  l = 2 * i;
  r = 2 * i + 1;

  if(l <= n && A[l] > A[i]){
      larg = l;
  }
  else {
      larg = i;
}
  if(r <= n && A[r] > A[larg]){
      larg = r;
}
  if(larg != i){
    tmp = A[i];
    A[i] = A[larg];
    A[larg] = tmp;
    maxHeapify(larg);
  }

}



Measured memory_bytes: 3664
#include <climits>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

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

constexpr double EPS = 1e-9;

struct point {
	double x, y, z;
	explicit point(double x_ = 0, double y_ = 0, double z_ = 0):x(x_), y(y_), z(z_) {}

	point operator-(const point &p) const {
		return point(x - p.x, y - p.y, z - p.z);
	}
};

struct sphere {
	point c;
	double r;
	sphere(const point &c_, double r_):c(c_), r(r_) {}
};

double norm(const point &p) {
  return p.x * p.x + p.y * p.y + p.z * p.z;
}

double dot(const point &a, const point &b) {
  return a.x * b.x + a.y * b.y + a.z * b.z;
}

vector<double> solve_quadratic_equation(double a, double b, double c) {
	const double d = b * b - 4 * a * c;
	if(d < -EPS) return {};
	return {(-b - sqrt(d)) / (2 * a), (-b + sqrt(d)) / (2 * a)};
}

double get_time(const sphere &a, const sphere &va, const sphere &b, const sphere &vb) {
	const point d = a.c - b.c;
	const point dv = va.c - vb.c;
	const double sum_r = a.r + b.r;
	const double sum_vr = va.r + vb.r;

	const double x = norm(dv) - sum_vr * sum_vr;
	const double y = 2.0 * (dot(d, dv) + sum_r * sum_vr);
	const double z = norm(d) - sum_r * sum_r;

	if(abs(x) < EPS) return INT_MAX;

	double res = INT_MAX;
	vector<double> ans = solve_quadratic_equation(x, y, z);
	for(const auto &e : ans) {
		if(e > 0) res = min(res, e);
	}
	return res;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(10);

	for(int n; cin >> n && n;) {
		vector<sphere> stars;
		vector<sphere> vec;
		stars.reserve(n);
		vec.reserve(n);

		rep(i, n) {
			double px, py, pz, vx, vy, vz, r, vr;
			cin >> px >> py >> pz >> vx >> vy >> vz >> r >> vr;
			stars.emplace_back(point(px, py, pz), r);
			vec.emplace_back(point(vx, vy, vz), vr);
		}

		typedef tuple<double, int, int> queue_t;
		priority_queue<queue_t, vector<queue_t>, greater<queue_t>> que;

		rep(i, n) {
			que.push(make_tuple(stars[i].r / vec[i].r, i, i));
		}

		rep(i, n) {
			rep(j, i) {
				que.push(make_tuple(get_time(stars[i], vec[i], stars[j], vec[j]), i, j));
			}
		}

		vector<double> ans(n);
		vector<bool> used(n, false);

		while(!que.empty()) {
			double t;
			int a, b;
			tie(t, a, b) = que.top();
			que.pop();

			if(used[a] || used[b]) continue;

			ans[a] = ans[b] = t;
			used[a] = used[b] = true;
		}

		for(const auto &e : ans) {
			cout << e << endl;
		}
	}
	return EXIT_SUCCESS;
}

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


int main()
{
  int n, k;
  cin >> n >> k;
  int mx = (n - 1) * (n - 2) / 2;
  if (k > mx)
  {
    cout << -1 << endl;
    return 0;
  }
  int m = n - 1 + (mx - k);
  printf("%d\n", m);
  for (int i=1; i<=n; i++)
    for (int j=i+1; j<=n; j++)
    {
      if (m == 0)
        break;
      printf("%d %d\n", i, j);
      m--;
    }
  return 0;
}

Measured memory_bytes: 3776
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [a,b] <- getIntList
    print $ maximum [a+b, a-b, a*b]

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

#ifdef TEST
struct test {
    int ans;
} td[] = {
    {},
};
#endif

int
distance(int f, int t)
{
    int d = f - t;
    if(d < 0)
        d = -d;
    return d;
}

void
solver(int n, int x, int y)
{
    int i, j;
    int len[2001];
    int min_len;
    int new_len;

    bzero(len, sizeof(len));
    for(i = 1; i < n + 1; i++) {
        for(j = i + 1; j < n + 1; j++) {
            min_len = distance(i, j);
            new_len = distance(i, x) + 1 + distance(j, y);
            if(min_len > new_len)
                min_len = new_len;
            new_len = distance(j, x) + 1 + distance(i, y);
            if(min_len > new_len)
                min_len = new_len;
            len[min_len]++;
        }
    }
    for(i = 1; i < n; i++) {
        printf("%d\n", len[i]);
    }
}

int
main(int argc, char *argv[])
{
#ifdef TEST
    int tt;
    for(tt = 0; tt < sizeof(td) / sizeof(struct test); tt++) {
        solver();
        printf("%d\n", td[tt].ans);
    }
#endif
    int N, X, Y;
    scanf("%d%d%d", &N, &X, &Y);
    solver(N, X, Y);
    return 0;
}

Measured memory_bytes: 128