akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll n, k;
  string s;
  cin >> n >> k >> s;

  ll cnt = 1;
  rep(i, n-1) {
    if (s[i] != s[i+1]) cnt++;
  }

  ll ans = n-cnt;
  cerr << cnt << endl;
  cerr << ans << endl;
  ans += min(cnt / 2, k) * 2;
  if (cnt%2 == 0 && k >= cnt/2) {
    ans--;
  }

  cout << ans << endl;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

bool solve() {
	ll n; cin >> n;
	vl a(n);
	FOR(i,0,n) cin >> a[i];
	sort(all(a));
	
	if (n%3 != 0) {
		return a[0] == 0 && a[n-1] == 0;
	}
	
	FOR(i,0,n) if (i%(n/3) > 0 && a[i] != a[i-1]) return false;
	
	ll x = a[0], y = a[n/3], z = a[2*n/3];
	return (x^y^z) == 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cout << (solve() ? "Yes" : "No") << endl;
}



Measured memory_bytes: 1024
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S, W = MAP()

print("unsafe" if W >= S else "safe")


Measured memory_bytes: 10044
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

A=list(map(int,input().split()))
for ai in A:
    if ai==1:
        ans+=300000
    elif ai==2:
        ans+=200000
    elif ai==3:
         ans+=100000
if A[0]==1 and A[1]==1:
    ans+=400000
print(ans)

Measured memory_bytes: 38384
n = int(input())
t, a = map(int, input().split())
points = list(map(int, input().split()))

def temp(x):
    return t - 0.006 * x

temps = [abs(temp(i) - a) for i in points]
minp = min(temps)

j = 0
while (temps[j] != minp):
    j += 1
    
print(j+1)

Measured memory_bytes: 3060
#高速化
import sys
input_ = sys.stdin.readline

n = int(input_())
t0, x0, y0 = 0, 0, 0

for i in range(n):
  ti, xi, yi = map(int, input_().split())
  test = (ti - t0) - (xi + yi - x0 - y0)
  
  if test >= 0 and test % 2 == 0:
    t0, x0, y0 = ti, xi, yi
    if i == n-1:
      print("Yes")
  else:
    print("No")
    break

Measured memory_bytes: 3064
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int H,W;//縦、横
char board[100][100];
int ans;
char c;
void dfs(int x,int y,char c){
  board[x][y] ='.';
  for(int i = 0;i <4;i++){
    int nx = x +dx[i];
    int ny = y +dy[i];
    if(nx >=0&&nx <H &&ny >=0 &&ny <W){
      if(board[nx][ny] ==c){
	dfs(nx,ny,c);
      }
  }
  }
}
int main()
{
  while(cin >>H>>W,H){
    ans = 0;
    for(int i = 0;i <H;i++){
      for(int j = 0; j < W;j++){
	cin >>board[i][j];
	  }
    }
    for(int i = 0;i < H;i++){
      for(int j = 0;j <W;j++){
	if(board[i][j] =='@'||board[i][j] =='#'||board[i][j] =='*'){
	  ans++;
	  c = board[i][j];
	  dfs(i,j,c);
      }
    }
    }
    cout <<ans<<endl;
  }
  return 0;
}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    char a[31];
    Scs(a);

    bool good = true;
    if( a[0] == a[1] ) good = false;
    if( a[1] == a[2] ) good = false;
    if( a[2] == a[3] ) good = false;


    printf ("%s\n", good ? "Good" : "Bad" );


    return 0;
}



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

using namespace std;

int main()
{
  int N, L;
  cin >> N >> L;
  vector<string> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < N; i++) {
    cout << v[i];
  }
  cout << endl;
  
  return 0;
}

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

char grid[300][300];
int ans[300][300];

int main(){
	int h,w,k;	cin>>h>>w>>k;
	vector<int>cnt(h,0);
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>grid[i][j];
			if(grid[i][j]=='#')cnt[i]++;
		}
	}

	int flag=1;
	for(int i=0;i<h;i++){
		int tmp=cnt[i];
		if(tmp==0)continue;

		for(int j=0;j<w;j++){
			ans[i][j]=min(k,flag);

			if(grid[i][j]=='#'&& tmp>1){
				tmp--;
				flag++;
			}
		}
		flag++;
	}

	for(int i=1;i<h;i++){
		if(cnt[i]==0){
			for(int j=0;j<w;j++){
				ans[i][j]=ans[i-1][j];
			}
		}
	}
	for(int i=h-2;i>=0;i--){
		if(cnt[i]==0){
			for(int j=0;j<w;j++){
				ans[i][j]=ans[i+1][j];
			}
			cnt[i]++;
		}
	}

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(j)cout<<" ";
			cout<<ans[i][j];
		}cout<<endl;
	}


	return 0;
}


