akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
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(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    int n,m,k;cin>>n>>m>>k;
    cout << min(n*m, k) << endl;
    return 0;
}


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

int main()
{
    int x;
    cin >> x;
    vector<bool> ex(x+1);

    ex[1] = 1;
    for(int i = 2; i < x; i++){
        int k = i * i;
        while(k <= x){
            ex[k] = 1;
            k *= i;
        }
    }
    for(int i = x; i >= 0; i--){
        if(ex[i] == 1){
            cout << i << endl;
            return 0;
        }
    }
}

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

int main()
{
  string s; cin >> s;
  string s1 = s.substr( 0, 4 );
  string s2 = s.substr( 4 );
  cout << s1 << " " << s2 << endl;
  return ( 0 );
}


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

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

    int n, d, x, y;
    cin >> n >> d;
    int xy[n][2];
    rep(i, n) {
        cin >> x >> y;
        xy[i][0] = x;
        xy[i][1] = y;
    }
    two_sat ts(n);
    for (int i=0; i<n-1; i++) for (int j=i+1; j<n; j++) rep(k, 2) rep(l, 2) {
        if (abs(xy[i][k]-xy[j][l])<d) ts.add_clause(i, 1-k, j, 1-l);
    }
    if (ts.satisfiable()) {
        cout << "Yes" << endl;
        auto ans = ts.answer();
        rep(i, n) cout << xy[i][ans[i]] << "\n";
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3756
import java.util.Scanner;
     
    public class Main {
     
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		char A[] = new char[200000];
    		A = sc.next().toCharArray();
    		int max=1;
    		int count=0;
    		boolean flag=false;
    		for(int i=0;i<A.length;i++){
    			if(A[i]=='A'){
    				flag=true;
    			}
    			if(A[i]=='Z' && flag){
    				count++;
    				if(max<count)
    				max=count;
    			}
    			else if(flag){
    				count++;
    			}
    		}
    		System.out.println(max);
    	}
    }

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ct = 0;
    for (int i = 0; i <= (n-3); i++) {
        if (p[i] < p[i+1] && p[i+1] < p[i+2]) ct++;
        else if (p[i] > p[i+1] && p[i+1] > p[i+2]) ct++;
    }
    cout << ct << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
while b:
    z=b.popleft()
    i=z[0]
    j=z[1]
    if i<h-1 and n[(i+1)*w+j]==-1:
      n[(i+1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i+1),j))
      f=True
    if i>0  and n[(i-1)*w+j]==-1:
      n[(i-1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i-1),j))
      f=True
    if j<w-1 and n[i*w+(j+1)]==-1:
      f=True
      n[i*w+(j+1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j+1)))
    if j>0  and n[i*w+(j-1)]==-1:
      f=True
      n[i*w+(j-1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j-1)))
   
print(c)
        

Measured memory_bytes: 140636
N = int(input())
h = list(map(int, input().split()))

dp = [10**9] * N
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2, N):
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N-1])

Measured memory_bytes: 85108
#include <bits/stdc++.h>
     
    using namespace std;
     
    int main(){
     
        int n,l;
        string s[100];
        cin >> n >> l;
        for(int i = 0; i < n; i++) cin >> s[i];
        sort(s, s+n);
        for(int i = 0; i < n; i++) cout << s[i];
        cout << "\n";
        
        return 0;
    }


Measured memory_bytes: 256
//A Point in a Triangle
#include<bits/stdc++.h>
using namespace std;

//(x1, y1)と(x2, y2)の距離
double dis(double x1, double y1, double x2, double y2){
  return sqrt(pow(x1-x2, 2.0)+pow(y1-y2, 2.0));
}

//ヘロンの公式
double helon(double x1, double y1, double x2, double y2, double x3, double y3){
  double a=dis(x1, y1, x2, y2), b=dis(x2, y2, x3, y3), c=dis(x3, y3, x1, y1);
  double s=(a+b+c)/2.0;
  return sqrt(s*(s-a)*(s-b)*(s-c));
}

int main(){
  double x1, y1, x2, y2, x3, y3, xp, yp;
  while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp)!=EOF){
    double hx1, hy1, hx2, hy2, hx3, hy3;//それぞれの点の中点
    hx1=(x1+x2)/2.0, hx2=(x2+x3)/2.0, hx3=(x3+x1)/2.0;
    hy1=(y1+y2)/2.0, hy2=(y2+y3)/2.0, hy3=(y3+y1)/2.0;
    double s=helon(hx1, hy1, hx2, hy2, hx3, hy3);
    if(s>helon(xp, yp, hx2, hy2, hx3, hy3) && s>helon(hx1, hy1, xp, yp, hx3, hy3) && s>helon(hx1, hy1, hx2, hy2, xp, yp)) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 107;

int n, a[M];
multiset<int> cur;

void read() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    cur.insert(a[i]);
  }
  sort(a, a + n);
}

bool del(int x) {
  auto it = cur.find(x);
  if (it == cur.end())
    return false;
  cur.erase(it);
  return true;
}

