akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef int Weight;
typedef int Capacity;
struct Edge {
	int src, dst; Capacity cap;
	Edge(int s, int d, Capacity c) : src(s), dst(d), cap(c) {}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct Dinic {
	int n, s, t;
	vector<int> level, prog, que;
	vector<vector<Capacity> > cap, flow;
	vector<vector<int> > g;
	Capacity inf;
	Dinic() {}
	Dinic(const Graph &graph)
		: n(graph.size()),
		cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
		g(n, vector<int>()), inf((int)1e9) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < graph[i].size(); j++) {
				const Edge& e = graph[i][j];
				int u = e.src, v = e.dst;
				Capacity c = e.cap;
				add_edge(u, v, c);
			}
		}
	}
	Dinic(int n_) : n(n_), cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
		g(n, vector<int>()), inf((int)1e9) {
	}
	void add_edge(int u, int v, Capacity c) {
		cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
		g[u].push_back(v); g[v].push_back(u);
	}
	void reset() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				cap[i][j] = flow[i][j] = 0;
			}
			g[i].clear();
		}
	}
	inline Capacity residue(int u, int v) { return cap[u][v] - flow[u][v]; }
	Capacity solve(int s_, int t_) {
		this->t = t_, this->s = s_;
		que.resize(n + 1);
		Capacity res = 0;
		while(levelize()) { prog.assign(n, 0); res += augment(s, inf); }
		return res;
	}
	bool levelize() {
		int l = 0, r = 0;
		level.assign(n, -1); level[s] = 0; que[r++] = s;
		while(l != r) {
			int v = que[l++]; if(v == t) break;
			for(int i = 0; i < g[v].size(); i++) {
				const int& d = g[v][i];
				if(level[d] == -1 && residue(v, d) != 0) {
					level[d] = level[v] + 1; que[r++] = d;
				}
			}
		}
		return level[t] != -1;
	}
	Capacity augment(int v, Capacity lim) {
		Capacity res = 0;
		if(v == t) return lim;
		for(int &i = prog[v]; i < (int)g[v].size(); i++) {
			const int &d = g[v][i];
			if(residue(v, d) == 0 || level[v] >= level[d]) continue;
			const Capacity aug = augment(d, min(lim, residue(v, d)));
			flow[v][d] += aug; flow[d][v] -= aug;
			res += aug; lim -= aug;
			if(lim == 0) break;
		}
		return res;
	}
};

string b[100];

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

	int H, W;
	cin >> H >> W;

	int sx = 0, sy = 0, tx = 0, ty = 0;
	Dinic d(H + W + 2);
	for(int y = 0; y < H; y++) {
		cin >> b[y];
		for(int x = 0; x < W; x++) {
			if(b[y][x] == 'S') sx = x, sy = y;
			if(b[y][x] == 'T') tx = x, ty = y;
			if(b[y][x] == 'o') {
				d.add_edge(x, W + y, 1);
				d.add_edge(W + y, x, 1);
			}
		}
	}

	if(sx == tx || sy == ty) {
		cout << -1 << endl;
		return 0;
	}

	int S = H + W, T = S + 1;
	d.add_edge(S, sx, 1000000);
	d.add_edge(S, W + sy, 1000000);
	d.add_edge(tx, T, 1000000);
	d.add_edge(W + ty, T, 1000000);

	cout << d.solve(S, T) << endl;
}

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

int main(){
    long long n,y;
    cin>>n>>y;
    int set=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            
                if(10000*i+5000*j+1000*(n-i-j)==y){
                    cout<<i<<" "<<j<<" "<<n-i-j<<endl;
                    set=0;
                    break;
                }
            
            
        }
        if(set==0) break;
    }
    if(set==1) cout<<"-1 -1 -1"<<endl;
}

Measured memory_bytes: 256
/*
        Author: Prokash
                CSE48, JU

*/

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

typedef long long ll;
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll mx=100001;
ll ara[mx+1];
int main()
{
    FAST;
    ll t,k,a,b;
    cin>>t>>k;
    while(t--)
    {
        cin>>a>>b;
        ara[a]+=b;
    }
    for(ll i=0;i<=mx;i++)
    {
        if(ara[i]>=k)
        {
            cout<<i<<endl;
            return 0;
        }
        k=k-ara[i];
    }
    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		// 入力フェーズ
		string S = Console.ReadLine();
        int N = S.Length;
        int fav = 753;
        int min = 1000;
        for (int i = 0; i <= N - 3; i++ )
        {
            // i文字目から3桁のXを取り出す
            int X = int.Parse(S.Substring(i, 3));
            if (Math.Abs(753-X) < min) min = Math.Abs(753-X);
        }
        //出力
        Console.WriteLine(min);
    }

}

Measured memory_bytes: 13140
#include <iostream>
using namespace std;
 
static const int ds = 6;
 
void dsort( int a[], int i0, int i1, int i2, int i3 ) {
    int ta[] = { a[i0], a[i1], a[i2], a[i3] };
    int min = ta[0];
    for( int i = 0; i < 4; i++ ) {
        if( min > ta[i] ) {
            min = ta[i];
        }
    }
 
    int t = 0;
    while( true ) {
        if( a[i0] == min ) {
            break;
        }
        t = a[i0];a[i0]=a[i1];a[i1]=a[i2];a[i2]=a[i3];a[i3]=t;
    }
 
    return;
}
 