Measured memory_bytes: 1152
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        A_h = A[h]
        dist_h = dist[h]
        for w in range(W):
            if A_h[w] == "#":
                dist_h[w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 113452
n = int(input())
a_li = list(map(int,input().split()))

cnt = 0
swich = ""

for i in range(n):
    if i == 0:
        s = a_li[i]
        continue
    
    if a_li[i] == s:
        continue
    
    if swich == "":
        if a_li[i] > s:
            swich = "+"
        else:
            swich = "-"
            
    elif a_li[i] > s:
        if swich == "+":
            pass
        else:
            cnt += 1
            swich = ""
    elif a_li[i] < s:
        if swich == "-":
            pass
        else:
            cnt += 1
            swich = ""
            
    s = a_li[i]

print(cnt + 1)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
using Int = long long unsigned;
Int const INF = 1e10;
typedef vector<pair<Int,Int>> pvec;

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

    int n; cin>>n;
    cout<<3*n*n<<'\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
const ll INF = ll(1e9);
const int N = 1e5 + 5;
const ll mod = 1000000007 ;
using namespace std;




int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif

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


	ll tc = 1;

	// cin >> tc;


	while (tc--) {

		ll n, i, j, r, x, y;
		ll k;

		ld a, b, h, m;

		cin >> a >> b >> h >> m;

		ld hour_angle = (h * 60 + m) * 0.5;
		ld min_angle = m * 6;

		ld angle = abs(hour_angle - min_angle);

		angle = min(360 - angle, angle);
		ld pi = 3.14159265358979323846;
		angle = angle * pi;
		angle = angle / 180;

		ld c = sqrt(a * a + b * b - 2 * a * b * cos(angle));

		cout << fixed << setprecision(15) << c << endl;

	}

}

Measured memory_bytes: 4124
#include<iostream>
#include<atcoder/dsu>
using namespace std;
using namespace atcoder;
int N,M;
main()
{
	cin>>N>>M;
	dsu P(N);
	int ans=N-1;
	for(int i=0;i<M;i++)
	{
		int a,b;cin>>a>>b;
		a--,b--;
		if(!P.same(a,b))
		{
			P.merge(a,b);
			ans--;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3732
#read test
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	#buf = zeros(UInt8,100)
	#println(length(buf))
	buf = read(STDIN,5000000)
	#println(size(buf))
	str = transcode(String,buf)
	str = map(strip,split(str,"\n"))
	#println(size(str))
	a = Array{Int}(2,n)
	for i in 1:n
		a[:,i] = str[i] |> split |> parseMap
	end
	a = sortcols(a, by=z->z[2])
	t = 0
	flg = 0
	for i in 1:n
		t += a[1,i]
		if t > a[2,i]
			flg = 1
			break
		end
	end
	println(flg==0?"Yes":"No")
end

main()


Measured memory_bytes: 178468
'use strict'
const main = () => {
    let arr2 = [];
    const arr = require("fs").readFileSync("/dev/stdin", "utf8");
    const a = arr.split("\n");
    const k = a[5];
    arr2.push(Math.abs(a[0] - a[1]));
    arr2.push(Math.abs(a[0] - a[2]));
    arr2.push(Math.abs(a[0] - a[3]));
    arr2.push(Math.abs(a[0] - a[4]));
    arr2.push(Math.abs(a[1] - a[2]));
    arr2.push(Math.abs(a[1] - a[3]));
    arr2.push(Math.abs(a[1] - a[4]));
    arr2.push(Math.abs(a[2] - a[3]));
    arr2.push(Math.abs(a[2] - a[3]));
    arr2.push(Math.abs(a[3] - a[4]));
    let c;
    arr2.map((val) => {
        if (val > k) {
            c = 0;
        }
    });
    if (c == 0) {
        console.log(":(");
    } else {
        console.log("Yay!");
    }
};
main();

Measured memory_bytes: 21064
#include<stdio.h>

int f(int p);
int g(int p);

int main(void)
{
	int i;
	int n, x, y, h, w, s;
	while (1)
	{
		scanf("%d", &n);
		if (n == 0)
			break;
		s = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d%d%d%d", &x, &y, &h, &w);
			if (f(x+y+h) != -1 && g(w) != -1)
				s += f(x+y+h) > g(w) ? f(x+y+h) : g(w);
		}
		printf("%d\n", s);
	}
	return 0;
}

int f(int p)
{
	if (p <= 60)
		return 600;
	else if (p <= 80)
		return 800;
	else if (p <= 100)
		return 1000;
	else if (p <= 120)
		return 1200;
	else if (p <= 140)
		return 1400;
	else if (p <= 160)
		return 1600;
	else
		return -1;
}

int g(int p)
{
	if (p <= 2)
		return 600;
	else if (p <= 5)
		return 800;
	else if (p <= 10)
		return 1000;
	else if (p <= 15)
		return 1200;
	else if (p <= 20)
		return 1400;
	else if (p <= 25)
		return 1600;
	else
		return -1;
}

Measured memory_bytes: 600
# include <bits/stdc++.h>
# define sz(x) (int)((x).size())
# define f first 
# define s second
# define pb push_back
# define ub upper_bound
# define lb lower_bound
# define all(x) x.begin(), x.end()
# define pqueue priority_queue
# define Speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
# define rep(i,n) for(int i=0;i<n;++i)
# define forn(i,n) for(int i=1;i<=n;++i)

using namespace std;

template<class T> void umin(T &a,T b){a=min(a,b);}
template<class T> void umax(T &a,T b){a=max(a,b);}

typedef long long ll;
typedef pair<int,int> pii;

const int inf=1e9,mod=1e9+7,N=2e5+5;

void solve(){
	int n,m,x;
	cin>>n>>m>>x;
	vector<int>a(m),used(n+1,0);
	rep(i,m){
		cin>>a[i];
		used[a[i]]=1;
	}
	int res=0;
	for(int i=1;i<=x;++i){
		res+=used[i];
	}
	int ans=0;
	for(int i=x;i<=n;i++){
		ans+=used[i];
	}
	cout<<min(res,ans);

}

int main(){
 	Speed();
	int T=1; 
	//cin>>T;	
	while(T--)solve();
}

Measured memory_bytes: 3660
var input = require( 'fs' ).readFileSync( '/dev/stdin' ).toString();
  var data = input.split( " " ).map( Number );
  var a = data[0];
  var b = data[1];
  var C = data[2]*(Math.PI/180);
  var h = Math.sin( C )*b;
  var S = (a*h)/2;
  var L = a+b+Math.sqrt( Math.pow( (a-Math.cos( C )*b), 2 )+Math.pow( h, 2 ) );
  console.log( S+'\n'+L+'\n'+h );

Measured memory_bytes: 15552
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc1 = new Scanner(System.in);

		int n = sc1.nextInt();
		int k = sc1.nextInt();
		int ans = (n-1)/(k-1);
		if((n-1)%(k-1) != 0) {
			ans++;
		}

		System.out.println(ans);

		sc1.close();
	}

}

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