void end() {
  cout << "Impossible\n";
  exit(0);
}

void kill() {
  int d = a[n - 1];

  for (int i = 0; i <= d; ++i) {
    int x = max(i, d - i);
    if (!del(x))
      end();
  }

  int bound = (d + 1) / 2 + 1;

  for (int x : cur)
    if (x < bound)
      end();

  cout << "Possible\n";
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  read();
  kill();
}


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

int main(){
	int a,b,c;
	vector<int> v(3);
	rep(i,3) cin>>v[i];
	sort(all(v));
	int r=v[2]-v[1];
	int l=(v[2]-v[0]-r);
	if(l%2==0) cout<<r+l/2<<endl;
	else cout<<r+l/2+2<<endl;
}

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

typedef long long int ll;

int main()
{
    string s, t;
    cin >> s >> t;
    ll ans = 0;

    for(ll i = 0;i < (ll)s.size();i++){
        if(s[i] != t[i]){
            ans++;
        }
    }

    cout << ans;

    return 0;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n;
ll t;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cin>>n;
  cin>>t;
  ll cur = 0; ll ans = 0;
  for (int i=0; i<n; i++) {
    ll x; cin>>x;
    if (x>=cur) {
      ans += t;
      cur = x + t;
    } else {
      ll tmp = x + t;
      ans += tmp - cur;
      cur = tmp;
    }
  }

  cout<<ans<<endl;
  return 0;
}
// don't forget to read in the input :^)


Measured memory_bytes: 256
//
// Created by kashi on 27-07-2020.
//
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define Endl endl
#define int long long
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
bool cmps(pair<int,int>p1,pair<int,int>p2) {
    return p1.ss<p2.ss;
}
int lcm(int a, int b){
    return (a*b)/gcd(a, b);
}
int32_t main() {
    int n;
    cin>>n;
    int count=0;
    int copy=n;
    while(copy!=0){
        copy/=2;
        count++;
    }
    int ans=1;
    while(count!=0){
        ans=ans*2;
        count--;
    }

    cout<<ans-1<<Endl;
}



Measured memory_bytes: 3616
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

int main() {
	ios;
	int a[6],index;
	for(int i=0;i<5;i++)
	{
	    cin>>a[i];
	    if(a[i]==0)
	    {
	        index = i+1;
	    }
	}
	cout<<index;
	return 0;
}


Measured memory_bytes: 3640
//package april2020;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class Main {
	static int n, in[][];
	static Integer[][] dp;
	public static void main(String[] args) {
		FastReader scn = new FastReader();
		
		n = scn.nextInt();
		
		in = new int[n][3];
		for(int i=0;i<n;i++) {
			for(int j=0;j<3;j++) {
				in[i][j] = scn.nextInt();
			}
		}
		
		dp = new Integer[n+1][5];
		
		int res = search(0,4);
		System.out.println(res);
	}
	public static int search(int d, int prev) {
		if(d>=n) {
			return 0;
		}
		if(dp[d][prev]!=null) {
			return dp[d][prev];
		}
		int ans = Integer.MIN_VALUE;
//		int mp = -1;
		for(int i =0;i<3;i++) {
			if(i!=prev) {
				int ta = search(d+1,i)+in[d][i];
				if(ta>ans) {
					ans= ta;
//					mp = i;
				}
			}
		}
//		System.out.println(in[d][mp]+" "+(d==0?-1:in[d-1][prev]));
		return dp[d][prev]=ans;
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
}


