akhauriyash/Code-Regression huggingface dataset:
a,b,c,k = map(int, input().split())
s = 0
if a > k:
  s = s + k
else:
  s = s + a
  k = k - a
  if b > k :
    s = s + k * 0
  else:
    s = s + b * 0
    k = k - b
    if c > k :
      s = s + (-1)*k
    else:
        s = s + (-1)*c
print(s)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1; 
    for(int T = 0; T < t ; T++){
        string s;
        cin >> s;
        std::cout << s[0] << s.size() - 2 << s[s.size() - 1]<<  std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_N 110

int n,time,head,tail;
int *queue;
int *dist;
int *color;
int **matrix;

void enqueue(int);
int dequeue(void);
void bfs(void);

int main(){
  int i,j,u,k,v;

  scanf("%d",&n);

  queue = malloc(MAX_N * sizeof(int));
  color = malloc(n * sizeof(int));
  dist = malloc(n * sizeof(int));

  matrix = malloc(n * sizeof(int *));
  for(i = 0 ; i < n ; i++){
    matrix[i] = malloc(n * sizeof(int));
 }
 for(i = 0 ; i < n ; i++){
   dist[i] = -1;
 }
 for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < n ; j++){
     matrix[i][j] = 0;
   }
 }

 for(i = 0 ; i < n ; i++){
    scanf("%d",&u); u--;
    scanf("%d",&k);
    for(j = 0 ; j < k ; j++){
      scanf("%d",&v); v--;
      matrix[u][v] = 1;
    }
  }

  bfs();
  for(i = 0 ; i < n ; i++){
    printf("%d %d\n",i+1,dist[i]);
  }

  for(i = 0 ; i < n ; i++){
    free(matrix[i]);
  }
  free(matrix);
  free(queue);
  free(dist);
  free(color);
  return 0;
}

void bfs(){
  int u,i;

  head = tail = 0;
  color[0] = GRAY;
  dist[0] = 0;
  enqueue(0);

  while(head != tail){
    u = dequeue();
    for(i = 0 ; i < n ; i++){
      if(matrix[u][i] == 1 && color[i] == WHITE){
        color[i] = GRAY;
        dist[i] = dist[u] + 1;
        enqueue(i);
      }
    }
    color[u] = BLACK;
  }
}

void enqueue(int q){
  queue[tail] = q;
  if(++tail == MAX_N+1) tail = 0;
}

int dequeue(){
  int v = queue[head];
  if(++head == MAX_N+1) head = 0;
  return v;
}

Measured memory_bytes: 636
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        char[] c = sc.next().toCharArray();
        int[] cnt = new int[c.length];
        
        for (int i = 0; i < c.length;) {
            int index = i;
            int tmp_cnt = 0;
            char tmp_c = c[i];
            while (tmp_c == c[i]) {
                tmp_cnt++;
                i++;
                if (i >= c.length)
                    break;
            }

            if (tmp_c == 'R') {
                if (tmp_cnt % 2 == 1) {
                    cnt[i-1]++;
                }
                cnt[i] += tmp_cnt / 2;
                cnt[i-1] += tmp_cnt / 2;
            } else {
                if (tmp_cnt % 2 == 1) {
                    cnt[index]++;
                }
                cnt[index] += tmp_cnt / 2;
                cnt[index-1] += tmp_cnt / 2;
            }
        }

        for (int i = 0; i < c.length; i++) {
            System.out.print(cnt[i] + " ");
        }
    }
}

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

int main(){
    int h,w,d;
    cin >> h >> w >> d;
    
    vector<P> a(h*w);

    rep(i,h){
        rep(j,w){
            int x;
            cin >> x;
            P p(i,j);
            x--;
            a[x] = p;
        }
    }

    
/*
    for(int i=0;i<h*w; ++i){
        cout << i << ":  "<< a[i].first << ":" << a[i].second << endl;
    }
*/
    

   int vec_num = (h*w)/d+2;
   vector<vector<int>> cum_sum(d,vector<int>(vec_num));
   rep(i,d){
       cum_sum[i][0]=0;
   }

   rep(i,d){
       int temp = i;
       int j = 0;
       while(temp+d<(h*w)){
           cum_sum[i][j+1]=cum_sum[i][j]+ abs(a[temp+d].first-a[temp].first)+abs(a[temp+d].second-a[temp].second);
            temp+=d;
            j++;
       }
   }

/*
   rep(i,d){
       for(auto c:cum_sum[i]) cout << c << " ";
       cout << endl;
   }
   */


    
    int query;
    cin >> query;
    vector<int> res;


    rep(i,query){
        int l,r;
        cin >> l >> r;
        l--; r--;

        int ind = 0;
        ind = l%d;
        l = l/d; r = r/d;
        res.push_back(cum_sum[ind][r]-cum_sum[ind][l]);
        
    }
    

    for(auto r:res) cout << r << endl;

}

Measured memory_bytes: 6528
import sys
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')

