akhauriyash/Code-Regression huggingface dataset:
use proconio::{fastout, input};
#[allow(unused_mut)]
#[fastout]
fn main() {
    input! {
        m1: usize,
        _: usize,
        m2: usize,
        _: usize
    }
    println!("{}", if m1 == m2 { 0 } else { 1 });
}


Measured memory_bytes: 2156
import numpy as np
n = int(input())
a = np.array(tuple(map(int, input().split())))
b = len(np.where(a < 0)[0])
a = abs(a)
if b % 2 == 0:
    print(np.sum(a))
else:
    print(np.sum(a) - 2 * np.min(a))

Measured memory_bytes: 23436
using System;
class p
{
  static void Main()
  {
    string S = Console.ReadLine();
    bool result = true;
    for (int i = 0; i < (S.Length - 1) / 2; i++) {
      if (S[i] != S[S.Length - (i + 1)]) {
        result = false;
        break;
      }
    }
    for (int i = 0; i < (S.Length - 1) / 4; i++) {
      if (S[i] != S[((S.Length - 1) / 2) - (i + 1)]) {
        result = false;
        break;
      }
    }
    Console.WriteLine(result ? "Yes" : "No");
  }
}

Measured memory_bytes: 13140
#include<stdio.h>
int calc(int n);

int main(){
	int n;
	scanf("%d",&n);
	printf("%d\n",calc(n));
	return 0;
}

int calc(int n){
	int a;
	a=100000;
	for(;n>0;n--){
		a*=1.05;
		if(a%1000!=0){
			a=(a/1000+1)*1000;
		}
	}
	return a;
}

Measured memory_bytes: 588
def get10(x):
    ans =0
    alphabet = {'m':1000,'c':100,'x':10,'i':1}
    i =0
    while i < len(x):
        if not x[i] in alphabet:
            ans += int(x[i])*alphabet[x[i+1]]
            i +=2
        elif x[i] in alphabet:
            ans +=alphabet[x[i]]
            i+=1
    return ans