int n;
string s;

int main()
{
    cin >> s;
    if(s.length() == 6 && s[2] == s[3] && s[4] == s[5]) puts("Yes");
    else puts("No");

    return 0;
}


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

int x,y;
int main (){
    cin >> x >> y;
    int a[13]={0};
    for(int i=1; i<13 ; i++){
        if(i == 4||i == 6||i == 9||i == 11) a[i]++;
        if(i == 2) a[i] = 2;
    }
    if( a[x] == a[y] ) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int x,y;
while(1){
scanf("%d %d",&x,&y);
if(x==0 && y==0)break;
if(x<=y){
printf("%d %d\n",x,y );
}
else{
printf("%d %d\n",y,x);}
}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int N, M; 
int par[200010] = {}; 
int depth[200010] = {}; 
int find(int x){
	if(par[x] == x){
		return x;
	}
	else{
		return par[x] = find(par[x]); 
	}
}
void unite(int x, int y){
	x = find(x); 
	y = find(y); 
	if(x == y) return;
	else if(depth[x] < depth[y]){
		par[x] = y; 
	}else{
		par[y] = x; 
		if(depth[x] == depth[y]) depth[x] ++; 
	}
}
bool same(int x, int y){
	return find(x) == find(y); 
}
int main(){
	cin >> N >> M; 
	for(int i = 1; i <= 200000; i++){
		depth[i] = 0; par[i] = i; 
	}
	for(int i = 1; i <= N; i++){
		int K; cin >> K; 
		for(int j = 1; j <= K; j++){
			int L; cin >> L; 
			unite(i, 100000 + L); 
		}
	}
	bool ans = true; 
	for(int i = 1; i <= N; i++){
		if(!same(1, i)) ans = false; 
	}
	if(ans) cout << "YES" << endl; 
	else cout << "NO" << endl;
}

Measured memory_bytes: 1792
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int h = sc.nextInt();
		int n = sc.nextInt();

		int k = 0;
		for ( int i=0; i<n; i++ ) {
			int a = sc.nextInt();
			k = k+a;
		}

		// 出力
		if ( k >= h ) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}
}

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

const int MAX_N = 1e3+10; 
int D[MAX_N];

void prime_factor(int n){
    for (int i = 2; i*i <= n; ++i){
        while(n % i == 0){
            D[i]++;
            n /= i;
        }
    }
    if (n != 1) D[n] += 1; 
}


