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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

ll totient(ll n)
{
    ll res = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i) continue;
        res = res * (i - 1) / i;
        while (n % i == 0) n /= i;
    }
    if (n != 1) res = res * (n - 1) / n;
    return res;
}

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

    ll n; cin >> n;
    cout << totient(n) << endl;
    return 0;
}



Measured memory_bytes: 3164
/*
   Author: @yash_31
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long int
#define eb emplace_back
#define pb push_back
#define fatafat ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define ft first
#define sd second
#define vpi vector<pair<int,int> >
#define vpl vector<pair<ll,ll> >
#define mkpr make_pair
#define todec() to_ulong()
#define toldec() to_ullong()
#define deb(x) std::cout<<#x<<":"<<x<<endl;
#define whole(x) (x).begin(),(x).end()
#define revwhole(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define sp " "
#define fbo find_by_order
#define ook order_of_key
 
using namespace std; 
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> gharKaSet;
 
const ll inf=1e12;
 
// same as CSES que

pair<ll,ll> dp[5000][5000];
vector<ll> arr;
vector<ll> prefixs;
 
pair<ll,ll> getRes(int i,int j){
   if(i==j){return mkpr(arr[i],0);}
   else if(dp[i][j].ft!=-inf){return dp[i][j];}
   else {
      dp[i][j].ft=max(getRes(i,i).ft+getRes(i+1,j).sd,getRes(j,j).ft+getRes(i,j-1).sd);
      dp[i][j].sd=prefixs[j]-prefixs[i]+arr[i]-dp[i][j].ft;
      // dp[i][j].sd=min(getRes(i,i).ft+getRes(i+1,j).sd,getRes(j,j).ft+getRes(i,j-1).sd);
      return dp[i][j];
   }
}
 
int main()
{
   fatafat
   int n;
   cin>>n;
   arr.resize(n);
   prefixs.resize(n);
   for(int i=0;i<n;i++)cin>>arr[i];
   prefixs[0]=arr[0];
   for(int i=1;i<n;i++){prefixs[i]=prefixs[i-1]+arr[i];}
   for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
         if(i==j){dp[i][i].ft=arr[i];dp[i][i].sd=0;}
         else{
            dp[i][j].ft=dp[i][j].sd=-inf;
         }
      }
   }
   auto val = getRes(0,n-1);
   cout<<val.ft-val.sd;
   return 0;
}

Measured memory_bytes: 156520
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    long n = scan.nextLong();
    long g =n%1000;
    if (g == 0){
      g = 1000;
    }
    System.out.println(1000-g);
  }
}


Measured memory_bytes: 35756
n = int(input())
a = list(map(int, input().split()))
 
for i in range(n):
    if a[i] == 0:
        print(0)
        exit()
ans = 1
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)

Measured memory_bytes: 21788
#include <iostream>
#include <vector>

int main(void) {
	// input
	int n, m;
	std::cin >> n >> m;
	std::vector<bool> is_line_1(n), is_line_n(n);
	for(int i = 0; i < m; ++i) {
		int a, b;
		std::cin >> a >> b;
		if(a == 1) is_line_1[b-1] = true;
		if(b == 1) is_line_1[a-1] = true;
		if(a == n) is_line_n[b-1] = true;
		if(b == n) is_line_n[a-1] = true;
	}

	bool is_line = false;
	for(int i = 0; i < n; ++i) {
		if(is_line_1[i] && is_line_n[i]) is_line = true;
	}

	std::cout << (is_line ? "POSSIBLE" : "IMPOSSIBLE") << std::endl;

	return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::Ordering;

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get {
    ([$t: ty]) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

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

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let n = get!(String);
    for c in n.chars() {
        if c == '7' {
            println!("Yes");
            return;
        }
    }
    println!("No");
}


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

int main(){
  int H,W;
  cin >> H>>W;
  int ni,nj;
  vector <string>s(50);
  for(int i=0;i<H;i++)
    cin >> s[i];
  vector <int>dx={0,1,1,1,0,-1,-1,-1};
  vector <int>dy={1,1,0,-1,-1,-1,0,1};
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      if(s[i].at(j)=='#')
        continue;
      int num=0;
      for(int k=0;k<8;k++){
          ni=i+dy.at(k);
          nj=j+dx.at(k);
          if(ni<0||ni>=H)
            continue;
          if(nj<0||nj>=W)
            continue;
          if(s[ni].at(nj)=='#')
            num++;
      }
      s[i].at(j)=char(num+'0');
    }
  }
  for (int i=0;i<H;i++){
      cout << s[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
// I think of what the world could be, A vision of the one I see, A million dreams is all it's gonna take

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

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

    int n;
    cin >> n;
    string s;
    cin >> s;
    bool a = 0, b = 0, c = 0;
    for(int i = 0; i < n; i++){
	a|= s[i] == '2';
	b^= s[i] == '2' && ((n-1) & i) == i;
	c^= s[i] == '3' && ((n-1) & i) == i;
    }
    if(b)
	return cout << 1 << endl, 0;
    if(a)
	return cout << 0 << endl, 0;
    if(c)
	return cout << 2 << endl, 0;
    else
	return cout << 0 << endl, 0;
}


Measured memory_bytes: 1948
#include <stdio.h>
int main(){
    int n,m,ans;
    while(1){
        scanf("%d%d",&n,&m);
        if(n==0)return 0;
        ans=0;
        for(int i=1;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<=n;k++){
                    if(i+j+k==m)ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 2672
// D - Chat in a Circle
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(int)(s);i<(int)(e);++i)

int main(){
	int N; cin>>N;
	vector<int> A(N); rp(i, 0, N) cin>>A[i];
	sort(A.rbegin(), A.rend());
	int64_t ans = 0;
	queue<int> q;
	q.push(A[0]);
	rp(i, 1, N){
		int a = A[i];
		ans += q.front(); q.pop();
		q.push(a); q.push(a);
	}
	cout<< ans <<endl;
}


Measured memory_bytes: 4852
def f(*a)
  return a if a.max > @max
  a << a.map { |aa| [aa * 10 + 3, aa * 10 + 5, aa * 10 + 7]}.flatten.uniq.map { |aa| f(aa) }.flatten.uniq
end

@max = gets.chomp.to_i

ll = f(3, 5, 7)
count = 0
ll.flatten!
ll.reject! { |n| n > @max  }
ll.each do |n|
  n = n.to_s
  if n.count('3') >= 1 && n.count('5') >= 1 && n.count('7') >= 1
    count += 1 
  end
end

puts count


Measured memory_bytes: 11260
import sys
s=int(input())
L=[s]
ans = 1
while s>0:
    if s%2==0:
        ans += 1
        s=s//2
        if s in L:
            print(ans)
            sys.exit()
        else:
            L.append(s)
    else:
        ans += 1
        s=3*s+1
        if s in L:
            print(ans)
            sys.exit()
        else:
            L.append(s)


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main(void) {
    
    int X;
    int A;
    int B;
    int delta;
    
    cin >> X >> A >> B;
    
    delta = A - B;
    
    if (delta >= 0) {
        
        cout << "delicious" << endl;
        
    }
    else if ((delta * -1) > X) {
        
        cout << "dangerous" << endl;
        
    }
    else {
        
        cout << "safe" << endl;
        
    }
    
    return 0;
    
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
m = 0
for i,j in enumerate(a):
  if i%2==1:
    m+=-1*j
  else:
    m+=j
ans = [m]
for i in a[:-1]:
  b = -1*m+2*i
  ans.append(b)
  m = b
print(' '.join(map(str,ans)))

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

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            var totalCost = 0;
            var last = 0;

            foreach (var pos in A.Concat(new[] { 0 }))
            {
                totalCost += Math.Abs(last - pos);
                last = pos;
            }

            last = 0;
            var beforeLast = 0;
            var i = 0;
            foreach (var pos in A.Concat(new[] { 0 }))
            {
                var cost2 = totalCost - Math.Abs(last - beforeLast) - Math.Abs(pos - last) + Math.Abs(pos - beforeLast);
                if (i != 0)
                {
                    Console.WriteLine(cost2);
                }

                beforeLast = last;
                last = pos;
                i++;
            }
        }
    }
}


Measured memory_bytes: 27492
from collections import defaultdict
N, M = map(int, input().split())
order = []
dd = defaultdict(int)

for i in range(M):
    p, y = map(int, input().split())
    order.append([i, p, y])

# 全体を年代順にソート
order.sort(key=lambda x: (x[2]))

res = defaultdict(str)
for i, pp, yy in order:
    dd[pp] += 1
    res[i] = str(pp).zfill(6) + str(dd[pp]).zfill(6)

for i in range(M):
    print(res[i])

Measured memory_bytes: 115760
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
#include <iomanip>
#define M_PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1000000007;
const int MAX_V = 201;
int now = 0;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
struct edge {
	int t;
	edge(int _t) : t(_t) {}
};
bool use[100010];


vector<edge> te[100010];
vector<edge> fe[100010];
int d[100100];
//ll rec(int num) {
//	if (num == 0) return 0;
//	return rec(num - 1) + num;
//}
ll gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll calc(ll b,ll n){
	if (n < b) return n;
	return calc(b, n / b) + n % b;
}

void Solve() {

	int n,a,b,c,d;
	cin >> n >> a >> b >> c >> d;
	ll nu = a;
	ll nl = a;
	for (size_t i = 2; i <= n; i++)
	{
		if (nl <= b && b <= nu) {
			if (b - nl < nu - b) {
				nu -= c;
				nl -= d;
			}
			else {
				nu += d;
				nl += c;
			}
			continue;
		}
		if (nu < b) {
			nu += d;
		}
		else {
			nu -= c;
		}
		if (nl < b) {
			nl += c;
		}
		else {
			nl -= d;
		}
	}
	if (nl <= b && b <= nu) {
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;

}


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



Measured memory_bytes: 6016
n,A,B,C=map(int,input().split())
Q=[int(input()) for ii in range(n)]
inf=10**15
def dfs(now,a,b,c):
    if now==n:
        return abs(a-A)+abs(b-B)+abs(c-C) if 0 not in [a,b,c] else inf
    q1= dfs(now+1,a,b,c)
    q2= dfs(now+1, a+Q[now],b,c)+10
    q3= dfs(now+1, a, b+Q[now], c)+10
    q4 = dfs(now+1,a,b,c+Q[now])+10
    return min(q1,q2,q3,q4)

print(dfs(0,0,0,0)-30)

Measured memory_bytes: 9084
from collections import defaultdict

G = defaultdict(set)
N, M = [int(_) for _ in input().split()]
for _ in range(M):
    A, B = [int(_) for _ in input().split()]
    G[A].add(B)
    G[B].add(A)

f = [-1 for _ in range(N+1)]
f[1] = 0

pool = set([1])
np = set()
cnt = 0
while pool:
    np = set()
    for p in pool:
        for v in G[p]:
            if f[v] == -1:
                f[v] = p
                cnt += 1
                np.add(v)
    pool = np

print("Yes")
for i in range(2, N+1):
    print(f[i])


Measured memory_bytes: 72148
import java.util.*;
import java.lang.*;
import java.io.*;
class Counter<T> extends HashMap<T,Integer>{
    public Counter(){
        super();
    }
    public Counter(T[] array){
        super();
        for(int i=0;i<array.length;i++) add(array[i]);
    }
    public Integer get(Object elm){
        return getOrDefault(elm,0);
    }
    public void add(T elm){
        put(elm, get(elm)+1);
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Integer[] A = new Integer[N];
        for(int n=0;n<N;n++)A[n]=sc.nextInt();
        Counter<Integer> count = new Counter(A);
        if((N-count.size())%2==0) System.out.println(count.size());
        else System.out.println(count.size()-1);
    }
}


Measured memory_bytes: 62980
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int dp[101][4][4][4];

int main() {

	int n; cin >> n;
	dp[0][3][3][3] = 1;
	map<char, int> m;
	int a = 0;
	int g = 1;
	int c = 2;
	int t = 3;

	for (int pos = 0; pos < n; pos++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					if (dp[pos][i][j][k] == 0)continue;

					for (int x = 0; x < 4; x++) {
						if (j == a && k == g && x == c)continue;
						if (j == a && k == c && x == g)continue;
						if (j == g && k == a && x == c)continue;

						if (i == a&& k == g && x == c)continue;
						if (i == a && j == g&& x == c)continue;

						dp[pos + 1][j][k][x] += dp[pos][i][j][k];
						dp[pos + 1][j][k][x] %= MOD;
					}
				}
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				ans += dp[n][i][j][k];
				ans %= MOD;
			}
		}
	}

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



Measured memory_bytes: 256
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <bits/stdc++.h>
#include <string>
using namespace std;
using ll = long long;
const ll MOD = 1000000007; 


int main(){   
    ll N;
    cin>>N;
    
    ll C[N-1],S[N-1],F[N-1];
    for(ll i=0;i<N-1;i++){
        cin>>C[i]>>S[i]>>F[i];
    }
    for(auto i=0;i<N;i++){
        int t=0;
        for(int j=i;j<N-1;j++){
            if(t<S[j])t=S[j];
            else if(t%F[j]==0);
            else{
                t=t+F[j]-t%F[j];
            }
            t+=C[j];
        }
        cout<<t<<endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    long ans,N;
    cin >> N;
    //処理
    for (long i=0;i<N;i++){
        if(i*i>N) {
            ans = (i-1)*(i-1);
            break;
        }
    }
    //解答
    if (N==1||N==2) cout << 1 << endl;
    else cout << ans <<endl;
}

Measured memory_bytes: 256
lmap = lambda f,s: list(map(f,s))
n,m = map(int, input().split())
a = [lmap(int, input().split()) for i in range(n)]
a = lmap(lambda xs: xs + [sum(xs)], a)
a.append(lmap(sum, zip(*a)))
for xs in a: print(*xs)


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

// マクロ
#define rep(i,N) for(int i = 0; i < N; i++)
#define all(x) x.begin(), x.end()
#define sort(x) sort(all(x))
#define cou(x) cout << x << endl
#define y() cout << "Yes" << endl
#define n() cout << "No" << endl
#define Y() cout << "YES" << endl
#define N() cout << "NO" << endl
#define x2(x) x * x

// 型エイリアス
using lint = long long;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;

int main() {

	int N, M; 

	cin >> N >> M;
	vector<pair<int, string>> answer(M);
	vb isAC(N);

	string s;
	int p;
	rep(i, M) {
		cin >> p >> s;
		answer[i] = make_pair(p, s);
	}

	map<int, int> penalty;
	int AC = 0;
	rep(i, M) {
		if (answer[i].second == "AC") {
			if (isAC[answer[i].first - 1] == false) {
				AC++;
			}
			isAC[answer[i].first - 1] = true;
		}
		else if (answer[i].second == "WA") {
			if (isAC[answer[i].first - 1] == false) {
				if (penalty.count(answer[i].first - 1)) {
					penalty[answer[i].first - 1]++;
				}
				else {
					penalty[answer[i].first - 1] = 1;
				}
			}
		}
	}
	int pena = 0;
	rep(i, N) {
		isAC[i] ? pena += penalty[i] : pena += 0;
	}
	cou(AC << " " << pena);
}

Measured memory_bytes: 11136
// ~maqsat~
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define in insert
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define count1 __builtin_popcountl
#define debug(x) cerr << (#x) << " = " << (x) << "\n";
#define TEZ ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define fre(f) if(fopen(f".in", "r")) freopen(f".in", "r", stdin),freopen(f".out", "w", stdout);

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
using db = double;
using ld = long double;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<ii> vii;
typedef vector<pll> vll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class U> inline void cmin(T &a, U b) { a = min(a, b); }
template <class T, class U> inline void cmax(T &a, U b) { a = max(a, b); }
template <class T, class U, class X, class Y> inline void psmn(T &a, U b, X &p, Y i) { if(b < a)a = b,p = i; }
template <class T, class U, class X, class Y> inline void psmx(T &a, U b, X &p, Y i) { if(b > a)a = b,p = i; }

const int oo = 0x3f3f3f3f;
const ll N = 1e5 + 345;
const ll MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const db EPS = 1e-9;
const db PI = acos(-1); // 3.14159265358979323846

int main() {
	fre(""); TEZ;

	int n;
	int k;
	cin >> n >> k;
	int ans = 0;
	for(int  i = 0; i < n; i++) {
		int x;
		cin >> x;
		ans += (x >= k);
	}
	cout << ans;

	return 0;
}


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

int max(string str)
{
    while(str.length())
    {
        if(str[0]==str[1])
        {
            if(str.length()!=2)
            {
                (::count)+=2;
                str.erase(0,3);
            }

            else
            {
                ++(::count);
                str.erase();
            }
            
        }

        else
        {
            ++(::count);
            str.erase(0,1);
        }
    }
    return (::count);
}

int main()
{
    string str;
    cin>>str;
    int K=str.length()==1?1:max(str);
    cout<<K;
    return 0;
}


Measured memory_bytes: 772
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
using namespace std;
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};


int main(int argc, char const *argv[]) {
  int n;
  ll a[100010],k,b[100010];
  bool f=false;
  std::cin >> n >> k;

  for(int i=0; i<n; i++){
    std::cin >> a[i];
    if(a[i]==k) f=true;
  }

  sort(a,a+n,greater<ll>());
  if(a[0]<k){
    std::cout << "IMPOSSIBLE" << '\n';
    return 0;
  }
  for(int i=0; i<n-1; i++){
    b[i]=a[i]-a[i+1];
    if(b[i]==0) continue;
    if(k%b[i]==0) f=true;
  }
  if(f) std::cout << "POSSIBLE" << '\n';
  else std::cout << "IMPOSSIBLE" << '\n';
  return 0;
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scan(&s)

	a := strings.Split(s, "")
	len := len(a)
	var cnt int
	for i, c := range a {
		if i == len/2 {
			break
		}

		if c != a[len-i-1] {
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 640
"""
dp[与えたダメージ] = 使用した魔力
"""
h, n = map(int, input().split())
attacks = []
INF = 10000000000000
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    attacks.append([a, b])
    
for i in range(h):
    for j in range(n):
        dp[min(h,i + attacks[j][0])] = min(dp[min(h, i + attacks[j][0])], dp[i] + attacks[j][1])
print(dp[h])


Measured memory_bytes: 42332
#include<stdio.h>

void swap(int *a,int *b);
int partition(int A[], int p,int r);

int partition(int A[], int p, int r){
	int x=A[r];
	int i=p-1,j;
	for(j=p;j<r;j++){
		if(A[j]<=x){
			i++;
			swap(&(A[i]),&(A[j]));
		}
	}
	swap(&(A[i+1]),&(A[r]));
	return i+1;
}

void swap(int *a,int *b){
	int tmp;
	tmp=*a;
	*a=*b;
	*b=tmp;
}

int main(void){
	int A[100000];
	int base,n;
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&(A[i]));
	}
	base=partition(A,0,n-1);
	for(i=0;i<n;i++){
		if(i==base){
			printf("[%d]%c",A[i],i==n-1?'\n':' ');
		}else{
			printf("%d%c",A[i],i==n-1?'\n':' ');
		}
	}
	return 0;
}

Measured memory_bytes: 992
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <math.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;


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

//INT_MAX	2,147,483,647 = 2*1.0e9

const int MOD = 1000000007;

ll cP[100010];

ll answer;

int N, K;

void dfs(Graph& _G, int v, int p){

  int cO;
  if(p==-1) cO = K-1;
  else cO = K-2;

  for (auto nv: _G[v]){
    if(nv==p)continue;
    cP[nv] = cO;
    cO -= 1;
    dfs(_G, nv, v);
  }

}


int main(){

  cin >> N >> K;
  Graph G(N);

  for(int i = 0; i <N-1; i++){
    int a,b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  cP[0] = K;
  dfs(G, 0, -1);

  ll answer = 1;
  for(int i = 0; i < N; i++){
    answer *= cP[i];
    answer %= MOD;
  }
  cout << answer << endl;

  return 0;
}



Measured memory_bytes: 11136
#include<iostream>

using namespace std;

int C[200000];

int main()
{
  int N, a, b, x = 0;
  cin >> N >> a;

  for(int i = 1; i < N; i++) {
    cin >> b;
    if(a == i) {
      x++;
      b = 0;
    } else {
      a = b;
    }
  }
  if(b == N) x++;

  cout << x << endl;

  return 0;
}

Measured memory_bytes: 256
N=int(input())
S,T=[],[]
for n in range(N):
    s,t=input().split()
    S.append(s)
    T.append(int(t))
X=input()
T_sum=sum(T)
now_sum=0
for n in range(N):
    now_sum+=T[n]
    if X==S[n]:
        print(T_sum-now_sum)
        break


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int N, K, C;
    string S;
    cin >> N >> K >> C;
    cin >> S;

    int dpl[K], dpr[K];
    int cur = - N;
    int cnt = 0;

    for(int i=0; i<N; i++){
       if(S[i] == 'o' && cur + C < i){
           dpl[cnt] = i;
           cnt ++;
           cur = i;
       } 
       if(cnt >= K) break;
    }    
    
    cur = 2 * N;
    cnt = K - 1;

    for(int i=N-1; i>=0; i--){
        if(S[i] == 'o' && i < cur - C){
            dpr[cnt] = i;
            cnt --;
            cur = i;
        }
        if(cnt < 0) break;
    }
    for(int i=0; i<K; i++){
        if(dpl[i] == dpr[i]) cout << dpl[i] + 1 << endl;
    }
    return 0;
}

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

bool visit[26],g[26][26];

bool dfs(int v){
  visit[v] = true;
  bool f = false;
  for(int i=0;i<26;i++)
    if(g[v][i]){
      f = true;
      if(!visit[i])dfs(i);
    }
  return f;
}
 
int graph_num(void){
  int res = 0;
  for(int i=0;i<26;i++)
    if(!visit[i] && dfs(i))res++;
  return res;
}
  
int main(){
  int i,n,pre[26],suf[26],h,t;
  string s;

  while(cin>>n && n){
    for(i=0;i<26;i++){
      visit[i] = false;
      pre[i] = suf[i] = 0;
      for(int j=0;j<26;j++)g[i][j] = false;
    }
    
    for(i=0;i<n;i++){
      cin >> s;
      h = s[0]-'a', t = s[(int)s.size()-1]-'a';
      
      pre[h]++;
      suf[t]++;
      g[h][t] = g[t][h] = true;
    }
  
    if(graph_num() != 1)printf("NG\n");
    else{
      for(i=0;i<26;i++)if(pre[i] != suf[i])break;
      
      if(i==26)printf("OK\n");
      else printf("NG\n");
    }
  }
}

Measured memory_bytes: 904
def read():
    return int(input())
 
def reads(sep=None):
    return list(map(int, input().split()))
 
def main():
	a = ['dream', 'dreamer', 'erase', 'eraser']
	s = input()
	flag = True
	while flag:
		flag = False
		for i in range(len(a)):
			if a[i] == s[-len(a[i]):]:
				s = s[:-len(a[i])]
				flag = True
	if 0 < len(s):
		print('NO')
	else:
		print('YES')
	
main()

Measured memory_bytes: 3316
import bisect


def main():
    n = int(input())
    ls = sorted(list(map(int, input().split())))

    ans = 0
    for i in range(n-1):
        for j in range(i+1, n):
            a = ls[i]
            b = ls[j]
            k = bisect.bisect_left(ls, a+b)
            if k > j:
                ans += k - j - 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static long count = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		String[] strArray = reader.readLine().split(" ");
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(strArray[i]);
		}
		mergeSort(arr, 0, arr.length);
		System.out.println(count);
	}

	private static void mergeSort(int[] arr, int left, int right) {
		if (left + 1 < right) {
			int mid = left + (right - left) / 2;
			mergeSort(arr, left, mid);
			mergeSort(arr, mid, right);
			merge(arr, left, mid, right);
		}
	}
 
	private static void merge(int[] arr, int left, int mid, int right) {
		
		int n1 = mid - left;
		int n2 = right - mid;
		
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];
		for (int i = 0; i < n1; i++) {
			L[i] = arr[left + i];
		}
		for (int i = 0; i < n2; i++) {
			R[i] = arr[mid + i];
		}
		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;
		int i = 0;
		int j = 0;
		int tmp = n1;		
		for (int k = left; k < right; k++) {
			if (L[i] <= R[j]) {
				if (R[j] != Integer.MAX_VALUE) {
					tmp--;
				}				
				arr[k] = L[i];
				i++;
			} else {
				if (L[i] != Integer.MAX_VALUE) {
					count += tmp;
				}
				arr[k] = R[j];
				j++;
			}
		}
	}
}


Measured memory_bytes: 61916
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int n,m,x,y;
int a[N][N];
int main()
{
	scanf("%d%d%d%d",&n,&m,&x,&y);
	if(n%x==0&&m%y==0)
	{
		printf("No");
		return 0;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=m;i++)
			a[k][i]=1000;
	for(int k=1;k<=n/x;k++)
		for(int i=1;i<=m/y;i++)
			a[k*x][i*y]=-(x*y*1000-1000+1);
	printf("Yes\n");
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=m;i++)
		{
			printf("%d ",a[k][i]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);
//cin.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[200010];
ll kai[200010];
ll beki(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k%2==1){
            ret*=now;
            ret%=mod;
        }
        now*=now;
        now%=mod;
        k/=2;
    }
    return ret;
}
ll gyaku(ll n){
    return beki(n,mod-2);
}
void nckinit(ll n){
    kai[0]=1;
    kai[1]=1;
    for(int i=2;i<=n;i++){
        kai[i]=kai[i-1]*i;
        kai[i]%=mod;
    }
    gya[n]=gyaku(kai[n]);
    for(int i=n-1;i>=1;i--){
        gya[i]=gya[i+1]*(i+1);
        gya[i]%=mod;
    }
    gya[0]=1;
}
ll nck(ll n,ll k){
    if(k<0)return 0;
    if(k==0||n==k)return 1;
    ll ret=kai[n];
    ret*=gya[n-k];
    ret%=mod;
    ret*=gya[k];
    ret%=mod;
    return ret;
}
ll npk(ll n,ll k){
    if(k<0)return 0;
    if(k==0)return 1;
    ll ret=kai[n];
    ret*=gya[n-k];
    ret%=mod;
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k;cin>>n>>k;
    ll a[n];
    ll b[n],c[n];
    rep(i,0,n)cin>>a[i];
    fill(b,b+n,0);
    fill(c,c+n,0);
    rep(i,0,n){
        rep(j,0,n){
            if(a[j]<a[i]){
                if(j<i)c[i]++;
                else{
                    b[i]++;
                    c[i]++;
                }
            }
        }
    }
    ll su=(k*(k-1))/2;
    su%=mod;
    ll ans=0;
    rep(i,0,n){
        ans+=b[i]*k+c[i]*su;
        ans%=mod;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 256
#include<stdio.h>

void bubbleSort(int a[100], int N);
void swap(int *a, int *b){
    int c;
    c=*a;
    *a=*b;
    *b=c;

}

int main(void){
    int a[100],N,i,j;
    scanf("%d",&N);
    
    for(i=0;i<N;i++){
        scanf("%d ",&a[i]);
    }

    bubbleSort(a,N);


}

void bubbleSort(int a[100], int N){
    int i,j,flag,count;
    flag = 1;
    count = 0;

    while(flag){
    flag = 0;
    
        for(j=N-1;j>0;j--){
            if(a[j] < a[j-1]){
                swap(&a[j],&a[j-1]);
                flag=1;
                count++;
            }
        }
    }
    printf("%d",a[0]);
    if(N>1){
        for(i=1;i<N;i++)
            printf(" %d",a[i]);
    }
    printf("\n"); 
    printf("%d\n",count);
}


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

typedef long long ll;

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

    ll sum = 0;
    ll count = 0;
    for (int i = 0; i < (1 << n - 1); i++) {
        for (int j = 0; j < n; j++) {
            sum += (s.at(n - j - 1) - '0') * pow(10, count);
            count++;
            if (i & (1 << j)) count = 0;
        }
        count = 0;
    }

    cout << sum << endl;
}


Measured memory_bytes: 3996
module ABC135

  ! <module>s to import
  use, intrinsic :: iso_fortran_env

  ! require all variables to be explicitly declared
  implicit none

  ! accessibility of <subroutine>s and <function>s in this <module>
  public  :: task_A
  private :: calculate_solution
  private :: is_even
  
  contains
  
  subroutine task_A
  
    ! variables for this <subroutine>
    integer(INT32) :: A, B
    integer(INT32) :: answer
    
    ! STEP.01
    ! read out the given data
    read(unit=INPUT_UNIT, fmt=*) A, B
    
    ! STEP.02
    ! calculate the answer of this task
    answer = calculate_solution (A, B)
    
    ! STEP.03
    ! output the answer of this task
    if ( answer .ge. 0_INT32 ) then
      write(unit=OUTPUT_UNIT, fmt='(I0)', advance='yes') answer
    else
      write(unit=OUTPUT_UNIT, fmt='(A)', advance='yes') "IMPOSSIBLE"
    end if
    
    ! STEP.END
    return

  end subroutine task_A
  
  pure function calculate_solution (A, B) result(solution)
  
    ! arguments for this <function>
    integer(INT32), intent(in) :: A, B
  
    ! return value for this <function>
    integer(INT32) :: solution
    
    ! variables for this <function>
    integer(INT32) :: sum_AB
    
    sum_AB = A + B;
    
    if ( is_even(sum_AB) ) then
        solution = sum_AB / 2_INT32
    else
        solution = -1_INT32
    end if
    
    return

  end function calculate_solution
  
  pure function is_even (val) result(stat)
  
    ! arguments for this <function>
    integer(INT32), intent(in) :: val
    
    ! return value of this <function>
    logical :: stat
    
    stat = mod(val, 2_INT32) .eq. 0_INT32
    return

  end function is_even

end module ABC135

program main

  ! <module>s to import
  use, non_intrinsic :: ABC135
  
  call task_A

end program main

Measured memory_bytes: 640
o = input()
e = input()
ans = ''
if len(o) == len(e):
    time = len(o) * 2
else:
    time = len(o) * 2 - 1
for i in range(time):
    if i % 2 == 0:
        ans += o[i // 2]
    else:
        ans += e[i // 2]
print(ans)

Measured memory_bytes: 9112
<?php
$n = trim(fgets(STDIN));
$b = explode(' ', trim(fgets(STDIN)));
$a = [];
$a[$n] = (int)$b[$n - 2];
for ($i = $n - 2; $i > 0; $i--) {
    $a[$i] = min((int)$b[$i], (int)$b[$i - 1]);
}
$a[0] = (int)$b[0];

echo array_sum($a) . PHP_EOL;


Measured memory_bytes: 4728
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

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

   int a, b, c, d;
   cin >> a >> b >> c >> d;
   int cnt = 1;
   while (true) {
      if (cnt % 2) {
         c -= b;
         if (c <= 0) {
            cout << "Yes" << endl;
            return 0;
         }
      } else {
         a -= d;
         if (a <= 0) {
            cout << "No" << endl;
            return 0;
         }
      }
      cnt++;
   }
   return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,q,sum[100005];
char ch[100005];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>q;
	cin>>ch+1;
	for(register int i=1;i<=n;i++)
	{
		if(ch[i]=='C'&&ch[i-1]=='A')
		{
			sum[i]=sum[i-1]+1;
		}
		else
			sum[i]=sum[i-1];
	}
	for(register int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<sum[r]-sum[l]<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
using namespace std;
int main()
{
    int W,a,b,t;
    cin>>W>>a>>b;
    if(a<b)
    {
        t=a;
        a=b;
        b=t;
    }
    if(a-b<=W)
        cout<<"0"<<endl;
    else
        cout<<a-b-W<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int min(int a, int b)
{

if(a<b)

return a;

else if(b<a)

return b;

}
int main()
{
    int i,a,b,c,p,q,r,s,t;

        scanf("%d%d%d",&a,&b,&c);

    p=a+b;
    q=b+c;
    r=c+a;
    t=min(p,q);
    s=min(t,r);
    printf("%d",s);




    return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    string s;
    cin >> s;
    int pos = 0;
    long long int ans = 0;
    for(int i = 0;i < s.size();i++)
    {
        if(s[i] == 'W')
        {
            ans += i - pos;
            pos++;
        }
    }
    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 9e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};
 
// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ---------------------------------------------------------------------------

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin >> A[i];
  }
  sort(A.begin(),A.end());
  int l=1,r=N-1;
  deque<int> deq;
  deq.push_front(A[0]);
  ll ans = 0;
  bool tf = false;
  while(l<r){
    if(tf){
      if(deq.front()-A[l] < deq.back()-A[l]){
        ans += deq.back() - A[l];
        deq.push_back(A[l]);
        l++;
        if(r == l) break;
        ans += deq.front() - A[l];
        deq.push_front(A[l]);
        l++;
      }else{
        ans += deq.front() - A[l];
        deq.push_front(A[l]);
        l++;
        if(l == r) break;
        ans += deq.back() - A[l];
        deq.push_back(A[l]);
        l++;
      }
      tf = false;
    }else{
      if(A[r]-deq.front() < A[r]-deq.back()){
        ans += A[r] - deq.back();
        deq.push_back(A[r]);
        r--;
        if(r == l) break;
        ans += A[r] - deq.front();
        deq.push_front(A[r]);
        r--;
      }else{
        ans += A[r] - deq.front();
        deq.push_front(A[r]);
        r--;
        if(r == l) break;
        ans += A[r] - deq.back();
        deq.push_back(A[r]);
        r--;
      }
      tf = true;
    }
  }
  ans += max(abs(deq.front()-A[l]),abs(deq.back()-A[l]));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1152
#include<stdio.h>
int main()
{
  char s[5];
  int n[4], i;
  scanf("%s", &s[0]);
  for(i=0;i<4;i++) n[i] = s[i] - '0';
  if((n[0] + n[1] + n[2] + n[3] ) == 7) printf("%d+%d+%d+%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] + n[1] + n[2] - n[3] ) == 7) printf("%d+%d+%d-%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] + n[1] - n[2] + n[3] ) == 7) printf("%d+%d-%d+%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] - n[1] + n[2] + n[3] ) == 7) printf("%d-%d+%d+%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] + n[1] - n[2] - n[3] ) == 7) printf("%d+%d-%d-%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] - n[1] - n[2] + n[3] ) == 7) printf("%d-%d-%d+%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] - n[1] + n[2] - n[3] ) == 7) printf("%d-%d+%d-%d=7\n", n[0], n[1], n[2], n[3]);
  else if((n[0] - n[1] - n[2] - n[3] ) == 7) printf("%d-%d-%d-%d=7\n", n[0], n[1], n[2], n[3]);
  else printf("error\n");
  return 0;
}
  

Measured memory_bytes: 128
a,b,c=map(int,input().split())
l=[]
for i in range(1,min(a,b)+1):
  if a%i==0 and b%i==0:
    l.append(i)
if l==[]:
  print("YES")
elif c%l[-1]==0:
  print("YES")
else:
  print("NO")

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

int64_t dp[51][2501];

signed main () {
    int n, a;
    cin >> n >> a;
    vector < int > x(n + 1, 0);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
        for (int j = n; j >= 1; --j) {
            for (int sum = 2500; sum >= x[i]; --sum) 
                dp[j][sum] += dp[j - 1][sum - x[i]];
        }
    }
    int64_t ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += dp[i][a * i];
    cout << ans << '\n';
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define REP(a, b) for(int a = 0; a < b; a++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> LL;
typedef vector<int> vi;

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

int A[MAXN][5], n;
int DP[MAXN][5];

int rek(int pos, int last) {
	if (pos == n) return 0;
	int &ret = DP[pos][last];
	if (ret != -1) return ret;
	ret = 0;
	FOR(i, 1, 3) {
		if (i != last) ret = max(ret, A[pos][i] + rek(pos + 1, i));		
	}
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	REP(i, n) cin >> A[i][1] >> A[i][2] >> A[i][3];	
	memset(DP, -1, sizeof DP);
	cout << rek(0, 0) << '\n';
}

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

int main() {
  int N;
  cin>>N;
  vector<int>a(N);

rep(i,N){
    cin>>a.at(i);
    }

    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    
    int A,B;
    A=0;
    B=0;
    
    rep(i,N){
    if(i%2==0){A+=a.at(i);}else{B+=a.at(i);}
    }
    cout<<A-B<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,a,b;
	cin>>n>>a>>b;
	if((a&1)==(b&1))
		cout<<(b-a)/2<<endl;
	else
		cout<<min(b+(a-b-1)/2,(n-a+1)+(a-b-1)/2)<<endl;
	return 0;
}

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

int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	string s,t;
  	cin>>s>>t;
  	if(t.substr(0,0+s.length()) == s)
       cout<<"Yes"<<endl;
       else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3616
MOD = 10**9+7
n, m = map(int, input().split())

U = max(n, m)
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


invfact = [0]*(U+1)
invfact[U] = pow(fact[U], MOD-2, MOD)
for i in reversed(range(U)):
    invfact[i] = invfact[i+1]*(i+1) % MOD


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]


def nPr(n, r):
    return fact[n]*invfact[n-r]


ans = 0
for k in range(n+1):
    tmp = nCr(n, k)*nPr(m, n)*nPr(m-k, n-k)
    if k % 2 == 0:
        ans += tmp
    else:
        ans -= tmp
    ans %= MOD
print(ans)


Measured memory_bytes: 48428
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,tot;
char str[MAXN];
void add_edge(int u,int v)
{
    printf("%d %d\n",u,v);
}
void chrysanthemum(int v,int cnt)
{
    for(int i=1;i<cnt;i++)
    {
        ++tot;
        add_edge(v,tot);
    }
}
void solve()
{
    tot=0;
    int v=++tot,last=1;
    for(int i=2;i<=n;i++)
    {
        if(str[i]=='1')
        {
            add_edge(++tot,v);
            v=tot;
            chrysanthemum(v,i-last);
            last=i;
        }
    }
    add_edge(++tot,v);
    chrysanthemum(tot,n-last);
}
int main()
{
    scanf("%s",str+1);
    n=strlen(str+1);
    if(str[n]=='1'||str[1]=='0')
    {
        puts("-1");
        return 0;
    }
    for(int i=1;i<=n-1;i++)
    {
        if(str[i]!=str[n-i])
        {
            puts("-1");
            return 0;
        }
    }
    solve();
    return 0;
}



Measured memory_bytes: 1536
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
A.sort()

l = 0
r = n - 1
flag = False  # マイナスになってしまうかフラグ
ans = 1
if k % 2 == 1:
    ans = A[r]
    r -= 1
    k -= 1
    if ans < 0:
        flag = True


if flag:  # どうしてもマイナスになってしまう場合(kが奇数で要素すべてがマイナスの場合)
    while k:
        ans *= A[r] * A[r - 1] % MOD
        ans %= MOD
        r -= 2
        k -= 2
else:  # 必ず0以上にできる場合
    while k:
        x = A[l] * A[l + 1]
        y = A[r] * A[r - 1]
        if x > y:
            ans *= x % MOD
            ans %= MOD
            l += 2
        else:
            ans *= y % MOD
            ans %= MOD
            r -= 2
        k -= 2

print(ans)


Measured memory_bytes: 101632