bool dcomp( int a[], int b[] )
{
    for( int i = 0; i < ds; i++ ) {
        if( a[i] != b[i] ) {
            return false;
        }
    }
 
    return true;
}
 
bool dcheck( int a[], int b[100][ds], int last ) {
    bool ret = false;
    for( int i = 0; i < last; i++ ) {
        ret = dcomp( a, b[i] );
        if( ret == true ) {
            break;
        }
    }
    return ret;
}
 
int main()
{
    int n, dx[ds], dbuff[100][ds];
    bool ret = false;
 
    cin >> n;
 
    for( int i = 0; i < n; i++ ) {
        for( int j = 0; j < ds; j++ ) {
            cin >> dx[j];
        }
        dsort( dx, 0, 1, 5, 4 );
        dsort( dx, 0, 3, 5, 2 );
        dsort( dx, 1, 2, 4, 3 );
 
        ret = dcheck( dx, dbuff, i );
        if( ret == true ) {
            break;
        }
 
        for( int j = 0; j < ds; j++ ) {
            dbuff[i][j] = dx[j];
        }
    }
 
    cout << (ret?"No":"Yes") << endl;
 
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);


int main(){
  int x,y,z;
  cin >> x >> y >> z;

  cout << (x-z)/(y+z) << endl;
}


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

using namespace std;

const int MAX = 100010;
int a[MAX];
int L[MAX];
int n;
int len;

int main() {
    scanf("%d", &n);
    len = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    L[0] = a[0];
    len = 1;
    for (int i = 1; i < n; i++) {
        if (L[len-1] < a[i]) {
            L[len++] = a[i];
        } else {
            *lower_bound(L, L+len, a[i]) = a[i];
        }
    }
    printf("%d\n", len);

    return 0;
}

Measured memory_bytes: 3940
N, M, C = list(map(int, input().split()))
B_list = list(map(int, input().split()))
ans = 0

for _ in range(N):
    judge_val = C
    A_list = list(map(int, input().split()))
    for i in range(M):
        judge_val += A_list[i] * B_list[i]
    if judge_val > 0:
        ans += 1

print(ans)



Measured memory_bytes: 3060
fun main(args: Array<String>) {
    val S = readLine()!!.toCharArray()
    val a = S.filterIndexed { i, c -> i % 2 == (c - 48).toInt() }.count()
    val b = S.filterIndexed { i, c -> i % 2 != (c - 48).toInt() }.count()
    println(Math.min(a, b))
}

Measured memory_bytes: 34484
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
using namespace std;
#define INF 1LL<<62
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

const int MAX_N=420000;

//セグメント木を持つグローバル配列
ll n;
ll dat2[2*MAX_N-1];

//初期化
void init2(ll n_){
    //簡単のために要素数を2のべき乗に
    n=1;
    while(n<n_) n*=2;

    //全ての値をINT_MAXに
    for(int i=0;i<2*n-1;i++) dat2[i]=0;
}

//k番目の値(0-indexed)をaに変更
void update2(int k,ll a){
    //葉の節点
    k+=n-1;
    dat2[k]=a;
    //登りながら更新
    while(k>0){
        k=(k-1)/2;
        dat2[k]=max(dat2[k*2+1],dat2[k*2+2]);
    }
}

//[a,b)の最小値を求める
//後ろの方の引数は、計算の簡単のための引数
//ｋは接点の番号、l,rはその接点が[l,r)に対応づいていることを表す
//したがって、外からはquery(a,b,0,0,n)として呼ぶ
ll query2(int a,int b,int k,int l,int r){
    //[a,b)と[l,r)が交差しなければ,INT_MAX
    if(r<=a || b<=l) return -1;

    //[a,b)が[l,r)を完全に含んでいれば、この節点の値
    if(a<=l && r<=b) return dat2[k];
    else{
        //そうでなければ、２つの子の最小値
        ll vl=query2(a,b,k*2+1,l,(l+r)/2);
        ll vr=query2(a,b,k*2+2,(l+r)/2,r);
        return max(vl,vr);
    }
}


int main(){
    int N;
    cin>>N;
    int h[210000];
    ll a[210000];
    for(int i=0;i<N;i++) cin>>h[i];
    for(int i=0;i<N;i++) cin>>a[i];

    init2(N+1);
    for(int i=0;i<N;i++){
        ll x=query2(0,h[i],0,0,n);
        update2(h[i],x+a[i]);
    }
    cout<<query2(1,N+1,0,0,n)<<endl;


}


Measured memory_bytes: 8704
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        // 主処理
        String result = s.charAt(2) == s.charAt(3) && s.charAt(4) == s.charAt(5) ? "Yes" : "No";

        // 出力
        System.out.println(result);
        sc.close();
    }
}


Measured memory_bytes: 22100
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli unsigned long long int
#define MOD 1000000007
#define DEBUG 0
#define REP(i,n) for(int i=0;i<n;i++)

#define TATE 0
#define YOKO 1

/* 文字列→形式に変換*/


