akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

int V;
int E;
bool connect[55][55];
bool visited[55];

void dfs(int v) {
    visited[v] = true;
    rep(i,V) {
        if(!connect[v][i]) continue;
        if(visited[i]) continue;
        dfs(i);
    }
    return ;
}

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

    cin >> V >> E;
    int a[55], b[55];
    rep(i,E) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }

    memset(connect, false, sizeof(connect));
    memset(visited, false, sizeof(visited));
    rep(i,E) connect[ a[i] ][ b[i] ] = connect[ b[i] ][ a[i] ] = true;


    int ans = 0;
    rep(i,E) {
        connect[ a[i] ][ b[i] ] = connect[ b[i] ][ a[i] ] = false;
        dfs(0);
        bool check = true;
        rep(j,V) if(!visited[j]) {check = false; break;}
        if(!check) ans++;
        connect[ a[i] ][ b[i] ] = connect[ b[i] ][ a[i] ] = true;
        memset(visited, false, sizeof(visited));
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
/* {{{ */
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */

fn main() {
    input! {
        a: u32,
        b: u32
    }
    let min = std::cmp::min(a,b);
    let max = std::cmp::max(a,b);
    for _ in 0..max {
        print!("{}", min);
    }
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 4352
from sys import stdin
import collections

N=int(input())
xlist=[]
ylist=[]
for i in range(N):
  x, y = map(int, stdin.readline().rstrip().split())
  xlist.append(x)
  ylist.append(y)

tupleList=[]
for i in range(N):
  for j in range(N):
    if i != j:
      tupleList.append((xlist[i] - xlist[j], ylist[i] - ylist[j]))

c = collections.Counter(tupleList)

maxNum=0
for val in c.values():
  maxNum = max(maxNum, val)

print(N-maxNum)


Measured memory_bytes: 39536
#!/usr/bin/env python3

def solve(N, K, A):
    ind = []
    tr = None
    visited = set()
    cur = 1
    while cur not in visited:
        ind.append(cur)
        visited.add(cur)
        cur = A[cur-1]
    tr = cur
    itr = ind.index(tr)
    if len(ind) > K:
        return ind[K]
    KK = K - itr
    iind = ind[itr:]
    return iind[KK%len(iind)]

        


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    print(solve(N, K, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


Measured memory_bytes: 32640
#include <bits/stdc++.h>
#define ll long long
#define pq priority_queue
using namespace std;
const ll INF=(ll)1e9;
const ll MOD=(ll)1e9+7;
const ll MAX=510000;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
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; }

int main(){
    ll N,M,ans=0;
    cin>>N>>M;
    ll A[N+1];
    A[0]=0;
    for(ll i=1;i<=N;i++){
        cin>>A[i];
        A[i]+=A[i-1];
    }
    map<ll,ll> m;
    for(ll i=0;i<=N;i++){
        A[i]%=M;
        m[A[i]]++;
    }
    for(auto a:m) ans+=a.second*(a.second-1)/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 4992
package main

import "fmt"

func main() {

  var n int
  fmt.Scan(&n)
  list := make([]int,n)
  for i := 0 ; i< n; i++ {
    fmt.Scan(&list[i])
  }
  
  var max = list[0]
  var count = 1
  for i:= 1; i< n; i++ {
    if list[i] >= max {
      max = list[i]
      count ++;
    }  
  }
  fmt.Print(count)
  
}



Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>

using namespace std;
int main (){
    int h,w;
    cin >> h >> w ;
    vector<string> s(h);
    for (int i = 0; i < h; i++){
        cin >> s[i];
    }
    for (int i = 0; i < w+2; i++){
        cout << "#";
    }
    cout << "\n";
    for (int i = 0; i < h; i++){
        cout << "#" << s[i] << "#\n";
    }
    for (int i = 0; i < w+2; i++){
        cout << "#";
    }
    cout << "\n";

}

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


def solve(N: int, S: str):
    ret = 0
    cur = 0
    for c in S:
        if c == 'I':
            cur += 1
            ret = max(ret, cur)
        else:
            cur -= 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::fixed;
using std::pair;
using std::make_pair;
using std::string;
using std::vector;
using std::list;
using std::map;
using std::set; // insert erase find count
using std::queue;
using std::priority_queue;
using std::stack;

typedef vector<int> VI;
typedef vector<vector<int> > VII;
typedef vector<string> VS;
typedef pair<int, int> PII;

bool suffix_check(string s) {
    int length = s.length();
    bool ret;
    if (s[length - 4] == 'w') {
        ret = true;
    } else if (s[length - 4] == 'o') {
        ret = false;
    }
    return ret;
}

void delete_string(string &s) {
    int length = s.length();
    if (length >= 8) {
        if (suffix_check(s) == true) {
            s = s.substr(0, length - 4); 
        } else if (suffix_check(s) == false) {
            s = s.substr(0, length - 5); 
        }
    } else if (length <= 5) {
        s = "";    
    }
    return;
}

int main(void) {
    string s;
    while (1) {
        cin >> s;
        if (s == "#") {
            break;
        }

        int a;
        if (suffix_check(s) == true) {
            a = 90;
        } else if (suffix_check(s) == false) {
            a = 0;
        }
        delete_string(s);
        int digit = 1;

        while (1) {
            if (s == "") {
                while (a % 2 == 0 && digit % 2 == 0) {
                    a /= 2;
                    digit /= 2;
                }
                if (digit != 1) {
                    cout << a << '/' << digit << endl;
                } else {
                    cout << a << endl;
                }
                break; 
            }
            digit *= 2;
            if (suffix_check(s) == true) {
                a = a * 2 + 90;
            } else if (suffix_check(s) == false) {
                a = a * 2 - 90;
            }
            delete_string(s);

        }
    }
    return 0;
}

Measured memory_bytes: 3212
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.replace(/\n$/,"")).split("\n");
while(true){
   var n=Arr.shift()-0;
   if(n===0)break;
   var m=Arr.shift()-0;
   var str=Arr.shift();
   var s="IOI";
   var flag=true;
   while(n!==1){
      s+="OI";
      n--;
   }
   var cnt=0;
   for(var i=0;i<m-s.length;i++){
      if(str.slice(i,i+s.length)==s)cnt++;
   }
   console.log(cnt);
}

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

int main()
{
    long long int a[200],n,i,flag=0,sum=0;
    scanf("%lld",&n);
    for(i=0;i<n;i++)
        scanf("%lld",&a[i]);
    while(flag==0)
    {
        for(i=0;i<n;i++)
        {
            if(a[i]%2!=0)
            {
                printf("%lld",sum);
                exit(0);
            }
        }
        for(i=0;i<n;i++)
        {
            a[i]=a[i]/2;
        }
        sum++;
    }
    printf("%lld",sum);
    return 0;
}

Measured memory_bytes: 128
import Control.Monad
main = do
  [h, w] <- fmap (map read . words) getLine :: IO [Int]
  if [h, w] == [0, 0] then
    return ()
  else do
    replicateM h $ (replicateM w (putStr "#") >> putStrLn "")
    putStrLn ""
    main

Measured memory_bytes: 3996
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	int n;lint d,c,ds=0,cs=0;
	cin>>n;
	rep(i,n){
		cin>>d>>c;ds+=c;cs+=d*c;
	}
	cout<<ds-1+(cs-1)/9<<endl;
}


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

using namespace std;

const int N=110;

int n,a[N],b[N];

int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]),b[a[i]]++;
  sort(a+1,a+1+n); int d=a[1];
  if(b[d]==1){
    int s=1;
    for(int i=d+1;i<=d+d;i++)
      if(b[i]<2){ s=0; break; }
    for(int i=1;i<=n;i++)
      if(a[i]>d+d) s=0;
    puts((s && b[d]<=2)?"Possible":"Impossible");
  }
  else{
    int s=1;
    for(int i=d+1;i<d+d;i++)
      if(b[i]<2){ s=0; break; }
    for(int i=1;i<=n;i++)
      if(a[i]>=d+d) s=0;
    puts((s && b[d]<=2)?"Possible":"Impossible");
  }
  return 0;
}