Measured memory_bytes: 64784
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (register ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 2e6 + 10 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T> void read(T &a)
{
	int f = 1 ; a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	a *= f;
}

ll n, tot, ans = 1;

char s[maxn];

signed main()
{
	scanf("%lld", &n);
	scanf("%s", s + 1);
	rep(i, 1, n * 2)
	{
		if(s[i] == 'B')
		{
			if(!(tot & 1)) tot ++;
			else (ans *= tot--) %= mod;
		}
		if(s[i] == 'W')
		{
			if(tot & 1) tot ++;
			else (ans *= tot--) %= mod;
		}
		// printf("%lld\n", tot);
	}
	rep(i, 1, n) (ans *= i) %= mod;
	printf("%lld\n", tot == 0 ? ans : 0);
	return 0;
}

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

int main(void){
    int N, cnt;
    long long D, x, y;
    cnt = 0;
    
    cin >> N >> D;
    D *= D;
    
    for(int i = 0; i < N; i++){
        cin >> x >> y;
        if(D >= x * x + y * y) cnt++;
    }
    
    cout << cnt << endl;
    
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 100003;

int x[N], y[N], c[N];
int a[N], b[N];

int main()
{
	//File("");
    int A = gi(), B = gi(), m = gi();
    for (int i = 1; i <= A; i+=1) a[i] = gi();
    for (int i = 1; i <= B; i+=1) b[i] = gi();
    for (int i = 1; i <= m; i+=1) x[i] = gi(), y[i] = gi(), c[i] = gi();
    int ans = INF;
    for (int i = 1; i <= m; i+=1)
    {
        if (a[x[i]] + b[y[i]] - c[i] < ans) ans = a[x[i]] + b[y[i]] - c[i];
    }
    sort(a + 1, a + 1 + A); sort(b + 1, b + 1 + B);
    cout << min(ans, a[1] + b[1]) << endl;
	return 0;
}

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

int main(){
	string s;long t;
	cin >> s >> t;
	int n;
  	for(n = 0; n<s.size() && s[n] == '1';n++)
    	;
  	if(n==s.size() || n>=t) {
    	cout << 1 << endl; 
      	return 0;
    }
  	cout << s[n] << endl;
}

Measured memory_bytes: 256
def solve(l, k):
    for i in range(len(l)):
        for j in range(i+1, len(l)):
            if l[j]-l[i] > k:
                return True
    return False


def main():
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())
    e = int(input())
    k = int(input())

    l = [a,b,c,d,e]
    if solve(l, k):
        print(":(")
    else:
        print("Yay!")



if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
using ll=long long;
int main()
{
    int a,b;
    cin>>a>>b;
    string str[101];
    for(int i=0;i<a;i++)
    {
        cin>>str[i];
    }
     for(int i=0;i<b+2;i++)
     {
         cout<<"#";
     }
     cout<<endl;
     for(int i=0;i<a;i++)
     {
         cout<<"#"<<str[i]<<"#"<<endl;
     }
     for(int i=0;i<b+2;i++)
     {
         cout<<"#";
     }
     cout<<endl;
     return 0;

}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i=0,n=1,a[10000];
	
	while(n!=0){
		scanf("%d",&n);
		a[i]=n;
		i=i+1;
	}
	for(n=0;n+1<i;n++){
		printf("Case %d: %d\n",n+1,a[n]);
	}
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <vector>
#include <iostream>
// #include <bits/stdc++.h>

using namespace std;

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

    int N, ans = 0;
    cin >> N;

    vector<int> V(N), C(N);
    for (int i = 0; i < N; i++)
    {
        cin >> V.at(i);
    }
    for (int i = 0; i < N; i++)
    {
        cin >> C.at(i);
    }

    for (int i = 0; i < N; i++)
    {
        if (V.at(i) - C.at(i) >= 0)
        {
            ans += V.at(i) - C.at(i);
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;
using ll = long long int;
using vec = vector<int>;

#define rep(n) for(int i = 0; i < (n); ++i)
#define Sort(a)    sort(a.begin(), a.end())
#define gSort(a)   sort(a.begin(), a.end(), greater<int>())
const int INF = 2147483647;
const ll  MOD = 1000000007;

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

    string ans;

    if(a < b) {
        rep(b) ans += to_string(a);
    }else {
        rep(a) ans += to_string(b);
    }

    cout << ans;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
playlist = []

for i in range(n):
    s, t = input().split()
    playlist.append((s, t))
last_song = input().rstrip()

init = False
ans = 0
for title, time in playlist:
    if init:
        ans += int(time)
    if title == last_song:
        init = True

print(ans)

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

class B
{
	static void Main()
	{
		var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
		int n = h[0], q = h[1];
		var ps = new int[h[0]].Select(_ => Console.ReadLine().Split()).Select(x => Tuple.Create(x[0], int.Parse(x[1])));
		var queue = new Queue<Tuple<string, int>>(ps);

		var r = new List<string>();
		var t = 0;
		while (queue.Any())
		{
			var v = queue.Dequeue();
			if (v.Item2 <= q)
			{
				r.Add($"{v.Item1} {t += v.Item2}");
			}
			else
			{
				t += q;
				queue.Enqueue(Tuple.Create(v.Item1, v.Item2 - q));
			}
		}
		Console.WriteLine(string.Join("\n", r));
	}
}



Measured memory_bytes: 35040
S = list(input())
N = len(S)
rS = [_ for _ in S[::-1]]
S1 = [S[i] for i in range((N-1)//2)]
S2 = [S[i] for i in range((N+1)//2,N)]
rS1 = [_ for _ in S1[::-1]]
rS2 = [_ for _ in S2[::-1]]

if S == rS and S1 == rS1 and S2 == rS2:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
const int N=101;
int n,m,flg,a[N],b[N],cnt;
inline int read(){
	char ch=getchar(); int x=0, f=1;
	while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
	return x*f;}
inline void swp(int &a,int &b){int t=a;a=b;b=t;}
int main()
{
	//freopen("Arrays and Palindrome.in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(); m=read();
	for(int i=1;i<=m;i++)
	{
		a[i]=read();
		if(a[i]%2) flg++;
	}
	if(m==1)
	{
		if(n==1) printf("1\n1\n1\n");
		else printf("%d\n2\n%d 1\n",n,n-1);
		return 0;
	}
	if(flg>2) printf("Impossible\n");
	else
	{
		for(int i=2;i<=m;i++) if(a[i]%2) a[1]%2 ? swp(a[m],a[i]) : swp(a[1],a[i]);
		b[++cnt]=a[1]+1;
//		if(a[1]>1) b[++cnt]=a[1]-1;
		for(int i=2;i<m;i++) b[++cnt]=a[i];
		if(a[m]>1) b[++cnt]=a[m]-1;
//		b[++cnt]=a[m]+1;
		for(int i=1;i<=m;i++) printf("%d ",a[i]); printf("\n");
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;i++) printf("%d ",b[i]); printf("\n");
	}
	//fclose(stdin); fclose(stdout);
	return 0;
}

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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fst first
#define scd second

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

inline int read(){
	int f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll readll(){
	ll f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=2e5+5;
int n,p[MAXN],fa[MAXN],c0[MAXN],c1[MAXN];
int get_fa(int x){return x==fa[x]?x:(fa[x]=get_fa(fa[x]));}
struct node{
	int u,c0,c1;
	friend bool operator < (node a,node b){
		if(a.u==1)return false;
		if(b.u==1)return true;
		if((ll)a.c0*b.c1==(ll)b.c0*a.c1)return a.u<b.u;
		return (ll)a.c0*b.c1>(ll)b.c0*a.c1;
	}
	node(int uu=0,int cc0=0,int cc1=0){u=uu,c0=cc0,c1=cc1;}
};
int main() {
	n=read();
	for(int i=2;i<=n;++i)p[i]=read();
	set<node>s;
	for(int i=1;i<=n;++i){
		fa[i]=i;
		node a;a.u=i;
		int v=read();
		if(v)c0[i]=a.c0=0,c1[i]=a.c1=1;
		else c0[i]=a.c0=1,c1[i]=a.c1=0;
		s.insert(a);
	}
	ll ans=0;
	while(s.size()!=1){
		node a=*s.begin();assert(a.u!=1);
		s.erase(a);
		int b=get_fa(p[a.u]);
		s.erase(node(b,c0[b],c1[b]));
		ans+=(ll)c1[b]*a.c0;
		c1[b]+=c1[a.u];
		c0[b]+=c0[a.u];
		fa[a.u]=b;
		s.insert(node(b,c0[b],c1[b]));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 15872
N=int(input().strip())
S=input().strip()
w_num=[0]*N
e_num=[0]*N
for i in range(1,N):
    j=N-i-1
    w_num[i] = w_num[i-1] + int(S[i-1]=="W")
    e_num[j] = e_num[j+1] + int(S[j+1]=='E')
total =[i+j for i, j in zip(w_num,e_num)]
print(min(total))

Measured memory_bytes: 39200
function main(input: string): void {
  const [N, _lines] = input.split('\n');
  const lines = _lines
    .split(' ')
    .map(n => parseInt(n, 10))
    .sort((a, b) => a - b); // sort by ascending order
  const longestLine = lines.pop(); // pop is destructive
  const ans: boolean = lines.reduce((sum, n) => sum + n) > longestLine;
  console.log(['No', 'Yes'][Number(ans)]);
}

import * as fs from 'fs';
main(fs.readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    bool ans = true;
    h[0]--;
    for(int i = 1; i < n; i++){
        if(h[i] < h[i - 1]){
            ans = false;
            break;
        }else if(h[i] > h[i - 1]){
            h[i]--;
        }
    }
    if (ans){
        for(int i = 1; i < n; i++){
            if(h[i] < h[i - 1]){
                ans = false;
                break;
            }
        }
    }
    cout << (ans? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    string S;
    cin>>S;
    long long r=0;
    long long g=0;
    long long b=0;
    int counter=0;
    for(int i=0; i<N; i++){
        if(S[i]=='R') r++;
        if(S[i]=='G') g++;
        if(S[i]=='B') b++;
    }
    long long a=r*g*b;
    
    for(int j=1; j<N-1; j++){
        int t=j;
        int u=N-1-j;
        int v=min(t,u);
        for (int i=1; i<=v; i++){
               
                if(S[j-i]!=S[j] && S[j]!=S[j+i] && S[j-i]!=S[j+i]) counter++;
            }
        }
        
    long long t=a-counter;
    cout<<t<<endl;
}

Measured memory_bytes: 3632
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())


n = I()
cnt = [0] * 10001
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v <= n:
                cnt[v] += 1

for i in range(1, n + 1):
    print(cnt[i])


Measured memory_bytes: 9264
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define INF 2e9
#define MOD (1000000007)
#define EPS 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long long int lli;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector <int>p(N);
  int count =0;
  REP(i,N){
    cin>>p[i];
    if (i+1!=p[i])count++;
  }
  cout <<(count<=2?"YES":"NO")<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define MaxN 1000+100
typedef long long LL ;
using namespace std;
LL sum[MaxN];
LL sx[MaxN][3];
LL ccopy[MaxN][3];
LL PP[3];
LL Max=0;
LL my_max(LL a,LL b)
{
	return a> b? a:b;
}
void dfs(int now,int M,int N)
{
	if(now==3)
	{
		memset(sum,0,sizeof(sum));
		for(int i=0;i<N;i++)
		{
			for(int k=0;k<3;k++)
			{
				ccopy[i][k]=sx[i][k]*PP[k];
				sum[i]+=ccopy[i][k];
			}
		}
		sort(sum,sum+N);
		LL uu=0;
		for(int i=N-1;i>=N-M;i--)
			uu+=sum[i];
		Max=my_max(Max,uu);
		return ;
	}
	PP[now]=1;
	dfs(now+1,M,N);
	PP[now]=-1;
	dfs(now+1,M,N);
}
int main()
{
	int N,M;
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++)
		scanf("%lld %lld %lld",&sx[i][0],&sx[i][1],&sx[i][2]);
	dfs(0,M,N);
	printf("%lld\n",Max);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <sstream>
#include <fstream>

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

using namespace std;
typedef long long ll;

int main() {
  ll N;
  cin >> N;
  vector<ll> B(N);
  ll A;
  for (ll i = 0; i < N; ++i) {
    cin >> A;
    B[i] = A - (i + 1);
  }

  sort(B.begin(), B.end());
  ll b = B[N / 2];
  ll ans = 0;
  for (int i = 0; i < N; ++i) {
    ans += abs(B[i] - b);
  }

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


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


#define M 1000000007
#define pb push_back
#define mp make_pair
#define s second
#define f first
#define mod 998244353
#define sz(v) (int)(v).size()

#define pii pair<int, int>
#define vi vector<int>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)

ll add(ll a,ll b)
{
	a%=M;
	b%=M;
	ll p = (a+b)%M;
	return (p+M)%M;
}

ll mul(ll a,ll b)
{
	a%=M;
	b%=M;
	ll p = (a*b)%M;
	return (p+M)%M;
}

const int NBITS = 60;

ll basis[NBITS]; 

ll sz; 

void insertVector(ll mask)
{
	for (ll i = 0; i < NBITS; i++)
	{
		if ((mask & 1LL << i) == 0) continue; 
		if (!basis[i]) 
		{ 
			basis[i] = mask;
			++sz;
			return;
		}

		mask ^= basis[i];
	}
}

int main()
{
	fastio;
	ll t;
	cin>>t;
	while(t--)
	{
		memset(basis,0,sizeof(basis));
		sz=0;
		ll n,a[1000],i;
		cin>>n;
		for(i=0;i<n;i++)
			cin>>a[i];
		string str;
		cin>>str;
		ll ans=0;
		for(i=n-1;i>=0;i--)
		{
			ll cur = sz;
			insertVector(a[i]);
			if((sz>cur)&&(str[i]=='1'))
			{
				ans=1;
				break;
			}
		}
		cout<<ans<<endl;
	}
    return 0;
}





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

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

  int k;
  cin >> k;

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

  int a[k], b[k], c[k], d[k];
  for(int i = 0; i < k; i++) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }

  int J[m+1][n+1];
  int I[m+1][n+1];
  int O[m+1][n+1];
  // 累積和の行列を生成
  for(int i = 0; i < m+1; i++) {
    J[i][0] = 0;
    I[i][0] = 0;
    O[i][0] = 0;
  }
  for(int i = 0; i < n+1; i++) {
    J[0][i] = 0;
    I[0][i] = 0;
    O[0][i] = 0;
  }
  for(int i = 1; i < m+1; i++) {
    for(int j = 1; j < n+1; j++) {
      if(place[i-1][j-1] == 'J') {
        J[i][j] = J[i-1][j] + J[i][j-1] - J[i-1][j-1] + 1;
        I[i][j] = I[i-1][j] + I[i][j-1] - I[i-1][j-1] + 0;
        O[i][j] = O[i-1][j] + O[i][j-1] - O[i-1][j-1] + 0;
      }else if(place[i-1][j-1] == 'I') {
        J[i][j] = J[i-1][j] + J[i][j-1] - J[i-1][j-1] + 0;
        I[i][j] = I[i-1][j] + I[i][j-1] - I[i-1][j-1] + 1;
        O[i][j] = O[i-1][j] + O[i][j-1] - O[i-1][j-1] + 0;
      }else {
        J[i][j] = J[i-1][j] + J[i][j-1] - J[i-1][j-1] + 0;
        I[i][j] = I[i-1][j] + I[i][j-1] - I[i-1][j-1] + 0;
        O[i][j] = O[i-1][j] + O[i][j-1] - O[i-1][j-1] + 1;
      }
    }
  }

  for(int i = 0; i < k; i++) {
    int ans_J = J[c[i]][d[i]] - J[a[i]-1][d[i]] - J[c[i]][b[i]-1] + J[a[i]-1][b[i]-1];
    int ans_I = I[c[i]][d[i]] - I[a[i]-1][d[i]] - I[c[i]][b[i]-1] + I[a[i]-1][b[i]-1];
    int ans_O = O[c[i]][d[i]] - O[a[i]-1][d[i]] - O[c[i]][b[i]-1] + O[a[i]-1][b[i]-1];
    cout << ans_J << " " << ans_O << " " << ans_I << endl;
  }
}



Measured memory_bytes: 17244
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<functional>
#include <tuple>
#include<iomanip>
#include<stack>
#include<cmath>
#define ll long long
using namespace std;
int main() {
	int r; cin >> r;
	cout << r * r << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vv vector<vector<int>>
using namespace std;

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

    set<int> s;
    rep(i,n)
    {
        int a; cin>>a;
        s.insert(a);
    }

    if(s.size()==n)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, a;
  cin >> n >> a;
  
  vector<int> x(n);
  for(int i = 0; i < n; i++){
    cin >> x.at(i);
    x.at(i) -= a;
  }
  vector<vector<ll>> dp(51, vector<ll>(5001, 0));
  dp[0][2500] = 1;
  for(int i = 0; i < n; i++){
    for(int j = 50; j < 4951; j++){
      dp[i + 1][j + x.at(i)] += dp[i][j];
      dp[i + 1][j] += dp[i][j];
    }
  }
  
  cout << dp[n][2500] - 1 << '\n';
}

Measured memory_bytes: 2304
#include <iostream>
#include <cmath>
#include <cstdio>
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;

int main(){
    ll n;
    cin>>n;
    float m=n;
    if(n%2==0){
        cout<<0.5<<endl;
    }else if(m==1){
        cout<<1<<endl;
    }else{
        cout<<(m+1)/2/m<<endl;
    }
}

Measured memory_bytes: 256
require 'pp'

def gets; ARGF.gets; end

class Solver

  def initialize
  end

  def main
    n = gets.chomp.to_i
    s = gets.chomp

    r_cnt = 0
    b_cnt = 0
    s.each_char do |c|
      if c == 'R'
        r_cnt += 1
      else
        b_cnt += 1
      end
    end

    if b_cnt < r_cnt
      puts "Yes"
    else
      puts "No"
    end
  end
end

if __FILE__ == $0
  Solver.new.main
end


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;cin>>n;
    int arr[n];
    for (int i=0;i<n;i++)cin>>arr[i];
    for (int i=0;i<n;i++){
        if(arr[i]%2==0){
            if (arr[i]%3!=0&&arr[i]%5!=0){
                cout<<"DENIED";
                return 0;
            }
        }
    }cout<<"APPROVED";
    return 0;
}

Measured memory_bytes: 256
#ABC059C
N=int(input())
A=list(map(int,input().split()))
ans=[0,0]
i=[1,0]
for c in range(2):
	summ=0
	for a in A:
		summ+=a
		if summ==0:
			ans[c]+=abs(summ-(-1)**i[c])
			summ=(-1)**i[c]
		elif (summ>0)==i[c]:
			ans[c]+=abs(summ-(-1)**i[c])
			summ=(-1)**i[c]
		i[c]=(i[c]+1)%2
print(min(ans))

Measured memory_bytes: 14468
n = gets.chomp.to_i

ans = 1
ndiv = 0
(1..n).each do |i|
  x = i
  if x.even?
    tmp = 1
    while x.even?
      x /= 2
      tmp += 1
    end
    if tmp > ndiv
      ndiv = tmp
      ans = i
    end
  end

end

puts ans

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()
const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    while(true){
        ll m,f,r; cin>>m>>f>>r;
        if(m==-1&&f==-1&&r==-1) break;

        if(m==-1||f==-1){
            cout<<'F'<<endl;
        }else if(m+f>=80){
            cout<<'A'<<endl;
        }else if(m+f>=65){
            cout<<'B'<<endl;
        }else if(m+f>=50){
            cout<<'C'<<endl;
        }else if(m+f>=30){
            if(r>=50) cout<<'C'<<endl;
            else cout<<'D'<<endl;
        }else cout<<'F'<<endl;
    }
    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG

int main() {
    int n;
    cin>>n;
    vector<int> a(n+10);
    vector<int> dp(n+10);
    rep(i,n){
        cin>>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    rep(i,n-2){
        dp[i+2]=min(dp[i+1]+abs(a[i+2]-a[i+1]),dp[i]+abs(a[i+2]-a[i]));
    }
    cout<<dp[n-1]<<endl;


    

    return 0;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <iostream> 
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std; 
int main(){
	int n, r;
	int d = 100000;
	cin >> n;
	for(int i = 0; i < n; i++){
		r = d*1.05;
		r = (r + 999) / 1000 * 1000;
		/*
		if(r%1000!=0){
			while(r%1000!=0){
			r = r+1;
			}
		}
		*/
		d = r;
	}
	cout << d << endl;
	return 0;
}


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

int main() {
	int N;
	cin >> N;
	if((N/100 == 7)||(N%10 == 7)||((N/10)%10==7)){
      cout << "Yes" <<endl;
    }else{
      cout << "No" << endl;
    }
}

Measured memory_bytes: 3632
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> inline void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> inline void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;

int main() {
    ll n;
    cin >> n;
    map<ll, ll> a;
    ll sum = 0;
    rep(i,n) {
        ll t;
        cin >> t;
        sum += t;
        ll temp = 0;
        auto it = a.find(t);
        if (it!=a.end()) {
            temp = it->second;
        }
        a[t] = 1 + temp;
    }
    ll q; cin >> q;
    rep(i, q) {
        ll b,c;
        cin >> b >> c;
        auto it = a.find(b);
        if (it!=a.end()) {
            sum -= it->second * b;
            sum += it->second * c;
            auto it2 = a.find(c);
            if(it2 != a.end()) {
                a[c] = it2->second + it->second;
            } else {
                a[c] = it->second;
            }
            a.erase(b);
        }

        print(sum);
    }

    return 0;
}


Measured memory_bytes: 7432
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n, m, c;
	cin >> n >> m >> c;
	int b[21];
	for (int i = 0; i < m; ++i)
	{
		cin >> b[i];
	}
	int a, now, ans = 0;
	for (int i = 0; i < n; ++i)
	{
		now = 0;
		for (int j = 0; j < m; ++j)
		{
			cin >> a;
			now += a * b[j];
		}
		ans += (now > -c);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
    ll n,ans=INF;
    cin>>n;
    vector<ll> v(n+1,0);
    for(int i=1;i <= n;i++)
    {
        cin>>v.at(i);
        v.at(i)+=v.at(i-1);
    }

    ll lb=1,rb=3;

    for(int i=2;i <= n-2;i++)
    {
      while(abs(v.at(0)-2*v.at(lb)+v.at(i)) > abs(v.at(0)-2*v.at(lb+1)+v.at(i)) && lb<i){
        lb++;
      }
      
      while(abs(v.at(i)-2*v.at(rb)+v.at(n)) > abs(v.at(i)-2*v.at(rb+1)+v.at(n)) && rb<n-1){
        rb++;
      }

      ll res=max({v[i]-v[lb],v[lb]-v[0],v[n]-v[rb],v[rb]-v[i]})-min({v[i]-v[lb],v[lb]-v[0],v[n]-v[rb],v[rb]-v[i]});

      ans=min(ans,res);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1920
from collections import deque

k = int(input())

q = deque([])

for i in range(1, 10):
    q.append(i)

count = 0

while count < k:
    p = q.popleft()
    
    rem = p % 10
    
    if rem != 0 and rem != 9:
        q.append(10*p + rem -1)
        q.append(10*p + rem)
        q.append(10*p + rem + 1)
    if rem == 0:
        q.append(10*p + rem)
        q.append(10*p + rem + 1)
    if rem == 9:
        q.append(10*p + rem -1)
        q.append(10*p + rem)
    
    count += 1

print(p)

Measured memory_bytes: 11968
#%%

x , y = map(int, input().split())

correct = False

i = 1
j = 1

for i in range(x + 1):
    for j in range(x + 1):
        if i * 4 + ((j - i) * 2) == y:
            correct = True
            break
        else:
            correct = False
            continue
    
if x == 1 and (y == 2 or y == 4):
    correct = True
                         
if correct == True:
    print ("Yes")
else:
    print ("No")

Measured memory_bytes: 9232
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;
const int MAX_NODE = 110;

vector<int> makeInput(string input){
    vector<int> ret;
    stringstream ss(input);

    while(ss >>input) ret.push_back(atoi(input.c_str()));
    return ret;
}

int main(){
    int n;
    while(cin >>n && n){
        int d[MAX_NODE][MAX_NODE];
        REP(i, MAX_NODE) REP(j, MAX_NODE) d[i][j] = INF;
        REP(i, MAX_NODE) d[i][i] = 0;
        vector< vector<int> > graph(MAX_NODE, vector<int>(MAX_NODE));
        string dust_str;
        getline(cin, dust_str);
        //make graph
        REP(i, n){
            string input;
            getline(cin, input);
            vector<int> sum_list = makeInput(input);

            //make
            REP(j, sum_list[1]){
                graph[sum_list[0]].push_back(sum_list[j + 2]);
                d[sum_list[0]][sum_list[j + 2]] = 1;
            }
        }

        //ワーシャルフロイド
        int v = n + 1;
        REP(k, v){
            REP(i, v){
                REP(j, v){
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }

        //cal ans
        int m;
        cin >>m;
        getline(cin, dust_str);
        REP(i, m){
            string input;
            getline(cin, input);
            vector<int> sum_list = makeInput(input);
            int from = sum_list[0], to = sum_list[1], ttl = sum_list[2];
            if(ttl < (d[from][to] + 1)) cout <<"NA" <<endl;
            else cout <<d[from][to] + 1 <<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1404
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,a[N];
LL l[N],r[N];
int main() {
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=3*n;i++)cin>>a[i];
  //
  priority_queue<int>q;
  LL tot=0;
  for(int i=1;i<=n;i++){
    tot+=a[i];
    q.push(-a[i]);
  }
  l[n]=tot;
  for(int i=n+1;i<=2*n;i++){
    //[1,i]  [i+1,3n]
    q.push(-a[i]);
    tot+=a[i];
    tot+=q.top();
    q.pop();
    l[i]=tot;
  }
  while(!q.empty())q.pop();tot=0;
  for(int i=3*n;i>2*n;i--)tot+=a[i],q.push(a[i]);
  r[2*n+1]=tot;
  for(int i=2*n;i>n;i--){
    tot+=a[i];
    q.push(a[i]);
    tot-=q.top();
    q.pop();
    r[i]=tot;
  }
  LL ans=LLONG_MIN;
  for(int i=n;i<=2*n;i++){
    ans=max(ans,l[i]-r[i+1]);
  }
  cout<<ans<<'\n';
  return 0;
}

Measured memory_bytes: 6548
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long ans=0;
		
		for(int c=0;c<n;c++){
    		long a=sc.nextInt();
          while(a>0){
            if(a%2==0){
          	ans++;
              a=a/2;
            }else{
            break;
            }
          }
    	}
    
    	System.out.println(ans);
    }
}


Measured memory_bytes: 48548
#include<iostream>
#include<map>
#include<vector>
#include<cstdio>
using namespace std;


int main()
{
  map<int,bool> exist;
  int a,b;
  cin >> a >> b;
  vector<int> A,B;
  vector<vector<int> > men;
  men.resize(2);
  men[0].resize(b),men[1].resize(b);
  A.resize(a),B.resize(b);
  for(int i=0;i<a;i++)
    scanf("%d",&A[i]);
  for(int i=0;i<b;i++)
    scanf("%d",&B[i]),men[0][i] = men[1][i] = 0,exist[B[i]] = true;

  

  int mex = 0;
  for(int i=0;i<a;i++)
    {
      if(!exist[A[i]])
	continue;
     
      for(int j=0;j<b;j++)
	{
	  if(A[i] == B[j])
	    {
	      men[1][j] = max(men[0][j],j-1>=0?men[0][j-1]+1:0);
	      if(!men[1][j])
		men[1][j] = 1;
	      mex = max(men[1][j],mex);
	    }
	}
      men[0] = men[1];
    }
 
  cout << mex << endl;
  return 0;
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;
using vvs = vector<vs>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, (int)v.size()) {
        if (i)
            os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
    for (auto val : array)
        std::cout << val << ", ";
    std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

    int n; std::cin >> n;
    vi a(n); rep(i, n) std::cin >> a[i];
    int x = 0;
    rep(i, n) x ^= a[i];
    rep(i, n) {
        std::cout << (x ^ a[i]) << (i+1 < n ? " " : "\n");
    }
}


Measured memory_bytes: 3944
import math

n, d = map(int, input().split())

arr = [list(map(int, input().split())) for i in range(n)]

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        sum_value = 0
        for k in range(d):
            sum_value += (arr[i][k] - arr[j][k]) ** 2
        if math.sqrt(sum_value).is_integer():
            ans += 1

print(ans)


Measured memory_bytes: 3060
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())
s = list(map(int, input().split()))

D = [[]]
for i in range(1, N):
  DD = []
  T = [0]
  for j in range(i, N, i):
    T.append(T[-1] + s[j])
  DD.append(T)
  T = [0]
  start = (N - 1) % i
  if start == 0: start += i
  for j in range(start, N, i):
    T.append(T[-1] + s[j])
  DD.append(T)
  D.append(DD)

ans = s[-1]
cnt = 0
for n in range(2, N - 1):
  end = N - 1 - n
  for m in make_divisors(end):
    if n <= m: break
    if n % m == 0 and end >= n: continue
    k = end // m
    a = D[m][0][k]
    l = len(D[m][1])
    b = D[m][1][-1] - D[m][1][l - k - 2]
    ans = max(ans, a + b)

print(ans)

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

using namespace std;

int main ()
{
	int N;
	while( cin >> N , N )
	{
		vector<vector<int>>data ( N + 1 , vector<int> ( N + 1 ) );
		for( size_t i = 1; i < N + 1; i++ )
		{
			for( size_t j = 1; j < N + 1; j++ )
			{
				char c;
				cin >> c;
				if( c == '.' )data[i][j] = 1;
			}
		}
		for( size_t i = 1; i < N + 1; i++ )
		{
			for( size_t j = 1; j < N + 1; j++ )
			{
				data[i][j] += data[i][j - 1];
			}
		}
		for( size_t i = 1; i < N + 1; i++ )
		{
			for( size_t j = 1; j < N + 1; j++ )
			{
				data[i][j] += data[i - 1][j];
			}
		}
		long long int ans = 0;
		for( size_t i = 0; i < N; i++ )
		{
			for( size_t j = 0; j < N; j++ )
			{
				for( size_t k = ans; i + k < N + 1 && j + k < N + 1; k++ )
				{
					long long int num = data[i + k][j + k] + data[i][j] - data[i + k][j] - data[i][j + k];
					if( k*k == num&& k > ans )
					{
						ans = k;
					}
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 5028