int main(){
    int N;
    int MOD = 1e9+7;
    cin >> N;
    for (int i = 2; i < N; ++i){
        D[i] = 0;
    }
    for (int i = 2; i <= N; ++i){
        prime_factor(i);
    }
    long long ans = 1;
    for (int i = 2; i <= N; ++i){
        // cout << i << ":" << D[i] << endl;
        ans = ans * (D[i] + 1) % MOD;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);



int main(){
    FIN;
    ll n,K;
    cin >> n >> K;
    vector<bool> a(n,false);

    for(int k=0;k<K;k++){
        int d; cin >> d;
        for(int i=0;i<d;i++){
            int num; cin >> num;
            a[num-1] = true;
        }
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        if(!a[i]) ans++;
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3680
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <cstring>
#include <functional>
//#include<unordered_map>
//#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P; 
const int N = 100005;
//////////////////////////////

string s;
int dig[102];
int k, n;
int dp[102][4];
int dp2[102][4];//equal

void solve()
{
	cin >> s;
	cin >> k;
	n = s.size();
	for (int i = 0; i < n; i++) {
		dig[i] = (s[i] - '0');
	}

	//init
	if (dig[0] == 0) {
		dp2[1][0] = 1;
	}
	else {
		dp[1][1] = dig[0] - 1;
		dp[1][0] = 1;
		dp2[1][1] = 1;
	}

	for (int i = 1; i < n; i++) {
		//equal
		if (dig[i] == 0) {
			for (int j = 0; j <= k; j++)
				dp2[i + 1][j] = dp2[i][j];
		}
		else {
			for (int j = 1; j <= k; j++)
				dp2[i + 1][j] = dp2[i][j - 1];
		}

		//less
		for (int d = 0; d < 10; d++) {
			if (d == 0) {
				for (int j = 0; j <= k; j++) {
					dp[i + 1][j] += dp[i][j];
				}
			}
			else {
				for (int j = 1; j <= k; j++) {
					dp[i + 1][j] += dp[i][j - 1];
				}
			}
		}

		for (int d = 0; d < dig[i]; d++) {
			if (d == 0) {
				for (int j = 0; j <= k; j++) {
					dp[i + 1][j] += dp2[i][j];
				}
			}
			else {
				for (int j = 1; j <= k; j++) {
					dp[i + 1][j] += dp2[i][j - 1];
				}
			}
		}
	}

	cout << dp[n][k] + dp2[n][k] << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);
	solve();
	return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<pair<int,int>> res;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N;
	priority_queue<int> P, M;
	cin>>N;
	for(int i=0;i<N;i++) {
		int a;
		cin>>a;
		if(a<0) M.push(a);
		else P.push(-a);
	}
	while(P.size()+M.size()>1) {
		if(P.empty()) {
			int a=M.top(), b;
			M.pop();
			b=M.top();
			M.pop();
			res.emplace_back(a,b);
			P.push(b-a);
		}
		else if(M.empty()) {
			int a=P.top(), b;
			P.pop();
			b=P.top();
			P.pop();
			res.emplace_back(-a,-b);
			M.push(b-a);
		}
		else {
			int a=M.top(), b=P.top();
			M.pop(); P.pop();
			if(P.empty()) {
				res.emplace_back(-b,a);
				P.push(a+b);
			}
			else {
				res.emplace_back(a,-b);
				M.push(a+b);
			}
		}
	}
	cout<<-P.top()<<'\n';
	for(auto v: res) cout<<v.first<<' '<<v.second<<'\n';
	return 0;
}

Measured memory_bytes: 3316
#include<iostream>

using namespace std;

int main()
{
    int x, y;
    char p[1000][100];
    cin >> x >> y;
    for(int i = 1; i <= x; i++)
        for(int j = 1; j <= y; j++)
            cin >> p[i][j];
    for(int i = 1; i <= 2*x; i++)
    {
        for(int j = 1; j <= y; j++)
            cout << p[(i+1)/2][j];
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//T+N
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const ll MAX_N = 51;
ll dist[MAX_N][2 * MAX_N * MAX_N];
ll n, m, silv;
ll c[MAX_N], d[MAX_N];

struct Edge {
    ll a, b, to;
};

vector<Edge> g[MAX_N];

void dij(ll s) {
    for(ll i = 0; i <= n; i ++) {
        for(ll j = 0; j < 2 * MAX_N * MAX_N; j ++) {
            dist[i][j] =  mod * mod;
        }
    }
    priority_queue<pair<ll, pair<ll, ll> > > pq;
    pq.push({0, {s, silv}});
    dist[s][silv] = 0;
    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        curr.first *= -1;
        //cout << curr.first << " " << curr.second.first << " " << curr.second.second << endl;
        if(dist[curr.second.first][curr.second.second] != curr.first) {continue;}
        if(curr.second.second + c[curr.second.first] < 2 * MAX_N * MAX_N) {
            if(dist[curr.second.first][curr.second.second + c[curr.second.first]] > curr.first + d[curr.second.first]) {
                dist[curr.second.first][curr.second.second + c[curr.second.first]] = curr.first + d[curr.second.first];
                pq.push({-dist[curr.second.first][curr.second.second + c[curr.second.first]], {curr.second.first, curr.second.second + c[curr.second.first]}});
            }
        }
        for(auto it : g[curr.second.first]) {
            if(curr.second.second < it.a) {continue;}
            if(dist[it.to][curr.second.second - it.a] > curr.first + it.b) {
                dist[it.to][curr.second.second - it.a] = curr.first + it.b;
                pq.push({-dist[it.to][curr.second.second - it.a], {it.to, curr.second.second - it.a}});
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> silv;
    for(ll i = 0; i < m; i ++) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        g[u].push_back({a, b, v});
        g[v].push_back({a, b, u});
    }
    for(ll i = 1; i <= n; i ++) {
        cin >> c[i] >> d[i];
    }
    if(silv > 2 * MAX_N * MAX_N) {
        silv = 2 * MAX_N * MAX_N - 1;
    }
    dij(1);
    for(ll i = 2; i <= n; i ++) {
        ll ans = mod * mod;
        for(ll j = 0; j < 2 * MAX_N * MAX_N; j ++) {
            chkmin(ans, dist[i][j]);
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 11456
// ITP1_1_C Rectangle
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_C&lang=ja
use std::io;

// 空白区切りの数字列をコレクションデータ型にして返却
fn int_collect() -> Vec<u8> {
    let mut buf = String::new();
    let stdin = io::stdin();
    stdin.read_line(&mut buf).unwrap();
    let iter = buf.split_whitespace().map(|s| s.parse::<u8>().unwrap());
    return iter.collect();
}


fn main() {
    // 読み込み
    let v: Vec<u8> = int_collect();

    // 図形の面積
    let area = v[0] * v[1];

    // 周の長さ
    let length = v[0] * 2 + v[1] * 2;

    // 図形の面積と周の長さを出力
    println!("{} {}", area, length);
}


Measured memory_bytes: 5024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        sc.close();

        //Nが奇数か偶数かで条件分岐
        if(N % 2 == 1) {
        	System.out.println(N * 2);
        }else {
        	System.out.println(N);
        }
	}
}

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

const long long INF = 1LL << 60;
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; }

typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)

int N, W;
int w[110], v[110];
ll dp[110][110000];

int main() {

	cin >> N >> W;
	rep1(i, N+1) cin >> w[i] >> v[i];
	rep1(j, 110000) dp[0][j] = INF;

	rep1(i, N+1) {
		rep(j, 110000) {
			dp[i][j] = dp[i - 1][j];
			if (j - v[i] >= 0) 
				chmin(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}

	int ans = 0;
	rep(v, 110000) {
		if (dp[N][v] <= W) chmax(ans, v);
	}

	cout << ans << endl;

}

Measured memory_bytes: 88320
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	long long ans=0;
	cin>>n;
	vector<int> l(n);
	for(int i=0;i<n;i++)
	{
		cin>>l[i];
	}
	sort(l.begin(),l.end(),greater<int>());
	for(int i=0;i<n-2;i++)
	{
		for(int j=i+1;j<n-1;j++)
		{
			if(l[j]+l[j+1]<=l[i])break;
			int v=j+1;
			while(v<n&&l[j]+l[v]>l[i])v++;
			ans+=(v-j-1);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using ll = long long;
using namespace std;
int main(){
string s,t;
cin>>s>>t;
sort(s.begin(),s.end());
sort(t.begin(),t.end());
reverse(t.begin(),t.end());
if(s<t)
printf("Yes\n");
else
printf("No\n");
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
/*

BubbleSort(A)
1 for i = 0 to A.length-1
2     for j = A.length-1 downto i+1
3         if A[j] < A[j-1]
4             swap A[j] and A[j-1]

入力例 1
5
5 3 2 4 1


*/

public class Main{ 

	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		BubbleSort sort = new BubbleSort(scan.nextInt());
		sort.loadSequence(scan);
		scan.close();
		sort.sort();
		System.out.println(sort);
		System.out.println(sort.swapTimes);
	}

}
class BubbleSort extends Sorting{
	public BubbleSort(int n){
		super(n);
	}
	@Override
	public void sort(){
		for(int i=0; i<seq.length;i++)
			for(int j=seq.length-1; i<j ;j--)
				if(seq[j]<seq[j-1])
					swap(j,j-1);
	}	
}
abstract class Sorting{
	int swapTimes;
	int[] seq;
	public Sorting(int n){
		swapTimes=0;
		seq = new int[n];
	}
	public void loadSequence(Scanner scan){
		for(int i=0; i<seq.length; i++)
			seq[i] = scan.nextInt();
	}
	@Override
	public String toString(){
		String tmp = "";
		for(int i=0; i<seq.length; i++)
			tmp = tmp + " " + seq[i];
		return tmp.trim();
	}
	void swap(int i, int j){
		swapTimes++;
		int tmp = seq[i];
		seq[i] = seq[j];
		seq[j] = tmp;
	}
	abstract public void sort();
}

Measured memory_bytes: 17356
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
struct edge{
	int to,next;
}e[N*N/2]; 
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
int head[N],tot;
int deg[N],a[N],n;
bool vis[N];
void add(int x,int y){
	e[++tot]=(edge){y,head[x]};
	head[x]=tot; deg[y]++;
}
void dfs(int x){
	vis[x]=1;
	for (int i=1;i<=n;i++)
		if (!vis[i]&&gcd(a[x],a[i])>1)
			add(x,i),dfs(i);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for (int i=1;i<=n;i++)
		if (!vis[i]) dfs(i);
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++)
		for (int j=n;j;j--)
			if (!vis[j]&&!deg[j]){
				vis[j]=1;
				printf("%d ",a[j]);
				for (int k=head[j];k;k=e[k].next)
					deg[e[k].to]--;
				break;
			}
} 

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>


using namespace std;

int main()
{
	long long int k;
	scanf("%lld", &k);
	long long int n=50;
	long long int r=k%n, q=k/n;
	printf("%lld\n", n);
	for(long long int i=0; i<n-r; i++){
		printf("%lld ", n-r-1-i+q);
	}
	for(long long int i=0; i<r; i++){
		printf("%lld ", n-i+q);
	}
	printf("\n");
	return 0;
}

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

char s1[10], s2[10], s3[10];

int main(void) {

	scanf("%s", s1);
	scanf("%s", s2);
	scanf("%s", s3);

	printf("%c%c%c\n", s1[0] - 32, s2[0] - 32, s3[0] - 32);

	
	return 0;

}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, K; string S; cin >> N >> S >> K;
    char a = S[K-1];
    for (char c : S) {
        cout << (c == a ? c : '*');
    }
    cout << '\n';
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,c1,c2;
    cin>>n;
    string a[n];
    int c[n];
    int i,j;
    for(i=0;i<n;i++)
        cin>>a[i];
        cin>>m;
        string b[m];
     for(i=0;i<m;i++)
        cin>>b[i];
     for(i=0;i<n;i++)
     {
         c1=0,c2=0;
        for(j=0;j<n;j++)
        {
            if(a[i]==a[j]) c1++;
        }
        for(j=0;j<m;j++)
        {
            if(a[i]==b[j]) c2++;
        }
        c[i]=c1-c2;
     }
     sort(c,c+n);
     if(c[n-1]>0) cout<<c[n-1]<<endl;
     else cout<<"0"<<endl;
     return 0;
}


Measured memory_bytes: 256
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

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

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r#"10"# => r#"9"#,
r#"1"# => r#"1"#,
}


fn solve(src: &str) -> String {
    input! {
        source = src,
        x: usize,
    }

    let mut ans = 1usize.pow(2);

    'outer: for i in (1..x + 1).rev() {
        // println!("-----[{}]--------", i);
        for b in 1..x + 1 {
            for p in 2..x + 1 {
                let n = b.pow(p as u32);
                // println!("n({}), p({}) = {}", b, p, n);
                if n == i {
                    // println!("{}", i);
                    ans = i;
                    break 'outer;
                }

                if n > x {
                    // println!("--");
                    break;
                }
            }
        }
    }

    ans.to_string()
}

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

int main(){
    string s,ans = "NO";
    cin >> s;
    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'o') {
            count++;
        }
    }
    
    if(count + (15 - s.size()) >= 8) {
        ans = "YES";
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import deque

n, m = map(int, input().split())
ab_array = [list(map(int, input().split())) for _ in range(m)]

ad_sum_array = [0] * n
ad_array = [set() for _ in range(n)]

for ab in ab_array:
    a, b = ab
    ad_array[a - 1].add(b - 1)
    ad_array[b - 1].add(a - 1)

check_array = [False] * n

def bfs(node_num):
    queue = deque([node_num])
    check_array[node_num] = True
    num = 1

    while queue:
        node = queue.popleft()
        for ad in ad_array[node]:
            if not check_array[ad]:
                check_array[ad] = True
                queue.append(ad)
                num += 1
    return num

ans = 0
for i in range(n):
    if not check_array[i]:
        ans = max(ans, bfs(i))

print(ans)

Measured memory_bytes: 109808
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  string S;
  cin>>S;
  ll N=S.size(),ans=0;
  S+="ppppp";
  
  ll cnt=0;
  REP(i,N){
    if(S[i]=='A'){
      cnt=1;
      while((S[i+1]=='B'&&S[i+2]=='C')||S[i+1]=='A'){
        if(S[i+1]=='A'){
          cnt++;
          i++;
        }
        else{
          ans+=cnt;
          i+=2;
        }
      }
    }
  }
  
  co(ans);
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
typedef struct data {
    ll x,y;
    bool operator<(const data& a) const
    {
        return x < a.x;
    }
} stu;



ll n,m,k;
ll arr[600000];
ll dp[600000];

void solve(){
     ll x = 10000000000;
     for (int i = 0; i < 600000; ++i)
     {
        dp[i]=x;
        arr[i]=x;
     }
    cin >> n >> k ;
    for (int i = 0; i < n; ++i)
    {   
        cin >> arr[i];    
    }

    //dp 
    dp[n-1]=0;
    for (int i = n-2; i >=0 ; i--)
    {
        for (int j = 1; j <= k; ++j)
        {
        dp[i]=min(dp[i+j]+abs(arr[i]-arr[i+j]),dp[i]);
        }
    }
    cout << dp[0]<<endl;

    //end dp



}




int main() {


        //clock_t startTime = clock();

    solve();
    //cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<<  endl;    
    return 0;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  long a,b;
  cin >> n >> a >> b;
  vector<long>x(n);
  int i;
  for(i=0;i<n;i++){
    cin >> x[i];
  }
  long ans = 0;
  for(i=1;i<n;i++){
    if(a*(x[i]-x[i-1])>=b)ans+=b;
    else ans += a*(x[i]-x[i-1]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
long long int solve(long long int, long long int, long long int, long long int*);
long long int check(long long int, long long int, long long int, long long int*);
main()
{
        long long int i, n, k, p = 0, w[100000];
        scanf("%lld %lld", &n , &k);
        //w = (long long int *)malloc(sizeof(long long int) * n);
        for (i = 0; i < n; i++) {
                scanf("%lld", &w[i]);
                if (p < w[i]) {
                        p = w[i];
                }
        }

        printf("%lld\n", solve(n, k, p, w));
}
long long int solve(long long int n, long long int k, long long int p, long long int *w)
{
        long long int i, mid, left = 1, right = n * p;
        while (left <= right ) {
                mid = (left + right) / 2;
                if(check(n, k, mid, w) >= n) {
                        right = mid - 1;
                } else {
                        left = mid + 1;
                }
        }
        return left;
}
long long int check(long long int n, long long int k, long long int p, long long int *w)
{
        int i, j = 0;
        for (i = 0; i < k; i++) {
                int s = 0;
                while (s + w[j] <= p) {
                        s += w[j++];
                }
                if (j == n) {
                        break;
                }
        }
        return j;
}

Measured memory_bytes: 2548
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		long[] clock = new long[n];
		for(int i = 0; i < n; i++){
			clock[i] = Long.parseLong(br.readLine());
		}
		
//		long result = clock[0];
		
		Arrays.sort(clock);
		long result = clock[clock.length - 1];
		
		for(int i = clock.length - 2; i >= 0; i--){
			if(result % clock[i] != 0){
				result = LCM(result, clock[i]);
			}
		}
		
		System.out.println(result);
	}

	static long GCDnew (long a, long b){
	    long candidate = a;
	    while (b % a != 0) {
	      candidate = b % a;
	      b = a;
	      a = candidate;
	    }
	    return candidate;
	}
	static long GCD(long a, long b){
		if(b > a){
            long tmpInt = b;
            b = a;
            a = tmpInt;
        }

		long GCD = 1;
         
        long j = b;
        while(j > 1){
            if(a%j == 0 && b%j == 0){
                GCD *= j;
                a/=j;
                b/=j;
                j = b;
            }
            else {
                j--;
            }
        }
        
        return GCD;
	}
	
	static long LCM (long a, long b){
		long GCD = GCDnew(a, b);
		//System.out.println("GCD("+a+","+b+") is "+GCD);
		return GCD * (a/GCD) * (b/GCD);
	}
}


Measured memory_bytes: 21204
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		
		int []a = new int [n];
		int []b = new int [n];
		
		for(int i = 0 ; i < n ;i++) {
			a[i] = Integer.parseInt(sc.next());
			b[i] = Integer.parseInt(sc.next());
		}
		
		Arrays.sort(a);
		Arrays.sort(b);
		
		if(n % 2 == 1) {
			int low = a[(n-1)/2];
			int high = b[(n-1)/2];
			System.out.println(high - low +1);
		}
		else {
			int low = a[(n-2)/2] +a[n/2];
			int high = b[(n-2)/2] +b[n/2];
			System.out.println(high - low + 1);
		}
	}
}


Measured memory_bytes: 61580
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

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

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

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void resolve() {
    int n;
    cin >> n;
    VI d(n);
    REP(i,0,n) cin >> d[i];
    int ans = -1, ans2 = 12;
    VI diff(13);
    REP(i,0,n) {
        if (d[i] == 12) diff[12]++;
        else diff[d[i] % 12]++;
    }
    REP(i,0,12) {
        int tmp = 12;
        if (diff[i] > 2) tmp = 0;
        else if (diff[i] >= 1) {
            if (diff[12] > 0) tmp = min(tmp, 12 - i);
            tmp = min(tmp, i);
            if (diff[i] == 2) {
                tmp = min(tmp, 24 - 2 * i);
            }
        }
        //cerr << tmp << endl;
        ans2 = min(ans2, tmp);
    }
    if (diff[12] > 1) ans2 = 0;
    dump(ans2);
    REP(b,0,1<<12) {
        int tmp = 12;
        bool bo = false;
        //cerr << tmp << endl;
        REP(i,1,12) REP(j,i+1,12) {
            if (diff[i] == 0 || diff[j] == 0) continue;
            int di = (b & (1 << i)) ? i : 24 - i;
            int dj = (b & (1 << j)) ? j : 24 - j;
            tmp = min(tmp, abs(dj - di));
            if (diff[i] > 1 || diff[j] > 1) tmp = min(tmp, j - i);
            bo = true;
            //cerr << i << " " << j << " " << di << " " << dj << endl;
        }
        //cerr << tmp << endl;
        if (bo) ans = max(ans, tmp);
        //break;
    }
    cout << min(ans2, (ans > -1) ? ans : 12) << endl;
}

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

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <numeric>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#ifdef ENABLE_ASSERT
#include <cassert>
#else
#undef assert
#define assert static_cast<void>(0)
#endif

using namespace std;
using namespace std::literals;

int main() {
  auto N = 0;
  auto S = ""s;
  cin >> N >> S;

  auto match = false;
  if (N % 2 == 0) {
    auto x = S.substr(0, N / 2);
    auto y = S.substr(N / 2, N / 2);
    match = x == y;
  }

  cout << (match ? "Yes" : "No");
  return 0;
}


Measured memory_bytes: 256
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

N, K = getMN()
candles = getlist()

shift = N - K + 1
ans = 400000000
for i in range(shift):
    l, r = candles[i] ,candles[i+K-1]
    if r > 0:
        if l >= 0:
            cost = r
        else:
            cost = min(r + 2*abs(l), 2*r + abs(l))
    elif r == 0:
        cost = abs(l)
    else:
        cost = abs(l)
    if cost < ans:
        ans = cost


print(ans)



Measured memory_bytes: 14568
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int main(){
    int n,q;
    cin >> n >> q;
    queue<pair<string,int>> que;
    rep(i,n){
        string name;
        int time;
        cin >> name >> time;
        que.push(pair<string,int>(name,time));
    }
    int now = 0;
    while(!que.empty()){
        string name = que.front().first;
        int time = que.front().second;
        que.pop();
        if(time <= q){
            now += time;
            cout << name << " " << now << endl;
        }else{
            time -= q;
            now += q;
            que.push(pair<string,int>(name,time));
        }
    }
    return 0;
}


Measured memory_bytes: 6228
#include<bits/stdc++.h>                                                     
using namespace std;                                                        
typedef long long l;                                                        
int main(){                                                                 
    l n;                                                                    
    cin>>n;                                                                 
    l input[n];                                                             
    map<l,l> check;                                                         
    for(l i=0;i<n;i++){                                                     
         cin >> input[i];                                                    
         check[input[i]]++;                                                  
      }                                                                       
      l count =0 ;                                                            
      map<l,l> :: iterator it = check.begin();                                
      while(it != check.end()){                                               
        if(it -> second % 2 != 0) count ++;                                 
        it++;                                                               
      }                                                                       
                                                                              
      cout<< count ; 
  }

Measured memory_bytes: 7296
S = input()

if S == 'RRR':
  print('3')
  
elif S == 'SSS':
  print('0')
  
elif S == 'RRS':
  print('2')

elif S == 'SRR':
  print('2')

elif S == 'RSS' or 'SRS' or 'SSR':
  print('1')
  
elif S == 'SSS':
  print('0')

Measured memory_bytes: 9024
#include<iostream>

using namespace std;

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a+b>c+d)cout<<"Left";
  else if(a+b<c+d)cout<<"Right";
  else cout<<"Balanced";
  cout<<endl;
  
 return 0; 
}

Measured memory_bytes: 256
s = input()
a = ['A', 'C', 'G', 'T'] 
i, tmp, ans = 0, 0, 0
while i < len(s):
  if s[i] in a:
    tmp += 1
    i += 1
    if tmp > ans:
      ans = tmp
  else:
    tmp = 0
    i += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;

int main() {
  char a, b, c;
  cin >> a >> b >> c;
  if (a == c)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256