# 区間更新　一点取得　1-indexed
class SegmentTree:
    def __init__(self, N):
        tmp = 1
        while tmp < N:
            tmp <<= 1
        # self.N : 完全二分木の葉の数(N以上の最小の2べき)
        self.N = tmp
        # 2*self.N - 1 : 完全二分木のノード数
        # 1-indexedで管理するので余分に１つ設ける
        self.Data = [inf for _ in range(2*self.N)]
    
    # [l, r) (0-indexed)
    def update(self, l, r, x):
        # インデックスを補正
        L = l + self.N
        R = r + self.N
        while L < R:
            # 右側なら右側を更新 右上に行く
            # 左側なら更新しない　上に行く
            if L & 1:
                self.Data[L] = min([self.Data[L], x])
                L += 1
            # 右側なら左側を更新　上に行く
            # 左側なら更新しない 上に行く
            if R & 1:
                R -= 1
                self.Data[R] = min([self.Data[R], x])
            L >>= 1; R >>= 1
    
    # k (0-indexed)
    def value(self, k):
        # インデックスを補正
        k += self.N
        res = self.Data[k]
        while k != 1:
            k >>= 1
            res = min(res, self.Data[k])
        return res


N, Q = map(int,input().split())
STX = [list(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

st = SegmentTree(Q)
for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    st.update(l, r, X)

for k in range(Q):
    ans = st.value(k)
    if ans == inf:
        ans = -1
    print(ans)

Measured memory_bytes: 118880
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

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

    map<string, int> ans{{"SUN", 7},
                         {"MON", 6},
                         {"TUE", 5},
                         {"WED", 4},
                         {"THU", 3},
                         {"FRI", 2},
                         {"SAT", 1}};
    string str;
    cin >> str;
    cout << ans[str] << "\n";
    return 0;
}



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

typedef long long ll;

int main(){
	std::ios::sync_with_stdio(false);

	std::string s;
	std::cin >> s;

	int k;	
	std::cin >> k;

	for(int i = 0; i < s.size(); i++){
		if(s[i] != '1'){
			std::cout << s[i] << '\n';
			break;
		} else if(s[i] == '1' and i == k - 1){
			std::cout << s[i] << '\n';
			break;
		}
	}
}

Measured memory_bytes: 256
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==
*/

f(A, B, C, D) :- abs(C - A) =< D.
f(A, B, C, D) :- abs(C - B) =< D , abs(B - A) =< D.

main :-
	get_number(A),
    get_number(B),
    get_number(C),
    get_number(D),
	f(A, B, C, D) -> writeln("Yes") ; writeln("No").


Measured memory_bytes: 8084
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    
    
n, m = map(int, input().split())
lang = []
for _ in range(n):
    a = [int(i) for i in input().split()[1:]]
    lang.append(a)    
un = UnionFind(n + m)

for i in range(n):
    for l in lang[i]:
        un.union(i, l + n)

ans = set([])
for i in range(n):
    k = un.find(i)
    ans.add(k)
    
if len(ans) == 1:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 32108
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}


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

    b += a*3;


    int ans = b/2;
    
    cout << ans << endl;
    return 0;
}
 
 


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 array[]=new int[N+1];
		String ans="APPROVED";
		for(int i=1;i<=N;i++){
			array[i]=sc.nextInt();
		}
		for(int i=1;i<=N;i++){
			if ((array[i]%2)==0) {
				if (((array[i]%3)==0)||(((array[i]%5)==0))) {
				}
				else{
				ans="DENIED";
				}
			}

		}
		System.out.println(ans);
    }
}

Measured memory_bytes: 24016
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

int main() {
  long long a,b,c;
  cin>>a>>b>>c;
  if(b-c>=0){
    cout<<"delicious"<<endl;
  }
  else{
    if(b-c<0&&a>=c-b){
      cout<<"safe"<<endl;
    }
    else{
      cout<<"dangerous"<<endl;
    }
  }
}


Measured memory_bytes: 256
def main():
    n=int(input())
    S=list(input() for _ in range(n))
    a,b,c,d,e=0,0,0,0,0
    for s in S:
        if s[0]=="M": a += 1
        if s[0]=="A": b += 1
        if s[0]=="R": c += 1
        if s[0]=="C": d += 1
        if s[0]=="H": e += 1
    print(c*(a+b)*(d+e)+a*b*(c+d+e)+d*e*(a+b+c))
main()

Measured memory_bytes: 9764
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  int n,m,x;
  cin >> n >> m >> x;
  int c[n],a[n][m];
  REP(i,n) {
    cin >> c[i];
    REP(j,m) cin >> a[i][j];
  }

  ll ans = INF;

  for (int bit = 1; bit < (1<<n); bit++) {
    vector<int> s;
    for (int i = 0; i <= n; i++) {
      if (bit & (1 << i-1)) s.push_back(i-1);
    }

    ll tot = 0;
    vector<int> totx(m,0);

    for(auto v: s) {
      tot += c[v];
      REP(i,m) {
        totx[i] += a[v][i];
      }
    }
    int ok = true;
    REP(i,m) {
      if (totx[i] < x) ok = false;
    }
    if (ok) ans = min(ans, tot);
  }

  if (ans == INF) COUT(-1);
  else COUT(ans);

  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
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 INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z temp.cpp
//./a.exe

int getrandom(int min,int max);

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

int x1,x2,x3,x4,y1,y2,y3,y4;