Measured memory_bytes: 256
public class Hello{
    public static void Main(){
        
        string line1 = System.Console.ReadLine();
        string line2 = System.Console.ReadLine();
        
        string line2buf = line2.Substring(0,line1.Length);
        
        string result = "No";
        if(line1 == line2buf)
        {
            result = "Yes";
        }
        
        System.Console.WriteLine(result);
    }
}


Measured memory_bytes: 25796
while 1:
    n,w,d = map(int,raw_input().split())
    if w == 0: break
    cake = [[w,d]]
    for loop in xrange(n):
        p,s = map(int,raw_input().split())
        x,y = cake.pop(p-1)
        s %= (x+y)
        if s < x:
            x1,x2 = sorted([s,x-s])
            cake += [[x1,y],[x2,y]]
        else:
            s -= x
            y1,y2 = sorted([s,y-s])
            cake += [[x,y1],[x,y2]]
    print " ".join(map(str,sorted([x*y for x,y in cake])))

Measured memory_bytes: 4240
from heapq import heappop, heappush, heapify
N = int(input())
a = list(map(int, input().split()))

pq1 = a[:N]
pq2 = [-x for x in a[2 * N:]]

heapify(pq1)
heapify(pq2)

s1 = sum(pq1)
s2 = sum(pq2)

ans1 = [s1]
ans2 = [s2]

for k in range(N, 2 * N):
    heappush(pq1, a[k])
    x = heappop(pq1)
    s1 += a[k] - x
    ans1.append(s1)
    
    heappush(pq2, -a[3 * N - k - 1])
    x = heappop(pq2)
    s2 += -a[3 * N - k - 1] - x
    ans2.append(s2)
    
print(max(ans1[i] + ans2[-i - 1] for i in range(len(ans1))))


Measured memory_bytes: 120848
#include <bits/stdc++.h>
#define tt this->
#define ll long long
using namespace std;
int main ()
{
int h,a,c=0;
cin>>h>>a;
while (h>0)
{
    c++;
    h=h-a;
}
cout<<c;

    return 0;
}