lli hash2(lli a,lli b){
	return a*10000000 + b;
}
int main(){

	lli n;

	cin>>n;
	map <lli,lli> d;
	map<lli,vector<lli>> v;
	REP(i,n-1){
		lli a,b,c;
		cin>>a>>b>>c;
		d[hash2(a,b)] = c;
		d[hash2(b,a)] = c;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	lli Q,k;
	cin>>Q>>k;

	/* 準備 kをから各点までの距離をさんしゅつしておけばよい*/
	/* これは単なる幅優先探索でOK*/

	lli flag[100010];
	REP(i,100010)flag[i]=0;

	queue<lli> q;
	queue<lli> length;
	q.push(k);
	length.push(0);
	flag[k]=0;

	while(q.size()){
		lli now = q.front();
		lli nowLength = length.front();
		q.pop();
		length.pop();
		d[hash2(k,now)] = nowLength;
		d[hash2(now,k)] = nowLength;

		for(auto e:v[now]){
			if(flag[e])continue;

			lli nextLength = nowLength + d[hash2(now,e)];
			flag[e]=1;
			q.push(e);
			length.push(nextLength);
		}
	}

	REP(i,Q){
		lli x,y;
		cin >> x>>y;
		cout<<d[hash2(x,k)]+d[hash2(k,y)]<<endl;
	}


	return 0;
}
 

Measured memory_bytes: 40576
import java.io.*;
import java.util.*;

 
public class Main{
	int N;
	int[] A;
	public void solve(){
		N = nextInt();
		A = new int[N];
		for(int i = 0; i < N; i++){
			A[i] = nextInt();
		}
		int[] cnt = new int[N];
		int max = 0;
		for(int i = 0; i < N; i++){
			cnt[A[i]]++;
			max = Math.max(max, A[i]);
		}
		if(max == 1){
			if(N == 2){
				out.println("Possible");
				return;
			}else{
				out.println("Impossible");
				return;
			}
		}else{
			for(int i = max; i >= max / 2 + 1; i--){
				if(cnt[i] < 2){
					out.println("Impossible");
					return;
				}
			}
			if(max % 2 == 0 && cnt[max / 2] != 1){
				out.println("Impossible");
				return;
			}
			if(max % 2 == 1 && cnt[(max + 1) / 2] != 2){
				out.println("Impossible");
				return;
			}
			for(int i = (max + 1) / 2 - 1; i > 0; i--){
				if(cnt[i] > 0){
					out.println("Impossible");
					return;
				}
			}
			out.println("Possible");
			return;
		}
		
	}
	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}

Measured memory_bytes: 8404
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int h, w, n;
    cin >> h >> w >> n;
    queue<int> q;
    rep(i, n) {
        int a;
        cin >> a;
        rep(_, a) q.push(i+1);
    }
    
    
    rep(i, h) {
        if (i % 2 == 0) {
            rep(j, w) {
                if (j != 0) cout << " ";
                cout << q.front();
                q.pop();
            }
        } else {
            vi a(w);
            for (int j = w-1; j >= 0; j--) {
                a[j] = q.front();
                q.pop();
            }
            rep(j, w) {
                if (j != 0) cout << " ";
                cout << a[j];
            }
        }
        cout << endl;
    }
}

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

int main() {
  string a;
  cin >> a;

  int c = 0;
  for (int i = 0; i < a.size(); i++) {
    if (a.at(i) == '1') {
      c++;
    }
  }

  cout << c << endl;
}


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

int main(){
	int n,k;
	cin>>n>>k;
	int a[n+1],mini = 1000000;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mini = min(mini,a[i]);
	}
	int dp[k+1] = {0};
	for(int i=0;i<mini;i++){
		dp[i] = 0;
	}
	for(int i=1;i<=k;i++){
		for(int j = 1;j<=n;j++){
			if(i >= a[j]){
				dp[i] = dp[i] || !dp[i-a[j]];
			}
		}
	}
	if(dp[k] == 1){
		cout<<"First"<<endl;
	}
	else
		cout<<"Second"<<endl;
}

Measured memory_bytes: 640
#include <cstdio>
using namespace std;
double W, H, x, y, u, v; int ans;
int main() {
  scanf("%lf %lf %lf %lf", &W, &H, &x, &y);
  u = W-x, v = H-y;
  if(x == u && y == v) ans = 1;
  else ans = 0;
  printf("%lf %d", W*H/2.0, ans);
}

Measured memory_bytes: 128
import java.util.*;

public class Main{

	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if((n |m) == 0) break;
			int [] hlist = new int[n];
			for(int i = 0; i < n; i++){
				hlist[i] = sc.nextInt();
			}
			int [] wlist = new int[m];
			for(int i= 0; i < m ;i++){
				wlist[i] = sc.nextInt();
			}
			HashMap<Integer, Integer> x = new HashMap<Integer, Integer>();
			HashMap<Integer, Integer> y = new HashMap<Integer, Integer>();
			int sum = 0;
			for(int i = 0; i < n; i++){
				sum += hlist[i];
				int v = sum;
				for(int j = 0; j <= i; j++){
					if(x.containsKey(v)){
						x.put(v, x.get(v) + 1);
					}
					else{
						x.put(v, 1);
					}
					v = v - hlist[j];
				}
			}
			
			sum = 0;
			for(int i = 0; i < m; i++){
				sum += wlist[i];
				int v = sum;
				for(int j = 0; j <= i; j++){
					if(y.containsKey(v)){
						y.put(v, y.get(v) + 1);
					}
					else{
						y.put(v, 1);
					}
					v = v - wlist[j];
				}
			}
			
			int ans = 0;
			for(int xx: x.keySet()){
				if(y.containsKey(xx)){
					ans += x.get(xx) * y.get(xx);
				}
			}
			System.out.println(ans);
		}
	}

	public static void main(String[] args) {
		new Main().doit();
	}
}

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