cin >> x1 >> y1 >> x2  >> y2;

x3 = (y1-y2)+x2;

y3 = (x2-x1)+y2;

x4 = (y1-y2)+x1;

y4 = (x2-x1)+y1;

cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;


//////////////////////////////////////////////////////
return 0;}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int N;
pair<long,int>A[2000];
long dp[2001][2001];
int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>A[i].first;
		A[i].second=i;
	}
	sort(A,A+N);
	reverse(A,A+N);
	for(int i=0;i<N;i++){
		for(int j=0;j<=i;j++){
			int k=N-(i-j);
			dp[j+1][k]=max(dp[j+1][k],dp[j][k]+A[i].first*abs(A[i].second-j));
			dp[j][k-1]=max(dp[j][k-1],dp[j][k]+A[i].first*abs(A[i].second-(k-1)));
		}
	}
	long ans=0;
	for(int i=0;i<=N;i++)
                    ans=max(ans,dp[i][i]);
	cout<<ans<<endl;
}


Measured memory_bytes: 26212
from itertools import accumulate
N = int(input())
W = [int(i) for i in input().split()]
w = list(accumulate(W))
ans = []
for i in range(N-1):
    s1 = w[i]
    s2 = w[-1] - s1
    ans.append(abs(s1-s2))
print(min(ans))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, q;
long long a[N], f[N], ans[N];
int main() {
	scanf("%d%d", &n, &q);
	a[++m] = n;
	for (int i = 1; i <= q; i++) {
		long long x;
		scanf("%lld", &x);
		while (m && a[m] >= x) m--;
		a[++m] = x;
	}
	f[m] = 1;
	for (int i = m, j; i >= 1; i--) {
		long long L = a[i];
		while (L > a[1]) {
			j = upper_bound(a + 1, a + i, L) - a - 1;
			f[j] += f[i] * (L / a[j]);
			L %= a[j];
		}
		ans[L] += f[i];
	}
	for (int i = n - 1; i >= 1; i--)
		ans[i] += ans[i + 1];
	for (int i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Measured memory_bytes: 4096
#include<iostream>
#include<cstdlib> 
#include<sstream>
#include<cstdio>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
#define me(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 1000000007
const int N=1111122;
int main()
{
	std::ios::sync_with_stdio(false);
	LL n,ans=0,m,i,q;
	cin>>n>>m;
	for(i=0;i<m;i++)
	{
		cin>>q;
		ans+=q;
	}
	LL sum=n-ans;
	if(sum>=0)cout<<sum<<endl;
	else cout<<-1<<endl;
	//system("pause");
	return 0;
}

Measured memory_bytes: 3192
use std::io;

fn main(){
    let mut line=String::new();
    io::stdin().read_line(&mut line).ok();
    let nums:Vec<&str>=line.split_whitespace().collect();
    let x:&str=nums[0];
    let y:&str=nums[1];
    let z:&str=nums[2];
    println!("{} {} {}",z,x,y);
    
}

Measured memory_bytes: 2116
#include<stdio.h>
int main(){
	int t,n,s,f,i,sum;
	while(1){
		sum=0;
		scanf("%d",&t);
		if(t==0)break;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d%d",&s,&f);
			sum+=(f-s);
		}
		if(sum>=t)printf("OK\n");
		else printf("%d\n",t-sum);
	}
	return 0;
}

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

using namespace std;

string ans[11000];

int main(void) {
    int v[3], n, r;
    double w, h, l;
    
    while (scanf("%d %d %d", &v[0], &v[1], &v[2]), v[0]) {
        sort(v, v + 3);
        w = v[0] / 2.0;
        h = v[1] / 2.0;
        l = sqrt(w * w + h * h);
        scanf("%d", &n);

        for (int i = 0; i < n; i++) {
            scanf("%d", &r);
            if ((double)r > l) ans[i] = "OK";
            else ans[i] = "NA";
        }
        
        for (int i = 0; i < n; i++)
            cout << ans[i] << endl;
    }

    return 0;
}


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

using namespace std;

int main() {
	int n;
	cin >> n;
	long long ga, sa, ba;
	cin >> ga >> sa >> ba;
	long long gb, sb, bb;
	cin >> gb >> sb >> bb;
	long long tot = n;
	long long mx = n;
	for (int i = 0; i <= 5000; ++i) {
		if(tot - i * 1ll * ga < 0) break;
		for (int j = 0; j <= 5000; ++j) {
			if(tot - i * 1ll * ga - j * 1ll * sa < 0) break;
				long long at = tot - i * 1ll * ga - j * 1ll * sa;
				long long rest = at/ba;
				long long start = at%ba;
				// sell all in b
				start += rest * 1ll * bb  + j * 1ll * sb + i * 1ll * gb;
				mx = max(mx, start);
		}
	}
	tot = mx;
	//printf("%lld\n", tot);
	for (int i = 0; i <= 5000; ++i) {
		if(tot - i * 1ll * gb < 0) break;
		for (int j = 0; j <= 5000; ++j) {
			if(tot - i * 1ll * gb - j * 1ll * sb < 0) break;
				long long at = tot - i * 1ll * gb - j * 1ll * sb;
				long long rest = at/bb;
				long long start = at%bb;
				// sell all in a
				start = start + rest * 1ll * ba  + j * 1ll * sa + i * 1ll * ga;
				mx = max(mx, start);
		}
	}
	for (int i = 0; i <= 5000; ++i) {
		if(tot - i * 1ll * bb < 0) break;
		for (int j = 0; j <= 5000; ++j) {
			if(tot - i * 1ll * bb - j * 1ll * sb < 0) break;
				long long at = tot - i * 1ll * bb - j * 1ll * sb;
				long long rest = at/gb;
				long long start = at%gb;
				// sell all in a
				start = start + rest * 1ll * ga  + j * 1ll * sa + i * 1ll * ba;
				mx = max(mx, start);
		}
	}
	for (int i = 0; i <= 5000; ++i) {
		if(tot - i * 1ll * bb < 0) break;
		for (int j = 0; j <= 5000; ++j) {
			if(tot - i * 1ll * bb - j * 1ll * gb < 0) break;
				long long at = tot - i * 1ll * bb - j * 1ll * gb;
				long long rest = at/sb;
				long long start = at%sb;
				// sell all in a
				start = start + rest * 1ll * sa  + j * 1ll * ga + i * 1ll * ba;
				mx = max(mx, start);
		}
	}
	cout << mx << endl;



}

Measured memory_bytes: 256
n, k = map(int, input().split())
tree = []
for i in range(n):
    h = int(input())
    tree.append(h)
tree.sort()
ans = 10**9
for i in range(n - k+1):
    t = tree[i+k-1]-tree[i]
    if ans > t:
        ans = t

print(ans)


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

int main(){
  int h,w;cin>>h>>w;
  string s;
  REP(i,w+2) cout<<'#';
  cout<<endl;
  REP(i,h){
    cin>>s;
    cout<<'#'<<s<<'#'<<endl;
  }
  REP(i,w+2) cout<<'#';  
}

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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}



  
int main() {

int n;
cin >> n;

vector<int>p(n);
REP(i, n) cin >> p.at(i);

int cnt = 0;
for(int i = 2; i < n; i++){ 
   if(p.at(i - 2) < p.at(i - 1) && p.at(i - 1) < p.at(i)) cnt++;
   if(p.at(i - 2) > p.at(i - 1) && p.at(i - 1) > p.at(i)) cnt++;
}

print(cnt);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long int a ,b,c,k;
  	cin >>a >> b>>c>>k;
  	long long int i=0;
  	if(k<=a){cout << k << endl;}
  	else{
    	if(k<=(a+b)){cout << a<<endl;}
       	else{
        	cout << a -(k-(a+b))<<endl;
        }
    }
  	
}

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