/*
▀█████████▄     ▄████████    ▄████████    ▄████████
  ███    ███   ███    ███   ███    ███   ███    ███
  ███    ███   ███    ███   ███    ███   ███    ███
 ▄███▄▄▄██▀    ███    ███  ▄███▄▄▄▄██▀   ███    ███
▀▀███▀▀▀██▄  ▀███████████ ▀▀███▀▀▀▀▀   ▀███████████
  ███    ██▄   ███    ███ ▀███████████   ███    ███
  ███    ███   ███    ███   ███    ███   ███    ███
▄█████████▀    ███    █▀    ███    ███   ███    █▀
                            ███    ███

*/


Measured memory_bytes: 3624
S = input()

Aflag = False
Cflag = False
smallflag=False
length = len(S)

for i,a in enumerate(S):
    if i==0 and a=='A':
        Aflag = True
    elif 2<=i<=length-2 and a=='C' and Cflag == False:
        Cflag = True
    elif not a.islower():
        smallflag = True

if Aflag and Cflag and (not smallflag):
    print('AC')
else:
    print('WA')


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

int main(){
  int L, A, B, C, D;
  
  cin >> L >> A >> B >> C >> D;
  
  int t;
  int a, b;
  a = A / C;
  if(A%C != 0) a++;
  b = B / D;
  if(B%D != 0) b++;
  t = max(a, b);
  cout << L-t << endl;
  return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>
#include <cctype>
#include <climits>
#include <list>
#include <queue>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int x,a,b; cin>>x>>a>>b;
  cout << (x - a) % b << endl;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()

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

    int ans = (N*(N-1))/2 + (M*(M-1))/2;
    cout << ans << endl;

}



Measured memory_bytes: 256
N = int(input())
A = [0] + [int(x) for x in input().split()] + [0]

Y = []
for i in range(N+1):
    Y.append(abs(A[i+1]-A[i]))
SUM = sum(Y)

for i in range(1, N+1):
    ans = SUM - (Y[i-1] + Y[i]) + abs(A[i+1] - A[i-1])
    print(ans)

Measured memory_bytes: 14176
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main(){
    string a, b,c;
    cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0])
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    
    
 }

Measured memory_bytes: 256
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=3007;

int n;

double dp[nax][nax];

int main()
{
	scanf("%d", &n);
	dp[0][0]=1;
	for (int i=1; i<=n; i++)
	{
		double x;
		scanf("%lf", &x);
		for (int j=0; j<i; j++)
		{
			dp[i][j]+=dp[i-1][j]*(1-x);
			dp[i][j+1]+=dp[i-1][j]*x;
		}
	}
	double wyn=0;
	for (int i=0; i<=n; i++)
		if (i>n-i)
			wyn+=dp[n][i];
	printf("%.11lf\n", wyn);
	return 0;
}