int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);

  int n;
  string s;
  cin >> n >> s;
  int num = 0;
  int ans = INT_MIN;
  for (int i = 0; i < n; ++i) {
    ans = max(ans, num);
    if (s[i] == 'I')
      num++;
    else
      num--;
  }
  ans = max(ans, num);
  cout << ans << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
typedef pair<int,int> P;
template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
signed main(signed argc, char* argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    const int MOD = 1000000007;
	int x;
	cin>>x;
	rep(i,-200,201){
		rep(j,-200,201){
			int a=i*i*i*i*i;
			int b=j*j*j*j*j;
			if(a-b==x){
				cout<<i<<' '<<j<<endl;
				return 0;
			}
		}
	}
}


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
  }*/

signed main(){
  string s;
  cin >> s;
  int n = s.size();

  int ans = 1, len = 1;
  rep(i, 1, n){
    if(len == 1 and s[i-1] == s[i]){
      i++;
      if(i >= n) break;
      len = 2;
    }else{
      len = 1;
    }
    ans++;
  }

  cout << ans << endl;

  return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  int sum = 0;
  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    sum += r - l + 1;
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int h, w;
char s, t;
string c[51];
P idx[30];

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
bool contain(int y, int x){
   return (0 <= y && y < h && 0 <= x && x < w);
}

vector<int> G[100];
int d[110];

void dijkstra(int s){
    fill(d, d + 100, INF);
    d[s] = 0;
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(P(d[s], s));
    while(!q.empty()){
        P p = q.top(); q.pop();
        int from = p.second;
        int cost = p.first;
        if(d[from] < cost) continue;
        rep(i, 0, G[from].size()){
            int next = G[from][i];
            // int next = e.to;
            int newCost = cost + 1;
            if(d[next] > newCost){
                d[next] = newCost;
                q.push(P(newCost, next));
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w >> s >> t;
    rep(i, 0, h) cin >> c[i];
    rep(i, 0, 30) idx[i] = {-1, -1};
    rep(i, 0, h){
        rep(j, 0, w){
            if('A' <= c[i][j] && c[i][j] <= 'Z'){
                idx[c[i][j] - 'A'] = {i, j};
            }
        }
    }
    rep(i, 0, 26){
        if(idx[i].first == -1) continue;
        rep(j, 0, 4){
            int y = idx[i].first + 2 * dy[j];
            int x = idx[i].second + 2 * dx[j];
            if(!contain(y, x)) continue;
            if(c[y][x] == '|'){
                if(j == 2 || j == 3) continue;
            }
            if(c[y][x] == '-'){
                if(j == 1 || j == 0) continue;
            }
            while(1){
                if(!contain(y, x)) break;
                if('A' <= c[y][x] && c[y][x] <= 'Z'){
                    G[i].push_back(c[y][x] - 'A');
                    break;
                }
                if(c[y][x] == '.') break;
                y += dy[j];
                x += dx[j];
            }
        }
    }
    dijkstra(s - 'A');
    cout << d[t - 'A'] << endl;
}


Measured memory_bytes: 3232
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <map>
#include <fstream>
#include <sstream>
#include <iterator>
#include <complex>
#include <iomanip>
using namespace std;

int main()
{
	int N,K;
	cin>>N>>K;

	double percentage = 0;

	for(int i=1; i<=N; i++)
	{
		
		//cout<<time<<endl;
		int base = 1;
		int now = i;
		while(now < K)
		{
			now *= 2;
			base *= 2;
		}
		percentage += 1.0 / (base * N);
	}

	cout<<setprecision(20)<<percentage<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <deque>
#include <iostream>
#include <set>
#include <string>
#include <utility>

using namespace std;

#define MAX_COST 9999999

int book_num, skill_num, target_point;
int min_cost = MAX_COST;

void recursive_calc(deque<bool> usages, int ind, deque<int> costs,
                    deque<deque<int>> points) {
  // 全ての本に対して購入するかどうかを決定した
  if (ind == book_num) {
    int cost = 0;
    deque<int> crt_points(skill_num, 0);

    // 購入する本のコストとポイントを加算
    for (int i = 0; i < book_num; i++) {
      if (usages[i]) {
        cost += costs[i];

        for (int j = 0; j < skill_num; j++) {
          crt_points[j] += points[i][j];
        }
      }
    }

    // コストが最小か確認
    if (cost >= min_cost) {
      return;
    }

    // スキルポイントが条件を満たしているか確認
    bool is_satisfy = true;

    for (int i = 0; i < skill_num; i++) {
      if (crt_points[i] < target_point) {
        is_satisfy = false;
        break;
      }
    }

    // スキルポイントが全て既定値を超えていたら、min_costを更新
    if (is_satisfy) {
      min_cost = cost;
    }

    return;
  }

  // この本を購入した場合としない場合で再帰
  usages[ind] = false;
  recursive_calc(usages, ind + 1, costs, points);
  usages[ind] = true;
  recursive_calc(usages, ind + 1, costs, points);
}

int main() {
  cin >> book_num >> skill_num >> target_point;

  deque<int> costs(book_num);
  deque<deque<int>> points(book_num, deque<int>(skill_num));

  // 入力
  for (int i = 0; i < book_num; i++) {
    cin >> costs[i];

    for (int j = 0; j < skill_num; j++) {
      cin >> points[i][j];
    }
  }

  deque<bool> usages(book_num);
  recursive_calc(usages, 0, costs, points);

  if (min_cost == MAX_COST) {
    cout << -1 << endl;
  } else {
    cout << min_cost << endl;
  }

  return 0;
}

Measured memory_bytes: 4048
d = {"AC":0,"WA":0,"TLE":0,"RE":0}
N = int(input())

for i in range(N):
    d[input()] += 1

print("AC x {}".format(d["AC"]))
print("WA x {}".format(d["WA"]))
print("TLE x {}".format(d["TLE"]))
print("RE x {}".format(d["RE"]))


Measured memory_bytes: 69828
import fractions
N = int(input())
A = list(map(int, input().split()))
x = [0] * N
y = [0] * N
tmp = A[0]
for i in range(1, N):
    t = fractions.gcd(tmp, A[i])
    x[i] = int(tmp / t)
    tmp = t
tmp = A[N - 1]
for i in range(N - 2, -1, -1):
    t = fractions.gcd(tmp, A[i])
    y[i] =  int(tmp / t)
    tmp = t
m = 0
for i in range(1, N - 1):
    a = fractions.gcd(x[i], y[i])
    if m < a:
        m = a
print(tmp * max(m, y[0], x[N - 1]))




Measured memory_bytes: 16124
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N,L;
    cin>>N>>L;
    int sum=((N-1)*N)/2+L*N;
    if(L>=0) cout<<sum-L;
    else if(L<0&&L>=-N+1) cout<<sum;
    else cout<<sum-(L+N-1);
}


Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
   
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a>=0 && b>=0)
  {
      if( d>=0)
      {
          cout<<b*d<<endl;
          return;
      }
      else
      {
          cout<<a*d<<endl;
          return;
      }
  }
  else if(a<0 && b>=0)
  {
      if(c>=0 && d>=0)
      {
          cout<<b*d<<endl;
          return;
      }
      else if(c<0 && d>=0)
       {
           cout<<max(a*c,b*d)<<endl;
           return;
       }
       else
       {
           cout<<a*c<<endl;
           return;
       }
  }
  else
  {
      if(c>=0 && d>=0)
      {
          cout<<b*c<<endl;
          return;
      }
     else
     cout<<a*c<<endl;
  }
}
int main(){
  ll t=1;
    while(t--)
    {
        solve();
    }
    
}


Measured memory_bytes: 3556
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

char s[60][30], buf[2];
int d[60][30][60][30][2];
struct st {
	int lx, ly, rx, ry, c;
	bool b;
};
bool operator<(st a, st b) {
	return a.c > b.c;
}
int C(char c) {
	if (isdigit(c))return c - '0';
	return 0;
}
int main() {
	int w, h;
	while (scanf("%d%d", &w, &h), w) {
		memset(d, 0x3f, sizeof(d));
		priority_queue<st>que;
		rep(i, h)rep(j, w) {
			scanf("%s", buf); s[i][j] = buf[0];
		}
		rep(j, w) {
			int i = h - 1;
			if (s[i][j] == 'S') {
				for (int k = -2; k <= 2; k++) {
					for (int t = 1; t <= 3 - abs(k); t++) {
						int nx = i + k, ny = j + t;
						if (0 <= nx&&nx < h && 0 <= ny&&ny < w&&s[nx][ny] != 'X') {
							d[i][j][nx][ny][0] = C(s[nx][ny]);
							que.push({ i,j,nx,ny,C(s[nx][ny]),0 });
						}
						nx = i + k, ny = j - t;
						if (0 <= nx&&nx < h && 0 <= ny&&ny < w&&s[nx][ny] != 'X') {
							d[nx][ny][i][j][1] = C(s[nx][ny]);
							que.push({ nx,ny,i,j,C(s[nx][ny]),1 });
						}
					}
				}
			}
		}
		while (!que.empty()) {
			st p = que.top(); que.pop();
			if (d[p.lx][p.ly][p.rx][p.ry][p.b] != p.c)continue;
			for (int k = -2; k <= 2; k++) {
				for (int t = 1; t <= 3 - abs(k); t++) {
					if (p.b) {
						int nx = p.lx + k, ny = p.ly + t;
						if (0 <= nx&&nx < h && 0 <= ny&&ny < w&&s[nx][ny] != 'X') {
							int&u = d[p.lx][p.ly][nx][ny][!p.b];
							int c = p.c + C(s[nx][ny]);
							if (u > c) {
								u = c; que.push({ p.lx,p.ly,nx,ny,u,!p.b });
							}
						}
					}
					else {
						int nx = p.rx + k, ny = p.ry - t;
						if (0 <= nx&&nx < h && 0 <= ny&&ny < w&&s[nx][ny] != 'X') {
							int&u = d[nx][ny][p.rx][p.ry][!p.b];
							int c = p.c + C(s[nx][ny]);
							if (u > c) {
								u = c; que.push({ nx,ny,p.rx,p.ry,u,!p.b });
							}
						}
					}
				}
			}
		}
		int Min = INF;
		rep(i, h)rep(j, w)rep(k, h)rep(t, w)rep(y, 2) {
			if (s[i][j] == 'T' || s[k][t] == 'T')Min = min(Min, d[i][j][k][t][y]);
		}
		if (Min == INF)puts("-1");
		else printf("%d\n", Min);
	}
}

Measured memory_bytes: 28724
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    map<string,int> mp;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        sort(all(s));
        mp[s] ++;
    }
    ll ans=0;
    for(auto &x:mp){
        int a = x.second;
        ans +=(ll)a*(a-1)/2;
    }
    cout << ans << endl;

}

