akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = readInt >>= flip replicateM getLine >>= print . length . group . sort

Measured memory_bytes: 165460
#include <bits/stdc++.h>
using namespace std;
const int maxn=205;
const int mod=998244353;
int x[maxn],y[maxn];
int gcd(int a,int b)
{
    while(b){
        a=a%b;
        swap(a,b);
    }
    return a;
}
map<pair<int,int>,int>mp;
int two[205];
int main()
{
    mp.clear();
    two[0]=1;
    int n;
    for(int i=1;i<maxn;i++)
        two[i]=two[i-1]*2%mod;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",x+i,y+i);
    }
    if(n<3){
        printf("0\n");
        return 0;
    }
    long long ans=two[n]-(n+1);
    for(int i=0;i<n;i++)
    {
        mp.clear();
        for(int j=i+1;j<n;j++)
        {
            int tx=x[i]-x[j];
            int ty=y[i]-y[j];
            //printf("%d %dss\n",tx,ty);
            if(tx==0) mp[make_pair(0,1)]=mp[make_pair(0,1)]+1;
            else if(ty==0) mp[make_pair(1,0)]=mp[make_pair(1,0)]+1;
            else{
                int t=gcd(abs(tx),abs(ty));
                tx/=t;ty/=t;
                if(tx<0){
                    tx=-tx;ty=-ty;
                }
                mp[make_pair(tx,ty)]=mp[make_pair(tx,ty)]+1;
            }
        }
        map<pair<int,int>,int>::iterator it;
        for(it=mp.begin();it!=mp.end();it++)
        {
            pair<int,int> fuck=it->first;
            int num=it->second;
            ans=ans-(two[num]-1);
            //printf("%d %lld %d %d\n",num,ans,fuck.first,fuck.second);
        }
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define nn '\n'
#define YES {cout<<"YES"<<'\n';}
#define NO {cout<<"NO"<<'\n';}
#define Yes {cout<<"Yes"<<'\n';}
#define No {cout<<"No"<<'\n';}
#define yes {cout<<"yes"<<'\n';}
#define no {cout<<"no"<<'\n';}
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) {cout << n << '\n';}
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

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

    string s; cin >> s;
    map<char,int> mp;
    REP(i,4) mp[s[i]]++;
    bool ok = 1;
    for(auto x:mp) if(x.second!=2) ok = 0;
    Yn(ok);

    return 0;
}

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