Measured memory_bytes: 69120
//??¶??´???3s   ?????´???256MB
//?¢????:???????????????,????±????1??°n?????°????????????,???????????????????????\????????????
//????????\??????????????????????°?
//??????:dp
//??¶???:???????????????i 
//??¶???:dp[i]??¨???1~n?????????????§£
//??????:dp[i]=value(allson)
//??¨??¬?§???¶,?????????????????????????????\????????????????????????,??±?????????????????°
//???????°?,?????\?????\?????¨????????¶????????¶?????????
//??\????????????????????????i??????????§£,???????????????????????\?????? 
#include<cstdio> 
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
vector<int>G[45];
map<ll,bool>visit;
int dp[45],a[45];
int n,m;
void add(ll & x,int w){
	x|=(1LL<<w);
}
int update(ll x){
	int sum=0;
	for(int i=1;i<=n;i++)
		if(x&(1LL<<i))sum+=a[i];
	return sum;
}
void dfs(int u,ll now){	
	visit[now]=true;//????????¶????????°???,??????????¬??????? 
//	cout<<now<<endl;
	int lena=G[u].size();
	for(int i=0;i<lena;i++){
		ll tmp=now;
		int v=G[u][i];
		int lenb=G[v].size();
		for(int j=0;j<lenb;j++){
			int w=G[v][j];
			add(tmp,w);
		}
		add(tmp,v);
		int tot=update(tmp);
		if(tot<=dp[v]){
			dp[v]=tot;
			if(visit[tmp])continue;
			dfs(v,tmp);
		}
	}
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=1;j<=m;j++){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	memset(dp,127,sizeof(dp));
	G[0].push_back(1);
	dfs(0,0);
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 3308
H,W = gets.split.map(&:to_i)
M = (0...H).map{ gets.split("") }
puts (0...H).all?{ |i|
  (0...W).all? { |j|
    next true if M[i][j] != "#"
    dr = (i < H-1 && M[i+1][j] == "#" ? 1 : 0) + (j < W-1 && M[i][j+1] == "#" ? 1 : 0) == 1
    ul = (i > 0 && M[i-1][j] == "#" ? 1 : 0) + (j > 0 && M[i][j-1] == "#" ? 1 : 0) == 1
    ([i,j] == [H-1,W-1] || dr) && ([i,j] == [0,0] || ul)
  }
} ? "Possible" : "Impossible"

Measured memory_bytes: 3836
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> adj[100002];

bool visited[100002];
ll dp[100002];

void initialize() 
{
        for(ll i = 0;i <100002;++i)
         {
		 visited[i] = false;
		 }
}

ll dfs(ll i)
{
	visited[i]=true;
	
	if(adj[i].size()==0)
	return dp[i]=0;
	
	ll c=INT_MIN;
	
	for(auto j : adj[i])
	{
		if(visited[j]==false)
		{
			c=max(c,dfs(j));
		}
		else
		{
			c=max(c,dp[j]);
		}
	}
	
	return dp[i]=1+c;
}



int main()
{
	ll N,M;
	cin>>N>>M;
	
	ll x,y;

for(ll i=0;i<M;i++)
{
		cin>>x; cin>>y;
		adj[x].push_back(y);
}
	
initialize();
	

for(ll i=1;i<=N;i++)
{
	dfs(i);
}
	
ll ans=-1;

for(ll i=1;i<=N;i++)
{
	if(dp[i]>ans)
	{
		ans=dp[i];
	}
}
cout<<ans<<endl;

}





Measured memory_bytes: 8704
a = []
while True:
    try:
        n = str(input())
    except EOFError:
        break
    b = n.lower()
    a.append(b)

c = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
d = ''.join(a)
for i in range(0,26):
    print('{} : {}'.format(c[i],d.count(c[i])))


Measured memory_bytes: 5568
import numpy as np


def main():
    N = int(input())
    d = np.array([int(a) for a in input().split(" ")])
    s = np.sum(d)
    s2 = np.sum(d * d)
    print(int((s * s - s2) / 2))


if(__name__ == "__main__"):
    main()


Measured memory_bytes: 14288
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;

int main(){
	IOS;
	int n,a,b;
	cin >> n >> a >> b;
	int ans=0;
	for(int i=1;i<=n;i++){
		int cal=i,tmp=0;
		while(cal>0){
			tmp+=cal%10;
			cal/=10;
		}
		if(a<=tmp && tmp<=b) ans+=i;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 256
def f(n):
    cnt = 1
    while n > 0:
        n  %= bin(n).count('1')
        cnt += 1
    return cnt

if __name__ == "__main__":
    n = int(input())
    x = input()
    d = x.count('1')
    if d == 1:
        for i in x[:-1]:
            if i == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    ans = []
    M = 0
    for i in x:
        M <<= 1
        if i == '1':
            M += 1
    p = M % (d + 1)
    m = M % (d - 1)
    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, d + 1)) % (d + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, d - 1)) % (d - 1)))
    print(*ans, sep='\n')


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

using namespace std;

const int A = 100000;

int kk[A + 1];

int main() {
	int n; cin >> n;
	long long x = 0;
	while (n--) {
		int a; cin >> a;
		x += a;
		kk[a]++;
	}
	int q; cin >> q;
	while (q--) {
		int b, c; cin >> b >> c;
		cout << (x += (c - b) * kk[b]) << '\n';
		kk[c] += kk[b];
		kk[b] = 0;
	}
	return 0;
}


Measured memory_bytes: 4024
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
ld EPS = 1e-12;
int INF = numeric_limits<int>::max() / 2;
int MOD = 1e9 + 7;

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

  int k, n;
  cin >> n >> k;

  ll num = n/k;

  if(k%2 == 1){
    cout << num * num * num << '\n';
    return 0;
  }else{
    ll numm = (n + k/2) / k;
    cout << num * num * num + numm * numm * numm << '\n';
    return 0;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[110],w[110],dp[100010],n,k,ans=-1,maxw=0;
/*void dq(int i,long long cost,long long weight){
    cout<<i<<" "<<cost<<" "<<weight<<endl;
    if(weight>k)return ;
    ans=max(ans,cost);
    for(;i<n;i++)
        dq(i+1,cost+w[i+1],weight+a[i+1]);
}*/
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){cin>>a[i]>>w[i];maxw+=w[i];}
    fill(dp,dp+100005,10000000000000);
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=maxw;j>=0;j--){
            if(j-w[i]>=0)dp[j]=min(dp[j-w[i]]+a[i],dp[j]);
        }
    for(int i=maxw;i>=0;i--)if(dp[i]<=k){cout<<i;return;}
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    //freopen("FORM MAU.inp","r",stdin);
    //freopen("FORM MAU.out","w",stdout);

    //srand(time(0));

    //int t;cin>>t;while(t--)
    //cout << setprecision(2) <<fixed;
    solve();
}

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

int main(){
	int n, m;
	cin >> n >> m;

	ll ans = 0;

	vector<ll> kaijo = {1};

	for(ll i = 1; i <= max(n, m); i++)
	{
		kaijo.push_back(kaijo[i-1] * i % (ll)(1e9+7));
	}
	
	if(n==m){
		ans = kaijo[n]*kaijo[m]*2 % (ll)(1e9+7);
	}else if(n+1==m || n==m+1){
		ans = kaijo[n]*kaijo[m] % (ll)(1e9+7);
	}

	cout << ans << endl;

	return 0;
}

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