Measured memory_bytes: 11404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;



int main(){
    ll n;
    cin >> n;
    ll a[n];
    ll cal[n+1];
    cal[0]=0;
    for(ll i=0;i<n;i++) cin >> a[i];
    sort(a,a+n);
    for(ll i=0;i<n;i++) cal[i+1]=cal[i]+a[i];
    ll memo=0;
    for(ll i=0;i<n-1;i++){
        if(cal[i+1]*2<a[i+1]) memo=i+1;
    }
    cout << n-memo << endl;
    return 0;
}  


Measured memory_bytes: 5100
from collections import Counter
n,k = map(int,input().split())
a = list(map(int,input().split()))
cnt = Counter(a)
mo = cnt.most_common()[::-1]
#print(mo)
ans = 0
for i in range(max(0,len(mo)-k)):
    ans += mo[i][1]
print(ans)


Measured memory_bytes: 39348
#include <bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define int long long
#define sz(x) (int)x.size()
#define mp make_pair
#define fi first
#define se second
#define io ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
#define INF 1e7
 
signed main()
{
	io;
	int k;
	cin >> k;
	string s = "ACL";
	string ans ="";
	rep(i,0,k)
	{
		ans+=s;
	}
	cout <<ans <<endl;
 
 
 
 
	
}
 
	