int main() {
  int N,K,Q;
  cin >> N >> K >> Q;
  vector<int> A(Q);
  for (int i = 0; i < Q; i++) {
    cin >> A.at(i);
    A.at(i)--;
  }
  vector<int> score(N);
  for (int i = 0; i < Q; i++) {
    score.at(A.at(i))++;
  }
  for (int i = 0; i < N; i++) {
    if (score.at(i) > Q-K) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 1408
#include<iostream>
 
using namespace std;
 
int main() {
    int b[3];
    cin >> b[0] >> b[1] >> b[2];
    if (b[0] + b[1] * 2 + b[2] * 3 >= 3)cout << "Open" << endl;
    else cout << "Close" << endl;
    return 0;
}

Measured memory_bytes: 3080
using System;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        string s = sc.Next();
        bool f = true;
        if (n % 2 != 0)
        {
            Console.WriteLine("No");
            return;
        }

        for (int i = 0; i < n / 2; i++)
        {
            if (s[i] != s[i + n / 2])
            {
                f = false;
                break;
            }
        }

        Console.WriteLine(f ? "Yes" : "No");
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 11092
#include <stdio.h>

#define MOD (1000000007L)



int main(void)
{
    long n;
    scanf("%ld",&n);

    long P1 = 1;
    long P2 = 1;
    long P3 = 2;

    if (n == 1) {
        printf("1\n");
    } else if (n == 2){
        printf("4\n");
    } else {
        for (long i = 3; i < n; i++) {
            const long newP = (P3 + (P3 -  (P2 - P1))%MOD) % MOD;
            P1 = P2;
            P2 = P3;
            P3 = newP;
        }
        printf("%ld\n", (1L + ((n-1L)%MOD) * ((n * (P3 - (P2 - P1)))%MOD + P2)%MOD + MOD)%MOD);
    }

    return 0;
}


Measured memory_bytes: 128
END { load __FILE__ unless $stdin.eof? }

def e25(n)
  e2 = e5 = 0
  loop do
    d, m = n.divmod(2)
    break if m != 0
    e2 += 1
    n = d
  end
  loop do
    d, m = n.divmod(5)
    break if m != 0
    e5 += 1
    n = d
  end
  [e2, e5]
end

n = gets.to_i
a = Array.new(n) do
  x, y = gets.chomp.split(".")
  y ||= "0"
  z = (x << (y << "000000000")[0, 9]).to_i
  e25(z)
end

b = a.tally.map { |k, v| k << v }.sort!

cnt = 0
until b.empty?
  e2, e5, m = b.shift
  cnt += m * m.pred / 2 if e2 >= 9 && e5 >= 9
  l = b.select { |f2, f5, *| e2 + f2 >= 18 && e5 + f5 >= 18 }.sum(&:last)
  cnt += m * l
end

p cnt


Measured memory_bytes: 28256
n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = {}
for i in range(m):
    if L[i][0] not in d:
        d[L[i][0]] = [L[i][1]]
    else:
        d[L[i][0]].append(L[i][1])
for j in d[1]:
    if j in d and n in d[j]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


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

int main(){
    int N , W; //Nは品物んp回数、Wは入れる重さ
    cin >> N >> W ;
    int v[N],w[N];
    int maxV[N+1][W+1];
    for(int i=1 ; i <= N ; i++){
        cin >> v[i] >> w[i];
    }
    for(int i=0 ; i <= W ; i++){
        maxV[0][i] = 0;
    }
    for(int i=1; i <= N ; i++){
        for(int j = 0 ; j <= W; j++){
            maxV[i][j] = maxV[i-1][j];
            if(j-w[i] >= 0) maxV[i][j] = max(maxV[i-1][j],maxV[i-1][j-w[i]] + v[i]);
        }
    }
    cout << maxV[N][W] << endl;

}


Measured memory_bytes: 7016
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String answer ="";
    if(S.equals("Sunny")){
      answer = "Cloudy";
    }else if(S.equals("Cloudy")){
      answer = "Rainy";
    }else{
      answer = "Sunny";
    }
      System.out.println(answer);

             

             
    
  }
  
  //最大公約数・最小公倍数（セットで使う）
static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
static int lcm (int a, int b) {return a*b/gcd(a,b);}


//素数判定
static boolean isPrime (int n) {
	if (n==2) return true;
	if (n<2 || n%2==0) return false;
	double d = Math.sqrt(n);
	for (int i=3; i<=d; i+=2) if(n%i==0){return false;}
	return true;
}


//倍数判定（10進数以外のときに有用）
static boolean isMultiple (String s, int base, int m) {
	int temp = 0;
	for (int i=0; i<s.length(); i++) {
		temp = (temp*base+Character.getNumericValue(s.charAt(i)))%m;
	}
	if (temp==0) {return true;}
	return false;
}


//階乗
static long factorial (int i) {
	if (i==1) {return 1;}
	else {return i*factorial(i-1);}
}


//進数変換
static String toNbase (String sm, int m, int n) {
	return Long.toString(Long.parseLong(sm,m),n);
}
  
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  ll a,b,c,d;
  cin >> a >> b >> c >> d;

  ll ans = -1400000000000000000;
  ans = max(b*d,ans);
  ans = max(ans,a*c);
  ans = max(ans,c*b);
  ans = max(ans,a*d);

  if(ans >= 0) cout << ans << endl;
  else {
    if(isin(0,a,b+1) or isin(0,c,d+1)) cout << 0 << endl;
    else cout << ans << endl;
  }


  return 0;
}


Measured memory_bytes: 3676
#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define DEBUG(x) cerr << #x << ": " << x << "\n"

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if (A >= B && A >= C) {
        cout << A * 10 + B + C << endl;
    } else if (B >= A && B >= C) {
        cout << B * 10 + A + C << endl;
    } else if (C >= A && C >= B) {
        cout << C * 10 + A + B << endl;
    }
    return 0;
}


