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

struct UnionFind{
	vector<int> rnk,par,num;
	UnionFind(int N) : rnk(N),par(N),num(N){
		init();
	}
	void init(){
		for(int i = 0;i < rnk.size();i++){
			rnk[i] = 0;
			par[i] = i;
			num[i] = 1;
		}
	}
	int find(int x){
		if(par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(rnk[x] < rnk[y]){
			par[x] = y;
			num[y] += num[x];
		}
		else{
			par[y] = x;
			num[x] += num[y];
			if(rnk[x] == rnk[y]) rnk[x]++;
		}
	}
	bool same(int x,int y){
		return (find(x) == find(y));
	}
	int size(int x){
		return num[find(x)];
	}
};

struct edge{int u, v, cost;};

bool comp(const edge& e1, const edge& e2){
  return e1.cost < e2.cost;
}

signed main(){
  int V, E; cin >> V >> E;
  UnionFind tree(V);
  vector<edge> es;
  for(int i = 0; i < E; i++){
    int s, t, w; cin >> s >> t >> w;
    edge e = {s, t, w};
    es.push_back(e);
  }
  int ans = 0;
  sort(es.begin(), es.end(), comp);
  for(int i = 0; i < E; i++){
    edge e = es[i];
    if(!tree.same(e.u, e.v)){
      ans += e.cost;
      tree.unite(e.u, e.v);
    }
  }
  cout << ans << endl;
}


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

int main(){
int N,K;
cin >> N >> K;
vector <vector<int>> A(K,vector<int>(N));
for(int i = 0; i < K; i++){
  int d;
  cin >> d; 
  for(int j = 0; j < d; j++){
    cin >> A.at(i).at(j);
  }
}

vector<int> memb(N);

for(int i = 0; i < K; i++){
  for(int j = 0; j < N; j++){
    if(A.at(i).at(j) >0) memb.at(A.at(i).at(j)-1)++;
  }
}

  int count = 0;
for(int i = 0; i < N; i++){
if(memb.at(i) == 0) count++;
}

  cout << count << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<bool>&,vector<vector<int>>&,int);
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> path(n + 1);
    for(int i = 0;i < m;i++){
        int a,b;
        cin >> a >> b;
        path[a].push_back(b);
        path[b].push_back(a);
    }
    vector<bool> flag(n + 1,false);
    int counter = 0;
    for(int i = 1;i <= n;i++){
        if(flag[i]){
            continue;
        }
        counter++;
        flag[i] = true;
        dfs(flag,path,i);


    }
    cout << counter - 1;
    return 0;
}

void dfs(vector<bool> &flag,vector<vector<int>> &path,int a){
    if(path[a].empty()){
        return;
    }
    for(auto i:path[a]){
        if(flag[i]){
            continue;
        }
        flag[i] = true;
        dfs(flag,path,i);
    }
    return;

}


Measured memory_bytes: 9560
def cv(t):
	return t/100*60+t%100

while 1:
	n,p,q = map(int,raw_input().split())
	if n==0: break
	v=[0]*1440
	for i in range(n):
		k = int(raw_input())
		a = map(int,raw_input().split())
		for j in range(k):
			for l in range(cv(a[::2][j]),cv(a[1::2][j])):
				v[l]+=1
	m=c=0
	for i in range(cv(p),cv(q)):
		c=c+1 if v[i]<n else 0
		m=max(m,c)
	print m

Measured memory_bytes: 4276
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cmath>
using namespace std;
int main(void)
{
	int a,b,x;
	double x2,d,s,d2;
	scanf("%d %d %d",&a,&b,&x);
	x2=(double)x/a;
	s=(double)a*b/2.0;
	if(s>=x2)	{
		d=atan(x2*2.0/(double)(b*b));
		d2=d*180.0/M_PI;
		d2=90.0-d2;
	}
	else {
		x2=(double)a*b-x2;
		d=atan(x2*2.0/(double)(a*a));
		d2=d*180.0/M_PI;
	}
	printf("%.10lf\n",d2);
	return 0;
}

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

int main(){
    int a,b,c=0,d=-1;
    cin >> a >> b;

    bool g[100][100];
    REP(i,100) REP(j,100) g[i][j] = i<50;
    while(--a>0) d<49 ? g[2*c][2*++d]=0 : g[2*++c][d=0]=0;
    c=26,d=-1;
    while(--b>0) d<49 ? g[2*c][2*++d]=1 : g[2*++c][d=0]=1;

    cout << "100 100\n";
    REP(i,100){
        REP(j,100) cout << (g[i][j] ? "#" : ".");
        cout << "\n";
    }
}


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