Measured memory_bytes: 3584
n = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      if L[i] < L[j] < L[k] and L[i] + L[j] > L[k] :
        ans += 1
print(ans) 
      

Measured memory_bytes: 9156
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> a,b;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1,x;i<=n;++i){
		cin>>x;
		a.push_back(x);
	}
	cin>>m;
	for(int i=1,x;i<=m;++i){
		cin>>x;
		b.push_back(x);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	if(includes(a.begin(),a.end(),b.begin(),b.end())){
		puts("YES");
	}
	else{
		puts("NO");
	}
	return 0;
}

Measured memory_bytes: 2548
#include "bits/stdc++.h"
using namespace std;
int INF = numeric_limits<int>::max() / 2;
using ll = long long;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;
    cin >> n >> k;
    map<int, int> mp;
    for(int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        mp[a]++;
    }
    vector<int> counts;
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
        //cout << itr->first << " " << itr->second << endl;
        counts.push_back(itr->second);
    }
    sort(counts.begin(), counts.end());
    int ans = 0;
    int num = counts.size() - k;
    if(num < 0) num = 0;
    for(int i = 0; i < num; i++){
        ans += counts[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10744
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int m1,m2,d1,d2;
    cin >> m1 >> d1 >> m2 >> d2;
    if(m2 == m1 + 1) cout << "1" << endl;
    else cout << 0 << endl;
    return 0;
}

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

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<ll> ans;
    ans.push_back(a*c);
    ans.push_back(a*d);
    ans.push_back(b*c);
    ans.push_back(b*d);
    cout << *max_element(ans.begin(), ans.end()) << endl;
    return 0;
}

Measured memory_bytes: 3628
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut edges = vec![];
    for i in 0..m {
        let v = read_vec::<usize>();
        let (a, b) = (v[0] - 1, v[1] - 1);
        edges.push((a, b));
    }
    let v = read_vec::<usize>();
    let (s, t) = (v[0] - 1, v[1] - 1);

    let mut graph = vec![vec![]; 3 * n];
    let to_index = |n, x| 3 * n + x;
    for (a, b) in edges {
        for ai in 0..3 {
            graph[to_index(a, ai)].push(Edge {
                to: to_index(b, (ai + 1) % 3),
                cost: 1,
            });
        }
    }

    let d = solve(&graph, to_index(s, 0));
    let ans = d[to_index(t, 0)];
    if ans == INF {
        println!("-1");
        return;
    }
    //debug!(d);
    println!("{}", ans / 3);
}
use std::cmp::Ordering;
use std::collections::BinaryHeap;
const INF: i64 = 100000_00000_00000;

#[derive(PartialEq, Debug)]
struct MinInt {
    value: i64,
}

impl Eq for MinInt {}

impl PartialOrd for MinInt {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.value.partial_cmp(&self.value)
    }
}

impl Ord for MinInt {
    fn cmp(&self, other: &MinInt) -> Ordering {
        other.value.cmp(&self.value)
    }
}

fn make_pair(x: i64, y: usize) -> (MinInt, usize) {
    (MinInt { value: x }, y)
}

#[derive(Debug, Clone)]
struct Edge {
    to: usize,
    cost: i64,
}