Measured memory_bytes: 256
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 08/15/20 20:19:01
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  string s; cin>>s;
  int ans = 0;
  int cnt = 0;
  for (auto c:s) {
    if (c == 'R') {
      cnt++;
    } else {
      cnt = 0;
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3644
#include<iostream>
using namespace std;
int main()
{
    int r, d, x;
    cin >> r >> d >> x;
    int s = x;
    for(int i = 1; i <= 10; i++)
    {
        s = r * s - d;
        cout << s << " ";
    }
    return 0;
}

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

int main() {

  long long N, A, B;
  cin >> N >> A >> B;

  long long answer = N / (A + B) * A;
  
  long long a = N % (A + B);

  answer += min(a, A);

  cout << answer << endl;

  return 0;

}


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

#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int N = 21;
const int M = (1LL<<N);
int a[N][N];
int dp[N][M];
int pw[N+5];
int n;

vector<int> go[N];

int cnt[M];
const int MOD = 1e9 + 7;

void solve()
{
    pw[0] = 1;
    for(int i=1;i<=N;i++) pw[i] = pw[i-1]<<1;
    
    cin >> n;
    f(i,n) f(j,n) cin >> a[i][j];
    
    f(i,n) if(a[0][i] == 1) dp[0][pw[i]] = 1;
        
    for(int i=1;i<n;i++)
    {
        for(auto j : go[i])
        {
            for(int k=0;k<n;k++)
            {
                if(a[i][k] == 1 && ( (j&pw[k]) == 0))
                    dp[i][j|pw[k]]=(dp[i][j|pw[k]] + dp[i-1][j])%MOD;
            }
        }
    }
    
    cout << dp[n-1][pw[n]-1]; 
}

signed main()
{
    f(i,M) go[__builtin_popcount(i)].pb(i);
    
    fast;
    solve();
}

Measured memory_bytes: 171452
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef double db;

#define fr first
#define sc second
#define pb push_back
#define rep(i,x) for(ll i=0;i<x;i++)
#define rep1(i,x) for(ll i=1;i<=x;i++)
#define rrep(i,x) for(ll i=x-1;i>=0;i--)
#define rrep1(i,x) for(ll i=x;i>0;i--)
ll n,t,s,a[3000],b[3000];
ll s1,s2;
ll dp1[3001];//??????j??\???????????§?\???????
ll dp2[3001];//??????j??\???????????§?\???????
ll ans1[3001];//i???????????§??§s1??\???????????§joy
ll ans2[3001];//i????????\?????§s2??\???????????§joy
int main()
{
	cin>>n>>t>>s;
	s1=s;
	s2=t-s;
	memset(dp1,0,sizeof(dp1));
	memset(dp2,0,sizeof(dp2));
	rep(i,n) cin>>a[i]>>b[i];
	for(ll i=b[0];i<=t;i++) dp1[i]=a[0];
	for(ll i=b[n-1];i<=t;i++) dp2[i]=a[n-1];
	ans1[0]=dp1[s1];
	ans2[n-1]=dp2[s2];
	rep1(i,n-1){
		//rep(j,t+1) dp1[i][j]=dp1[i-1][j];
		rrep(j,t+1-b[i]){
			dp1[j+b[i]]=max(dp1[j+b[i]],dp1[j]+a[i]);
		}
		ans1[i]=dp1[s1];
	}
	rrep(i,n-1){
		//rep(j,t+1) dp2[i][j]=dp2[i+1][j];
		rrep(j,t+1-b[i]){
			dp2[j+b[i]]=max(dp2[j+b[i]],dp2[j]+a[i]);
		}
		ans2[i]=dp2[s2];
	}
	ll ans=max(ans1[n-1],ans2[0]);
	rep(i,n-1){
		ans=max(ans,ans1[i]+ans2[i+1]);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3272
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <complex>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T> T iabs(const T& x) { return max(x, -x); }

int main() {
    int n;
    string s;
    cin >> n >> s;
    int x = 0, ans = 0;
    for (char c : s) {
        x += c == 'I' ? 1 : -1;
        ans = max(ans, x);
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef long long lli;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<ll> vll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<ll, str>> vpls;
typedef vector<tuple<str, ll, ll>> vtsl;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//実行部
void Main()
{
  str s; cin >> s;
  str Y = s.substr(0, 4); ll y = stoi(Y);
  str M = s.substr(5, 2); ll m = stoi(M);
  str D = s.substr(8); ll d = stoi(D);
  if(y <= 2019&&m <= 4&&d <= 30) fin("Heisei")
  else fin("TBD")
}

//前処理
int main()
{
  //ios::sync_with_stdio(false);
  //cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long int
using namespace std;
int main()
{
    ll n,k; cin>>n>>k;
    ll a[n];
    for(ll i=0;i<n;i++) cin>>a[i];
    ll dp[n]; dp[0]=0;
    for(int i=1;i<n;i++)
    {
        dp[i]=INT_MAX;
        for(int j=i-1;j>=0 and j>=i-k;j--)
        {
            dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
        }
        //cout<<dp[i]<<" ";
    }
    cout<<dp[n-1];
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <math.h>
#include <string>
using namespace std;
 
const double PI = acos(-1);
const int M=1e9+7;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define oo 1e16

vi a;
vi dP;

void solve(){
	int n;
	cin>>n;
	a.resize(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
	}
	dP.resize(n);
	dP[1]=abs(a[0]-a[1]);
	for (int i = 2; i < n; ++i)
	{
		dP[i]=min(dP[i-1]+abs(a[i]-a[i-1]),dP[i-2]+abs(a[i]-a[i-2]));
	}
	printf("%d\n",dP[n-1] );
}

int main()
{

	int t;
	t=1;
	while(t--){
		solve();
	}

	return 0;
}




Measured memory_bytes: 3608
/* Murad Eynizade */
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
int n,ans = 0;
bool f[100001];
vector<int>v;
int main() {
	cin>>n;
	int a[n+1];
	for (int i = 1;i<=n;i++) {
		cin>>a[i];
		if (a[i] == i)f[i] = true;
	}
	for (int i = 1;i<=n;i++) {
		if (i == n && f[i] == true) {
			ans += 1;
			break;
		}
		else if (f[i] == true){
			ans += 1;
			f[i] = false;
			if (f[i+1] == true) {
				i++;
				f[i] = false;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 768
package main

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

const Inf = 1 << 60

func main() {
	K, T := ReadInt(), ReadInt()
	a := ReadInts(T)
	max := Max(a...)

	ans := max - (K - max) - 1
	if ans < 0 {
		fmt.Println(0)
	} else {
		fmt.Println(ans)
	}
}

func Max(xs ...int) int {
	max := xs[0]
	for _, x := range xs[1:] {
		if max < x {
			max = x
		}
	}
	return max
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1844
#include <stdio.h>
int main()
{
  int r,count=0;
  scanf("%d",&r);
  int ar[r];
  for(int i=0;i<r;i++)
  {
    scanf("%d",&ar[i]);
  }
  for(int i=1;i<r-1;i++)
  {
    if(((ar[i-1]<ar[i])&&(ar[i]<ar[i+1]))||((ar[i-1]>ar[i])&&(ar[i]>ar[i+1])))
  {
    count++;
  }
  
  }
  printf("%d\n",count);
  return 0;
  }
  
    
   
 

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

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


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)
def f(p, c):
    if P[p] == 0:
        P[p] = c
        for j in range(len(F[p])):
            f(F[p][j], c)
N, M = map(int, input().split())
F = [[] for _ in range(N)]
P = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
for i in range(N):
    f(i, i+1)
C = [0] * N
for i in range(N):
    C[P[i]-1] += 1
print(max(C))


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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

// I SCREAM

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto a = load<int>();
	auto b = load<int>();
	auto k = (a+b)/2;
	if (abs(a - k) == abs(b - k))
		cout << k << '\n';
	else cout << "IMPOSSIBLE\n";
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n, p;
  cin >> n >> p;
  string s;
  cin >> s;

  if (10%p == 0) { // 2, 5
    ll ans = 0;
    rep(i, n) {
      if ((s[i]-'0') % p == 0) {
        ans += i+1;
      }
    }
    cout << ans << endl;
    return 0;
  }

  vector<ll> d(n+1);
  ll ten = 1; // 10^k at digit k
  for (int i = n-1; i >= 0; --i) {
    int a = (s[i]-'0') * ten % p;
    d[i] = (d[i+1]+a) % p;
    ten *= 10; ten %= p;
  }
  vector<ll> cnt(p);
  // We want to find the count of pairs (i,j) where d[i] == d[j]. This means d[i] - d[j]=0 mod p.
  ll ans = 0;
  for (int i = n; i >= 0; --i) {
    ans += cnt[d[i]];
    ++cnt[d[i]];
  }
  cout << ans << endl;
}


Measured memory_bytes: 2196
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    cout << (n-1)*(m-1);
    
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int, input().split())

roads=[]

for _ in range(m):
  a,b=map(int, input().split())
  roads.append([a,b])
  
group=[i for i in range(n)]

group2=[]

while group2!=group:
  group2=list(group)
  for road in roads:
    if group[road[1]-1]>group[road[0]-1]:
      group[road[1]-1]=group[road[0]-1]
    else:
      group[road[0]-1]=group[road[1]-1]
  
counter=1
group.sort()

for i in range(n-1):
  if group[i]!=group[i+1]:
    counter+=1

print(counter-1) 
      



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

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

    vector<int> a(M), b(M);
    vector<set<int>> vse(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        vse[a[i]].insert(b[i]);
        vse[b[i]].insert(a[i]);
    }

    bool f = false;
    for (auto x : vse[1]) {
        f |= vse[x].find(N) != vse[x].end();
    }

    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;

    return 0;
}


Measured memory_bytes: 29952
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define _rep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define _REP(i, e, s) for (int i = (int)(e - 1); i >= (int)(s); i--)

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define ll long long
#define ull unsigned long long
#define vi vector<int>

const double PI = 3.14159265358979323846;

ll gcd(ll a, ll b) {
    if (a < b) return gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

int main() {
    long long N, M, A, B, ans = 0;
    cin >> N >> M;
    vector<long long> H(N), H2(N);
    rep(i, N) cin >> H[i];
    rep(i, M) {
        cin >> A >> B;
        H2[A - 1] = max(H2[A - 1], H[B - 1]);
        H2[B - 1] = max(H2[B - 1], H[A - 1]);
    }

    for (int i = 0; i < N; i++) {
        ans += H[i] > H2[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 4756
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
 int i,n,s;
 s=0;
 cin >> n;
 int a[n],b[n],c[n-1];
 for(i=0;i<n;i++)
 cin >> a[i];
 for(i=0;i<n;i++)
 {
  cin >> b[i];
  s+=b[i];
 }
 for(i=0;i<(n-1);i++)
 cin >> c[i];
 for(i=1;i<n;i++)
 {
  if(a[i]==(a[i-1]+1))
  s+=c[a[i-1]-1];
 }
 cout << s;
 return 0;
}

Measured memory_bytes: 3592
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
  int n,i,sum = 0,test = 0,sub0,sub1;
  scanf("%d\n",&n);
  int w[n];
  for(i = 0;i < n;i++) {
    scanf("%d",&w[i]);
    sum += w[i];
  }
  for(i = 0;i < n;i++) {
    test += w[i];
    if(test >=sum / 2) break;
  }
  sub0 = abs( test - (sum - test) );
  
  test -= w[i];
  sub1 = abs( test - (sum - test) );
  
  if(sub0 < sub1) printf("%d\n",sub0);
  else  printf("%d\n",sub1);   
  
  return 0;
}

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

typedef unsigned long long ll;

const int MOD = 1000000007;

int main() {
  int m;
  cin >> m;
  ll s = 0;
  ll ans = -1;
  for (int i = 0; i < m; ++i) {
    ll d;
    ll c;
    cin >> d >> c;
    s += d*c;
    ans += c;
  }
  while (s >= 10) { 
    // cout << s << " " << ans << endl;
    ans += s / 10;
    s = s/10 + s%10;
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		long sum=0;
		
		int[] c = new int[2001];
		for(int i=0;i<=1000;i++) {
			for(int j=0;j<=1000;j++) {
				c[i+j]++;
			}
		}
		
		while(sc.hasNext()) {
			int n = sc.nextInt();
			
			for(int k=0;k<=n;k++) {
				if(0<=k && k<=2000 && 0<=n-k && n-k<=2000) {
					sum+=c[k]*c[n-k];
				}
			}
			System.out.printf("%d\n",sum);
			sum=0;
		}
	}
}



Measured memory_bytes: 27280
import java.util.Scanner;

public class Main {
	  public static void main(String args[]) {
		    Scanner scanner = new Scanner(System.in);

		    int N = scanner.nextInt();
		    long array[];
		    array = new long [N];
		    int counter = 0;
		    for(int i = 0; i < array.length; i++)
		    {
		    	array[i] = scanner.nextLong();
		    	while(array[i]%2 == 0)
		    	{
		    		counter = counter + 1;
		    		array[i] = array[i]/2;
		    	}
		    }
		    System.out.println(counter);
		    		scanner.close();}
		  }

Measured memory_bytes: 34276
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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 main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;cin>>s;
    int t = s.size()%2;
    t += int(s[0]!=s[s.size()-1]);
    cout << (t%2 ? "Second" : "First") << endl;
    return 0;
}


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

int main(){
  int n,k;
  cin >> n >> k;
  int len=0;
  vector<int> x(n);
  rep(i,n){
    cin >> x[i];
  }
  rep(i,n){
    if(abs(x[i])<abs(k-x[i])){
      len +=2*abs(x[i]);
    }else len += 2*abs(k-x[i]);
  }
  cout << len << endl;
  return 0;
}


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

using lli = long long int;

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


template <class T> inline T& chmin(T& a, T b){return (a > b) ? a = b : a;}
template <class T> inline T& chmax(T& a, T b){return (a < b) ? a = b : a;}

std::vector<lli> A, B;

constexpr lli inf = 5e18;

int main(void){
    int n, m; scanf("%d%d", &n, &m);
    int SET_SIZE = 1 << n;
    A.resize(SET_SIZE, inf), B.resize(SET_SIZE);
    A[0] = 0;
    REP(i, m){
        B = A;
        int a, b; scanf("%d%d", &a, &b);
        int p = 0;
        REP(_, b){
            int t; scanf("%d", &t); t--;
            p |= (1 << t);
        }
        REP(j, SET_SIZE){
            chmin(B[j | p], A[j] + a);
        }
        std::swap(A, B);
    }
    if(A[SET_SIZE-1] == inf) puts("-1");
    else printf("%lld\n", A[SET_SIZE-1]);


    return 0;
}


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

int main(){
	int X; cin >> X;
	vector<int> cul;
	cul.push_back(0);

	int max = 0;
	for(int i = 1; i <= X; ++i){
		cul.push_back(cul[i-1]+i);
		if(cul[i-1] < X && X <= cul[i]){
			if(max < i) max = i;
		}

		if(cul[i] > X) break;
	}

	cout << max << endl;

	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define MAX 305

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int a,b,c;

int main(){
  cin >> a >> b >> c;
  if(a+b+c>=22){
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }

  return 0;
}


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

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;

inline ll pow(ll i){
  return i*i*i*i*i;
}

void ans(ll i, ll j){
  cout << i << " " << j << endl;
}

int main(){
  IO; ll X; cin >> X;
  REPN(i,125){
    REPN(j,125){
      if(pow(i)-pow(j)==X){
        ans(i,j);
        return 0;
      }
      if(pow(i)+pow(j)==X){
        ans(i,-j);
        return 0;
      }
      if(-pow(i)+pow(j)==X){
        ans(-i,-j);
        return 0;
      }
    }
  }
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define rep(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define rep_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9) + 7;
const ll INF = ll(1e10);
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";
const double PI = acos(-1);

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector<pair<ll, ll>> prime_factorize(ll n)
{
	vector<pair<ll, ll>> p;
	for (ll i = 2; i * i <= n; i++)
	{
		if ((n % i) != 0)
			continue;
		pair<ll, ll> a = make_pair(i, 0);
		while ((n % i) == 0)
		{
			n /= i;
			a.second += 1;
		}
		p.push_back(a);
	}

	if (n != 1)
		p.push_back(make_pair(n, 1));
	return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a)
{
	ll b = MOD, u = 1, v = 0;
	while (b)
	{
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0)
	{
		u += MOD;
	}
	return u;
}
// 順列
ll permutation(const ll n, const ll m)
{
	ll result = 1;
	for (ll i = n; i > n - m; i--)
	{
		result = (result * i) % MOD;
	}
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x)
{
	if (x == 0)
		return 1;
	ll res = repeat_square(n, x / 2);
	res = res * res % MOD;
	if ((x % 2) == 1)
		res = res * n % MOD;
	return res;
}
// 組み合わせ nCm
ll combination(ll n, ll m)
{
	ll p = permutation(n, m);
	ll div = 1;
	for (ll i = 2; i <= m; i++)
	{
		div = (div * i) % MOD;
	}
	return (p * modinv(div)) % MOD;
}

int calc(int n, int a, int b, vector<int> v)
{
	int result = 0;
	rep(i, n)
	{
		if (i % 2 == 0)
		{
			if (v[i] != a)
				result += 1;
		}
		else if (i % 2 == 1)
		{
			if (v[i] != b)
				result += 1;
		}
	}

	return result;
}

int main() {
	int A, B;
	cin >> A >> B;
	cout << (A * B) << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  string S;
  cin >> S;
  int N = S.length();
  ll ans = 0;
  for (int i = 1; i < N; i++) {
    if (S[i] != S[i - 1]) ans++;
  }
  cout << ans << endl;
}

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

using namespace std;

typedef long long ll;

const int MAX_N = 303;
const ll MOD = 1e9 + 7;

int N, M, K, A[MAX_N * 2], Ar[MAX_N * 2], events[MAX_N * 2];
ll F[MAX_N * 2][MAX_N * 2][MAX_N];

int main() {
    scanf("%d", &N);
    for (int i = 0; i < 2 * N; i++) Ar[i] = -1;
    for (int i = 0; i < 2 * N; i++) {
        scanf("%d", &A[i]);
        if (A[i] != -1) Ar[--A[i]] = i;
    }
    for (int i = 0; i < 2 * N; i++) {
        if (Ar[i] == -1) {
            events[++M] = 1;
        } else if (A[Ar[i] ^ 1] == -1) {
            events[++M] = -1;
        }
    }
    for (int i = 0; i < 2 * N; i += 2)
        if (A[i] == -1 && A[i + 1] == -1) K++;
    F[M][0][0] = 1;
    int item = 0, slot = 0;
    for (int i = M; i; i--) {
        for (int j = 0; j <= item; j++) {
            for (int k = 0; k <= K; k++) {
                if (events[i] == -1) {
                    (F[i - 1][j][k] += F[i][j][k]) %= MOD;
                    if (j) {
                        (F[i - 1][j - 1][k] += F[i][j][k]) %= MOD;
                    }
                } else {
                    int used = j + 2 * k;
                    if (used > item) continue;
                    int cnt = slot - (item - used);
                    if (cnt < 0) continue;
                    (F[i - 1][j + 1][k] += F[i][j][k]) %= MOD;
                    if (cnt) {
                        (F[i - 1][j][k] += F[i][j][k] * cnt) %= MOD;
                    }
                    if (j && k < K) {
                        (F[i - 1][j - 1][k + 1] += F[i][j][k] * (K - k)) %= MOD;
                    }
                }
            }
        }
        if (events[i] == -1) slot++;
        else item++;
    }
    ll ans = F[0][0][K];
    printf("%lld\n", ans);
}


Measured memory_bytes: 862464
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ll n;
	cin >> n;
	++n;
	vector<ll> a(n);
	for (ll i = 0; i < n; ++i)cin >> a[i];
	ll sum = accumulate(a.begin(), a.end(), 0ll);
	ll ans = 1;
	ll left = 1;
	if (n == 1) {
		if (a[0] == 1) {
			cout << 1 << endl;
		}
		else {
			cout << -1 << endl;
		}
		return 0;
	}
	if (a[0] != 0) {
		cout << -1 << endl;
		return 0;
	}
	if (sum <= 2) {
		for (ll i = 0; i < n; ++i) {
			ans += a[i] * i;
		}
		cout << ans << endl;
		return 0;
	}
	ans = 1;
	left = 1;
	for (ll i = 1; i < n; ++i) {
		left *= 2;
		if (sum <= left) {
			for (ll j = 0; i + j < n; ++j) {
				ans += a[i + j] * (j + 1);
			}
			cout << ans << endl;
			return 0;
		}
		else {
			ans += left;
			left -= a[i];
			sum -= a[i];
			if (left < 0) {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	cout << -1 << endl;
}


Measured memory_bytes: 4052
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    int[] buf = new int[3];

    for ( int i = 0; i < buf.length; i++ ) {
      buf[i] = num % 10;
      num /= 10;
    }
    for ( int b : buf ) {
      if ( b == 7 ) {
        System.out.println("Yes");
        System.exit(0);
      }
    }
    System.out.println("No");
  }
}


Measured memory_bytes: 35848
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
inline int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
    int x;
    scanf("%d",&x);
    printf("%d\n",360/gcd(x,360));
    return 0;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef tuple<ll, ll, ll> ti;
 
#define REP(a,b,c) for(ll a=(b);a<(c);a++)
#define PER(a,b,c) for(ll a=(b);a>=(c);a--)

ll ii(){ ll x; cin >> x; return x; }
string is(){ string x; cin >> x; return x; }
void oi(ll x){ cout << x; }
void od(ld x){ cout << fixed << setprecision(10) << x; }
void os(string x){ cout << x; }
void oie(ll x){ cout << x << endl; }
void ode(ld x){ cout << fixed << setprecision(10) << x << endl; }
void ose(string x){ cout << x << endl; }
void oe(){ cout << endl; }

int main(){
    ll N=ii();
    ll M=ii();
    vector<ll> a;
    REP(i,0,M) a.push_back(ii());
    ll s=accumulate(a.begin(), a.end(), 0LL);
    if(s>N){
        oie(-1);
    }else{
        oie(N-s);
    }

    return 0;
}


Measured memory_bytes: 3720
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<sstream>
using namespace std;
int inf = 1000000000;

int f(int a){
  if( a == 2 ) return 1;
  else if( a == 4 || a == 6 || a == 9 || a == 11 ) return 2;
  else return 3;
}

int main(){

  int x, y;
  cin >> x >> y;
  if( f(x) == f(y) ) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}



//


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Measured memory_bytes: 82456
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first

int main()
{
    int n,ans=0;
    cin>>n;

    ll arr[n];

    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        ans=ans^arr[i];
    }

    for(int i=0;i<n;i++)
    {
        int b=ans^arr[i];
        cout<<b<<" ";
    }

    return 0;
}


Measured memory_bytes: 5184
#include<iostream>
#include<cstdlib>

using namespace std;

int h[112345];
int dp[112345];
int INF = 1e9;

int N,K;
int main () {
    cin >> N >> K;
    for(int i=0; i<N; i++) dp[i] = INF;
    for(int i=0; i<N; i++) cin >> h[i];
    dp[0] = 0;
    for(int i=0; i<N; i++) {
        for(int j=1; j<=K; j++) {
            if(i+j >= N ) continue;
            dp[i+j] = min( dp[i+j], dp[i] + abs(h[i+j] - h[i]));
        }
    }
    cout << dp[N-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>

typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	int n;
	cin >> n;
	n %= 10;
	if (n == 3) {
		cout << "bon";
	} else if ((n < 2) || (n == 6) || (n == 8)) {
		cout << "pon";
	} else {
		cout << "hon";
	}


	return 0;
}


Measured memory_bytes: 3644
N = int(input())
Score = [0] + [int(input()) for _ in range(N)]
Score.sort()
ans = sum(Score)
flag = True
for s in Score:
    ans -= s
    if ans % 10 != 0:
        flag = False
        break
    else:
        ans += s

if flag:
    print(0)
else:
    print(ans)

Measured memory_bytes: 62560
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int N;
  cin >> N;

  pair<pair<string, int>, int> SPN[N];  //市名、点数、番号
  rep(i,N){
    string S; int P;
    cin >> S >> P;
    SPN[i] = make_pair(make_pair(S, - P), i);
  }

  sort(SPN, SPN + N);

  rep(i,N){
    cout << SPN[i].second + 1 << endl;
  }
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int mn = 0;
    int mx = 0;
    int cnt[9];
    for (int i = 0; i < 9; i++) {
        cnt[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < 9; j++) {
            if (a[i] < 400 * j) {
                cnt[j - 1]++;
                break;
            }
            if (j == 8) {
                cnt[j]++;
            }
        }
    }
    for (int i = 0; i < 8; i++) {
        if (cnt[i] > 0) {
            mn++;
            mx++;
        }
    }
    if (mn == 0) {
        mn++;
    }
    mx += cnt[8];
    cout << mn << " " << mx << endl;
    return 0;
}


Measured memory_bytes: 256