def getN(x):
    ans =[]
    temp = x
    while temp !=0:
        if temp//1000:
            if temp//1000 == 1: ans.append('m')
            else:
                ans.append(str(temp//1000)+'m')
            temp = temp%1000
        elif temp//100:
            if temp//100 == 1: ans.append('c')
            else:
                ans.append(str(temp//100)+'c')
            temp = temp%100
        elif temp//10:
            if temp//10 == 1: ans.append('x')
            else:
                ans.append(str(temp//10)+'x')
            temp = temp%10
        else:
            if temp == 1:ans.append('i')
            elif temp >0:
                ans.append(str(temp)+'i')
            temp = temp//10
        
    
    return  ''.join(ans)



n = int(input())
for _ in range(n):
    x,y = input().split(' ')
    temp =get10(x) + get10(y)
    print(getN(temp))




Measured memory_bytes: 5620
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;

const int MAXN=1e5+100;
const int INF=0x3FFFFFFF;
const ll MOD=1e9+7;

int t[MAXN],x[MAXN],y[MAXN];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>t[i]>>x[i]>>y[i];
    bool flag=1;
    for(int i=1;i<=n;i++)
    {
        int disx=abs(x[i]-x[i-1]);
        int disy=abs(y[i]-y[i-1]);
        int dist=t[i]-t[i-1];
        if(disx+disy>dist||(dist-disx-disy)%2!=0)
        {
            flag=0;
            break;
        }
    }
    if(flag)    cout<<"Yes"<<endl;
    else    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Contest
{
	class Program
	{
		static void Main(string[] args)
		{
			int[] abc = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int a = abc[0], b = abc[1], c = abc[2];
			Console.WriteLine(b - a == c - b ? "YES" : "NO");
		}
	}
}


Measured memory_bytes: 13268
#include<cstdio>
#include<cstring>

int fie[16][16];
int n;

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		memset(fie,0,sizeof(fie));
		int x=n/2,y=n/2+1;
		int cnt=1;
		while(cnt<=n*n){
			while(1){
				if(x>=0 && x<n && y>=0 && y<n){
					if(fie[x][y]==0)break;
					if(fie[x][y]!=0)x--,y++;
				}else{
					if(x<0)x=n-1;
					if(x>=n)x=0;
					if(y>=n)y=0;
				}
			}
			fie[x][y]=cnt;
			x++,y++;
			cnt++;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)printf("%4d",fie[j][i]);
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 1044
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println(getString(sc).substring(0, 3));
	}

	/**
	 * *汎用メソッド<br>
	 * 入力した配列に対する順列を取得
	 *
	 * @param numArray
	 * @return
	 */
	private static List<Integer[]> getPermutation(int[] numArray) {
		List<Integer[]> permutation = new ArrayList<>();
		Integer[] ans = new Integer[numArray.length];
		boolean[] used = new boolean[numArray.length];

		return buildPermutaion(permutation, numArray, ans, used, 0);
	}

	/**
	 * *汎用メソッド(内部)<br>
	 * 入力した配列に対する順列を作成
	 *
	 * @param list
	 * @param numArray
	 * @param ans
	 * @param used
	 * @param depth
	 * @return
	 */
	private static List<Integer[]> buildPermutaion(List<Integer[]> list, int[] numArray, Integer[] ans, boolean[] used,
			int depth) {

		// 全部使い切った時=>できた順列を返す
		if (depth == numArray.length) {
			list.add(ans.clone());
			return list;
		}
		// 使い切っていない場合

		for (int i = 0; i < numArray.length; i++) {
			if (used[i]) {
				continue;
			}
			ans[depth] = numArray[i];
			used[i] = true;
			list = buildPermutaion(list, numArray, ans, used, depth + 1);

			used[i] = false;
		}

		return list;
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}

class Status {
	long x;
	long tmpCoins;

	public Status(long x, long tmpCoins) {
		this.x = x;
		this.tmpCoins = tmpCoins;
	}
}


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

typedef long long ll;

int n, A[18];
map<pair<ll, ll>, ll> mem[18][18];

ll dfs(int l, int r, ll x, ll y) {
	if (r - l == 1)
		return 0;
	if (mem[l][r].count({x, y})) return mem[l][r][{x, y}];
	ll res = 1ll << 60;
	for (int i = l + 1; i < r; ++i)
		res = min(res, dfs(l, i, x, x + y) + dfs(i, r, x + y, y) + (x + y) * A[i]);
	return mem[l][r][{x, y}] = res;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", A + i);
	printf("%lld\n", dfs(0, n - 1, 1, 1) + A[0] + A[n - 1]);
	return 0;
}


Measured memory_bytes: 16512
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    
    int h,w;
    cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++)cin>>s[i];
    int dx[8] = {-1,-1,-1,0,0,1,1,1};
    int dy[8] = {-1,0,1,-1,1,-1,0,1};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j] == '.'){
                int cnt = 0;
                for(int k=0;k<8;k++){
                    int x = i+dx[k], y = j+dy[k];
                    if(x>=0 && x<h && y>=0 && y<w && s[x][y]=='#')cnt++;
                }
                s[i][j] = '0'+cnt;
            }
        }
    }
    for(int i=0;i<h;i++)cout<<s[i]<<endl;
}

Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline

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

    ans = float('inf')
    for i in range(1, 101):
        tmp = 0
        for j in range(N):
            tmp += (X[j] - i)**2
        ans = min(ans, tmp)
    print(ans)
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int N, M, X;
	cin >> N >> M >> X;
	int A[M];
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	int R = 0, L = 0;
	for (int i = X - 1; i > 0; i--)
	{
		for (int j = 0; j < M; j++)
		{
			if (i == A[j])
			{
				R++;
			}
		}
	}
	for (int i=X+1; i <N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			if(i == A[j])
			{
				L++;
			}
		}
	}
	cout << min(R, L) << endl;
	return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var s = Console.ReadLine().Split(' ');

        var dict = new Dictionary<int, int>();
        for (int i = 0; i < n; i++)
        {
            var x = int.Parse(s[i]);
            if (dict.ContainsKey(x))
            {
                dict[x]++;
            }
            else
            {
                dict[x] = 1;
            }
        }

        var ans = 0;
        foreach (var item in dict)
        {
            if (item.Key < item.Value)
            {
                ans += item.Value - item.Key;
            }
            else if (item.Key > item.Value)
            {
                ans += item.Value;
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 25056
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header
int main() {
	string s, t;
	cin >> s >> t;
	if(s.size()==t.size()){
		rep(i,s.size()){
			if(s[i]>t[i]){
				puts("GREATER");
				return 0;
			}else if(s[i]<t[i]){
				puts("LESS");
				return 0;
			}else ;
		}
		puts("EQUAL");
	}else{
		if(s.size()>t.size()) puts("GREATER");
		else puts("LESS");
	}
	return 0;
}

Measured memory_bytes: 3580
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = list(map(int, readline().split()))
    N.sort()
    if N==[1,4,7,9]:
        print('YES')
    else:
        print('NO')



if __name__ == '__main__':
    main()


Measured memory_bytes: 9232
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        byte a = scan.nextByte();
        byte b = scan.nextByte();
        if(a + b >= 10){
            System.out.println("error");
        }else{
            System.out.println(a + b);
        }
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
int n, A[100010], B[100010], P[100010][2];
ll s[200010];
vector<pair<int,int> > v;
int main() {
	memset(P, -1, sizeof(P));
	scanf("%d", &n);
	ll r1 = 0, r2 = 0;
	for(int i=1; i<=n; i++) {
		scanf("%d%d", A+i, B+i);
		r1 += A[i]; r2 += B[i];
		v.push_back({A[i], i});
		v.push_back({B[i], i});
	}
	sort(all(v));
	for(int i=0; i<sz(v); i++) {
		s[i] += v[i].first;
		s[i+1] += s[i];
		if(P[v[i].second][0] == -1) P[v[i].second][0] = i;
		else P[v[i].second][1] = i;
	}
	ll r = min(r1, r2);
	for(int i=1; i<=n; i++) {
		ll val = 0;
		if(n == 2);
		else if(n-3 < P[i][0]) val = s[n-3];
		else if(n-3 >= P[i][1]) val = s[n-1] - A[i] - B[i];
		else if(n-2 == P[i][1]) val = s[n-1] - A[i] - B[i];
		else val = s[n-2] - v[P[i][0]].first;
		r = min(r, val + A[i] + B[i]);
	}
	printf("%lld", r);
	return 0;
}

Measured memory_bytes: 5104
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

class SCC {
    void dfs(int v){
        used[v] = 1;
        for (auto &&u : G[v]) if(!used[u]) dfs(u);
        vs.emplace_back(v);
    }

    void dfs_r(int v, int k){
        used[v] = 1;
        cmp[v] = k;
        sz[k]++;
        for (auto &&u : G_r[v]) if(!used[u]) dfs_r(u, k);
    }
public:
    vector<vector<int>> G, G_r, G_out;
    vector<int> vs, used, cmp, sz;
    SCC() = default;
    explicit SCC(int n) : G(n), G_r(n), G_out(n), used(n), cmp(n), sz(n) {}

    void add_edge(int a, int b){
        G[a].emplace_back(b);
        G_r[b].emplace_back(a);
    }

    int build() {
        int n = G.size();
        for (int i = 0; i < n; ++i) if(!used[i]) dfs(i);
        fill(used.begin(),used.end(), 0);
        int k = 0;
        for (int i = n - 1; i >= 0; --i) {
            if(!used[vs[i]]){
                dfs_r(vs[i], k++);
            }
        }
        G_out.resize(k);
        sz.resize(k);
        for (int i = 0; i < n; ++i) {
            for (auto &&j : G[i]) {
                if(cmp[i] != cmp[j]){
                    G_out[cmp[i]].emplace_back(cmp[j]);
                }
            }
        }
        return k;
    }

    int operator[](int k) const { return cmp[k]; }
};



int main() {
    int n, m;
    cin >> n >> m;
    SCC G(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        G.add_edge(a, b);
    }
    printf("%d\n", G.build());
    vector<vector<int>> res(G.sz.size());
    for (int i = 0; i < n; ++i) {
        res[G[i]].emplace_back(i);
    }
    for (int i = 0; i < G.sz.size(); ++i) {
        printf("%d", G.sz[i]);
        for (auto &&j : res[i]) {
            printf(" %d", j);
        }
        puts("");
    }
    return 0;
}

Measured memory_bytes: 105032
#include <bits/stdc++.h>
   
#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)<(y)?(x):(y)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
int main(){
    LL n,a,b; cin >> n >> a >> b;
    if(a > b) swap(a,b);
    if((b-a+1)&1) cout << (b-a)/2 << '\n';
    else{
        cout << min(a,n-b+1)+(b-a)/2 << '\n';
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const double EPS =  1e-10;
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point{
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y){}

    Point operator + (Point p){
        return Point(x + p.x, y + p.y);
    }
    Point operator - (Point p){
        return Point(x - p.x, y - p.y);
    }
    Point operator * (Point p){
        return Point(x * p.x, y * p.y);
    }
    Point operator / (Point p){
        return Point(x / p.x, y / p.y);
    }

    double abs(){
        return sqrt(norm());
    }
    double norm(){
        return x * x + y * y;
    }

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator == (const Point &p) const {
        return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
    }
    
    
};



typedef Point Vector;

class Segment : public Point{
    public:
    Point p1, p2;
    Segment(double a, double b, double c, double d){
        Point(a, b);
        Point(c, d);
    }
    
};

typedef Segment Line;

double dot(Point a, Point b){
    return a.x * b.x + a.y * b.y;
}
double cross(Point a, Point b){
    return a.x * b.y - a.y * b.x;
}
bool isOrthogonal(Point a, Point b){
    return equals(dot(a, b), 0.0);
}
bool isParallel(Point a, Point b){
    return equals(cross(a, b), 0.0);
}
bool isOrthogonal(Segment s1, Segment s2){
    return equals(dot(s1.p2 - s1.p1, s2.p2 - s1.p1), 0.0);
}
bool isParallel(Segment s1, Segment s2){
    return equals(cross(s1.p2 - s1.p1, s2.p2 - s1.p1), 0.0);
}

int main(void){
    int n;
    std::cin >> n;
    std::vector<Vector> v(2);
    int x1, x2, y1, y2;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            std::cin >> x1 >> y1 >> x2 >> y2;
            v[j] = Vector(x1 - x2, y1 - y2);
        }
    
        if(isParallel(v[0], v[1])){
            std::cout << 2 << std::endl;
        }else if(isOrthogonal(v[0], v[1])){
            std::cout << 1 << std::endl;
        }else{
            std::cout << 0 << std::endl;
        }
    }



    return 0;
    
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 1e6+5, P = 998244353, I2 = (P+1)/2;
int n, c[N], f[N], ans, mu[N], vis[N], g[N]; void fix(int &x) { x<P?0:x-=P; }
int main()
{
    scanf("%d", &n); for(int i = 1, a; i <= n; ++i) scanf("%d", &a), ++c[a], fix(ans += P-a);
    for(n = N-1; !c[n]; --n); mu[1] = 1;
    for(int i = 1; i <= n; ++i) for(int j = i; j <= n; j += i) fix(f[i] += (i64)c[j]*(j/i)%P);
    for(int i = 2; i <= n; ++i) if(!vis[i]) for(int j = i; j <= n; j += i)
        vis[j] = 1, mu[j] = (j/i)%i?P-mu[j/i]:0;
    for(int i = 1; i <= n; ++i) if(mu[i]) for(int j = i; j <= n; j += i) fix(g[j] += (i64)mu[i]*i%P);
    for(int T = 1; T <= n; ++T) fix(ans += (i64)T*f[T]%P*f[T]%P*g[T]%P);
    printf("%lld\n", (i64)ans*I2%P);
    return 0;
}

Measured memory_bytes: 23352
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LINF = 9223372036854775807;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main(){
	ll n, k; cin >> n >> k;
	cout << min(n%k,k-(n%k)) << endl;
	return 0;
}

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

long long d[100000];
int main() {
    long long n;
    cin >> n;
    long long a;
    long long ans=1;
    for(int i=0;i<n;i++){
        cin >> a;
        d[a]++;
        if(i==0&&a>0){
            ans=0;
            cout << ans << endl;
            return 0;
        }
        else if(i!=0&&a==0){
            ans=0;
            cout << ans << endl;
            return 0;
        }
    }
    long long m;
    for(int i=0;i<n-1;i++){
        if(d[i]>0) m=i;
        if(d[i]==0&&d[i+1]!=0){
            ans=0;
            cout << ans << endl;
            return 0;
        }
    }
    long long mod=998244353;
    for(int i=1;i<m;i++){
        for(int j=0;j<d[i+1];j++){
            ans=ans*d[i]%mod;
        }
    }
    cout << ans << endl;
    return 0;
}

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

bool check(int cx,int cy,int H,vector<int> x,vector<int> y,vector<int> h){
    int ch;
    bool flag = false;
    rep(i,x.size()){
        ch = max(H-abs(x[i]-cx)-abs(y[i]-cy),0);
        if(ch != h[i]){

        }
    }
}

int main(void)
{
    int N,cx,cy,H,ch,n;
    bool flag = true;

    cin >> N;
    vector<int> x(N),y(N),h(N);

    rep(i, N){
        cin >> x[i] >> y[i] >> h[i];
    }

    n = 0;

    //h[i] = 0だとHが求められない。0以外が出てくるまでループ
    rep(i,N){
        if(h[i] > 0){
            n = i;
            break;
        }
    }

    rep(cx,101){
        rep(cy,101){
            flag = true;
            H = h[n]+abs(x[n]-cx)+abs(y[n]-cy);
            rep(i,N){
                if(h[i] != max(H-abs(x[i]-cx)-abs(y[i]-cy),0)){
                    flag = false;
                    break;
                }
            }
            if(flag){//制約よい一つのピラミッドしか存在しない
                cout << cx << " " << cy << " " << H << endl;
            }
        }

    }
    

    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<map>
#include<random>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include <queue>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldb = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIF(v, n) printf("%."#n"f\n", v)
#define PRIY PRI("Yes")
#define PRIN PRI("No")
#define MINS(a,b) a = min(a,(decltype(a))(b))
#define MAXS(a,b) a = max(a,(decltype(a))(b))

ll mod = 1e9 + 7;

//拡張ユークリッドの互除法。戻り値は最大公約数、x,yはax+by=gcd(a,b)を満たす組の一つ
long long gcdext(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long g = gcdext(b, a % b, y, x);
	y -= a / b * x;
	return g;
}

//モジュラ逆数
long long modinv(long long a, long long mod) {
	long long x, y;
	gcdext(a, mod, x, y);
	x = ((x % mod) + mod) % mod;
	return x;
}

class com_table {
public:
	vector<long long> frac;
	vector<long long> finv;
	long long mod;
	com_table() = default;
	void init(long long size, long long mod) {
		this->mod = mod;
		frac.resize(size + 1);
		finv.resize(size + 1);
		frac[0] = 1;
		finv[0] = 1;
		for (int i = 1; i <= size; ++i) frac[i] = frac[i - 1] * i % mod;
		finv[size] = modinv(frac[size], mod);
		for (int i = size; i >= 2; --i) finv[i - 1] = finv[i] * i % mod;
	}
	long long operator()(int a, int b) {
		if (a < b)return 0;
		return ((frac[a] * finv[b] % mod) * finv[a - b]) % mod;
	}
};

com_table tbl;

ll T(ll X, ll Y) {
	ll ans = 0;
	REP(y, 0, Y + 1) {
		ans = (ans + tbl(y + X + 1, X)) % mod;
	}
	return ans;
}

ll Mod(ll  x) { return (x % mod + mod) % mod; }

int main() {
	tbl.init(3000000,mod);

	ll r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	--r1; --c1;
	ll ans = T(r2, c2);
	ans = Mod(ans);
	ans -= T(r2, c1);
	ans = Mod(ans);
	ans -= T(r1, c2);
	ans = Mod(ans);
	ans += T(r1, c1);
	ans = Mod(ans);
	PRI(ans);
	return 0;
}




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

int main(){
    ll x,a;
    cin>>x>>a;
    if(x<a){
        cout<<0<<endl;
    }else{
        cout<<10<<endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
long long R=1,C=1,H[800010],N[800010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(long long a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
double g(long long a,long long b,double c){return (b-1)/(c+a)+1+c;}
long long f(long long a,long long b){
  double l=0,r=1e16,m1,m2,i;
  //double m1,m2;
  while(l+0.0001<r){//printf("%d %d %d %d\n",l,m1,m2,r);
    m1=(l+l+r)/3;
    m2=(l+r+r)/3;//printf("%lf %lf %lf %lf\n",l,m1,m2,r);
    if(g(a,b,m1)>=g(a,b,m2))l=m1;//(long long)(m1+0.5);
    else                   r=m2;//(long long)(m2+0.5);
    //if(l+2>=r)break;
    //(b-1)/(m+a)>=(b-1)/(m+1+a)+1?(l=m):(r=m);
  }//printf("%lf %lld\n",l,(long long)(l+0.5));
  return (long long)(l+0.5);
}
int      ta[200010],to[400010],nt[400010];
long long a[400010], b[400010], c[400010],CO[200020];
void dijk(int v,int mi){
  int i,id[200010],f[200010]={0};
  R=C=1;
  for(i=0;i<=v;i++)CO[i]=1e18+10;
  CO[mi]=0;
  while(f[mi]-1){
    f[mi]=1;
    for(i=ta[mi];i+1;i=nt[i]){
      if(CO[mi]>c[i]){
	if(   CO[      to[i]]>CO[mi]+(b[i]-1)/(CO[mi]+a[i])+1){
	  hin(CO[id[R]=to[i]]=CO[mi]+(b[i]-1)/(CO[mi]+a[i])+1);
	}
      }
      else{
	if(   CO[      to[i]]>c[i]+  (b[i]-1)/(c [i ]+a[i])+1){
	  hin(CO[id[R]=to[i]]=c[i]+  (b[i]-1)/(c [i ]+a[i])+1);
	}
      }
    }
    while(f[mi]&&C-1)mi=id[hout()];
  }
}
int main(){
  int n,m,s,t,i,j,k;
  scanf("%d %d %d %d",&n,&m,&s,&t);
  for(i=0;i<=n;i++)ta[i]=-1;
  for(i=0;i<m;i++){
    scanf("%d %d %lld %lld",&j,&k,&a[i],&b[i]);
    to[i]=k;
    nt[i]=ta[j];
    ta[j]=i;
    to[i+m]=j;
    nt[i+m]=ta[k];
    ta[k  ]=i+m;
    a[i+m]=a[i];
    b[i+m]=b[i];
    c[i]=c[i+m]=f(a[i],b[i]);
  }
  //for(i=0;i<m;i++)printf("%d\n",c[i]);
  //printf("%d %d\n",(b[0]-1)/(c[0]+a[0])+1,c[0]+  (b[0]-1)/(c[0]+a[0])+1);
  dijk(n+1,s);
  printf("%lld\n",CO[t]<1e18?CO[t]:-1);
  return 0;
}



Measured memory_bytes: 21348
#include<stdio.h>
#define TRUE 1
#define FALSE -1

int solve(int, int);
int n;
int A[20];

int main(){
  int i, q, res;
  int Mj[200];

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

  for(i=0; i<q; i++){
    res = solve(0, Mj[i]);
    if(res == FALSE) printf("no\n");
    else printf("yes\n");
  }
  
}

int solve(int i, int m){
  int res, res2;
  if(m == 0) return TRUE;
  if(i >= n) return FALSE;

  res = solve(i+1, m);
  if(res == FALSE) res = solve(i+1, m-A[i]);
  return res;
}



Measured memory_bytes: 2048
def enter_card(L, R, f_point, e_point):
    if f_point < L:
        f_point = L
    if e_point > R:
        e_point = R
    return f_point, e_point

def open_list(L, R):
    if L > R:
        return 0
    else:
        return R - L + 1
   

N, M = map(int, input().split(' '))
f_point = 1
e_point = N
for i in range(M):
    L,  R = map(int, input().split(' '))
    f_point, e_point = enter_card(L, R, f_point, e_point)
a = open_list(f_point, e_point)
print(a)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<functional>
using namespace std;
using ll=long long;
int main(){
	int n;
	cin>>n;
	vector<ll> vec(n);
	set<ll> se;
	vector<ll> d;
	for(int i=0;i<n;i++){
		cin>>vec[i];
		if(se.count(vec[i])){
			d.push_back(vec[i]);
			se.erase(vec[i]);
		}else{
			se.insert(vec[i]);
		}
	}
	sort(d.begin(),d.end(),greater<ll>());
	if(d.size()>=2){
		cout<<d[0]*d[1]<<endl;
	}else{
		cout<<0<<endl;
	}
	return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
string a1;
string a2;
int maxlen[4000][4000];
vector<char> g;
void zxl(int x, int y){
  while(x > 0 && y > 0){
      if(a1[x-1] == a2[y-1]){
        g.push_back(a1[x-1]);
        x = x - 1;
        y = y - 1;
      }else{
        if(maxlen[x][y-1] >= maxlen[x-1][y]){ 
          x = x;
          y = y - 1;
        }else if(maxlen[x][y-1] < maxlen[x-1][y]){
          x = x - 1;
          y = y;
        }
      }
    }
    for(int i = g.size() - 1 ; i >= 0 ; i--){
      cout<<g[i];
    } 
}
int main(){
  while(cin>>a1>>a2){
    int length1 = a1.size();
    int length2 = a2.size();
    for(int i = 0; i <= length1; i++)
    maxlen[i][0] = 0;
    for(int j = 0; j <= length2; j++)
    maxlen[0][j] = 0;
    for(int i = 1; i <= length1; i++){
      for(int j = 1; j <= length2; j++){
        if(a1[i - 1] == a2[j - 1])
          maxlen[i][j] = maxlen[i - 1][j - 1] + 1;
        else
        maxlen[i][j] = max(maxlen[i][j - 1], maxlen[i - 1][j]);
      }
    }
    zxl(length1, length2);
    return 0; 
  }
} 


Measured memory_bytes: 47360
#include <stdio.h>

int solve(int i,int *a,int n,int q){
  int res=0;
  
  if(q==0)return 1;
  if(i>=n)return 0;
  return res = solve(i+1,a,n,q) || solve(i+1,a,n,q-a[i]);
}

int main(){
  int n,i,m,j,k;
  int a[20],q[200];
  
  scanf("%d",&n);
  for(i=0;i<n;++i){
    scanf("%d",&a[i]);
  }
  scanf("%d",&m);
  for(j=0;j<m;j++){
    scanf("%d",&q[j]);
  }

  for(k=0;k<m;k++){
    if(solve(0,a,n,q[k]))printf("yes\n");
    else printf("no\n");
  }
  return 0;
}



Measured memory_bytes: 2052
n = int(input())
d = {}
for _ in range(n):
    s = str(input())
    s = ''.join(sorted(s))
    if s not in d:
        d[s] = 1
    else:
        d[s] += 1
cnt = 0
for k, v in d.items():
    if v != 1:
        cnt += v * (v - 1) // 2
print(cnt)

Measured memory_bytes: 17808
#include<iostream>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
int main(){
  int n;
  cin >> n;
  while(n--){
    string done,message;
    cin >> done >> message;
    reverse(done.begin(),done.end());
    for(int i = 0 ; i < done.size() ; i++ ){
      switch(done[i]){
      case 'J':
        rotate(message.begin(),message.begin()+message.size()-1,message.end());
        break;
      case 'C':
        rotate(message.begin(),message.begin()+1,message.end());
        break;
      case 'E':
        for(int j = 0 ; j < message.size() / 2 ; j++ ){
          swap(message[j],message[(message.size()+1)/2+j]);
        }
        break;
      case 'A':
        reverse(message.begin(),message.end());
        break;
      case 'P':
        for(int j = 0 ; j < message.size() ; j++ ){
          if(isdigit(message[j])) message[j] = (message[j]-'0'+9)%10+'0';
        }
        break;
      case 'M':
        for(int j = 0 ; j < message.size() ; j++ ){
          if(isdigit(message[j])) message[j] = (message[j]-'0'+1)%10+'0';
        }
        break;
      }
      //cout << message << endl;
    }
    cout << message << endl;
  }
}

Measured memory_bytes: 1220
// Author:: Mohammad Faisal
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int alice, bob;
  cin >> alice >> bob;
  if(alice== bob)
    cout<<"Draw";
  else if(alice > bob && bob!=1)
    cout<<"Alice";
  else if(alice > bob && bob==1)
    cout<<"Bob";
  else if(alice < bob && alice!=1)
    cout<<"Bob";
  else if(alice <bob && alice==1)
    cout<<"Alice";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int a, b; cin >> a >> b;
  if(a <= 0 && 0 <= b) {
    cout << "Zero" << endl;
  } else if(0 < a) {
    cout << "Positive" << endl;
  } else if((b - a + 1) % 2) {
    cout << "Negative" << endl;
  } else {
    cout << "Positive" << endl;
  }
}


Measured memory_bytes: 256
N, Y = map(int, input().split())

for x in range(0, N+1):
    for y in range(0, N + 1):
        z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y and z >= 0:
            print(str(x) + ' ' + str(y) + ' ' + str(z))
            exit()
print('-1 -1 -1')


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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dumpi(x1) fprintf(stderr, "#%s.%d (%s) = (%d)\n", __func__, __LINE__, #x1, x1);
#define dumpii(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%d, %d)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumpiii(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%d, %d, %d)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);

struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
};

template<typename a>
struct S001 {
  int n;
  std::vector<a> xs;
  S001(const std::vector<a>& ys) : xs(ys.size() + 1) {
    int n = (int)ys.size();
    a t = 0;
    xs[0] = 0;
    for(int i = 0; i < n; ++i) {
      t += ys[i];
      xs[i+1] = t;
    }
  }
  a operator [] (int i) {
    return xs[i];
  }
  a f(int x, int y) {
    return xs[y] - xs[x];
  }
};

struct Solver {
  long n;
  std::vector<long> xs;
  Solver() {
    S002 r;
    r >= n >n>= xs;
  }
  void solve() {
    std::sort(xs.begin(), xs.end());
    S001<long> ys(xs);
    long res = 1;
    for(int i = n - 2; i >= 0; --i) {
      if( ys.f(0, i + 1) * 2 >= xs[i + 1] ) {
        res += 1;
      }
      else {
        break;
      }
    }
    printf("%ld\n", res);
  }  
};

int main() {
  for(;;) std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n, k;
    cin >> n >> k;

    constexpr auto M = 1000000007L;
    int64_t ans = 0;
    for (auto i : irange(k, n + 2)) {
        ans += (n + 1 + n + 1 - i) * i / 2 - i * i / 2 + 1;
        ans %= M;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3632
import java.util.Scanner;

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

        System.out.println((X / 500) * 1000 + ((X % 500) / 5) * 5);
    }

}


Measured memory_bytes: 23764
def calc(s)
  res = []
  loop do
    if s[$pos] == '['
      $pos += 1
      res << calc(s)
    elsif s[$pos] == ']'
      break
    else  # num
      x = ''
      while s[$pos] != ']'
        x += s[$pos]
        $pos += 1
      end
      return x.to_i / 2 + 1
    end
    $pos += 1
  end
  res.sort.first(res.size/2+1).reduce(:+)
end

gets.to_i.times do
  $pos = 1
  puts calc(gets)
end

Measured memory_bytes: 6144
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10e+6
#define DEKA 1000000007

using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    if(b==1){
        cout << 0 << endl;
    }
    else{
    int ans=1;
    b=b-a;
    if(b<=0) cout << ans << endl;
    else {
        int d=b/(a-1);
        if(b%(a-1)==0) cout << ans+d << endl;
        else cout << ans+d+1 << endl;
    }
    }
}

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

int main()
{
   bool can = false;
   int animals, legs;
   cin >> animals >> legs;
   if (animals == 1){
      if(legs == 4 || legs == 2){
         can = true;
      } 
   }else{
      for(int i = 0; i <= animals; i++){
         int sum = 0, turtles = 0;
         turtles = animals - i;
         sum = (2 * i) + (4 * turtles);
         if(sum == legs){ 
            can = true;
            break;
         }
      }
   }
   if (can == true) cout << "Yes" << endl;
   else cout << "No" << endl;
   return 0;
}


Measured memory_bytes: 3568
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;
	int n, m;
	cin >> n >> m;
	
	cout << n*(n-1)/2 + m*(m-1)/2 << endl;
}

Measured memory_bytes: 256
import sys
s=input()
q=int(input())
a=[]
b=[]
c=0
for i in sys.stdin:
  if '1' in i.split()[0]:
    a,b=b,a
    c+=1
  else:
    if '1' in i.split()[1]:
      a.append(i.split()[2])
    else:
      b.append(i.split()[2])
if c%2==1:
  s=''.join(list(s)[::-1])
print(''.join(a[::-1])+s+''.join(b))

Measured memory_bytes: 6260
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: int, B: int, v: "List[int]"):
    def choose(n, k):
        ret = 1
        k = min(k, n - k)
        for i in range(1, k + 1):
            ret *= (n - i + 1)
            ret //= i
        return ret

    count = {}
    v.sort(reverse=True)
    ave = [0] * N
    for val in v:
        if val in count:
            count[val] += 1
        else:
            count[val]  = 1
    for i in range(A - 1, B):
        ave[i] = sum(v[:i + 1]) / (i + 1)
    mx = max(ave)

    ret = 0
    for i in range(A - 1, B):
        if ave[i] == mx:
            c = 0
            for j in range(i + 1, N):
                if v[j] == v[i]:
                    c += 1
            ret += choose(count[v[i]], c)
    print(mx)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    v = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, B, v)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <numeric>
#include <sstream>
#include <queue>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()
#define print(s) cout << (s) << endl

string strAdd(string a,string b){
    if(a.size() < b.size())return strAdd(b,a);
    
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    
    int carry = 0;
    for(int i=0;i<a.size();i++){
        a[i] += carry;
        if(i<b.size())a[i] += b[i] - '0';
        if(a[i] > '9'){
            carry = 1;
            a[i] -= 10;
        }else carry = 0;
    }
    
    if(carry)a += "1";
    reverse(a.begin(),a.end());
    return a;
}

bool checkStr(string s) {
    return s.size() > 1 && s[0] == '0';
}

bool isCorrect(string s) {
    int plus;
    REP(i,s.size()) {
        if (s[i] == '+') {
            plus = i;
            break;
        }
    }
    int equal;
    FOR(i,plus+2,s.size()) {
        if (s[i] == '=') {
            equal = i;
            break;
        }
    }
    string a = "", b = "", c = "";
    REP(i,plus) {
        a += s[i];
    }
    FOR(i,plus+1,equal) {
        b += s[i];
    }
    FOR(i,equal+1,s.size()) {
        c += s[i];
    }
    if (checkStr(a) || checkStr(b) || checkStr(c)) {
        return false;
    }
    return strAdd(a,b) == c;
}

string replaceX(string s, int j) {
    string t = "";
    REP(i,s.size()) {
        if (s[i] == 'X') t += (char)('0' + j);
        else t += s[i];
    }
    return t;
}

void solve110(string s) {
    REP(i,10) {
        string t = replaceX(s,i);
        if (isCorrect(t)) {
            cout << i << endl;
            return;
        }
    }
    cout << "NA" << endl;
}

int main() {
    string s;
    while (cin >> s) {
        solve110(s);
    }
    return 0;
}

Measured memory_bytes: 3056
//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

const long long INF = 1LL << 55;

#define itn int
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define rrep(i,n) for(int i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }

#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void) {
	int n; cin >> n;
	vector<ll> a(3 * n);
	rep(i, 3 * n) {
		cin >> a[i];
	}

	vector<ll> left(3*n), right(3*n);
	priority_queue<ll,vector<ll>,greater<ll>> l;
	ll sum = 0;
	for (int i = 0; i < n; i++)
	{
		l.push(a[i]);
		sum += a[i];
	}
	left[n - 1] = sum;
	for (int i = n; i < 2 * n; i++) {
		if (l.top() < a[i]) {
			sum += a[i] - l.top();
			l.pop();
			l.push(a[i]);
			left[i] = sum;
		}
		else {
			left[i] = sum;
		}
	}

	priority_queue<ll> r;
	sum = 0;
	for (int i = 3 * n - 1; i >= 2 * n; i--) {
		sum += a[i];
		r.push(a[i]);
	}
	right[2 * n] = sum;
	for (int i = 2 * n - 1; i >= n; i--) {
		if (r.top() > a[i]) {
			sum -= r.top() - a[i];
			right[i] = sum;
			r.pop();
			r.push(a[i]);
		}
		else {
			right[i] = sum;
		}
	}

	vector<ll> ans;
	for (int i = n - 1; i < 2 * n; i++) {
		ans.pb(left[i] - right[i+1]);
	}
	sort(all(ans));
	reverse(all(ans));
	cout << ans[0] << endl;
	return 0;
}

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

int main() {

  int N;
  string S,answer; cin>>N>>S;

  for(int i =0; i<N/2;i++){
   if(S.at(i+N/2)!=S.at(i)){answer="No"; break;}
    else{answer="Yes";}
  }
if(N%2==1){answer="No";}
	cout<<answer<<endl;
}


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

int solve(vector<int>& v1, vector<int>& v2) {
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());

  int sum1 = accumulate(v1.begin(), v1.end(), 0);
  int sum2 = accumulate(v2.begin(), v2.end(), 0);
  int diff = sum2 - sum1;

  if (diff % 2 == 0) {
    diff /= -2;
    for (auto i = 0; i < v1.size(); i++) {
      for (auto j = 0; j < v2.size(); j++) {
	if (v1[i] - v2[j] == diff) {
	  cout << v1[i] << " " << v2[j] << endl;
	  return 0;
	}
      }
    }
  }
  cout << -1 << endl;
  return 1;
}

int main() {
  int n, m;
  while(cin >> n >> m, n | m) {
    vector<int> taro(n), hanako(m);
    int s;
    for (int i = 0; i < n; i++) {
      cin >> taro[i];
    }
    
    for (int i = 0; i < m; i++) {
      cin >> hanako[i];
    }

    solve(taro, hanako);
  }

  return 0;
}


Measured memory_bytes: 3112
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>
#include <cassert>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

vector<int> linear(vector<int> stone){
	int n = stone.size();
	int state = 0;
	for(int i = n-2; i >= 0; i--){
		bool eq = (stone[i+1] == stone[i]);
		if(!eq && (state || i % 2 == 0)){
			stone[i] = !(stone[i]);
			state = 1;
		}else if(eq && (i % 2 != 0)){
			state = 0;
		}
	}
	return stone;
}
vector<int> wrong(vector<int> v){
	REP(i,v.size()){
		if(i % 2 == 1){
			for(int j = i - 1; j >= 0; j--){
				if(v[i] == v[j]) break;
				else v[j] = v[i];
			}
		}
	}
	return v;
}

int main(void){
  int n;
  while(cin>>n,n){
    if(n==0) break;
		vector<int> stone(n);
		REP(i,n)cin>>stone[i];
    /*
		if(linear(stone) != wrong(stone)){
      REP(i,n){cout<<stone[i]<<" ";} cout<<endl;
      cout<<"linear:"; REP(i,n){cout<<linear(stone)[i]<<" ";} cout<<endl;
      cout<<"wrong:"; REP(i,n){cout<<wrong(stone)[i]<<" ";} cout<<endl;
		}
    */
    /*
		//REP(i,n){cout<<stone[i]<<" ";} cout<<endl;
		vector<int> ans = linear(stone);
		int count = 0;
		REP(i,n)if(ans[i]==0)count++;
		//REP(i,n){cout<<ans[i]<<" ";} cout<<endl;
		cout<<count<<endl;
    */
    vector<int> comp;
    int last = -1;
    int ans = 0;
    REP(i,n){
      if(i % 2 == 1){
        comp.back() += 1;
        if(last != stone[i]){
          if(stone[i]==0) ans += comp.back();
          else ans -= comp.back() - 1;
          if(comp.size() >= 2){
            int t = comp.back();
            comp.pop_back();
            comp.back() += t;
          }
        }else{
          ans += (stone[i] == 0);
        }
      }else{
        if(last != stone[i]) {
          comp.push_back(1);
        }else{
          comp.back() += 1;
        }
        ans += (stone[i] == 0);
      }
      last = stone[i];
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
int modpow(int X,int Y){
  int sum=X,cnt=1;
  vi A;
  while(Y>=cnt){
    A.pb(sum);
    sum*=sum;
    sum%=MOD;
    cnt*=2;
  }
  int ret=1,M=A.size();
  REP(i,1,M){
    if(Y>=(1ll<<M-i)){
      ret*=A[M-i];
      ret%=MOD;
      Y-=(1ll<<M-i);
    }
  }
  return ret;
}
int fac[500000],finv[500000];
void COMinit(){
  fac[0]=fac[1]=finv[0]=finv[1]=1;
  rep(i,2,500000){
    fac[i]=fac[i-1]*i%MOD;
    finv[i]=finv[i-1]*modpow(i,MOD-2)%MOD;
  }
}
int COM(int N,int K){
  if(N<K||N<0||K<0) return 0;
  return fac[N]*finv[K]%MOD*finv[N-K]%MOD;
}
signed main(){
  COMinit();
  int N; cin>>N;
  vi A(N),B(N+1);
  rep(i,0,N) cin>>A[i];
  sort(ALL(A),greater<int>());
  int ans=0;
  int sum=0;
  rep(i,0,N){
    sum=(sum*2+modpow(2,i-1))%MOD;
    ans+=modpow(2,N)*modpow(2,N-i-1)%MOD*A[i]%MOD*sum%MOD;
    ans%=MOD;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 11136
maze = []
maze.append(list(map(int, input().split())))
maze.append(list(map(int, input().split())))
maze.append(list(map(int, input().split())))

num = int(input())
for _ in range(num):
    num = int(input())
    for row in maze:
        if num in row:
            idx = row.index(num)
            row[idx] = "X"

if maze[0][0] == "X" and maze[1][1] == "X" and maze[2][2] == "X":
    print("Yes")
elif maze[0][2] == "X" and maze[1][1] == "X" and maze[2][0] == "X":
    print("Yes")
elif maze[0][0] == "X" and maze[0][1] == "X" and maze[0][2] == "X":
    print("Yes")
elif maze[1][0] == "X" and maze[1][1] == "X" and maze[1][2] == "X":
    print("Yes")
elif maze[2][0] == "X" and maze[2][1] == "X" and maze[2][2] == "X":
    print("Yes")
elif maze[0][0] == "X" and maze[1][0] == "X" and maze[2][0] == "X":
    print("Yes")
elif maze[0][1] == "X" and maze[1][1] == "X" and maze[2][1] == "X":
    print("Yes")
elif maze[0][2] == "X" and maze[1][2] == "X" and maze[2][2] == "X":
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3188
#include <stdio.h>

int main(void) {
  int i,n,answer=0;
  scanf("%d",&n);
  int S[n];
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
    }
  int q;
  scanf("%d",&q);
  int T[q];
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
    }
    
    
  for(i = 0; i < q; i++){
    int right = n;
    int left = 0;
    int mid;
    while(left < right){
      mid = (left + right) / 2;
      if(S[mid] == T[i]){
    answer++;
    break;
      }else if(S[mid] > T[i]){
    right = mid;
      }else{
    left = mid+1;
      }
    }
  }
    
  printf("%d\n", answer);
  return 0;
}

Measured memory_bytes: 1184