long long int N, a;
vector<long long> A, L, S;

int main(){
    cin >> N;
    for(int i = 0; i < N; ++i){
        cin >> a;
        A.push_back(a);
    }
    sort(A.begin(), A.end());
    for(int i = 0; i < N; ++i){
        (2 * i < N ? S : L).push_back(A[i]);
    }
    if(N & 1){
        cout << 2 * accumulate(L.begin(), L.end(), 0LL) + max(*S.rbegin() - *L.begin(), *(S.rbegin() + 1) - *S.rbegin()) - 2 * accumulate(S.begin(), S.end() - 1, 0LL) << endl;
    }else{
        cout << 2 * accumulate(L.begin(), L.end(), 0LL) - *L.begin() + *S.rbegin() - 2 * accumulate(S.begin(), S.end(), 0LL) << endl;
    }
}


Measured memory_bytes: 2292
N, T = list(map(int, input().split()))
pairs = []
for i in range(N):
  c, t = list(map(int, input().split()))
  if t<=T:
    pairs.append((c, t))
if len(pairs)==0:
  print('TLE')
else:
  print(sorted(pairs, key=lambda p:p[0])[0][0])

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
using pii = pair<int, int>;
using vi = vector<int>;
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
//manip
template<class T> bool chmax(T &a, T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, T &b) {if (a > b) {a = b; return 1;} return 0;}
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b)
{return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
//output
#define out(a) cout << a << endl
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl
#define outp(v) rep(i, SZ(v)) cout << v[i].F << " " << v[i].S << endl
#define outc(s, t) cout << fixed << setprecision(10) << (double)(t - s) / CLOCKS_PER_SEC << endl
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
#define brep(i, n) for (int i = n - 1; i >= 0; --i)
//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0

int main() {
    //cast caution
    //look constraints always
    cin.tie(0); ios::sync_with_stdio(false);
    
    
    
    int n, x; cin >> n >> x;
    int d = 0;
    int c = 1;
    rep(i, n) {
        int l; cin >> l;
        d += l;
        if (d <= x) c++;
    }
    cout << c << endl;
    
    
    
}
//cast caution




Measured memory_bytes: 256
n = gets.to_i

a = 0
count = 0

(1..n).each do |a| # each do で数を取り出す
  if a.odd?  # が奇数の時trueを返す→カウントを足す
    count += 1
  end
end
  
puts count / n.to_f 
  # to_f で小数点以下を表示

Measured memory_bytes: 2044
#include<cstdio>



int main(){
     int n,a,b,c,d;
     while(~scanf("%d",&n)){
     a=n/1000;
     b=(n/100)%10;
     c=(n%100)/10;
     d=n%10;
	if(a==b&&b==c||b==c&&c==d||a==b&&b==c&&c==d)
     	 printf("Yes\n");
     else
     	 	 printf("No\n");
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;

int main(){
    int N,K;
    cin >> N >> K;
    int B[N];
    for(int i = 0; i < N; i++) B[i]=0;
    int d[K];
    for(int i = 0; i < K; i++){
        cin >> d[i];
        int A[d[i]];
        for(int j = 0; j < d[i]; j++){
            cin >> A[j];
            B[A[j]-1] += 1;
        }
    }
    int count = 0;
    for(int i = 0; i < N; i++){
        if(B[i]==0) count += 1;
    }
    cout << count << endl;
}

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

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a==b&&b!=c){
    cout<<"Yes"<<endl;
  }else if(b==c&&a!=c){
    cout<<"Yes"<<endl;
  }else if(a==c&&b!=c){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3532
import java.util.Scanner;
import java.util.stream.Stream;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str  = sc.nextLine();
        String[] astr = str.split(""); //状況に合わせて
        sc.close();

        Arrays.sort(astr);

        if(astr[0].equals(astr[1]) && !astr[1].equals(astr[2]) && astr[2].equals(astr[3])){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 22608
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define elif(a) else if(a)
#define INF INT_MAX
#define F first
#define S second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c;
  cin>>a>>b>>c;
  if(a==1 && b==1 || c==1){
    cout<<"Open"<<endl;
  }else{
    cout<<"Close"<<endl;
  }
  return 0;
}




Measured memory_bytes: 3212
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

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

    vector<int> h;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >>tmp;
        h.push_back(tmp);
    }

    sort(h.begin(), h.end());
    int ans = INT_MAX;
    for(int i = 0; i+k-1 < n; i++){
        ans = min(ans, h[i+k-1] - h[i]);
    }
    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 892
#include <iostream>

using namespace std;

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

    bool flag = false;
    for (int i = 1; i < 10; i++) {
        for (int j = i; j < 10; j++) {
            if (i * j == N) {
                flag = true;
                break;
            }
        }
        if (flag) break;
    }

    cout << (flag ? "Yes" : "No") << endl;
}

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

int main() {
	string s;
	cin >> s;
	int ans = 0;
	rep(i, 3) if (s[i] == '1') ans++;
	cout << ans << endl;
}

Measured memory_bytes: 256
A, B, C, D, E, F = map(int, input().split())
Swater, sugar, percent = 100*A, 0, 0
for k in range(F//(100*A) + 1):
  for l in range(F//(100*B) + 1):
    if k == 0 and l == 0:
      continue
    M = k*A + l*B
    if 100 * M > F:
      continue
    for x in range(M*E//C + 1):
      for y in range(M*E//D + 1):
        S = C*x + D*y
        if 100*M+S > F:
          continue
        if S > M*E:
          continue
        t = 100*S / (100*M+S)
        if t > percent:
          percent = t
          Swater = 100*M+S
          sugar = S
print(Swater, sugar)

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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

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




/*
・とざんくん
Bの要素より小さいAの要素を小さくする。
・げざんくん
Aの要素より大きいBのを小さくする
つまり、Bの要素だけ必要

もしAの要素の方がBの要素より大きいものがある時：最後にAの方が大きい要素の中で一番小さい要素のみが残る
*/

int n;
ll sum = 0;
ll mi = 1e11;
ll ans = 0;

int main(){
  cin >> n;
  REP(i,n){
    ll a,b;
    cin >> a>> b;
    sum += a;
    if(a <= b) ans += b;
    else{
      mi = min(mi,b);
    }
  }
  if(mi == 1e11){
    cout << 0 << endl;
    return 0;
  }
  cout << sum - mi <<endl;
}





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

class P
{
    static void Main()
    {
        //int[] N = Console.ReadLine().Split().Select(int.Parse).ToArray();
        string s = Console.ReadLine();
        for (int i = 2; i < s.Length; i += 2)
        {
            string subs = s.Substring(0, s.Length - i);
            if (subs.Substring(0,subs.Length / 2) == subs.Substring(subs.Length / 2, subs.Length / 2))
            {
                Console.WriteLine(subs.Length);
                return;
            }
        }
    }
}

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

int main() {
  unsigned int n;
  std::cin >> n;
  std::vector<unsigned int> A(n);
  for (size_t i = 0; i < n; ++i) {
    std::cin >> A.at(i);
  }

  std::sort(A.begin(), A.end());
  while (true) {
    const unsigned int min = A.at(0);
    for (size_t i = 1; i < A.size(); ++i) {
      A.at(i) = A.at(i) % min;
    }

    A.erase(std::remove(A.begin(), A.end(), 0), A.end());

    std::sort(A.begin(), A.end());
    if (A.at(0) == min) {
      break;
    }
  }

  std::cout << A.at(0) << std::endl;
  return 0;
}


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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RREP(i, a, b) for (int i = (int)(a)-1; i >= (int)(b); --i)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)
#define ALL(r) (r).begin(), (r).end()

void Main();

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

void Main() {
    int n; cin >> n;
    vector<int64_t> l(n);
    rep(i, n) cin >> l[i];
    sort(ALL(l));
    int64_t x = 0;
    REP(i, 0, n-2) {
        REP(j, i+1, n-1) {
            REP(k, j+1, n) {
                if (l[i] != l[j] && l[j] != l[k] && l[i] + l[j] > l[k]) {
                    x++;
                }
            }
        }
    }
    cout << x << endl;
}


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

int main() {
  int N;
  cin >> N;
  
  bool flg = false;
  for (int i = 0; i <= N / 4; i++){
    for (int j = 0 ; j <= N / 7; j++){
      if ( 4 * i + 7 * j == N) {
      flg = true;
      break;
    }
  }
  }
  if(flg) cout << "Yes";
  else cout << "No";
}

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


#include "boost/multiprecision/cpp_int.hpp"
#include "boost/multiprecision/cpp_dec_float.hpp"
namespace mp = boost::multiprecision;
typedef mp::cpp_int LL;
typedef mp::number<mp::cpp_dec_float<1024>> DD;// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)

 
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define rrep(i,r,l) for(ll i=r;i>=l;i--)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
template<class T,class S>
inline bool chmax(T &a, S b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T,class S>
inline bool chmin(T &a, S b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

void mod_print(ll k){
    ll P=1000;
    rep(y,1,P){
        ll x=mod(y*k);
        if(x+P>=i_7){
            x-=i_7;
        }
        if(abs(x)<=P){
            //cout<<x<<"/"<<y;
            cout<<setprecision(5)<<(dd)x/(dd)y;
            return;
        }
    }
    cout<<"nun"<<endl;
}
#define all(c) c.begin(),c.end()
//////////////////////////


struct item{
    ll l,r,num;
};

int main(){fastio
    
    ll n;cin>>n;
    bool f[n];memset(f,0,sizeof(f));
    item a[n],b[n];
    rep(i,0,n-1){
        cin>>a[i].l>>a[i].r;
        a[i].num=i;
        b[i]=a[i];
    }
    sort(a,a+n,[](item x,item y){
        return x.l>y.l;
    });
    sort(b,b+n,[](item x,item y){
        return x.r<y.r;
    });
    ll ans=0;
    ll sum=0;
    rep(i,0,n-1){
        if(f[a[i].num])break;
        sum+=a[i].l*2;
        f[a[i].num]=0;
        chmax(ans,sum);
        if(f[b[i].num])break;
        sum+=-b[i].r*2;
        f[b[i].num]=0;
        chmax(ans,sum);
    }
    sum=0;
    memset(f,0,sizeof(f));
    rep(i,0,n-1){
        if(f[b[i].num])break;
        sum+=-b[i].r*2;
        f[b[i].num]=0;
        chmax(ans,sum);
        if(f[a[i].num])break;
        sum+=a[i].l*2;
        f[a[i].num]=0;
        chmax(ans,sum);
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

#define MAX_N (50)
#define INF (1000000000)

using namespace std;

int calc_s(int nds[13], int ps[13]) {
  int ret;
  vector<int> ts;
  for (int d = 0; d < 13; d++) {
    if (nds[d] > 0) {
      if (ps[d] == 0) {
        ts.push_back(d);
        ts.push_back(24 - d);
      } else if (ps[d] > 0) {
        ts.push_back(d);
      } else {
        ts.push_back(24 - d);
      }
    }
  }
  sort(ts.begin(), ts.end());
  // for (int d = 0; d < 13; d++) {
  //   printf("d = %d, nd = %d, p = %d\n", d, nds[d], ps[d]);
  // }
  // for (int i = 0; i < ts.size(); i++) {
  //   printf("i = %d, t = %d\n", i, ts[i]);
  // }
  ret = 24 + ts[0] - ts[ts.size() - 1];
  for (int i = 1; i < ts.size(); i++) {
    ret = min(ret, ts[i] - ts[i - 1]);
  }
  // printf("ret = %d\n", ret);
  return ret;
}

int solve(int nds[13], int d, int ps[13]) {
  if (d >= 13) {
    return calc_s(nds, ps);
  }
  if (nds[d] == 0) {
    return solve(nds, d + 1, ps);
  } else if (nds[d] == 1) {
    int ret1, ret2;
    ps[d] = 1;
    ret1 = solve(nds, d + 1, ps);
    ps[d] = -1;
    ret2 = solve(nds, d + 1, ps);
    return max(ret1, ret2);
  } else {
    ps[d] = 0;
    return solve(nds, d + 1, ps);
  }
}

int main(int argc, char *argv[]) {
  // read inputs
  int n, ds[MAX_N + 1];
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &ds[i]);
  }
  ds[n] = 0;

  // count how many times each value occurs
  int nds[13] = {};
  for (int i = 0; i <= n; i++) {
    nds[ds[i]]++;
  }

  // if a value occurs more than 3 times, the answer is 0
  for (int d = 1; d < 13; d++) {
    if (nds[d] >= 3) {
      printf("0\n");
      return 0;
    }
  }
  if (nds[0] >= 2) {
    printf("0\n");
    return 0;
  }

  // NOTE : from here, each value occurs at most 2 times
  //        and the answer is not 0
  int ps[13] = {};
  printf("%d\n", solve(nds, 0, ps));

  return 0;
}


Measured memory_bytes: 256
// 2020-08-15 18:36:36
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

const int V = 100010;
vector<P> G[V]; // to, mi
vector<int> used;
int visited[V], flag[V];
bool dfs(int u) {
  for(auto& p : G[u]) {
    int v, mi;
    tie(v, mi) = p;
    if(!visited[v]) {
      visited[v] = 1;
      if(dfs(v)) {
        used.push_back(mi+1);
        flag[v] = !flag[v];
        flag[u] = !flag[u];
      }
    }
  }
  return flag[u];
}
void answer() {
  int n, m;
  cin >> n >> m;
  vector<P> xs; // x, f
  {
    vector<P> ab(n+2);
    rep(i, n) cin >> ab[i].first >> ab[i].second;
    ab[n] = P(0, 0);
    ab[n+1] = P(1e9+5, 0);
    sort(ALL(ab));
    REPC(i, 1, n+1) {
      xs.emplace_back(P(ab[i].first-1, ab[i-1].second ^ ab[i].second));
    }
  }
  rep(i, xs.size()) flag[i] = xs[i].second;
  rep(mi, m) {
    int l, r;
    cin >> l >> r;
    auto l_itr = lower_bound(ALL(xs), P(l-1, -1));
    if(l_itr == xs.end()) continue;
    auto r_itr = upper_bound(ALL(xs), P(r, -1))--;
    int li = l_itr - xs.begin();
    int ri = r_itr - xs.begin();
    if(li < ri) {
      G[li].emplace_back(P(ri, mi));
      G[ri].emplace_back(P(li, mi));
    }
  }
  rep(i, xs.size()) if(!visited[i]) {
    visited[i] = 1;
    if(dfs(i)) {
      cout << -1 << '\n';
      return;
    }
  }
  sort(ALL(used));
  cout << used.size() << '\n';
  rep(i, used.size()) {
    if(i > 0) cout << ' ';
    cout << used[i];
  }
  cout << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 20280
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {

    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static ArrayList<String> list = new ArrayList<String>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] P = new int[N];
        int[] Q = new int[N];
        for(int i=0;i<N;i++){
            P[i]=sc.nextInt();
        }
        for(int i=0;i<N;i++){
            Q[i]=sc.nextInt();
        }
        permutation(P);
        list.sort(Comparator.naturalOrder());
        System.out.println(Math.abs(list.indexOf(Arrays.toString(P))-list.indexOf(Arrays.toString(Q))));
    }

    private static void permutation(int[] seed) {
		int[] perm = new int[seed.length];
		boolean[] used = new boolean[seed.length];
		buildPerm(seed, perm, used, 0);
	}

	private static void buildPerm(int[] seed, int[] perm, boolean[] used, int index) {
		if (index == seed.length) {
			procPerm(perm);
			return;
		}
		for (int i = 0; i < seed.length; ++i) {
			if (used[i])
				continue;
			perm[index] = seed[i];
			used[i] = true;
			buildPerm(seed, perm, used, index + 1);
			used[i] = false;
		}
	}

	private static void procPerm(int[] perm) {
		list.add(Arrays.toString(perm));
	}
}


Measured memory_bytes: 38560
#include<stdio.h>
#include<string.h>

int main()
{
	char S[12];
	scanf("%s", S);
	int len = strlen(S);

	for (int i = 0; i < len-1; i++)
	{
		if (S[i] == 'A' && S[i + 1] == 'C')
		{
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#define NDEBUG

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <iostream>
using namespace std;

constexpr long long mod = 1000000007;

long long expr(string::const_reverse_iterator &it);
long long term(string::const_reverse_iterator &it);
long long number(string::const_reverse_iterator &it);

long long expr(string::const_reverse_iterator &it) {
	long long res = term(it);
	if(*it == '>') {
		++it;
		assert(*it == '>');
		++it;
		res = (expr(it) >> min(32ll, res));
	}
	return res;
}

long long term(string::const_reverse_iterator &it) {
	if(isdigit(*it)) return number(it);

	assert(*it == '>');
	++it;
	long long res = expr(it);
	assert(*it == '<');
	++it;
	assert(*it == 'S');
	++it;
	return (res * res) % mod;
}

long long number(string::const_reverse_iterator &it) {
	long long res = 0;
	for(int d = 1; isdigit(*it); d *= 10, ++it) {
		res += d * (*it - '0');
	}
	return res;
}

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

	for(string expression; getline(cin, expression) && expression != "#";) {
		expression.erase(remove(expression.begin(), expression.end(), ' '), expression.end());
		auto it = expression.crbegin();
		cout << expr(it) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 2880
#include <cstdio>
#include <queue>
#include <functional>
#include <vector>
using namespace std;
int main() {
    int n, m; scanf(" %d %d", &n, &m);
    int d[n]; for (int i = 0; i < n; i++) scanf(" %d", &d[i]);
    vector<vector<pair<int, int> > > adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; scanf(" %d %d", &u, &v);
        u--; v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    const int WMAX = 1e9;
    int w[m], col[n];
    fill(col, col+n, -1);
    fill(w, w+m, WMAX);

    vector<bool> root(n, false);
    for (int i = 0; i < n; i++) {
        bool eq = false, down = false;
        for (auto e : adj[i]) {
            const int j = e.first;
            if (d[j] < d[i]) { down = true; break; }
            else if (d[j] == d[i]) eq = true;
        }
        if (!down) {
            if (!eq) { puts("-1"); return 0; }
            else root[i] = true;
        }
    }
    function <void(int, int)> process_roots = [&](int i, int c) {
        col[i] = c;
        root[i] = true;
        for (auto e : adj[i]) {
            int j = e.first, k = e.second;
            if (d[j] == d[i] && col[j] == -1) {
                w[k] = d[i];
                process_roots(j, 1^c);
            }
        }
    };
    for (int i = 0; i < n; i++) if (root[i] && col[i] == -1) process_roots(i, 0);

    function <void(int, int)> process_tree = [&](int i, int c) {
        for (auto e : adj[i]) {
            const int j = e.first, k = e.second;
            if (d[j] > d[i] && col[j] == -1) {
                w[k] = col[i] == c ? d[j] - d[i] : d[j];
                col[j] = c;
                process_tree(j, c);
            }
        }
    };
    for (int i = 0; i < n; i++) if (root[i]) process_tree(i, 1^col[i]);

    for (int i = 0; i < n; i++) putchar(col[i] == 0 ? 'B' : 'W');
    putchar('\n');
    for (int i = 0; i < m; i++) printf("%d\n", w[i]);
}


Measured memory_bytes: 12672
/************************************************
   Start coding only after you have clear idea. 
*************************************************/

#include <bits/stdc++.h>

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxm = 2e3+23;
const int maxn = 2e5+35;
int n,a[maxn],b[maxn];
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n ; ++i) scanf("%d %d",a+i,b+i);
    sort(a+1,a+n+1); sort(b+1,b+n+1);
    if(n&1){
        cout << b[(n+1)/2]-a[(n+1)/2]+1 << endl;
    }
    else{
        cout << (b[n/2+1]+b[n/2])-(a[n/2+1]+a[n/2])+1<< endl;
    }
    return 0;
}

Measured memory_bytes: 5372