fn solve(edges: &Vec<Vec<Edge>>, start_idx: usize) -> Vec<i64> {
    let num_apexes = edges.len();
    let mut d = vec![INF; num_apexes];
    d[start_idx] = 0;
    let mut que = BinaryHeap::new();
    que.push(make_pair(0, start_idx));

    while let Some((u, v)) = que.pop() {
        if d[v] < u.value {
            continue;
        }
        for e in &edges[v] {
            if d[v] != INF && d[e.to] > d[v] + e.cost {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
    d
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 20680
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = ll(k); i <= ll(n); i++)
#define rep3(i, n, k) for(ll i = ll(n); i >= ll(k); i--)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  string n;
  cin >> n;
  
  ll sum=0;
  rep(i, n.size()) {
    sum += n[i]-'0';
  }
  cout << (sum%9==0 ? "Yes" : "No") << newl;
  return 0;
}

Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
  int N; cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  
  sort(A.begin(),A.end());
  vector<int> x(N-1),y(N-1);
  int ans;
  if (A[N-2] < 0) {
    ans = A[N-1];
    for (int i = 0; i < N-1; i++) {
      y[i] = ans;
      x[i] = A[i];
      ans -= A[i]; 
    }
  } else if (A[0] >= 0) {
    ans = A[0];
    for (int i = 0; i < N-1; i++) {
      if (i != N-2) {
        y[i] = ans;
        x[i] = A[i+1];
        ans -= A[i+1];
      } else {
        y[i] = A[i+1];
        x[i] = ans;
        ans = A[i+1] - ans;
      }
    }
  } else {
    int k = lower_bound(A.begin(),A.end(),0) - A.begin();
    ans = A[0];
    for (int i = N-1; i >= 1; i--) {
      if (i != k) {
        y[N-1-i] = ans;
        x[N-1-i] = A[i];
        ans -= A[i]; 
      } else {
        y[N-1-i] = A[k];
        x[N-1-i] = ans;
        ans = A[k] - ans;
      }
    }
  }
  
  cout << ans << endl;
  rep(i,N-1) cout << y[i] << " " << x[i] << endl;
}

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

typedef long long ll;

int main(){
  int a[106];
  int x;
  int d;
  int n,k;
  int i,j;
  int cnt = 0;
  int sum = 0;

  scanf("%d %d", &n, &k);

  for(i = 0;i < n;i++) a[i] = 0;

  for(i = 0;i < k;i++){
    scanf("%d", &d);
    for(j = 0;j < d;j++){
      scanf("%d", &x);
      a[x - 1]++;
    }
  }

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

  printf("%d\n", cnt);


  return 0;
}

Measured memory_bytes: 1728
<?php
  fscanf(STDIN, "%d %d", $A, $B);
  $ans = 0;
  for($i = 1; $i <= 20; $i ++){
    if($i == 1 && $B == 1){
      break;
    }else if($B - $A <= 0){
      $ans ++;
      break;
    }else{
      $B = $B - $A + 1;
      $ans ++;
    }
  }
  echo "$ans\n";
?>

Measured memory_bytes: 3576
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int n,m,X,Y;
  cin >>n>> m>>X>>Y;
  int x[n];int y[m];
  for(int i=0;i<n;i++) cin >>x[i];
  for(int j=0;j<m;j++) cin >> y[j];
  sort(x,x+n);sort(y,y+m);
  for(int i=X+1;i<=Y;i++) {
      if(i>x[n-1]&&i<=y[0]){
        cout <<"No War"<<endl;
        return 0;
      }
  }
  cout <<"War"<<endl;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
    auto s = readln().split();
    assert(s.length == t.length);
    foreach(ref ti; t) {
        ti = s[0].to!(typeof(ti));
        s = s[1..$];
    }
}

class UnionFindTree {
public:
    this(size_t n) {
        parent = iota(n).array();
        rank = new size_t[](n);
    }
    size_t find(size_t n) {
        if(n == parent[n]) {
            return n;
        } else {
            parent[n] = find(parent[n]);
            return parent[n];
        }
    }
    void unite(size_t n, size_t m) {
        auto p1 = find(n);
        auto p2 = find(m);
        if(n == m) {
            return;
        }
        if(rank[p1] < rank[p2]) {
            swap(p1, p2);
        }
        if(rank[p1] == rank[p2]) {
            ++rank[p1];
        }
        parent[p2] = p1;
    }
private:
    size_t[] parent;
    size_t[] rank;
}
unittest {
    auto uft = new UnionFindTree(10);
    foreach(i; iota(10)) {
        assert(uft.find(i) == i);
    }
    foreach(i; iota(10).filter!(a => a%3 == 0).drop(1)) {
        uft.unite(i, i-3);
    }
    foreach(i; iota(10).filter!(a => a%3 == 0)) {
        assert(uft.find(0) == uft.find(i));
    }
    foreach(i; iota(10).filter!(a => a%3 != 0)) {
        assert(uft.find(0) != uft.find(i));
    }
}

const real eps = 1e-10;

const long p = 1_000_000_000 + 7;

void main(){
    long n, z, w;
    readlnTo(n, z, w);

    auto a = readLongs();
    a.reverse();

    a ~= w;

    long[] X, Y;
    X ~= abs(a[0] - a[1]);
    Y ~= abs(a[0] - a[1]);
    foreach(i; iota(1, a.length-1)) {
        auto nX = max(reduce!max(0L, Y), abs(a[i+1] - a[0]));
        auto nY = min(reduce!min(0L, X), abs(a[i+1] - a[0]));
        X ~= nX;
        Y ~= nY;
    }
    writeln(X[$-1]);
}