int pre(int i){
	if(i < 10){
		return i;
	}
	else{
		return pre(i / 10);
	}
}

int suf(int i){
	return i % 10;
}

int main(){
	int N, i, j, ans = 0;
	scanf("%d", &N);
	vector<vector<int>> x(10, vector<int>(10, 0));
	for(i = 1; i <= N; i++){
		x[pre(i)][suf(i)]++;
	}
	for(i = 0; i < 10; i++){
		for(j = 0; j < 10; j++){
			ans += x[i][j] * x[j][i];
		}
	}
	printf("%d\n", ans);
	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 all(v) (v).begin(), (v).end()
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
const int INF = 999999999;
int dp[101010];
int main(){
    int n, k;
    cin >> n >> k;
    vector<int> h(n+k, INF);
    rep(i, n) cin >> h[i];
    rep1(i, n+k) dp[i] = INF;
    rep(i, n)rep1(j, k+1){
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#pragma warning(disable:4996)
#define P pair<int,int>//cost to
using namespace std;

int d[10010];
vector<P>rinsetu[10010];
struct room {
	int now, cost, state, keika;
};
bool operator <(room a, room b) {
	return a.cost > b.cost;
}
int mincost[10010][4][301];//??¨?±?????????????????????????
int main() {
	int a, b, c; cin >> a >> b >> c;
	for (int e = 0; e < a; e++) {
		scanf("%d", &d[e]);
	}
	for (int e = 0; e < b; e++) {
		int f, g, h; scanf("%d%d%d", &f, &g, &h);
		f--; g--;
		rinsetu[f].push_back(P(h, g));
		rinsetu[g].push_back(P(h, f));
	}
	memset(mincost,0x3f, sizeof(mincost));
	mincost[0][0][0] = 0;
	priority_queue<room>Q;
	Q.push({0,0,0,0});
	while (Q.size()) {
		room e = Q.top(); Q.pop();
		if (mincost[e.now][e.state][e.keika] < e.cost)continue;
		for (P f : rinsetu[e.now]) {
			int x = min(c, f.first + e.keika), y = d[f.second];
			if (abs(e.state - y) == 2 && x < c)continue;
			if (y == 1) {
				y = e.state;
			}
			else {
				x = 0;
			}
			if (mincost[f.second][y][x] > e.cost + f.first) {
				mincost[f.second][y][x] = e.cost + f.first;
				Q.push({f.second,mincost[f.second][y][x],y,x});
			}
		}
	}
	int MIN = 1 << 29;
	for (int i = 0; i <= c; i++) {
		MIN = min({MIN,mincost[a-1][0][i],mincost[a-1][1][i],mincost[a-1][2][i]});
	}
	cout << MIN << endl;
}

Measured memory_bytes: 51224
#include <iostream>
#include <algorithm>
#define INF 1<<21
using namespace std;
int d[128][128];
int N, M;

void warshall_floyd(){
  for (int k = 0; k < N; k++){
    for (int i = 0; i < N; i++){
      for (int j = 0; j < N; j++){
	d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

int main()
{
  while(1){
    int s, g1, g2;
    cin >> N >> M >> s >> g1 >> g2;
 
    if (!N&&!M&&!s&&!g1&&!g2) break;   
    s--;g1--;g2--;
    for (int i = 0; i < N; i++){
      fill_n(d[i], N, INF);
    }
    for (int i = 0; i < N; i++){
      d[i][i] = 0;
    }
    for (int i = 0; i < M; i++){
      int u, v, c;
      cin >> u >> v >> c;
      u--;v--;
      d[u][v] = c;
    }

    warshall_floyd();
    int res = INF;
    for (int i = 0; i < N; i++){
      res = min(res, d[s][i] + d[i][g1] + d[i][g2]);
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1208
#include <stdio.h>
#include <iostream>

using namespace std;

int N,M,K;
void input(void){
	cin >> N >> M >> K;
}

void show(void){
	cout << N << M << K;
}

int main(void){
	input();

	int flg = 0;
	for (int i = 0; i <= N; i++)
	{
		for (int j = 0; j <= M; j++)
		{
			if(K==(j*(N-i)+i*(M-j))){
				flg = 1;
			}
		}
	}

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

	cout << endl;


	return 0;
}


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

typedef struct{
  double x;
  double y;
} P;

void kock(int n, P p1, P p2){
  P s,t,u;
  
  if (n == 0) return;

  s.x = ((2*p1.x)+(1*p2.x))/3;
  s.y = ((2*p1.y)+(1*p2.y))/3;
  t.x = ((1*p1.x)+(2*p2.x))/3;
  t.y = ((1*p1.y)+(2*p2.y))/3;

  u.x = (t.x - s.x)*cos(M_PI/3)-(t.y - s.y)*sin(M_PI/3)+s.x;
  u.y = (t.x - s.x)*sin(M_PI/3)+(t.y - s.y)*cos(M_PI/3)+s.y;
  
  kock(n-1,p1,s);
  printf("%.8f %.8f\n",s.x,s.y);
  
  kock(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);

  kock(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  
  kock(n-1,t,p2);
}

int main(){
  int n;
  P p1 = {0,0};
  P p2 = {100,0};

  scanf("%d",&n);
  
 printf("%.8f %.8f\n",p1.x,p1.y);
 
  kock(n,p1,p2);
  
 printf("%.8f %.8f\n",p2.x,p2.y);
 
  return 0;

}




Measured memory_bytes: 2104
from collections import deque
n,m = map(int,input().split())

Map = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)

q = deque()
q.append((0,0))
while q:
    now,cnt = q.popleft()
    if now==n-1 and cnt==2:
        print('POSSIBLE')
        exit()
    if cnt>=2:
        continue
    for index in Map[now]:
        q.append((index,cnt+1))
print('IMPOSSIBLE')

Measured memory_bytes: 47256
import math


def main():
    # n = int(input())
    n, k = map(int, input().split())
    # h = list(map(int, input().split()))
    s = list(input())
    # h = [int(input()) for _ in rane(n)]

    s[k-1] = s[k-1].lower()
    print("".join(s))


if __name__ == '__main__':
    main()


Measured memory_bytes: 61820
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <list>
#include <string>
#define REP(i, n) for (int i = 0; i < n; i++)
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

int main()
{
    int A, P;
    cin >> A >> P;

    int ret = A * 3 + P;
    cout << ret / 2 << endl;
}

void cheatsheet()
{
    // loop
    // vector<int> vec(10);
    vector<int> vecloop;
    REP(i, 10)
    {
        vecloop.push_back(i);
    }

    // swap
    int a = 1;
    int b = 5;
    swap(a, b); // -> a = 5, b = 1

    // sort
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    sort(arr, arr + 9, greater<int>()); // 9 8 7 6 5 4 3 2 1

    // lower
    vector<int> vec(arr, end(arr));
    sort(vec.begin(), vec.end());
    cout << lower_bound(vec.begin(), vec.end(), 2)[0]; // 2

    // map
    map<Pll, ll> m;
    m[Pll(10, 100)] = 100;
}

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

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	int N;
	string s;
	cin >>N >>s;
	int R=0, B=0;
	Rep0(i, N)
		if ('R'==s.at(i))
			R++;
		else
			B++;
	if (R>B)
		cout <<"Yes" <<endl;
	else
		cout <<"No" <<endl;
	return 0;
}



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

const int64_t MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  int n,k;
  cin >> n >> k;
  vector<int> h(n);
  for(int i=0;i<n;i++){
    cin >> h[i];
  }  
  sort(h.begin(), h.end());
  
  int diff = h[k-1]-h[0];
  for(int i=k;i<n;i++){
    diff = min(diff,h[i]-h[i-k+1]);
  }
  cout << diff << endl;
  return 0;
}



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


int main(void){
    int H,W,i,j;
    while(1){
        scanf("%d%d",&H,&W);
        if(H==0&&W==0){
            break;
        }
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                if(i%2==0){
                    if(j%2==0){
                        printf("#");
                    }
                    if(j%2==1){
                        printf(".");
                    }
                }
                if(i%2==1){
                    if(j%2==0){
                        printf(".");
                    }
                    if(j%2==1){
                        printf("#");
                    }
                }
            }    
                printf("\n");
        }
        printf("\n");
    }
    return 0;
}

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

int main(){
	int N;
	cin >> N;
	int u, v;
	ll w;
	vector<vector<pair<int, int>>> tree(N);
	for(int i(0);i<N-1;++i){
		cin >> u >> v >> w;
		u--; v--;
		tree[u].push_back(make_pair(v, w%2));
		tree[v].push_back(make_pair(u, w%2));
	}
	queue<int> q;
	vector<int> ans(N,-1);
	ans[0] = 0;
	q.push(0);
	while(!q.empty()){
		int node = q.front(); q.pop();
		for(int i(0);i<tree[node].size();++i){
			int to = tree[node][i].first;
			int weight = tree[node][i].second;
			if(ans[to] != -1) continue;
			ans[to] = (ans[node] + weight)%2;
			q.push(to);
		}
	}
	for(int i(0);i<N;++i){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 6784
while True:
    a,op,b=input().split()
    a,b=int(a),int(b)
    if op=="+":
        print(a+b)
    elif op=="-":
        print(a-b)
    elif op=="*":
        print(a*b)
    elif op=="/":
        print(a//b)
    else:
        break
        


Measured memory_bytes: 5600
#include <stdio.h>
int main(void){
  int x,y;
  for( ; ; ){
  scanf("%d %d",&x,&y);


  if( x==0 && y==0 )
  break ;
  else{
    if ( x >= y)
    printf("%d %d\n",y,x);
    else
    printf("%d %d\n",x,y);
  }


}
return 0;



}



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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}


int main() {
  int N, Q;
  cin >> N >> Q;
  map< int, vector< int > > add;
  for(int i = 0; i < N; i++) {
    int s, t, x;
    cin >> s >> t >> x;
    s -= x;
    t -= x;
    // sからtに出発する人はxで破滅する
    add[s].emplace_back(x);
    add[t].emplace_back(-x);
  }
  auto it = add.begin();
  multiset< int > st;
  for(int i = 0; i < Q; i++) {
    int d;
    cin >> d;
    while(it != add.end() && it->first <= d) {
      for(auto &v : it->second) {
        if(v >= 0) st.emplace(v);
        else st.erase(st.find(-v));
      }
      ++it;
    }
    if(st.size()) cout << *st.begin() << endl;
    else cout << -1 << endl;
  }
}






Measured memory_bytes: 54400
N = gets.to_i
S = gets.to_i

if N == S
  puts N + 1
  exit
end

def f(b, n)
  res = 0

  while n > 0
    res += n % b
    n /= b
  end

  res
end

L = Math.sqrt(N).floor

2.upto(L) do |b|
  s = f(b, N)

  if s == S
    puts b
    exit
  end
end

L.downto(1) do |i|
  j = S - i
  next if (N - j) % i != 0

  b = (N - j) / i
  next if b < 2

  s = f(b, N)

  if s == S
    puts b
    exit
  end
end

puts -1


Measured memory_bytes: 3836
#include<stdio.h>
#include<math.h>
double fmax(double x,double y){
    if(x>=y){
        return x;
    }else if(y>x){
        return y;
    }
}

int main(){
    int x,i,j,k=0,ans,max=0,a[500];
    scanf("%d",&x);
    for(i=1;i<=31;i++){
        for(j=2;j<=10;j++){
            ans=pow((double)i,(double)j);
            if(ans<=x){
                a[k]=ans;
                k++;
            }
        }
    }
    for(i=0;i<k;i++){
            max=fmax((double)max,(double)a[i]);
    }
    printf("%d\n",max);
}

Measured memory_bytes: 384
N=input()
N = [int(i) for i in input().split(" ")]
num = []
for i in N:
    count = 0
    temp = i
    while(1):
        if temp%2 == 0:
            temp = temp/2
            count += 1
        else:
            break
    num.append(count)

print(sum(num))

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

char c;

int main(){ 

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

cin>>c;

for(ll i=0; i<1000000000000; i++){
	int x=0;
	int y=1;
	x++; y++;
}

if(c=='a'){
	cout<<"vowel"<<endl;
	return 0;
}
if(c=='e'){
	cout<<"vowel"<<endl;
	return 0;
}
if(c=='i'){
	cout<<"vowel"<<endl;
	return 0;
}
if(c=='o'){
	cout<<"vowel"<<endl;
	return 0;
}
if(c=='u'){
	cout<<"vowel"<<endl;
	return 0;
}

cout<<"consonant"<<endl;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

const int N = 100;
const int INF = 1919;

vector<int> G[N];
int vis[N]={};
bool valid = true;
void dfs(int v)
{
    if(vis[v]==1) return;

    vis[v]=2;
    for(const auto &x:G[v])
    {
        if(vis[x]==0) dfs(x);
        if(vis[x]==2) valid=false;
    }
    vis[v]=1;
}

string solve()
{
    int m,n;
    cin >>m >>n;

    vector<vector<pi>> c(m,vector<pi>(n,pi(0,INF)));
    rep(i,m)
    {
        int k;
        cin >>k;
        while(k--)
        {
            int s,t;
            string cond;
            cin >>s >>cond >>t;
            --s;
            if(cond[0]=='>') c[i][s].fi = max(c[i][s].fi, t);
            else c[i][s].se = min(c[i][s].se, t);
        }
    }

    // check self contradiction
    rep(i,m)rep(j,n)if(c[i][j].fi>c[i][j].se) return "No";

    // check i->j
    rep(i,m)rep(j,m)if(i!=j)
    {
        bool make = false;
        rep(k,n)if(c[i][k].se<c[j][k].fi) make = true;
        if(make) G[i].pb(j);
    }

    rep(i,m) dfs(i);
    return (valid?"Yes":"No");
}

int main()
{
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 3328
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		char s[] = br.readLine().toCharArray();
		char t[] = br.readLine().toCharArray();
		br.close();

		int row = t.length;
		int col = s.length;
		int tb[][] = new int[row + 1][col + 1];

		for ( int r = 0; r < row; r++ ) {
			for ( int c = 0; c < col; c++ ) {
				if ( t[r] == s[c] ) {
					tb[r + 1][c + 1] = tb[r][c] + 1;
				} else {
					tb[r + 1][c + 1] = Math.max(tb[r + 1][c], tb[r][c + 1]);
				}
			}
		}

		int r = row;
		int c = col;
		ArrayDeque<Character> stack = new ArrayDeque<Character>();
		stack.add(' ');
		while ( tb[r][c] != 0 ) {

			// 左上に行けるとき
			if ( tb[r - 1][c - 1] == tb[r][c] ) {
				r -= 1;
				c -= 1;
			} else
			// 上
			if ( tb[r - 1][c] == tb[r][c] ) {
				r -= 1;
			} else
			// 左
			if ( tb[r][c - 1] == tb[r][c] ) {
				c -= 1;
			} else
			// 行き止まり
			{
				stack.addFirst((Character) s[c - 1]);
				r -= 1;
				c -= 1;
			}
		}
		
		for ( Character ch : stack ) {
			System.out.print(ch);
		}

//		StringBuilder sb = new StringBuilder();
//		while ( stack.size() > 0 ) {
//			sb.append(stack.pollLast());
//		}
//		System.out.println(sb);
	}
}


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

void solve() {
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.length(), m = t.length();
    vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    string ans = "";
    int r = n, c = m;
    while (r && c) {
        if (s[r - 1] == t[c - 1]) {
            ans += s[r - 1];
            r--;
            c--;
        }            
        else {
            if (dp[r - 1][c] >= dp[r][c - 1])
                r--;
            else
                c--;
        }            
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 38544
N=int(input())
li=list(map(int,input().split()))
if N%2==0:
    ans_normal=li[::2]
    ans_rev=li[1::2]
else:
    ans_rev=li[::2]
    ans_normal=li[1::2]  
ans_rev.reverse()
ans=ans_rev+ans_normal
for n in range(N):
    ans[n]=str(ans[n])
print(' '.join(ans))

Measured memory_bytes: 33476
//hinagata.cpp
/*includes*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <numeric>
/*namespace*/
using namespace std;
/*define macro*/
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPi(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(x) (x).begin(),(x).end()

int main(){
    int N,K;//N:全体　K：拾う玉
    int mod=1e9+7;
    cin>>N>>K;
    //条件
    long long int A=N-K+1;
    long long int B=1;
    REPi(i,1,K+1){
        if(N-K+1<i||K<i){
            cout<<0<<endl;
        }else{
            cout<<A*B%mod<<endl;
            A*=N-K+1-i;
            while(A%(i+1)!=0){
                A+=mod;
            }
            A=A/(i+1);
            B*=K-i;
            while(B%i!=0){
                B+=mod;
            }
            B=B/i;
            A%=mod;B%=mod;
        }
    }
}

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

using namespace std;

int main(){
    vector<char> s(4);
    for (int i = 0; i < 4; i++){
        cin >> s[i];
    }

    int kami, shimo;
    int t[4];
    bool k_flag = false;
    bool s_flag = false;
    for (int i = 0; i < 4; i++){
        t[i] = s[i] - '0';
    }
    kami = 10 * t[0] + t[1];
    shimo = 10 * t[2] + t[3];


    if(1 <= kami && kami <= 12)
        k_flag = true;
    if(1 <= shimo && shimo <= 12)
        s_flag = true;
    
    if(k_flag and s_flag)
        cout << "AMBIGUOUS" << endl;
    else if(k_flag == true and s_flag == false)
        cout << "MMYY" << endl;
    else if(k_flag == false and s_flag == true)
        cout << "YYMM" << endl;
    else
        cout << "NA" << endl;

    return 0;
}

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

int main(){
	int x, y; cin >> x >> y;
	if(x==0 && y==0) cout << 0 << endl;
	else if(x==0 && y < 0) cout << 1-y << endl;
	else if(y==0 && x < 0) cout << y-x << endl;
	else if(x==0 && y > 0) cout << y << endl;
	else if(y==0 && x > 0) cout << x+1 << endl;
	else if(x > 0 && y > 0){
		if(x <= y) cout << y-x << endl;
		else cout << 2 + x-y << endl;
	}
	else if(x < 0 && y < 0){
		if(x <= y) cout << y - x << endl;
		else{
			cout << 2 + x-y << endl;
		}
	}
	else if(x < 0 && y >= 0){
		cout << 1 + abs(y-abs(x)) << endl;
	}else{
		cout << 1 + abs(x-abs(y)) << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    unsigned long long int s,c;
    unsigned long long int ans,hako;
    scanf("%llu %llu",&s,&c);

    if(2*s>=c){
        ans=c/2;
    }else{
        //hako=2*s+c;
        ans=(2*s+c)/4;
    }
    printf("%llu\n",ans);
    return 0;
}

Measured memory_bytes: 128
#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::uint64_t n_) : n(n_ % mod) {};
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	std::uint32_t get() const { return n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint binpow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() { return (*this).binpow(mod - 2); }
};

#endif // ___CLASS_MODINT

#include <vector>
#include <iostream>
using namespace std;
using modulo = modint<1000000007>;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> used(N, -1);
	int side = -1;
	for (int i = 0; i < N + 1; ++i) {
		int x;
		cin >> x; --x;
		if (used[x] == -1) {
			used[x] = i;
		}
		else {
			side = (N + 1) - (i - used[x] + 1);
			break;
		}
	}
	modulo ans = 1, duplicate = 1;
	for (int i = 1; i <= N + 1; ++i) {
		ans *= modulo(N - i + 2);
		ans *= modulo(i).inv();
		cout << (ans - duplicate).get() << '\n';
		if (i <= side + 1) {
			duplicate *= modulo(side - i + 1);
			duplicate *= modulo(i).inv();
		}
	}
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
const int lim = 1e6 + 100;
const int inf = 1e9;

int dp[lim];
int dp_odd[lim];

int main(){
    //init dp talbe
    for(int i=0; i<lim; i++){
        dp[i] = inf;
        dp_odd[i] = inf;
    }
    dp[0] = 0;
    dp_odd[0] = 0;

    for(int n=1; n<lim; n++){
        int num = n * (n+1) * (n+2) / 6;
        if(num >= lim) break;

        for(int i=num; i<lim; i++){
            dp[i] = min(dp[i], dp[i - num] + 1);
            if(num%2 == 1) dp_odd[i] = min(dp_odd[i], dp_odd[i - num] + 1);
        }
    }

    while(true){
        int N;
        cin >> N;
        if(N == 0) return 0;
        cout << dp[N] << " " << dp_odd[N] << endl;
    }
}


Measured memory_bytes: 10872
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 998244353;
const ll MAX = 200001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}
int main(){
  ll x; cin >> x; const ll n = x; 
  ll a,b; a = 0; b = 0; 
  ll cnt = 1;
  vl pnum(n); vl qnum(n); vl nownum(n);
  
  rep(i,n) cin >> pnum[i];
  rep(i,n) cin >> qnum[i];
  rep(i,n) nownum[i] = i+1;
  
  do{
    bool pflag = true; bool qflag = true;
    rep(i,n){
      if(pnum[i] != nownum[i]) pflag = false;
      if(qnum[i] != nownum[i]) qflag = false;
    }
    
    if(pflag) a = cnt;
    if(qflag) b = cnt;
    
    next_permutation(nownum.begin(),nownum.end());
    cnt++;
  
  } while(a == 0 || b == 0);
  
  cout << abs(a-b) << endl;
  

}
    
    
    

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;

using namespace std;


signed main() {
  int X;
  cin >> X;

  vector<int> vec(10100000, 0);
  vec[0] = 1;
  REP(k, 6){
    REP(i, 101000){
      if(vec[i]) vec[i+100+k] = 1;
    }
  }

  if(vec[X]) cout << 1 << endl;
  else cout << 0 << endl;

  return 0;
}

Measured memory_bytes: 79232
#include <iostream>
#include <algorithm>
#define INF 90000000000
using namespace std;

int ary[100010];
int main(){
	int N,K;
	long long cnt,ccnt;
	while(1){
		cin>>N>>K;
		if(N==0&&K==0) break;
		for(int i=1;i<=N;i++){
			cin>>ary[i];
		}
		ccnt=0;
		for(int j=1;j<=K;j++){
			ccnt+=ary[j];
		}
		cnt=ccnt;
		for(int i=2;i+(K-1)<=N;i++){
			ccnt+=ary[i+(K-1)];
			ccnt-=ary[i-1];
			cnt=max(cnt,ccnt);
		}
		cout<<cnt<<endl;
	}
	return 0;
}

Measured memory_bytes: 1544