akhauriyash/Code-Regression huggingface dataset:
package main

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

var sc = bufio.NewScanner(os.Stdin)

// var rdr = bufio.NewReaderSize(os.Stdin, 100000)
var rdr *bufio.Reader

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	solve()
}

func solve() {
	// AGC002A
	a, b := nextInt(), nextInt()
	ans := "Positive"

	switch {
	case 0 < a:
		break
	case a <= 0 && 0 <= b:
		ans = "Zero"
	case (abs(a)-abs(b)+1)%2 == 1:
		ans = "Negative"
	default:
		break
	}

	fmt.Println(ans)
}

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

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

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

func maxi64(a int64, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func updateMax(a *int, b int) {
	if *a < b {
		*a = b
	}
}

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

func mini64(a int64, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func updateMin(a *int, b int) {
	if *a > b {
		*a = b
	}
}

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

func absi64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func anser(b bool, y string, n string) string {
	if b {
		return y
	}
	return n
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {


    public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int x, y;
		while(scan.hasNext()){
			x = scan.nextInt();
			y = scan.nextInt();
			if(x == 0 && y == 0)
				break;
			if(x < y)
	         System.out.println(x + " " + y);
			else
				System.out.println(y + " " + x);
		}
        scan.close();
    }

}

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

int main()
{
  ll d,g,t,sum=1e9;
  cin >>d>>g;
  vector<P> p(d);
  rep(i,d){
    cin >>p[i].first>>p[i].second;
  }
  rep(i,1<<d){
    ll ans=0,num=0;
    rep(j,d){
      if(i&1<<j){
        ans+= 100*(j+1)*p[j].first+p[j].second;
        num+=p[j].first;
      }else{
        t=j;
      }
    }
    for(int j=0;j<p[t].first&&ans<g;j++) ans+=100*(t+1),num++;
    if(ans>=g) sum=min(sum,num);
  }
  cout <<sum<<endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int n, m; cin>>n>>m;
    int a[n][m];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>a[i][j];
            a[i][j]--;
        }
    }

    int ans=1000;
    vector<bool> used(m, false);

    for(int k=0; k<m; k++){
        vector<int> cnt(m, 0);

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(!used[a[i][j]]){
                    cnt[a[i][j]]++;
                    break;
                }
            }
        }

        int maxid = max_element(cnt.begin(), cnt.end()) - cnt.begin();

        used[maxid] = true;
        chmin(ans, cnt[maxid]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,N) for(int i=0; i<n; i++);
int main() {
ll N,A,B;
cin>>N>>A>>B;
long long answer=0; 
answer+=N/(A+B)*A;
if(N%(A+B)>A){
    answer+=A;
}
else
{
  answer+=N%(A+B);
}
cout<<answer<<endl;
 }




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