Measured memory_bytes: 2428
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,s,f) for(int i=s;i<f;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define endl "\n"
#define fcout cout<<fixed<<setprecision(15)
typedef pair<int, int> P;
//struct edge { int to, cost; };

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

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

bool prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)return false;
    }
    return n != 1;
}
int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
int lcm(int x, int y) {
    return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int t = mod_pow(n, p / 2, m);
        return (t * t) % m;
    }
    return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int modinv(int a, int m) {
    int b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int modinv2(int a, int mod) {
    return mod_pow(a, mod - 2, mod);
}
int digit(int x) {
    int cnt = 0;
    while (x > 0) {
        cnt += x % 10;
        x /= 10;
    }
    return cnt;
}
int read() {
    int tmp;
    cin >> tmp;
    return tmp;
}
int xor128() {
    static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    int t = (x xor (x << 11));
    x = y; y = z; z = w;
    return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}
map<int, int> factaring(int x) {
    map<int, int>ans;
    int now = 2;
    while (now * now <= x) {
        if (x % now == 0) {
            x /= now;
            ans[now]++;
        }
        else now++;
    }
    if (x != 1) ans[x]++;
    return ans;
}
int comb(int n, int k, int mod) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    k = min(k, n - k);
    int x = 1, y = 1;
    rep(i, k) {
        y *= i + 1;
        y %= mod;
    }
    for (int i = n - k + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }
    return x * modinv(y, mod) % mod;
}

signed main() {
    //srand((unsigned)time(NULL));

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

    int k;
    string s;
    cin >> k >> s;
    if (s.size() <= k) cout << s << endl;
    else {
        cout << s.substr(0, k) << "..." << endl;
    }

    return 0;
}


Measured memory_bytes: 3672
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
   
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

const ll MOD=1e9+7;
const int MAX_N=1<<17;

ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k>0){
        if(k%2==1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k/=2;
    }
    return ans;
}

ll inv(ll a){
	return powmod(a, MOD-2);
}

ll prime[12]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
int cp[12][2*MAX_N-1];
ll s[100000];
int p[100000];
int n, n0;

ll sum;
bool used[100000];
vector<int> v;

void dfs(int x){
	used[x]=1;
	sum+=((ll)(x+1));
	v.push_back(x);
	if(!used[p[x]]) dfs(p[x]);
}

void init(){
	for(int j=0; j<12; j++){
		for(int i=n0-2; i>=0; i--){
			cp[j][i]=max(cp[j][2*i+1], cp[j][2*i+2]);
		}
	}
}

int find(int j, int a, int b, int k, int l, int r){
	if(a>=r || b<=l) return 0;
	if(a<=l && r<=b) return cp[j][k];
	return max(find(j, a, b, 2*k+1, l, (l+r)/2), find(j, a, b, 2*k+2, (l+r)/2, r));
}

int main()
{
	int q;
	cin>>n>>q;
	n0=1;
	while(n0<n) n0*=2;
	for(int i=0; i<n; i++){
		cin>>p[i];
		p[i]--;
	}
	for(int i=0; i<n; i++){
		if(used[i]) continue;
		sum=0;
		v.clear();
		dfs(i);
		ll ct=v.size();
		sum=sum*inv(ct)%MOD;
		for(auto x:v){
			s[x]=sum;
		}
		int fc[12]={};
		for(int j=0; j<12; j++){
			ll p=prime[j];
			while(ct%p==0){
				fc[j]++;
				ct/=p;
			}
		}
		for(auto x:v){
			for(int j=0; j<12; j++){
				cp[j][n0-1+x]=fc[j];
			}
		}
	}
	init();
	for(int i=1; i<n; i++){
		s[i]+=s[i-1];
		s[i]%=MOD;
	}
	for(int t=0; t<q; t++){
		int l, r;
		cin>>l>>r;
		l--; r--;
		ll lcm=1;
		for(int j=0; j<12; j++){
			int m=find(j, l, r+1, 0, 0, n0);
			for(int i=0; i<m; i++){
				lcm*=prime[j];
				lcm%=MOD;
			}
		}
		ll sl=0, sr=s[r];
		if(l>0) sl=s[l-1];
		cout<<(sr-sl+MOD)*lcm%MOD<<endl;
	}
    return 0;
}


Measured memory_bytes: 15312
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

ll n,ar[N][2];
ll pre[N][2];

ll get_sum(ll i,ll j,ll p)
{
    if(i == 0)
        return pre[j][p];

    return pre[j][p]-pre[i-1][p];
}

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

    cin >> n;

    rep(j,0,2)
    {
        rep(i,0,n)
        {
            cin >> ar[i][j];

            if(i == 0)
                pre[i][j] = ar[i][j];
            else
                pre[i][j] = pre[i-1][j] + ar[i][j];
        }
    }

    ll ans = 0;

    rep(i,0,n)
    {
        ans = max(ans,get_sum(0,i,0) + get_sum(i,n-1,1));
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 2304
#include<iostream>
#include<queue>
using namespace std;
int h,w;
int sz,used[444][444];
long ans;
string s[444];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++)cin>>s[i];
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(used[i][j])continue;
			sz++;
			queue<pair<pair<int,int>,bool> >P;
			P.push(make_pair(make_pair(i,j),s[i][j]=='#'));
			used[i][j]=sz;
			long cw=0,cb=0;
			(s[i][j]=='.'?cb:cw)++;
			while(!P.empty())
			{
				int x=P.front().first.first,y=P.front().first.second;
				bool b=P.front().second;
				P.pop();
				for(int r=0;r<4;r++)
				{
					int tx=x+dx[r],ty=y+dy[r];
					if(tx<0||ty<0||tx>=h||ty>=w||used[tx][ty]||(b==(s[tx][ty]=='#')))continue;
					(b?cb:cw)++;
					used[tx][ty]=sz;
					P.push(make_pair(make_pair(tx,ty),!b));
				}
			}
			ans+=cb*cw;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1152