int main() {
  string S;
  long long int K;
  cin>>S>>K;
  for(int i=0;i<S.size();i++){
    char c=S.at(i);
    if(c=='1'&&K-1!=i){continue;}
    else if(c=='1'&&K-1==i){cout<<c<<endl;break;}
    else{cout<<c<<endl;break;}
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

i64 pow_mod(i64 n, i64 k, i64 m){
  i64 r = 1;
  for(;k;k>>=1){
    if(k&1) r=(r*n)%m;
    n=(n*n)%m;
  }
  return r;
}

void Main()
{
  i64 N,M;
  cin >> N >> M;

  map<i64,i64> mp;
  i64 i = 2;
  i64 P = M;
  while(i*i<=P){
    while(P%i==0){
      mp[i] = mp[i] + 1;
      P /= i;
    }
    i++;
    if(P != 1 and P<i*i){
      mp[P] = mp[P] + 1;
      P = 1;
    }
  }

  vi fractal(N+50);
  fractal.at(0) = 1;
  rep(i,1,N+50){
    fractal.at(i) = fractal.at(i-1) * i;
    fractal.at(i) %= MOD;
  }


  i64 ans = 1;
  for(auto &p:mp){
    ans *= fractal.at(N-1+p.second);
    ans %= MOD;
    ans *= pow_mod(fractal.at(N-1),MOD-2,MOD);
    ans %= MOD;
    ans *= pow_mod(fractal.at(p.second),MOD-2,MOD);
    ans %= MOD;
  }
  
  cout << ans << "\n";
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main
{
    static boolean max_log_size(int s, int arr[], int n, int k){
        long cuts = 0l;

        for(int i = 0; i < n; i++)
            cuts += arr[i]/s + (arr[i] % s == 0 ? -1 : 0);

        return cuts <= k;
    }

    public static void process(int test_number)throws IOException
    {
        int n = ni(), k = ni(), arr[] = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = ni();

        int l = 1, r = 1000*1000*1000, mid, res = 0;

        while(l <= r){
            mid = l + (r - l)/2;

            if(max_log_size(mid, arr, n, k)){
                res = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }   

        pn(res);
    }
 
    static final long mod = (long)1e9+7l;
    
    static FastReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc = new FastReader();
 
        long s = System.currentTimeMillis();
        int t = 1;
        //t = ni();
        for(int i = 1; i <= t; i++)
            process(i);
 
        out.flush();
        System.err.println(System.currentTimeMillis()-s+"ms");
    }

    static void trace(Object... o){ System.err.println(Arrays.deepToString(o)); };
    static void pn(Object o){ out.println(o); }
    static void p(Object o){ out.print(o); }
    static int ni()throws IOException{ return Integer.parseInt(sc.next()); }
    static long nl()throws IOException{ return Long.parseLong(sc.next()); }
    static double nd()throws IOException{ return Double.parseDouble(sc.next()); }
    static String nln()throws IOException{ return sc.nextLine(); }
    static long gcd(long a, long b)throws IOException{ return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{ return (b==0)?a:gcd(b,a%b); }
    static int bit(long n)throws IOException{ return (n==0)?0:(1+bit(n&(n-1))); }
    
    static class FastReader{ 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader(){ 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next(){ 
            while (st == null || !st.hasMoreElements()){ 
                try{ st = new StringTokenizer(br.readLine()); } catch (IOException  e){ e.printStackTrace(); } 
            } 
            return st.nextToken(); 
        } 
  
        String nextLine(){ 
            String str = ""; 
            try{ str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } 
            return str; 
        } 
    } 
}


Measured memory_bytes: 57412
nlist = [int(input()) for i in range(5)]
#print(nlist)
total_time=0
tail=[]
for number in nlist:
    if number % 10 == 0:
        total_time += number
    else:
        total_time += (number+10-(number%10))
        tail.append(number%10)
if tail:
    total_time -= (10-min(tail))
print(total_time)


Measured memory_bytes: 2940
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();        
        int N, K;
        {int[] a = r.ii(); N = a[0]; K = a[1];}
        int k = (N-1)*(N-2)/2;
        if(k < K){
            println(-1);
            return;
        } else{
            int extra = k-K;
            int M = N-1+k-K;
            println(M);
            int n = 1;
            for(int i = 1; i < N; i++){
                println(i+" "+N);
            }
            if(extra == 0)
                return;
            for(int i = 1; i < N-1; i++){
                for(int j = i+1; j < N; j++){
                    println(i+" "+j);
                    extra--;
                    if(extra == 0){
                        return;
                    }
                }
            }
        }
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long.parseLong(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 24276
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int lli;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s,t;
    cin>>s>>t;
    lli ans=0;
    
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3796
import itertools
N,K = map(int, input().split())
a = [input().split() for i in range(2*K)]

b = []

for j in range(K):
    b.append(a[2*j +1])
b = list(itertools.chain.from_iterable(b))
b = set(b)
print(N-len(b))

Measured memory_bytes: 9312
#include<cmath>
#include<cstdio>
#include<algorithm>

#define N 51

using namespace std;

#define eps 1e-18
#define delta 0.98
#define T 100

int n;
struct Point
{
    double x,y,z;
};
Point P[N];
double ans;

double dist(Point A,Point B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

double solve()
{
    double t;
    Point s=P[0];
    int k; double mx,res;
    int u=10;
    ans=1e20;
    while(u--)
    { 
	    t=T;
		while(t>eps)
	    {
	        mx=0;
	        for(int i=1;i<=n;i++)
	        {
	            res=dist(s,P[i]);
	            if(res>mx) mx=res,k=i;
	        }
	        ans=min(ans,mx);
	        s.x+=(P[k].x-s.x)/mx*t;
	        s.y+=(P[k].y-s.y)/mx*t;
	        t*=delta;
	    }
	} 
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
	{
		scanf("%lf%lf",&P[i].x,&P[i].y);
		P[0].x+=P[i].x;
		P[0].y+=P[i].y;
	}
	P[0].x/=n;
	P[0].y/=n;
    printf("%.10lf\n",solve());
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

long long modinv(long long a, long long m)
{
    long long 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 nck(int n, int k, int MOD)
{
    int res = 1;

    for(int i = 0; i < k; ++i)
    {
        res = (res * (n - i)) % MOD;
    }

    for(int i = k; i >= 1; --i)
    {
        res = (res * modinv(i, MOD)) % MOD;
    }

    return res;
}

int pow2quick(int n, int MOD)
{
    if(n == 0)
    {
        return 1;
    }

    int half = pow2quick(n / 2, MOD);
    if(n % 2 == 1)
    {
        return ((half * half) % MOD * 2) % MOD;
    }
    else
    {
        return (half * half) % MOD;
    }
}

signed main()
{
    int n, a, b;
    const int MOD = 1e9 + 7;

    cin >> n >> a >> b;

    int ans = pow2quick(n, MOD) - 1;

    if(ans < 0) ans += MOD;
    
    ans = (ans - nck(n, a, MOD)) % MOD;
    if(ans < 0) ans += MOD;

    ans = (ans - nck(n, b, MOD)) % MOD;
    if(ans < 0) ans += MOD;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << endl;
}
const int mod = 1e9 + 7;

int main(){
	ll n; cin >> n;
	vl a(n); rep(i,n) cin >> a[i];
	multiset<ll> mse;
	rep(i,n){
		if(mse.empty()) mse.insert(-a[i]);
		else{
			auto itr = mse.upper_bound(-a[i]);
			if(itr != mse.end()) mse.erase(itr);
			mse.insert(-a[i]);
		}
	}
	cout << mse.size() << endl;
}

Measured memory_bytes: 5760
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

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

fn main() {
    input! {
        s:chars,
    }
    for i in 0..s.len() {
        if s[i] == ',' {
            print!(" ");
        } else {
            print!("{}", s[i]);
        }
    }
}


Measured memory_bytes: 4352
s=sorted(input())
t=sorted(input(),reverse=True)
s1=""
for i in s:
  s1+=i
t1=""
for i in t:
  t1+=i

arr=[s1,t1]
arr2=sorted(arr)
if arr==arr2:
  if s==t:
    print('No')
  else:
    print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    ll N, W;
    cin >> N >> W;

    vec<vec<ll>> v(4,vec<ll>(1));
    ll w0;
    cin >> w0 >> v[0][0];
    rep(i, N-1){
        ll w,val;
        cin >> w >> val;
        v[w-w0].push_back(val);
    }

    rep(i,4){
        sort(all(v[i]),greater<ll>());
        v[i].insert(v[i].begin(),0);
        for(int j=1;j<v[i].size();++j){
            v[i][j] = v[i][j]+v[i][j-1];
        }
    }

    ll ans = 0;
    rep(i,v[0].size())rep(j,v[1].size())rep(k,v[2].size())rep(l,v[3].size()){
        ll count = w0*(i+j+k+l)+j+2*k+3*l;
        if(count > W) break;
        ans = max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l]);
    }

    cout << ans << '\n';
}


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

#define fi first
#define se second
#define long long long
typedef pair<int,int> ii;

int main()
{
	// freopen("input.in", "r", stdin);

	int A, B;
	scanf("%d %d", &A, &B);
	if(A != 1 && B != 1) printf("%d\n", 1);
	else if(A != 2 && B != 2) printf("2\n");
	else printf("3\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

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

__attribute__((constructor))
void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X  << " " << Y << endl;
}


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

using namespace std;


#define  SZ(items) (int)items.size()
#define  CLR(a)  memset(a,0,sizeof(a))
#define  SET(a)  memset(a,-1,sizeof(a))
#define  nl "\n";

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




template <class T> inline T biton(T n, T pos)
{
    return n | ((T)1 << pos);
}
template <class T> inline T bitoff(T n, T pos)
{
    return n & ~((T)1 << pos);
}
template <class T> inline T ison(T n, T pos)
{
    return (bool)(n & ((T)1 << pos));
}
template <class T> inline T gcd(T a, T b)
{
    while (b)
    {
        a = a % b;
        swap(a, b);
    }
    return a;
}
template <class T> inline T bigmod(T p, T e, T m)
{
    T ret = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            ret = (ret * p) % m;
        p = (p * p) % m;
    }
    return (T)ret;
};


#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1)
{
    cerr << name << " is " << arg1 << std::endl;
}
template < typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args)
{
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " is " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define debug(...)
#endif

int inf=1e9+5;

void solve()
{
    int n;
    cin>>n;

    vector<int> items(n);
    for(int i=0; i<n; i++)
    {
        cin>>items[i];
    }
    vector<int> dp(n,inf);
    dp[0]=0;

    for(int i=0; i<n; i++)
    {

        for(int j=1; j<=2; j++)
        {
            if(i-j>=0)
            {
                dp[i]=min(dp[i],dp[i-j]+abs(items[i]-items[i-j]));
            }
        }
    }

    cout<<dp[n-1]<<nl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int t = 1;

    while (t--)
    {
        solve();
    }

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

int main(int argc, char* argv[])
{
  uint32_t N;
  double percent;
  std::cin >> N;

  if (N == 0 || N > 100) {
    return 0;
  }

  if ((N%2) == 0) {
    percent = 1.0 / 2.0;
  } else {
    percent = ((N / 2) + 1) / (double)N;
  }
  std::cout << percent << std::endl;
}

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

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

  for (int i = 0; i< N; i++){
    cin >> d.at(i);
  }
  sort(d.begin(),d.end());
  
  int dan = 0;
  int current_size = 0;
  for (int i=0; i<N; i++){
    if ( d.at(i) > current_size ){
      dan++;
      current_size = d.at(i);
    }
  }
  cout << dan << endl;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc163/tasks/abc163_b

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscanf(in, "%d%d\n", &n, &m)
	var sum = 0

	for i := 0; i < m; i++ {
		var temp int
		fmt.Fscanf(in, "%d ", &temp)
		sum += temp
	}

	if sum > n {
		fmt.Fprintln(out, -1)
	} else {
		fmt.Fprintln(out, n-sum)
	}
}


Measured memory_bytes: 2020
#include<iostream>
 
int main()
{
	unsigned ai, ao, at, aj, al, as, az;
	std::cin >> ai >> ao >> at >> aj >> al >> as >> az;
	bool bi = ai % 2 == 0;
	bool bj = aj % 2 == 0;
	bool bl = al % 2 == 0;
	if (bi)
	{
		if (bj)
		{
			if (bl)
			{
				std::cout << ao + ai + aj + al << std::endl;
			}
			else
			{
				std::cout << ao + ai + aj + al - 1 << std::endl;
			}
		}
		else
		{
			if (bl)
			{
				std::cout << ao + ai + aj + al - 1 << std::endl;
			}
			else
			{
				if (ai > 0)
				{
					std::cout << ao + ai + aj + al - 1 << std::endl;
				}
				else
				{
					std::cout << ao + ai + aj + al - 2 << std::endl;
				}
			}
		}
	}
	else
	{
		if (bj)
		{
			if (bl)
			{
				std::cout << ao + ai + aj + al - 1 << std::endl;
			}
			else
			{
				if (aj > 0)
				{
					std::cout << ao + ai + aj + al - 1 << std::endl;
				}
				else
				{
					std::cout << ao + ai + aj + al - 2 << std::endl;
				}
			}
		}
		else
		{
			if (bl)
			{
				if (al > 0)
				{
					std::cout << ao + ai + aj + al - 1 << std::endl;
				}
				else
				{
					std::cout << ao + ai + aj + al - 2 << std::endl;
				}
			}
			else
			{
				std::cout << ao + ai + aj + al << std::endl;
			}
		}
	}
}

Measured memory_bytes: 256
x, k, d = map(int, input().split())

if x < 0:
    x = -x

if x >= k * d:
    print(x - k * d)
else:
    if (x // d) % 2 == 1:
        if k % 2 == 1:
            print(x % d)
        else:
            print(d - x % d)
    else:
        if k % 2 == 1:
            print(d - x % d)
        else:
            print(x % d)

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

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

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
#define out(v) cout<<v<<"\n"
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int N; cin >> N;
  string s, t; cin >> s >> t;

  rrep(l, N) {
    bool matched = true;
    rep(i, l) {
      if (s[N-l+i] != t[i])
        matched = false;
    }
    if (matched) {
      out(s.size() + t.size() - l);
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
// C.

#include <iostream>
#include <sstream>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[])
{
	int n;
	cin >> n;
	const char p[5] = {'M','A','R','C','H'};
	LL cnt[5] = {};
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < 5; ++j) {
			if (s[0] == p[j]) {
				++cnt[j];
			}
		}
	}
	LL ans = 0;
	for (int i = 0; i < 3; ++i) {
		for (int j = i + 1; j < 4; ++j) {
			for (int k = j + 1; k < 5; ++k) {
				ans += cnt[i] * cnt[j] * cnt[k];
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import queue

k = int(input())
q = queue.Queue()

counter = 0
for i in range(9):
    q.put(i+1)
while counter < k:
    n = q.get()
    counter += 1
    mod = n % 10
    if mod != 0:
        q.put(10*n+mod-1)
    q.put(10*n+mod)
    if mod != 9:
        q.put(10*n+mod+1)
print(n)


Measured memory_bytes: 18940
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import calendar as cal

i = input().split(' ')
d = int(i[0])
n = int(i[1])

z = 1
c = 0
while True:
    if z%(100**3)==0:
        pass
    elif z%(100**2)==0:
        if d==2:
            c = c+1
    elif z%100==0:
        if d==1:
            c = c+1
    else:
        if d==0:
            c = c+1
    if c == n:
        print(z)
        break
    z = z+1


Measured memory_bytes: 4592
# include <iostream>

int main() {
	{
		using namespace std;
		const int MAX = 1000000000LL;
		long long int n;
		cin >> n;

		long long int current_profit = -MAX;
		long long int min = +MAX;
		long long int max_profit = -MAX;

		for (long long int i = 0; i < n; i++) {
			long long int r;
			cin >> r;
			if ( i > 0)
				current_profit = r - min;
			if (r < min)
				min = r;
			if (current_profit > max_profit)
				max_profit = current_profit;
		}
		cout << max_profit << endl;
	}

	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct RollingHash{
  ll base, mod;
  vector<ll> hashed, power;
  RollingHash(){ base = 9973ll, mod = 1000000007ll; }
  void init(const int* s, int sz)
  {
    hashed.assign(sz + 1, 0);
    power.assign(sz + 1, 0);
    
    hashed[0] = 0ll;
    power[0] = 1ll;
    
    for(int i = 0; i < sz; i++){
      hashed[i+1] = (hashed[i] + s[i]) * base;
      power[i+1] = power[i] * base;
    }
  }
  ll get(int l, int r)
  {
    return hashed[r] - hashed[l]*power[r-l];
  }
};

int decode(char c, int shift)
{
  int bit = 0;
  if(c == '+') bit = 62;
  else if(c == '/') bit = 63;
  else if('A' <= c && c <= 'Z') bit = c - 'A';
  else if('a' <= c && c <= 'z') bit = c - 'a' + 26;
  else if('0' <= c && c <= '9') bit = c - '0' + 52;
  return (bit >> shift) & 1;
}

void Reverse(int array[101][101], int w, int h)
{
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w/2; j++) swap(array[i][j], array[i][w-1-j]);
  }
}

void Rotate(int array[101][101], int w, int h)
{
  int carray[101][101];
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++) carray[i][j] = array[i][j];
  }
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++) array[i][j] = carray[w-1-j][i];
  }
}

RollingHash imghash[1000];
RollingHash ptnhash[100];

int main()
{
  int w, h, p;
  int image[1001][1001];
  int pattern[101][101];
  while(cin >> w >> h >> p, w || h || p){
    for(int i = 0; i < h; i++){
      string data; cin >> data;
      for(int j = 0; j < w; j++){
	image[i][j] = decode(data[j/6], 5-j%6);
      }
      imghash[i].init(image[i], w);
    }
    for(int i = 0; i < p; i++){
      string data; cin >> data;
      for(int j = 0; j < p; j++){
	pattern[i][j] = decode(data[j/6], 5-j%6);
      }
      ptnhash[i].init(pattern[i], p);
    }
    int ans = 0;
    map<vector<int>, bool> mp;
    for(int l = 0; l < 8; l++){
      if(l == 4) Reverse(pattern, p, p);
      Rotate(pattern, p, p);
      for(int i = 0; i < p; i++) ptnhash[i].init(pattern[i], p);
      vector<int> vec;
      for(int i = 0; i < p; i++) vec.push_back(ptnhash[i].get(0, p));
      if(mp.count(vec) == 1) continue;
      mp[vec] = true;
       for(int i = 0; i <= h-p; i++){
	for(int j = 0; j <= w-p; j++){
	  bool same = true;
	  for(int k = 0; k < p; k++){
	    //if(i == 0 && j == 0 && l == 0) cout << imghash[i+k].get(j, j+p) << " " << ptnhash[k].get(0, p) << endl;
	    if(imghash[i+k].get(j, j+p) != ptnhash[k].get(0, p)){
	      same = false;
	      break;
	    }
	  }
	  if(same) ans++;
	}
      }
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 21108
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
from collections import Counter
n=int(input())
s=Counter(prime_factorize(n))
t=list(s.values())
cnt=0
#print(s)
#print(t)
for i in t:
  if i==1:
    cnt+=1
    
  else:
    s=1
    while i>0:
      i=i-s
      s+=1
      if i<0:
        break
      cnt+=1
      
print(cnt)
      

Measured memory_bytes: 9452
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=100005;
int n;
ll h[max_n];
int a,b;
int main(){
    scanf("%d%d%d",&n,&a,&b);
    a-=b;
    for(int i=1;i<=n;i++)scanf("%lld",h+i);
    int l=0,r=1000000000/b+1;
    int mid,ans;
    function<bool(int)> check=[&](int x){
        ll res=0;
        for(int i=1;i<=n;i++){
            ll tmp=h[i]-1ll*b*x;
            if(tmp>=0)res+=(tmp+a-1)/a;
        }
        return res<=x;
    };
    while(l<=r){
        mid=l+r>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 1024
K = int(input())
l = [0 for i in range(K)]
r = 0
for i in range(K):
    r = (10*r+7)%K
    if r == 0:
        print(i+1)
        break
    elif l[r] != 0:
        print(-1)
        break
    else:
        l[r] = 1

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

void main_()
{
    int N;
    cin >> N;
    vector<int64_t> As, Bs;
    copy_n(istream_iterator<int64_t>(cin), N + 1, back_inserter(As));
    copy_n(istream_iterator<int64_t>(cin), N, back_inserter(Bs));

    int64_t ans = 0;
    for (int i = 0; i < N; ++i) {
        auto b = Bs[i];
        auto a0 = As[i];
        auto& a1 = As[i + 1];

        ans += min(b, a0 + a1);
        a1 -= max((b - a0), 0L);
        a1 = max(0L, a1);
    }
    cout << ans << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 2548
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int x,gcd,n,k,mx;
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        mx=max(x,mx);
        gcd=__gcd(gcd,x);
    }
    if(k>mx)puts("IMPOSSIBLE");
    else puts(gcd==1|k%gcd==0?"POSSIBLE":"IMPOSSIBLE");
}


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

const int maxn=2e5+7;
int t[maxn],f[maxn],cnt,tot,cb,ce,n,m;
char s[maxn],ch[maxn],b[maxn],e[maxn];

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	cin>>m;
	for(int i=1;i<=m;++i) {
		scanf("%d",&t[i]);
		if(t[i]==1) cnt++;
		else {
			scanf("%d",&f[i]);
			char c=getchar();
			while(c<'a'||c>'z') c=getchar();
			ch[i]=c;
		}
	}
	for(int i=1;i<=m;++i) {
		if(t[i]==1) tot++;
		else {
			if((cnt-tot)%2==0) {
				if(f[i]==1) b[++cb]=ch[i];
				else e[++ce]=ch[i];
			}
			else {
				if(f[i]==1) e[++ce]=ch[i];
				else b[++cb]=ch[i];
			}
		}
	}
	for(int i=cb;i>=1;--i) 
		putchar(b[i]);
	if(cnt%2)
		for(int i=n;i>=1;--i) putchar(s[i]);
	else 
		for(int i=1;i<=n;++i) putchar(s[i]);
	for(int i=1;i<=ce;++i) 
		putchar(e[i]);
}

Measured memory_bytes: 2560
package main

import (
	"fmt"
	"sort"
)

var n int
var edges_origin []Edge
var edges []Edge

type Edge struct {
	x, y, idx, cost int
}

// atcoderのgolangがいつまでたっても古いせいでたかだか構造体のソートにこんな実装を書かなきゃならない羽目になる
type ByX []Edge
type ByY []Edge
type ByCost []Edge

func (_e ByX) Len() int           { return len(_e) }
func (_e ByX) Swap(i, j int)      { _e[i], _e[j] = _e[j], _e[i] }
func (_e ByX) Less(i, j int) bool { return _e[i].x < _e[j].x }

func (_e ByY) Len() int           { return len(_e) }
func (_e ByY) Swap(i, j int)      { _e[i], _e[j] = _e[j], _e[i] }
func (_e ByY) Less(i, j int) bool { return _e[i].y < _e[j].y }

func (_e ByCost) Len() int           { return len(_e) }
func (_e ByCost) Swap(i, j int)      { _e[i], _e[j] = _e[j], _e[i] }
func (_e ByCost) Less(i, j int) bool { return _e[i].cost < _e[j].cost }

func main() {
	// MSTに落とし込みたいがNが大きすぎる
	// 二次元座標のグラフはどちらかの軸でソートしてみるとみえてくるものがある
	// xでソートしたとき、明らかにその順番にノードを選ぶとよさそう（x1->x2->x3とx1->x3->x2を比べると後者はいったん行き過ぎてから戻るため無駄がある）
	// ではyも考えるとするとどうなるか？で詰んだ。

	// 「x,yそれぞれでソートしてみると、『2点間を貼るエッジが2つ存在する』となる」
	// なのでエッジ数は2(N-1)となりMSTができそうになる
	// （そこからMSTをやるのがまたなんかめんどくさかったんだけどそれは別の話）

	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		e := Edge{x: x, y: y, idx: i}
		edges_origin = append(edges_origin, e)
	}
	sort.Sort(ByX(edges_origin))
	for i := 1; i < n; i++ {
		payload := abs(edges_origin[i-1].x - edges_origin[i].x)
		edges = append(edges, Edge{x: edges_origin[i-1].idx, y: edges_origin[i].idx, cost: payload})
	}
	sort.Sort(ByY(edges_origin))
	for i := 1; i < n; i++ {
		payload := abs(edges_origin[i-1].y - edges_origin[i].y)
		edges = append(edges, Edge{x: edges_origin[i-1].idx, y: edges_origin[i].idx, cost: payload})
	}
	sort.Sort(ByCost(edges))
	ans := 0
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		parents[i] = i
	}
	for _, e := range edges {
		if same(e.x, e.y, parents) == false {
			union(e.x, e.y, parents)
			ans += e.cost
		}
	}
	fmt.Println(ans)
}

func root(x int, arr []int) int {
	if x == arr[x] {
		return x
	}
	y := root(arr[x], arr)
	arr[x] = y
	return arr[x]
}

func same(a, b int, arr []int) bool {
	return root(a, arr) == root(b, arr)
}

func union(a, b int, arr []int) {
	ra, rb := root(a, arr), root(b, arr)
	arr[ra] = rb
}

func abs(a int) int {
	if a <= 0 {
		return -1 * a
	} else {
		return a
	}
}


Measured memory_bytes: 44416
#include <bits/stdc++.h>
using namespace std;
int n;
vector< pair <string,char> > sol,tmp;
int main()
{
    cin >> n;
    sol.push_back({"a",'a'});
    for (int i = 2; i <= n; i++){
        vector< pair<string,char> > tmp;
        for(int j = 0; j < sol.size(); j++){
            for(char x = 'a'; x <= sol[j].second + 1; x++){
                string aa = sol[j].first + x;
                tmp.push_back({aa,max(sol[j].second, x)});
            }
        }
        sol = tmp;
    }
    for(int i = 0; i < sol.size(); i++){
        cout << sol[i].first<<endl;
    }
    return 0;
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;

const int INF = 1001001001;

int main() {

    ll n;
    cin >> n;

    cout << ((n - 1) * (n) / 2) << endl;

}


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

using namespace std;

#define ll long long

const ll MOD = 1000000007LL;
ll dp[4001][4001];

// aのb乗を求める.
ll modpow(ll a, ll b) {
	if (a > MOD) a %= MOD;
	if (b == 0LL) return 1LL;
	ll tmp = modpow(a, b / 2);
	if (b & 1LL)
		return tmp * tmp % MOD * a % MOD;
	return tmp * tmp % MOD;
}

// aの逆元を求める.
ll inverse(ll a) {
	return modpow(a, MOD - 2);
}

// kの階乗を計算する.(sgnを0以外に設定すると逆元を返す)
ll fact(ll k, int sgn = 0) {
	static vector<ll> fac(2, 1LL);
	static vector<ll> inv(2, 1LL);
	static vector<ll> finv(2, 1LL);
	static ll nx = 2LL;
	while (nx <= k) {
		fac.push_back(fac[nx - 1] * nx % MOD);
		inv.push_back(MOD - inv[MOD % nx] * (MOD / nx) % MOD);
		finv.push_back(finv[nx - 1] * inv[nx] % MOD);
		++nx;
	}
	if (sgn == 0)
		return fac[k];
	return finv[k];
}

// aCbを計算する.
ll comb(ll a, ll b) {
	if (b < 0 || b > a) return 0;
	return fact(a) * fact(b, 1) % MOD * fact(a - b, 1) % MOD;
}


signed main() {
	int n; cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i] >> b[i];

	// dpの初期化
	for (int i = 0; i < n; ++i) {
		int x = -a[i] + 2000, y = -b[i] + 2000;
		++dp[x][y];
	}

	// dpの遷移
	for (int x = 0; x < 4001; ++x) {
		for (int y = 0; y < 4001; ++y) {
			if (x < 4000) // 右に遷移可能
				dp[x + 1][y] = (dp[x + 1][y] + dp[x][y]) % MOD;
			if (y < 4000) // 上に遷移可能
				dp[x][y + 1] = (dp[x][y + 1] + dp[x][y]) % MOD;
		}
	}

	// 答えの計算
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		res += dp[a[i] + 2000][b[i] + 2000];
		res %= MOD;
	}
	for (int i = 0; i < n; ++i) { // 余分なものを除く
		ll rem = comb(2LL * a[i] + 2LL * b[i], 2LL * a[i]);
		res -= rem;
		res = (res + MOD) % MOD;
	}
	res *= inverse(2);
	res %= MOD;

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 127232
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
int main(){
	vector<int> str;
	string q,key;
	map<string,char> mp;
	map<string,char>::iterator itr;
	int n;
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>q;
		if(q=="insert"){
			cin>>key;
			mp[key]=true;
		}
		else{
			cin>>key;
			itr=mp.end();
			if(mp.end()==mp.find(key))cout<<"no"<<endl;
			else cout<<"yes"<<endl;
		}
	}

	return 0;
}


Measured memory_bytes: 36892
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;

int main()
{
    string s;
    ll K;
    cin >> s >> K;

    vector<pair<char, int>> runlength;
    {
        char now = s.front();
        int cnt = 1;
        REP(i, 1, s.size()) {
            if (s[i] == now)cnt++;
            else {
                runlength.emplace_back(now, cnt);
                now = s[i];
                cnt = 1;
            }
        }
        runlength.emplace_back(now, cnt);
    }
    if (runlength.size() == 1) {
        cout << (ll)s.size()*K / 2 << endl;
        return 0;
    }
    ll need = 0;
    for (const auto& p : runlength)need += p.second / 2;

    if (runlength.front().first != runlength.back().first) {
        need *= K;
    }
    else {
        ll normal = need;
        need = 0;
        const int M = runlength.size();
        runlength[M - 1].second += runlength.front().second;
        runlength.erase(runlength.begin());
        for (const auto& p : runlength)need += p.second / 2;
        need *= K - 1;
        need += normal;
    }
    cout << need << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const ll mod=998244353;
const ll LINF=1ll<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};



int M_N = 200000;

vector<ll> fact;
vector<ll> inver(M_N+1);
 
ll combi(int n,int r){
    if(n<r||n<0||r<0) return 0;
    return fact[n]%mod*inver[n-r]%mod*inver[r]%mod;
}
 
 
ll fpow(ll a, ll n){
    ll x = 1;
    while(n > 0){
        if(n&1){
            x=x*a%mod;
        }
        a=a*a%mod;
        n >>= 1;
    }
    return x;
}
 
void set_combi(){
    ll s=1;
    fact.push_back(1);
    for(int i=1;i<=M_N;i++){
        s*=i;
        s%=mod;
        fact.push_back(s);
    }
    inver[M_N]=fpow(fact[M_N],mod-2);
    for(int i=M_N-1;i>=0;i--){
        inver[i]=inver[i+1]*(i+1)%mod;
    }
}

using mint = modint998244353;
 
mint f(int j){
    return mint(fact[2 * j]) * inver[j] * inv_mod(mint(2).pow(j).val(), mod);
}

int main(){
    set_combi();
    int n;cin >> n;
    vector<int> cnt(1 << 17, 0);
    for (int i = 0; i < 2 * n; i++) {
        int x;cin >> x;
        cnt[x]++;
    }
    queue<vector<mint>> q;
    for (int i = 0; i < 1<<17; i++) {
        if(cnt[i]){
            int sz = cnt[i] / 2;
            vector<mint> a(sz + 1);
            for (int j = 0; j <= sz; j++) {
                a[j] = mint(combi(cnt[i], 2 * j)) * f(j);
            }
            q.push(a);
        }
    }
    while(q.size() > 1){
        auto a = q.front();q.pop();
        auto b = q.front();q.pop();
        auto c = convolution(a, b);
        q.push(c);
    }
    auto d = q.front();q.pop();
    mint ans = 0;
    for (int i = 0; i < d.size(); i++) {
        int t = n - i;
        ans += mint(i % 2 ? -1 : 1) * d[i] * f(t);
    }
    cout << ans.val() << endl;
    return 0;
}


Measured memory_bytes: 12452
#include <bits/stdc++.h>
using namespace std;
const string MINUSINF = "-";

void chmax(string &a, string b)
{
    if (a == MINUSINF)
        a = b;
    else if (a.size() < b.size())
        a = b;
    else if (a.size() == b.size())
    {
        if (a < b)
            a = b;
    }
}

long long match[10] = {2, 5, 5, 4, 5, 6, 3, 7, 6};
string dp[11000];

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> A(m);
    for (int i = 0; i < m; ++i)
        cin >> A[i];

    for (int i = 0; i < 11000; ++i)
        dp[i] = MINUSINF;
    dp[0] = "";

    for (int i = 0; i <= n; ++i)
    {
        if (dp[i] == MINUSINF)
            continue;
        for (auto a : A)
            chmax(dp[i + match[a - 1]], dp[i] + (char)('0' + a));
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 43776
#include <stdio.h>

int main(void){

  int h,w;
	scanf("%d %d", &h, &w);
	char c[h][w+1];
	for (int i = 0; i < h; i++) {
		scanf("%s", c[i]);
	}
	for (int i = 0; i < h; i++) {
		printf("%s\n", c[i]);
		printf("%s\n", c[i]);
	}

  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long n;
long long step;
long long a[1001];
long long ans;
int main() {
	cin>>n;
	long long x = n;
	while(x){ 
		step++;
		a[step] = x - (x / 10 * 10);
		x/=10;
	}
	for(int i=1;i<=step;i++) {
		if(a[i] < 9 && a[i] != step) a[i+1]--;
		if(i != step) {
			ans += 9;
		}
		else ans += a[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void func(int n);
int MAX=-1;
int sum=0;
int n;
	int box1[51];
	int box2[51];
	int box[51];
int main(void){
	
	int i;
	cin>>n;
	for(i=0;i<n;i++)	cin>>box1[i];
	for(i=0;i<n;i++)	cin>>box2[i];
	for(i=0;i<n;i++)	box[i]=box1[i]-box2[i];
	func(0);
	cout<<MAX<<endl;
	
	return 0;
}
void func(int cnt){
	if(cnt>=n)	MAX=max(MAX,sum);
	else{
		sum+=box[cnt];
		func(cnt+1);
		sum-=box[cnt];
		func(cnt+1);
	}
}


Measured memory_bytes: 256
//https://codeforces.com/contest/877/problem/D
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<string> s;
int n,m,k,j,X1,X2,Y1,Y2,d,dist;
vector<vector<vector<int>>> vis, dp;
//int vis[N][N][4],dp[N][N][4];
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};

bool valid(int i, int j){
    return i >= 0 && i < n && j >= 0 && j < m && s[i][j] != '@';
}

void bfs(int x, int y){
    deque<pair<pair<int,int>,pair<int,int>>> q;
    for(int j = 0; j < 4; ++j)dp[x][y][j] = 1, q.push_front({{x,y},{j,0}});
    while(q.size()){
        pair<pair<int,int>,pair<int,int>> u = q.front();
        q.pop_front();
        tie(x,y) = u.first;
        tie(d,dist) = u.second;
        if(vis[x][y][d])continue;
        vis[x][y][d] = 1;
        for(int dir = 0; dir < 4; ++dir){
            int i = x+dx[dir], j = y+dy[dir];
            if(!valid(i,j))continue;
            if(dir == d && dist < k && dp[i][j][dir] > dp[x][y][dir]){
                q.push_front({{i,j},{dir,dist+1}});
                dp[i][j][dir] = dp[x][y][dir];
            }else if(dp[i][j][dir] > dp[x][y][d]+1){
                q.push_back({{i,j},{dir,1}});
                dp[i][j][dir] = dp[x][y][d]+1;
            }
        }
    }
}

int main(){
    cin >> n >> m >> k;
    s = vector<string> (n+1);
    vis = vector<vector<vector<int>>> (n+1,vector<vector<int>>(m+1,vector<int>(4,0)));
    dp = vector<vector<vector<int>>> (n+1,vector<vector<int>>(m+1,vector<int>(4,int(1e9))));
    cin >> X1 >> Y1 >> X2 >> Y2;
    for(int i = 0; i < n; ++i)cin >> s[i];
    X1--,Y1--,X2--,Y2--;
    if(X1 == X2 && Y1 == Y2)return cout << 0 , 0;
    bfs(X1,Y1);    
    int ans  = min({dp[X2][Y2][0],dp[X2][Y2][1],dp[X2][Y2][2],dp[X2][Y2][3]});
    if(ans == (int)1e9)ans=-1;
    return cout << ans,0;
}


Measured memory_bytes: 276708
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
class Parser{
public:
  string s;
  vector< vector<string> > DP;
  string parse(){
    int n = s.length();
    DP = vector< vector<string> >(n+1, vector<string>(n+1,"?"));
    return expr(0,s.length());
  }

  string expr(int l, int r){
    if(DP[l][r] != "?") return DP[l][r];
    string ret = "!";
    ret = comp(ret, L(l,r));
    ret = comp(ret, R(l,r));
    ret = comp(ret, num(l,r));
    //printf("expr(%d,%d) = ",l,r);cout << ret << endl;
    DP[l][r] = ret;
    return ret;
  }
  
  string num(int l, int r){
    string ret;
    if(r - l > 1 && s[l] == '0') return "!";
    for(int i = l; i < r; ++i){
      if(isdigit(s[i])) ret += s[i];
      else if(s[i] == '?') ret += '9';
      else return "!";
    }
    return ret;
  }

  string comp(const string &a, const string &b){
    if(a == "!" && b != "!") return b;
    if(b == "!" && a != "!") return a;
    if(a.length() > b.length()) return a;
    if(a.length() < b.length()) return b;
    for(int i = 0; i < (int)a.length(); ++i){
      if(a[i] < b[i]) return b;
      if(a[i] > b[i]) return a;
    }
    return a;
  }

  string L(int l, int r){
    if(s[l] != '?' && s[l] != 'L') return "!";
    if(s[l+1] != '(' && s[l+1] != '?') return "!";
    if(s[r-1] != ')' && s[r-1] != '?') return "!";
    string ret = "!";
    for(int i = l+3; i < r-2; ++i){
      if(s[i] != ',' && s[i] != '?') continue;
      string x = expr(l+2,i), y = expr(i+1,r-1);
      if(y == "!" || x == "!") continue;
      ret = comp(ret,x);
    }
    return ret;
  }

  string R(int l, int r){
    if(s[l] != '?' && s[l] != 'R') return "!";
    if(s[l+1] != '(' && s[l+1] != '?') return "!";
    if(s[r-1] != ')' && s[r-1] != '?') return "!";
    string ret = "!";
    for(int i = l+3; i < r-2; ++i){
      if(s[i] != ',' && s[i] != '?') continue;
      string x = expr(l+2,i), y = expr(i+1,r-1);
      if(y == "!" || x == "!") continue;
      ret = comp(ret,y);
    }
    return ret;
  }
};

int main(){
  string s;
  cin >> s;
  Parser p;
  p.s = s;
  string ans = p.parse();
  if(ans == "!") cout << "invalid" << endl;
  else cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3280
#include<bits/stdc++.h>
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 1e9
#define All(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;

vector<ll> nck(2*100000+2,-1);

ll binomial(ll n,ll k){
    if(nck[n]!=-1)return nck[n];
    ll ans=1,K=1;
    for(int i=n-2+1;i<=n;i++)ans*=i;
    ans/=2;
    nck[n]=ans;
    return ans;

}

int main(){
    int N;cin>>N;
    vector<ll> A(N+2,0),a(N,0),an(N+2,0);
    ll ans=0;
    REP(i,N){
        cin>>a[i];
        A[a[i]]++;
    }
    REP(i,N+1){
        ans+=binomial(A[i],(ll)2);
    }
    //cout<<ans<<endl;
    REP(i,N){
        
        cout<<ans-binomial(A[a[i]],2)+binomial(A[a[i]]-1,2)<<endl;
    }
}


Measured memory_bytes: 8832