int main(void) {
    int a, b, c; cin >> a >> b >> c;
    if (a > b) cout << '0' << endl;
    else {
        int d = b / a;
        if (d < c) cout << d << endl;
        else if (d >= c) cout << c << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999999
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> LV;

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



int main() {
	llong A,B,T;
    cin >> A >> B >> T;
    llong ans =0;
    ans = (T/A)*B;


    if (true ){

    }else{


    }

    cout << ans << endl;





}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
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 main() {
	int N;
	int sum = 0;
	cin >> N;
	vi W(N);
	rep(i, N) {
		cin >> W[i];
		sum += W[i];
	}
	int sumtmp = 0;
	int ans = pow(10, 9);
	rep(i, N) {
		sumtmp += W[i];
		int anstmp = abs(sum - sumtmp*2);
		ans = min(ans, anstmp);
	}
	cout << ans << endl;
	return 0;
}

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

int N, K;
int keiji = 1;

int sousa_a(int x){
    return x*2;
}

int sousa_b(int x){
    return x+K;
}

int main() {
    cin >> N >> K;
    for(int i=0; i<N; i++){
        if(sousa_a(keiji) >= sousa_b(keiji)){
            keiji = sousa_b(keiji);
        }else{
            keiji = sousa_a(keiji);
        }
    }
    cout << keiji;
}


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

int main() {
  int n;
  cin >> n;
  
  int a;
  string s, t;
  set<string> x;
  bool shiritori = true;
  for(int i=0; i<n; i++) {
    //しりとり
    cin >> s;
    if(i != 0 && s[0] != t[t.size()-1]) shiritori = false;
    t = s;
    //被り
    a = x.size();
    x.insert(s);
    if(a == x.size()) shiritori = false;
  }
  if(shiritori) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <tuple>
#include <stdlib.h>
using namespace std;

int main()
{
	double A, B, C;
	cin >> A;
	cout << double(1.0-(int (A/2)/A));
}

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

namespace AOJ.Codes
{
    //問題の名称... Combinatorial - 0-1 Knapsack Problem
    //問題文のURL... http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp#
    //所要時間... AAA
    //学んだこと... AAA
    //教室内の大まかな着席位置... 左 x 中央


    class Knapsack
    {
        static void Main(string[] args)
        {
            //読み込み
            var x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = x[0];
            var W = x[1];

            var items = new List<int[]>();
            for (int i = 0; i < N; i++)
            {
                var item = Console.ReadLine().Split().Select(int.Parse).ToArray();
                items.Add(item);
            }

            //計算
            var memo = new int[N, W];
            for (int i = 0; i < N; i++)
                for (int j = 0; j < W; j++)
                    memo[i, j] = -1;

            var ans = GetVic(N, W, items, ref memo);

            //出力
            Console.WriteLine(ans);

            //Enterを押して終了
            Console.ReadLine();
        }


        public static int GetVic(int i, int c, List<int[]> items, ref int[,] memo)
        {
            if (i <= 0 || c <= 0)
                return 0;


            if (memo[i-1, c-1] != -1)
                return memo[i - 1, c - 1];

            var v = items[i - 1][0];
            var w = items[i - 1][1];
            var Vi_1c = GetVic(i - 1, c, items, ref memo);

            if (c - w < 0)
            {
                memo[i - 1, c - 1] = Vi_1c;
                return Vi_1c;
            }
            else
            {
                var ans = Math.Max(v + GetVic(i - 1, c - w, items, ref memo), Vi_1c);
                memo[i - 1, c - 1] = ans;
                return ans;

            }

        }

    }
}



Measured memory_bytes: 19788
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;


int main(){
    int n, k, a, sp = 0;
    int A[200020] = {0};
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if(A[a]==0) sp++;
        A[a]++;
    }
    sort(A, A+200020, greater<int>());
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += A[i];
    }
    cout << n - sum << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

ll N,M,S,T;

void solve() {
	cin >> N >> M;
	vector<vector<ll>> edge(3*N,vector<ll>());//edge[i]はiから移動できる頂点
	rep(i, M) {
		ll u, v;
		cin >> u >> v;
		u--; v--;
		edge[3*u].emplace_back(3*v+1);
		edge[3*u+1].emplace_back(3*v+2);
		edge[3*u+2].emplace_back(3*v);
	}
	cin >> S >> T;
	S--; T--;

	queue<ll> Q;
	Q.push(3 * S);

	vector<ll> chk(3*N, -1);

	chk[3*S] = 0;
	bool end = false;
	while (Q.size() != 0) {

		ll pos = Q.front();
		Q.pop();

		rep(i, edge[pos].size()) {
			if (chk[edge[pos][i]] == -1) {
				Q.push(edge[pos][i]);
				chk[edge[pos][i]] = chk[pos] + 1;
			}
		}

	}
	
	cout << (chk[3*T] == -1 ? -1 : chk[3 * T]/3);

}

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


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

namespace AtCoder_CSharp
{
    class AtCoder
    {
        static void Main(string[] args)
        {
            int A, B;
            string input;
            string[] input2;

            while ((input = Console.ReadLine()) != null)
            {
                input2 = input.Split(' ');

                A = int.Parse(input2[0]);
                B = int.Parse(input2[1]);

                int gcd = GCD(A, B);
                int lcm = A * (B / gcd);

                Console.WriteLine(gcd + " " + lcm);
            }

        }
        
        //最大公約数
        static int GCD(int x,int y)
        {

            int big = Math.Max(x, y), small = Math.Min(x, y);

            if (small == 0)
            {
                return big;
            }

            //ユークリッドの互除法    余り0で終了
            while (big % small != 0)
            {
                int amari = big % small;
                big = small;
                small = amari;
            }

            return small;
        }

    }
}



Measured memory_bytes: 19956
//https://atcoder.jp/contests/abc143/tasks/abc143_c
//2019-11-27
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;

int main()
{
    int num;
    cin >> num;
    int ans = 1;
    char A,B;
    cin >> A;
    for(int i=1;i<num;i++){
        cin >> B;
        if(A!=B){
            ans ++;
        }
        A = B;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
using vs= vector<string>;
using vb= vector<bool>;
using vl= vector<ll>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()

int main(){
  int n,a,b;
  cin >> n;
  if(n-1){
    cin >> a >> b;
    cout << a+b;
  }else{
    cout << "Hello World";
  }
  return 0;
}


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

int main(){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    int s=0,t=0,u=0,ans;
    if(a+b>=2*c){
        if(x>y){
            if(a>=2*c){
                s=0;t=0;u=2*x;
            }else s=x-y;t=0;u=2*y;
        }else{
            if(b>=2*c){
                s=0;t=0;u=2*y;
            }else{
                s=0;t=y-x;u=2*x;
        }
        }
    }else{
        s=x;t=y;u=0;
    }
    ans=a*s+b*t+c*u;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
	ll n;
	cin>>n;
	ll a[n+1],fq[n+1],sum=0,i,ans,k,fk;
	for(i=1;i<=n;i++)fq[i]=0;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		fq[a[i]]++;
	}
	for(i=1;i<=n;i++)
	{
		if(fq[i]>1)
		sum+=(fq[i]*(fq[i]-1)/2);
	}
	for(k=1;k<=n;k++)
	{
		fk=fq[a[k]];
		if(fk<2)ans=sum;
		else
		{
			ans=sum-fk+1;
		}
		cout<<ans<<"\n";
	}
}

Measured memory_bytes: 5760
from collections import defaultdict

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
h = defaultdict(int)
g = defaultdict(int)
for k in d:
    h[k] += 1
for k in t:
    g[k] += 1
f = True
for k in g.keys():
    if h[k] < g[k]:
        f = False
        break
print(("YES" if f else "NO"))

Measured memory_bytes: 57056
N,M=map(int, input().split())
c=[1]*(N+1)
p=[0]*(N+1)
p[1]=1
for _ in range(M):
    x,y=map(int, input().split())
    p[y]=1 if p[x]==1 else p[y]
    c[x]-=1
    c[y]+=1
    if c[x]==0: p[x]=0
print(sum(p))


Measured memory_bytes: 51672
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    System.out.println((A==B)&&(B==C) ? "Yes" : "No");
  }
}

Measured memory_bytes: 23124
n, m = map(int,input().split())
s = list(list(map(int, input().split())) for _ in range(m)) 
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
    # 全switch(n)のon/offパターン数
    sw = [False]*m
    # 各電球の点灯リストを作成
    for j in range(m):
        # 各電球について
        cnt = 0
        for k in range(1,len(s[j])):
            if i>>s[j][k]-1&1:
                cnt += 1
        if cnt%2==p[j]:
            sw[j]=True
    if all(sw):
        ans+=1
print(ans)

Measured memory_bytes: 9116
n,x = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
ans = 0
for aa in a[:-1]:
  x -= aa
  if x >= 0:
    ans += 1
  else:
    break

if a[-1] == x:
  print(ans+1)
else:
  print(ans)

Measured memory_bytes: 61816
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct L {
	int x, y, z;
	int type;
	L() : x(0), y(0), z(0) {}
};

int main() {
	while(true) {
		int n, h;
		cin >> n >> h;
		if(!n && !h) break;

		vector<L> v;
		vector<vector<bool> > cross(h, vector<bool>(h, false));
		int cnt = n*n*n;
		for(int i = 0; i < h; ++i) {
			L l;
			string s;
			cin >> s;
			if(s == "xy") {
				cin >> l.x >> l.y;
				l.type = 0;
			}
			else if(s == "xz") {
				cin >> l.x >> l.z;
				l.type = 1;
			}
			else if(s == "yz") {
				cin >> l.y >> l.z;
				l.type = 2;
			}
			int dupcnt = 0;
			for(int j = 0; j < i; ++j) {
				bool c = false;
				if(l.type == v[j].type) continue;
				if(l.type == 0) {
					if(l.x == v[j].x || l.y == v[j].y) c = true;
				}
				if(l.type == 1) {
					if(l.x == v[j].x || l.z == v[j].z) c = true;
				}
				if(l.type == 2) {
					if(l.y == v[j].y || l.z == v[j].z) c = true;
				}
				if(c) {
					cross[i][j] = cross[j][i] = true;
					for(int k = 0; k < j; ++k) {
						if(cross[i][k] && cross[k][j]) {
							c = false;
							break;
						}
					}
					if(c) ++dupcnt;
				}
			}
			cnt -= n-dupcnt;
			v.push_back(l);
		}
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 0
def main(argv)
  n = gets.chomp.to_i
  h = gets.chomp.split(' ').map(&:to_i)
  
  a = [0]
  (n - 1).times do |i|
    a.push(i + 1) if h[i + 1] > h[i]
  end
  a.push(n)
  
  d = 0
  (a.size - 1).times do |j|
    d = [d, a[j + 1] - a[j]].max
  end
  puts (d - 1).to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 12420
// Practice Educational DP Contest
// author: Leonardone @ NEETSDKASU

fn main() {
	let mut stdin = String::new();
	std::io::Read::read_to_string(
		&mut std::io::stdin(),
		&mut stdin).unwrap();
	let mut stdin = stdin.split_whitespace();
	let mut get = || stdin.next().unwrap();
	macro_rules! get {
		($t:ty) => (get().parse::<$t>().unwrap());
		() => (get!(usize));
	}
	let n = get!();
	let mut ps = vec![];
	for _ in 0..n {
		ps.push(get!(f64));
	}
	
	let mut dp = vec![0.0; (n+1)/2+1];
	dp[0] = 1.0;
	
	for i in 0..n {
		for j in 0..dp.len()-1 {
			let j = dp.len()-1-j-1;
			dp[j+1] += dp[j] * ps[i];
			dp[j] *= 1.0 - ps[i];
		}
	}
	
	println!("{}", dp[(n+1)/2]);
}

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

int main()
{
   string str;
   long long int a;
   
   cin>> str;
   
   for (int i = 0; i < str.size(); ++i) {
       a = a + str[i]-'0';
    }
    cout<<(a%9==0?"Yes":"No")<<endl;
    
    return 0;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
int f1[30],f2[30];
int main() {
	int n;
	scanf("%d", &n);
	char s[105];
	scanf("%s", s);
	int ans=0;
	for (int i=1; i<n-1; i++) {
		memset(f1,0,sizeof(f1));
		memset(f2,0,sizeof(f2));
		for (int j=0; j<=i; j++) {
			int x=s[j]-'a';
			++f1[x];
		} 
		for (int k=i+1; k<n; k++) {
			int x=s[k]-'a';
			++f2[x];
		}
		int cnt=0;
		for (int i=0; i<26; i++) {
			if (f1[i]>0 && f2[i]>0) {
				++cnt;
			}
		}
		ans=max(ans,cnt);
	}
	printf("%d\n", ans);
	return 0;
}

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

signed main(){
	string S; cin>>S;
	bool ans=true;
	ans=(S[1]==S[2] and (S[1]==S[0] or S[2]==S[3]));
	cout<<(ans ? "Yes" : "No")<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 101
 
int A[MAX][MAX], s[MAX], h[MAX];
 
void serch(int x, int y){
  int i;
  h[x] = y;
  for(i=1; i<=s[x]; i++){
    if(h[A[x][i]] > y)
      serch(A[x][i], y+1);
  }
}
 
int main(){
  int i, j, k, n;
   
  scanf("%d", &n);
  for(i=1; i<=n; i++){
    h[i] = 10000;
    for(j=1; j<=n; j++)
      A[i][j] = 0;
  }
   
  for(i=1; i<=n; i++){
    scanf("%d", &k);
    scanf("%d", &s[k]);
    for(j=1; j<=s[k]; j++)
      scanf("%d", &A[k][j]);
  }
   
  serch(1,0);
   
  for(i=1; i<=n; i++){
    if(h[i] == 10000)
      h[i] = -1;
    printf("%d %d\n", i, h[i]);
  }
  return 0;
}


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

int main(){
  string s;
  cin >> s;
  int n = s.size();
  int dp[n+1][2];
  for(int i=0;i<=n;i++)dp[i][0] = dp[i][1] = 0;
  dp[1][0] = 1;
  for(int i=1;i<n;i++){
    if(s[i]==s[i-1]){
      dp[i+1][0] = dp[i][1] + 1;
      dp[i+1][1] = dp[i-1][0] + 1;
    }else {
      dp[i+1][0] = max(dp[i][0],dp[i][1])+1;
      dp[i+1][1] = dp[i-1][0] + 1;
    }
  }
  cout << max(dp[n][0],dp[n][1]) << endl;
  return 0;
}


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

int main() {
  int a,b,c;
  cin>>a>>b>>c;
  if((a==b&&a!=c)||
     (a==c&&a!=b)||
     (c==b&&b!=a)){
    cout<<"Yes";
  }
  else{
    cout<<"No";
  }
}


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

using namespace std;

string w[100];

int
main()
{
	int n;
	cin >> n;

	bool result = true;
	
	for (int i = 0; i < n; ++i) {
		cin >> w[i];
		if (i != 0) {
			if (w[i][0] != w[i-1].back()) {
				result = false;
			}
		}
	}

	if (result == false) {
		cout << "No" << endl;
		return 0;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (w[i] == w[j]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	cout << "Yes" << endl;


	return 0;
}

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

int main() {
    int x;
    cin >> x;
    vector<int> dp(100001);
    dp[0] = 1;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j <= 100000; j++) {
            if (j-(100+i) >= 0) dp[j] |= dp[j-(100+i)];
        }
    }

    cout << (dp[x] ? 1 : 0) << endl;
}


Measured memory_bytes: 640
import java.util.*;

class Main{

    public static void main(String args[]) throws Exception{
        Main main = new Main();
    }

    public Main(){
        Scanner scanner = new Scanner(System.in);
        int[] point = new int[3];
        int N,K;
        String T;
        N = scanner.nextInt();
        K = scanner.nextInt();

        point[0] = scanner.nextInt(); //r
        point[1] = scanner.nextInt(); //s
        point[2] = scanner.nextInt(); //p
        T = scanner.next();

        int[] V = new int[N];

        for(int i=0;i<N;i++){
            switch(T.charAt(i)){
                case 'r':
                    V[i] = 2;
                    break;
                case 's':
                    V[i] = 0;
                    break;
                case 'p':
                    V[i] = 1;
                    break;
            }
        }

        int result = 0;
        boolean[] isWin = new boolean[N];
        for(int i=0;i<K;i++){
            result += point[V[i]];
            isWin[i] = true;
        }
        for(int i=K;i<N;i++){
            if(V[i] == V[i-K] && isWin[i-K]){
                isWin[i] = false;
            } else {
                result += point[V[i]];
                isWin[i] = true;
            }
        }

        System.out.print(result);
    }
}


Measured memory_bytes: 26736
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
  int n,x,y;
  cin >> n >> x >> y;
  vector<vector<int>> g(n);
  rep(i,n-1){
    g[i].push_back(i+1);
    g[i+1].push_back(i);
  }
  g[--x].push_back(--y);
  g[y].push_back(x);
  
  vector<int> anss(n);
  
  rep(i,n){
    vector<int> dis(n,-1);
    dis[i] = 0;
    queue<int> q;
    q.push(i);
    while(!q.empty()){
      //cout << "{";
      //rep(p,n){
        //cout << dis[p] << " ";
      //}
      //cout << "}" << endl;
      int tmp = q.front();q.pop();
      for (auto nx :g[tmp]){
        if (dis[nx] == -1){
          q.push(nx);
          dis[nx] = dis[tmp] + 1;
        }
      }
    }
    for (int k = 0; k < n; k++){
      anss[dis[k]]++;
    }
  }
  for (int k = 1; k < n;k++){
    cout << anss[k]/2 << endl;
  }

  return 0;
}


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

if (b - a) % 2 == 0:
  print((b - a) // 2)
else:
  anses = [b - 1, n - a]
  x = (a - 1) + 1
  y = (n - b) + 1
  if (b - x) - 1 > 0:
    anses.append(x + ((b - x) - 1) // 2)
  if n - (a + y) > 0:
    anses.append(y + (n - (a + y)) // 2)
  print(min(anses))


Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		String res = "hon";
		if(N == 3) res = "bon";
		if(N == 0 || N == 1 || N == 6 || N == 8) res = "pon";
		Console.WriteLine(res);
		
	}
	int N;
	public Sol(){
		N = ri();
		N %= 10;
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 17628
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

const int MAX = 100001;

int main(){
    int N,M;
    int A[MAX];
    pair<int,int> p[MAX];

    cin >> N >> M;
    for(int i = 0;i < N;i++){
        cin >> A[i];
    }
    for(int i = 0;i < M;i++){
        cin >> p[i].second >> p[i].first;
    }

    sort(A,A + N);
    sort(p,p + M);

    int cnt = 0;
    for(int i = M - 1;i >= 0;i--){
        int b = p[i].second;
        int c = p[i].first;

        while(b && cnt >= 0){
            if(A[cnt] < c)A[cnt] = c;
            else break;
            b--;
            cnt++;
        }
    }

    long long ans = 0;
    for(int i = 0;i < N;i++){
        ans += A[i];
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1300005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int power(int x, unsigned int y, unsigned int m)
{
    if (y == 0)
        return 1;
    int p = power(x, y/2, m) % m;
    p = (p * p) % m;
    return (y%2 == 0)? p : (x * p) % m;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    int TESTS=1;
    // cin>>TESTS;
    while(TESTS--)
    {   
        int n;
        cin>>n;
        int a[n+1],b[n+1],c[n+1];
        rep(i,1,n+1) 
            cin>>a[i]>>b[i]>>c[i];
        int dp[n+1][3];
        rep(i,1,n+1)
            rep(j,0,3)
                dp[i][j] = -INF;
        dp[1][0] = a[1];
        dp[1][1] = b[1];
        dp[1][2] = c[1];
        rep(i,2,n+1){
            dp[i][0] = max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
            dp[i][1] = max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
            dp[i][2] = max(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
        }
        cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
    }       
}     

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define NewNode (ListNode *)malloc(sizeof(ListNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 4e5 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const unsigned long long mod = 998244353;
const double II = 3.1415926535;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int k,a,b,sum = 0,num = 0,ans = 0;
    cin >> k >> a >> b;
    while(sum < b)
    {
        sum = k * num;
        num++;
        if(sum >= a && sum <= b)
        {
            cout << "OK" << endl,ans = 1;
            break;
        }
    }
    if(!ans)
        cout << "NG" << endl;
}


Measured memory_bytes: 3612
using System;

public class Hello
{
    public const int SS = 1000000007;
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var res = 1L;
        for (long i = 1; i <= n; i++)
        {
            res *= i;
            res = res % SS;
        }
        Console.WriteLine(res);
    }
}

Measured memory_bytes: 11092
package main

import (
  "fmt"
  "math"
)

func main() {
  var A, B int
  fmt.Scan(&A, &B)
  
  if B == 1 {
    fmt.Println(0)
  } else {
    fmt.Println(math.Ceil(float64(B-1)/float64(A-1)))
  }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include <iomanip>
using namespace std;

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

  int m;
  cin >> m;

  int p[110] = {};
  int x[110] = {};

  for(int i = 0; i < m; i++){
    cin >> p[i] >> x[i];
  }

  for(int i = 0; i < m; i++){
    int ans = 0;
    int tmp = t[p[i] - 1];
    t[p[i] - 1] = x[i];
    for(int j = 0; j < n; j++){
      ans += t[j];
    }
    t[p[i] - 1] = tmp;
    cout << ans << endl;
  }
}


Measured memory_bytes: 256
n = int(input())
s = input()
q = int(input())

# セグ木

#使う操作
#####segfunc#####
def segfunc1(x, y):
    return x | y
#################

#####ide_ele#####
ide_ele1 = set()
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

al = [{s[i]} for i in range(n)]
seg = SegTree(al, segfunc1, ide_ele1)

for i in range(q):
    x,y,z = input().split()
    y = int(y) - 1
    if x == "1":
        seg.update(y, {z})
    if x == "2":
        ans = len(seg.query(y, int(z)))
        print(ans)

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

int main() {
  int i, j;

  int n, t;
  int before;
  int current = -1;

  long long int sum = 0;

  scanf("%d %d", &n, &t);
  for (i = 0; i < n;i++){
    before = current;
    scanf("%d", &current);
    if (before < 0) {
      continue;
    }

    if (current - before > t) {
      sum += t;
    }
    else {
      sum += current - before;
    }
  }

  sum += t;

  printf("%lld", sum);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main(){
    long long k; cin>>k;
    if(k==0){
        cout<<2<<endl;
        cout<<0<<" "<<0<<endl;
        return 0;
    }
    cout<<50<<endl;
    if(k%50==0){
        rep(i,50) cout<<(i?" ":"")<<49+k/50;
        cout<<endl;
        return 0;
    }
    rep(i,k%50) cout<<(i?" ":"")<<100+k/50-k%50;
    rep(i,50-k%50) cout<<" "<<49+k/50-k%50;
    cout<<endl;
    return 0;
}


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

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var Instance = new Question();
			Instance.Exec();
		}
	}

	public class Question
	{
		public void Exec()
		{
			long h = -1;
			long w = -1;
			List<long[]> hwlist = new List<long[]>();

			while (h != 0 && w != 0) {
				var array = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
				h = array[0];
				w = array[1];
				if (h == 0 && w == 0) {
					break;
				}

				hwlist.Add(new[] { h, w });
			}

			foreach (var item in hwlist) {
				for (int i = 0; i < item[0]; ++i) {
					for (int j = 0; j < item[1]; ++j) {
						Console.Write("#");
					}
					Console.WriteLine("");
				}

				Console.WriteLine("");
			}

			Console.ReadKey();
		}
	}
}


Measured memory_bytes: 18396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
double ans;

int main() {
    //cout.precision(10);
    int N;
    cin >> N;
    vector<double> v(N);
    for(int i = 0; i < N; i++) cin >> v[i];
    sort(v.begin(), v.end(), greater<double>());
    double factor = 0.5;
    for(int i = 0; i < N; i++) {
        ans += factor * v[i];
        if(i != N - 2) factor /= 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define inf (int)(1e18)
typedef long long ll;
using namespace std;

int main() {
    ll n; cin >> n;
    ll a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    ll num = min({a,b,c,d,e});
    cout << (n-1)/num+1+4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<array>
using namespace std;
#define llint long long int
const llint mod=1000000007LL;
const llint B = 101;
#define pub push_back
llint big =2.19e15+1;
bool mineq(string &a,string b){if(a>b){a=b;return true;}return false;}
bool maxeq(string &a,string b){if(a<b){a=b;return true;}return false;}
bool can(array<int,6>in){
	if(in[0]<0){return false;}
	int z=in[0]+in[5];
	int x=in[1]+in[4];
	int y=in[2]+in[3];
	if(x>z+y+1||y>z+x+1||z>x+y){return false;}
	return true;
}
string toku(array<int,6>in){
	string ans;
	array<int,6>kai;
	int i;
	while(-1){
		int sum=0;
		for(i=0;i<6;i++){sum+=in[i];}
		if(sum==0){return ans;}
		kai[0]=in[1]-1;
		kai[1]=in[5];
		kai[2]=in[2];
		kai[3]=in[3];
		kai[4]=in[0];
		kai[5]=in[4];
		if(can(kai)){ans.pub('E');in=kai;continue;}
		kai[0]=in[2]-1;
		kai[1]=in[1];
		kai[2]=in[5];
		kai[3]=in[0];
		kai[4]=in[4];
		kai[5]=in[3];
		if(can(kai)){ans.pub('N');in=kai;continue;}
		kai[0]=in[3]-1;
		kai[1]=in[1];
		kai[2]=in[0];
		kai[3]=in[5];
		kai[4]=in[4];
		kai[5]=in[2];
		if(can(kai)){ans.pub('S');in=kai;continue;}
		kai[0]=in[4]-1;
		kai[1]=in[0];
		kai[2]=in[2];
		kai[3]=in[3];
		kai[4]=in[5];
		kai[5]=in[1];
		if(can(kai)){ans.pub('W');in=kai;continue;}
		return "ZZZ";
	}
}
int solve(void){
	array<int,6> num;
	int i,sum=0;
	for(i=0;i<6;i++){cin>>num[i];sum+=num[i];}
	sort(num.begin(),num.end());
	string ans="ZZZ";
	if(sum==0){return 0;}
	//場所はnext_permutationする 6!=720
	do{
		mineq(ans,toku(num));
	}while(next_permutation(num.begin(),num.end()));
	//ENSW
	int p,q;cin>>p>>q;
	if(ans=="ZZZ"){cout<<"impossible"<<endl;return 1;}
	for(i=p;i<=q;i++){cout<<ans[i-1];}cout<<endl;
	
	return 1;
}
int main(void){
	while(solve()){}
	return 0;
}


Measured memory_bytes: 3244
/// referenced: https://beta.atcoder.jp/contests/abc066/submissions/2252964
#include <bits/stdc++.h>
using namespace std;

constexpr int64_t MOD = 1000000007;

int64_t Power(int64_t base, int64_t exp) {
  int64_t x = 1;
  while (exp) {
    if (exp % 2) {
      x = x * base % MOD;
    }
    base = base * base % MOD;
    exp /= 2;
  }
  return x;
}

int64_t Inv(int64_t x) {
  return Power(x, MOD - 2);
}

int64_t Factorial(int64_t x) {
  static vector<int64_t> xs;
  if (xs.size() == 0) {
    xs.resize(100002);
    xs[0] = 1;
    for (int i = 1; i < xs.size(); ++i) {
      xs[i] = xs[i - 1] * i % MOD;
    }
  }
  return xs[x];
}

int64_t InvFact(int64_t x) {
  static vector<int64_t> xs;
  if (xs.size() == 0) {
    xs.resize(100002);
    xs[100001] = Inv(Factorial(100001));
    for (int i = 100000; i >= 0; --i) {
      xs[i] = xs[i + 1] * (i + 1) % MOD;
    }
  }
  return xs[x];
}

int64_t Combination(int64_t n, int64_t r) {
  if (n < r) return 0;
  int64_t x = Factorial(n);
  x = x * InvFact(r) % MOD;
  x = x * InvFact(n - r) % MOD;
  return x;
}


int main(){
  int n;
  cin >> n;
  bool c[100002];
  for(int i = 1; i <= n; ++i) {
    c[i]=false;
  }
  int p[100002];
  int l,r;

  for(int i = 0; i <= n; ++i){
    int a;
    cin >> a;
    if(c[a]){
      l = p[a];
      r = i;
    }
    c[a] = true;
    p[a] = i;
  }
  for (int k = 1; k <= n + 1; ++k) {
    int64_t x0, x1, x2;
    x0 = Combination(n + 1, k);
    x1 = Combination((l - 1) + (n + 1 - r), k - 1);
    x2 = (x0 - x1 + MOD) % MOD;
    cout << x2 << endl;
  }
}


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int l = 0, r = s.size() - 1, ans = 0;
  while (l < r) {
    if (s[l] == s[r]){
      l++;r--;
    }
    else if (s[l] == 'x') {
      l++;ans++;
    }
    else if (s[r] == 'x') {
      r--;ans++;
    }
    else {
      puts("-1");
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String args[]){

		boolean prime[]=new boolean[100000];
		prime[0]=true;
		for(int i=1;i<100000;i++) {
			if(!prime[i]) {
				for(int j=1;j<Math.ceil(100000/(i+1));j++) {
					prime[(i+1)*(j+1)-1]=true;
				}
			}
		}

		int count[]=new int[100000];

		for(int i=1;i<100000;i++) {
			if((!(prime[i-1]))&&(!(prime[(i+1)/2-1]))) {
				count[i]+=count[i-1]+1;
			}else {
				count[i]=count[i-1];
			}
		}

		Scanner scan=new Scanner(System.in);

		int q=scan.nextInt();

		int l[]=new int[q];
		int r[]=new int[q];

		for(int i=0;i<q;i++) {
			l[i]=scan.nextInt();
			r[i]=scan.nextInt();
		}

		for(int i=0;i<q;i++) {
			System.out.println(count[r[i]]-count[l[i]-1]);
		}
	}
}


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

int count(int n, int b) {
  int res = 0;
  while (n) {
    res += n % b;
    n /= b;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  int res = 1001001001;
  for (int i = 0; i < n + 1; i++) {
    res = min(res, count(i, 6) + count(n - i, 9));
  }
  cout << res << '\n';
  return 0;

}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
	int n;
	int a[1028];

	cin >> n;

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

	for (int i = 0; i < n; i++){
		cout << a[i] << (i + 1 == n ? '\n' : ' ');
	}

	for (int i = 1; i < n; i++){
		int v = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > v){
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
		for (int i = 0; i < n; i++){
			cout << a[i] << (i + 1 == n ? '\n' : ' ');
		}
	}

	

	return 0;
}

Measured memory_bytes: 3072
from heapq import*
def main():
  h,w=map(int,input().split())
  s=[input()for _ in range(h)]
  g=h*w+1
  e=[[]for _ in range(g)]
  for i in range(h):
    for j in range(w):
      for y,x in((i+1,j),(i,j+1)):
        if y<h and x<w:
          if s[i][j]=='.'and s[y][x]!='.':
            e[i*w+j]+=(1,y*w+x),
          else:
            e[i*w+j]+=(0,y*w+x),
  e[g-1]+=(s[0][0]!='.',0),
  q=[g-1]
  d=[10**12]*g
  while q:
    c=heappop(q)
    c,v=c//g,c%g
    if c>d[v]:continue
    d[v]=c
    for x,w in e[v]:
      x+=c
      if d[w]>x:
        d[w]=x
        heappush(q,x*g+w)
  print(d[g-2])
main()

Measured memory_bytes: 53084
NK = list(map(int, input().split()))
N = NK[0]
K = NK[1]
sumOfAll = 0
for howManyWeChoose in range(K, N+2):
    until = int(N*(N+1)/2 - (N-howManyWeChoose)*(N-howManyWeChoose+1)/2)
    start = int(howManyWeChoose*(howManyWeChoose-1)/2)
    sumOfAll += until-start+1
print(sumOfAll%(7+10**9))

Measured memory_bytes: 9184
from sys import stdin

sx,sy,tx,ty = [int(x) for x in stdin.readline().rstrip().split()]

s = ""

s += (ty-sy)*"U"
s += (tx-sx)*"R"
s += (ty-sy)*"D"
s += (tx-sx)*"L"
s += "L"
s += (ty-sy+1)*"U"
s += (tx-sx+1)*"R"
s += "D"
s += "R"
s += (ty-sy+1)*"D"
s += (tx-sx+1)*"L"
s += "U"

print(s)

Measured memory_bytes: 3060
// review
#include <iostream>

using namespace std;
typedef long long ll;
const int MAXN = 1e5+10;
const ll INF = 1e16;

int n, k;
ll x[MAXN];

void solve() {
  ll ans = INF;
  k--;
  for (int i=0;i+k<n;i++) {
    ans = min(ans, abs(x[i]) + abs(x[i+k] - x[i]));
    ans = min(ans, abs(x[i+k]) + abs(x[i+k] - x[i]));
  }
  cout << ans << endl;
}

int main() {
  cin >> n >> k;
  for (int i=0;i<n;i++) {
    cin >> x[i];
  }
  solve();
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
//#pragma GCC optimize("Ofast")
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
//#define int ll
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX / 2;
const ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  ll A, B, N;
  cin >> A >> B >> N;
  
  if(B == 1) {
    fin(0);
    return 0;
  }
  
  ll x = min(B - 1, N);
  
  ll res = (A * x) / B - A * (x / B);
  fin(res);
}

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

using namespace std;
const int MX = 50+10;
int mp[MX][MX];
int vis[MX];

int main()
{
    int ans = 0;
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) //初始化
    {
        int x, y;
        scanf("%d%d", &x, &y);
        vis[x]++; vis[y]++; //统计度数
        mp[x][y] = mp[y][x] = 1;
    }
    while(true)
    {
        bool flag = true; // 用于判断是否结束
        int pos = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(vis[i] == 1) //当度数是1时需要把它分离出来！
            {
                ans++;
                pos = i;
                flag = false; // 仍有度数的点，故不可结束循环
                vis[i]--;
                break;
            }
        }
        if(flag) break; // 若没有有度数的点则循环结束
        for(int i = 1; i <= n; ++i)
        {
            if(mp[pos][i] == 1) //根据拓扑排序该点连的另外一边也度数减一
            {
                vis[i]--;
            }
        }
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rlcfpoj(x) scanf("%I64d",&x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define plcfpoj(x) printf("%I64d",x)
#define lfd() printf("\n")
#define sp() printf(" ")
#define inrep(x) int x;scanf("%d",&x);while(x--)
int n;
long long a[100100],b[100100];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n+1;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	long long res=0;
	for(int i=1;i<=n;i++){
		if(a[i]<=b[i])
		{
			b[i]-=a[i];
			res+=a[i];
			a[i]=0;
		}
		else{
			a[i]-=b[i];
			res+=b[i];
			b[i]=0;
		}
		if(a[i+1]<=b[i])
		{
			b[i]-=a[i+1];
			res+=a[i+1];
			a[i+1]=0;
		}
		else{
			a[i+1]-=b[i];
			res+=b[i];
			b[i]=0;
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 1792
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int N, K;
	cin >> N >> K;

	int P[200000];
	rep(i, N) cin >> P[i];

	ll saidai = 0;
	ll ima = 0;
	rep(i, K) ima += P[i] + 1;
	saidai = ima;

	for (int i = K; i < N; i++) {
		ima += P[i] + 1;
		ima -= P[i - K] + 1;
		chmax(saidai, ima);
	}

	double kotae = saidai * 0.5;

	cout << fixed << kotae << endl;


	Would you please return 0;
}

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

struct Task {
	int n;
	string s;
	vector<int> a;

	Task(int n): n(n), a(n) {
		cin >> s;
	}

	bool check(int first, int second) {
		a[0] = first;
		a[1] = second;
		for (int i = 2; i < n; ++i) {
			a[i] = a[i-2]^(s[i-1]=='x')^a[i-1];
		}
		if (a[0] != (a[n-2]^(s[n-1]=='x')^a[n-1])) {
			return false;
		}
		if (a[1] != (a[n-1]^(s[0]=='x')^a[0])) {
			return false;
		}
		return true;
	}

	void run() {
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				if (check(i, j)) {
					for (auto& item : a) {
						cout << (!item ? 'S' : 'W');
					}
					cout << endl;
					return;
				}
			}
		}
		cout << -1 << endl;
	}
};

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

	int n;
	cin >> n;

	Task a(n);
	a.run();

	return 0;
}

Measured memory_bytes: 976