akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main(void)
{
  int a,b,k,max,ans,count,i;
  ans = 0;
  count =0;
  scanf("%d",&a);	
  scanf("%d",&b);	
  scanf("%d",&k);	
  max = a;
  if (b>a)	max = b;
  i = max;
  do {
	if (a % i==0 && b % i ==0)
		count = count + 1, ans = i;
	i = i -1;

  } while (count<k);
  printf("%d",ans);
  return 0;
}
  
  

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1);}
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
main(){
    int N,K,L;
    cin >> N >> K >> L;
    vector<int> A(K),B(K),C(L),D(L);
    rep(i,0,K){
        cin >> A[i] >> B[i];
        A[i]--,B[i]--;
    }
    rep(i,0,L){
        cin >> C[i] >> D[i];
        C[i]--,D[i]--;
    }
    UnionFind uf1(N),uf2(N);
    rep(i,0,K)uf1.merge(A[i], B[i]);
    rep(i,0,L)uf2.merge(C[i], D[i]);
    vector<int> r1(N),r2(N);
    rep(i,0,N)r1[i] = uf1.root(i);
    rep(i,0,N)r2[i] = uf2.root(i);
    map<pair<int,int>, int>mp;
    rep(i,0,N)mp[make_pair(r1[i], r2[i])]++;
    rep(i,0,N){
        cout << mp[make_pair(r1[i], r2[i])] << " \n"[i==N-1];
    }

}

Measured memory_bytes: 16640
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    vector<int>c(a);
    for (int i = 0; i < a; i++) {
        cin >> c[i];
    }
    if ((a - 1) % (b - 1) != 0) {
        cout << ((a - 1) / (b - 1)) + 1;
    }
    else {
        cout << ((a - 1) / (b - 1));
    }
}

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

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

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define zeroes(x) memset(x,0,sizeof(x))
typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =1e9+7;
const ll maxn=100000;


ll knapSack(ll W, ll wt[], ll val[], ll n) 
{ 
   ll i, w; 
   ll K[n+1][W+1]; 
  
   // Build table K[][] in bottom up manner 
   for (i = 0; i <= n; i++) 
   { 
       for (w = 0; w <= W; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
   } 
  
   return K[n][W]; 
} 
int main()
{		
	
    
    IOS
    ll n,W;
    cin>>n>>W;
    ll  a[n],v[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i]>>v[i];
    }


    cout<<knapSack(W,a,v,n);


}


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

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

using namespace std;

const int INF = 1 << 29;

int dp[100][100];
int field[100][100];
int main(){
	int H, W;
	cin >> H >> W;
	rep(i, H) rep(j, W){
		char c;
		cin >> c;
		field[i][j] = c-'0';
	}

	rep(i, 100) rep(j, 100) dp[i][j] = INF;

	dp[0][0] = field[0][0];
	rep(i, H){
		rep(j, W){
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]+field[i+1][j]);
			dp[i][j+1] = min(dp[i][j+1], dp[i][j]+field[i][j+1]);
		}
	}
	cout << dp[H-1][W-1] << endl;

	return 0;
}

Measured memory_bytes: 1224
/* Author: Dhruv Rastogi */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(sdk) sdk.begin(),sdk.end()
#define mll map<int, int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define endl '\n'
#define vvll vector<vector<int> >
#define vll vector<int>
#define mint map<int,int> 
#define sz(x) (int)x.size()
#define sll set<int>
#define pll pair<int,int>
#define F first
#define S second
const long double PI = acos(-1.0);

void solve(){  
	double ans=0;
	priority_queue<double,vector<double>, greater<double> > pq;
	int n;
	cin>>n;
	rep(i,0,n){
		double x;
		cin>>x;
		pq.push(x);
	}
	while(sz(pq)>1){
		double k = pq.top();
		pq.pop();
		double j=pq.top();
		pq.pop();
		pq.push((k+j)/2);
	}
	cout<<fixed<<setprecision(12)<<pq.top()<<endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int main()
{
    int n, c, k;
    cin >> n >> c >> k;
    priority_queue<int, vector<int>, greater<int>> pque;
    for(int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        pque.push(t);
    }
    int ans = 0;
    while(!pque.empty())
    {
        int t = pque.top() + k;
        pque.pop();
        int cnt = 1;
        while(!pque.empty() && pque.top() <= t && cnt < c)
        {
            pque.pop();
            cnt++;
        }
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3924
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


using namespace std;



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

    vector<int>A(N);

    for(int i = 0; i < N; i++)cin >> A[i];

    sort(A.begin(),A.end());
    int i =0;

  

while(sum < x && i<N){
        
  		sum += A[i];
        i++;
      	

    }
  	if(sum==x)cout <<i;
  	else cout << i-1;
  	


}


Measured memory_bytes: 256
import numpy as np

k = int(input())


def get_top(rem):
    number = 0

    numbers = np.zeros((100,10), dtype=np.int64)
    numbers[0] += 1
    for i in range(100):
        for j in range(10):
            if j == 0:
                numbers[i+1][j] = numbers[i][j] + numbers[i][j+1]
            elif j == 9:
                numbers[i+1][j] = numbers[i][j-1] + numbers[i][j]
                number += numbers[i+1][j]
            else:
                numbers[i+1][j] = numbers[i][j-1] + numbers[i][j] + numbers[i][j+1]
                number += numbers[i+1][j]
            if number >= rem:
                break
        if number >= rem:
            break
    return i, j, k-(number - numbers[i+1][j]), numbers


def get_after_second(top, remains):
    pass

ans = ""

if k <= 9:
    print(k)
else:
    k -= 9
    dig, top, remain, nums = get_top(k)
    ans += str(top)
    for i in range(dig+1):
        digit = dig - i
        if not top == 0:
            second_top = top - 1
            if not top == 9:
                for j in range(3):
                    if remain - nums[digit][second_top + j] <= 0:
                        top = second_top + j
                        break
                    else:
                        remain -= nums[digit][second_top + j]
            else:
                for j in range(2):
                    if remain - nums[digit][second_top + j] <= 0:
                        top = second_top + j
                        break
                    else:
                        remain -= nums[digit][second_top + j]
        else:
            second_top = top
            for j in range(2):
                if remain - nums[digit][second_top + j] <= 0:
                    top = second_top + j
                    break
                else:
                    remain -= nums[digit][second_top + j]
        ans += str(top)
    print(ans)



Measured memory_bytes: 12504
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
 lint digit(lint);

int main(){

    int n;
    cin >> n;
    if(n%2)cout << n/2+1 << endl;
    else cout << n/2 << endl;

}
lint digit(lint num){
    lint dig = 0;
    while(num){
        num /= 10;
        ++dig;
    }
    return dig;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

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

    char x,y;
    cin>>x>>y;
    if (x>y){
        cout<<'>';
    }else if (x<y){
        cout<<'<';
    }else cout<<'=';
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {

	int A, B, C;

	scanf("%d %d %d",&A,&B,&C);

	int flag = 0;

	int i;

	for (i = 0; i < B; i++) {
		if ((i*A) % B == C) {
			flag = 1;
		}
	}

	if (flag == 1) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main() {
	int v[] = {
		2, 11, 31, 41, 61, 71, 101, 131, 151, 181,
		191, 211, 241, 251, 271, 281, 311, 331, 401, 421,
		431, 461, 491, 521, 541, 571, 601, 631, 641, 661,
		691, 701, 751, 761, 811, 821, 881, 911, 941, 971,
		991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201,
		1231, 1291, 1301, 1321, 1361
	};

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cout << v[i] << (i == N - 1 ? '\n' : ' ');
	}
	return 0;
}


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 CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

#define ALL(v) (v).begin(), (v).end()
#define DEBUG(x) cout<<#x<<": "<<(x)<<endl

int n;
using P = complex<double>;
P p[8];

int main(){
	scanf("%d",&n);
	REP(i,n){
		int x,y;
		scanf("%d%d",&x,&y);
		p[i] = P(x,y);
	}
	double ans = 0.0;
	double sum = 0.0;
	vector<int> q(n);
	REP(i,n)q[i] = i;
	do{
		REP(i,n-1)ans += abs(p[q[i]] - p[q[i+1]]);
		sum++;
	}while(next_permutation(ALL(q)));
	printf("%.9f\n", ans/sum);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

int main(){
    int n;
    cin >> n;
    if(n<=2){
        cout << 0 << endl;
    }else{
        int s = 0;
        for(int i=1;i<=n/2;i++){
            int k = n-i;
            if(k!=i){
                s++;
            }
        }
        cout << s << endl;
    }
    return 0;
}

Measured memory_bytes: 888
S = input()
K = int(input())


def c(ss, k):
    s = list(ss)
    s *= k
    n = len(s)
    ret = 0
    for i in range(n - 2):
        if s[i] == s[i + 1] == s[i + 2]:
            s[i + 1] = 'AB' [(i + 1) % 2]
            ret += 1
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            s[i + 1] = 'AB' [(i + 1) % 2]
            ret += 1
    return ret


x1 = c(S, 1)
x2 = c(S, 2)
x3 = c(S, 3)
x4 = c(S, 4)
x5 = c(S, 5)
if K < 100:
    print(c(S, K))
elif K % 2:
    K //= 2
    K -= 1
    print(x3 + K * (x5 - x3))
else:
    K //= 2
    K -= 1
    print(x2 + K * (x4 - x2))


Measured memory_bytes: 3064
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n=parseInt(readline())
    c=split(readline(),"")
    s=sort(c)
    cnt=0
    for i in 1:n
        if c[i]!=s[i]
            cnt+=1
        end
    end
    println(cld(cnt,2))
end
main()

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

public class Main {
    
    public static final int INFTY = 2000000000;
    public static final int MOD   = 1000000003;
    
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        try {
            int N = Integer.parseInt(br.readLine());
            String[] input = new String[N];
            int[] array    = new int[N];
            
            input = br.readLine().split("\\s+");
            for(int i = 0; i < N; i++) {
                array[i] = Integer.parseInt(input[i]);
            }
            
            int Q = Integer.parseInt(br.readLine());
            String[] input_T = new String[Q];
            int tmp, ans = 0;
            
            input_T = br.readLine().split("\\s+");
            for(int i = 0; i < Q; i++) {
                tmp = Integer.parseInt(input_T[i]);
                
                for(int k = 0; k < N; k++) {
                    if(tmp == array[k]) {
                        ans++;
                        break;
                    }
                }
            }
            
            System.out.println(ans);
            
        } catch(NumberFormatException e) {
            e.printStackTrace();
        } catch(IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 29192
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==
*/

f(A, B, C) :- A + B >= C.

main :-
    get_number(A, B),
    get_number(C),
    f(A, B, C) -> writeln("Yes") ; writeln("No").


Measured memory_bytes: 8080
while true
    n = gets.to_i
    break if n == 0
    arr = gets.chomp.split.map(&:to_i)
    arr2 = [0, 0, 0]
    arr.each{|x| arr2[[x, 2].min] += 1}
    puts (arr2[2] == 0) ? "NA" : arr2[1] + arr2[2] + 1
end


Measured memory_bytes: 10028
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi deque<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<int,ll>
#define pll pair<ll,ll>
#define _path pair<ll,pair<ll,int> > 
#define vv deque
//#define endl '\n'
//#define mp make_pair
using namespace std;
const int MAXN = 10000+5;
const int MAXK = 1000+5;
const ll INF = 1e18;
ll arr[MAXN];
ll dp[MAXK][MAXN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	// int t;
	// cin >> t;
	// while(t--)
	// {
	string s;
	cin >> s;
	int count=0;
     int i=0;
     if(s=="RSS")
     {
     	cout << 1  << endl;
     	return 0;;
     }
     while(i<3 && s[i]=='R')
     	{
     		count++;
     		i++;
     	}
     if(i==0)
     {
     	i=1;
     	while(i<3 && s[i]=='R')
     		{
     			count++;
     			i++;
     		}

     } 
     if(i==1)
      {
      	if(s[2]=='S')
      	cout << "0" << endl;
      else
      	cout << "1" << endl;
      	return 0;
      }
   
   cout << count << endl;
		  		
		  //}

	
	
		return 0;
}

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

using namespace std;

int main(){
  int n, ma = 0, sum = 0;
  
  cin >> n;
  
  for(int i = 0;i < n;i++){
    int p;
    
    cin >> p;
    ma = max(ma, p);
    sum += p;
  }
  
  cout << sum - ma / 2 << endl;
  
  return 0;
}

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

int main()
{
    ll n,m,r;
    std::cin >> n >> m >> r;
    std::vector<ll> city(r);
    for(ll i = 0; i < r; i++){std::cin >> city[i]; city[i]--;}
    std::vector<std::vector<ll>> dist(n,std::vector<ll>(n,100000000000000000));
    for(ll i = 0; i < m; i++){
        ll a,b,c;
        std::cin >> a >> b >> c;
        a--; b--;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    //std::cout << 334334 << std::endl;
    for(int i = 0; i < n; i++)dist[i][i] = 0;
    for(ll k = 0; k < n; k++){
        for(ll i = 0; i < n; i++){
            for(ll j = 0; j < n; j++){
                dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    ll min = 10000000000000000;
    std::sort(city.begin(), city.end());
    do{
        ll cur = 0;
        for(int i = 1; i < r; i++){
            cur += dist[city[i]][city[i - 1]];
        }
        min = std::min(cur,min);
    }while(std::next_permutation(city.begin(), city.end()));

    std::cout << min << std::endl;





}


Measured memory_bytes: 512
def inpl(): return list(map(int, input().split()))
x1,y1,x2,y2 = inpl()
dx,dy = x2-x1, y2-y1
x3,y3 = x2-dy, y2+dx
x4,y4 = x3-dx, y3-dy

print(x3,y3,x4,y4)

Measured memory_bytes: 3060
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def main():
    N = I()
    if '7' in str(N): print('Yes')
    else: print('No')
if __name__ == '__main__':
    main()

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

int a[1000][1000];
int xg,yg,w,h,ans;

void solve(int xs,int ys){

  if(xs == xg && ys == yg){
    ans = 1;
    return;
  }

  if(a[ys][xs] != a[yg][xg]) return;
  a[ys][xs] = 100;

  if(xs+1 <= w) solve(xs+1,ys);
  if(ys+1 <= h) solve(xs,ys+1);
  if(xs-1 > 0) solve(xs-1,ys);
  if(ys-1 > 0) solve(xs,ys-1);

}

int main(){

  int xs,ys;
  int n;

  while(1){
    cin >> w >> h;
    if(!w && !h) break;
    cin >> xs >> ys >> xg >> yg >> n;

    memset(a,0,sizeof(a));
    ans = 0;

    int c,d,x,y;

    for(int i=0;i<n;i++){
      cin >> c >> d >> x >> y;

      if(d == 0){
	for(int j=0;j<4;j++){
	  a[y][x+j] = c;
	  a[y+1][x+j] = c;
	}
      }

      else if(d == 1){
	for(int j=0;j<4;j++){
	  a[y+j][x] = c;
	  a[y+j][x+1] =c ;
	}
      }
    }

    solve(xs,ys);

    if(ans == 1) cout << "OK" << endl;
    else cout << "NG" << endl;
  }
}

Measured memory_bytes: 5068
from itertools import permutations

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
l = list(range(1, N+1))
cnt = 0

for p in permutations(l):
    if list(p)==P:
        a = cnt
    
    if list(p)==Q:
        b = cnt
    
    cnt += 1
    
print(abs(a-b))

Measured memory_bytes: 41456
import bisect, collections, copy, heapq, itertools, math, sys
input = sys.stdin.readline
n, m = [ int(v) for v in input().split() ]
edge = []
in_list = [0] * n
out_list = [0] * n
dp_list = [0] * n
connect_list = [ [] for i in range(n) ] 

for i in range(m):
    s, t = [ int(v)-1 for v in input().split() ]
    edge.append((s,t))
    in_list[t] += 1
    out_list[s] += 1
    connect_list[t].append(s)

search_list = [ i for i, v in enumerate(out_list) if v == 0 ]
while search_list:
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:
            out_list[j] -= 1
            if dp_list[j] < dp_list[i] + 1:
                dp_list[j] = dp_list[i] + 1
            if out_list[j] == 0:
                new_search_list.append(j)
    search_list = new_search_list

print(max(dp_list))

Measured memory_bytes: 66736
/*
 * @Date: 2020-03-12 16:23:17
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2020-03-12 16:28:16
 */
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 1e5+10;

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

Measured memory_bytes: 1152
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(void) {

	int h, w;

	string tmp;

	cin >> h >> w;

	vector<string> a, st(w);

	bool delet = false;

	for (int ih = 0; ih < h; ih++)
	{
		cin >> tmp;
		a.push_back(tmp);
		/*for (int iw = 0; iw < w; iw++)
		{
			st[iw][ih] = a[ih][iw];
		}*/
	}

	for (int iw = 0; iw < w; iw++)
	{
		delet = false;

		for (int ih = 0; ih < h; ih++)
		{
			if (a[ih][iw] == '#')break;
			if (ih == h - 1)delet = true;
		}

		if (delet) {
			for (int ih = 0; ih < h; ih++)
			{
				a[ih].erase(a[ih].begin() + iw);
			}
			w--;
			iw--;
		}
	}

	for (int ih = 0; ih < h; ih++)
	{
		string b(w,'.');
		if (equal(a[ih].begin(), a[ih].begin()+w, b.begin())) {
			a.erase(a.begin() + ih);
			h--;
			ih--;
		}
	}


	cout << "\n";
	for (int ih = 0; ih < h; ih++)
	{
		cout << a[ih]<<"\n";
	}



	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S,T;
  cin >> S >> T;
  int s=S.size();
  vector<pair<char,char>> q(s),w(s);
  for(int i=0;i<s;i++)q[i]=make_pair(S[i],T[i]);
  for(int i=0;i<s;i++)w[i]=make_pair(T[i],S[i]);
  sort(q.begin(),q.end());
  sort(w.begin(),w.end());
  for(int i=0;i<s-1;i++){
    if(q[i].first==q[i+1].first){
      if(q[i].second!=q[i+1].second){cout << "No" << endl; return 0;}
    }
  }
  for(int i=0;i<s-1;i++){
    if(w[i].first==w[i+1].first){
      if(w[i].second!=w[i+1].second){cout << "No" << endl; return 0;}
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 1544
#include <iostream>
#include <vector>
using namespace std;
struct A{
    char ch;
    int num;
};
bool is_stable(const vector<A> &a,const vector<A> &b)
{
    vector<A> t=a;
    unsigned int i,j;
    for(i=0;i<b.size();i++)
    {
        for(j=0;j<t.size();j++)
        {
            if(t[j].num == b[i].num)
            {
                if(t[j].ch!=b[i].ch)
                {
                    return false;
                }
                t[j].num = 0;
                break;
            }
        }
    }
    return true;
}
void bubblesort(vector<A> &a)
{
    unsigned int i,j;
    A t;
    bool flag = true;
    for(i=0;flag&&i<a.size();i++)
    {
        flag = false;
        for(j=a.size()-1;j>i;j--)
        {
            if(a[j].num<a[j-1].num)
            {
                t = a[j];
                a[j] = a[j-1];
                a[j-1] = t;
                flag = true;
            }
        }
    }
}
void selectionsort(vector<A> &a)
{
    A t;
    unsigned int i,j,min;
    for(i=0;i<a.size();i++)
    {
        min = i;
        for(j=i+1;j<a.size();j++)
        {
            if(a[j].num<a[min].num)
            {
                min = j;
            }
        }
        if(min != i)
        {
            t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
    }
}
void show(const vector<A> &a)
{
    unsigned int i;
    for(i=0;i<a.size();i++)
    {
        if(i)
            cout<<' ';
        cout<<a[i].ch<<a[i].num;
    }
    cout<<endl;
}
int main()
{
    vector<A> a,b,c;
    A m;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>m.ch>>m.num;
        a.push_back(m);
    }
    b=a;
    c=a;
    bubblesort(b);
    show(b);
    if(is_stable(a,b))
        cout<<"Stable"<<endl;
    else
        cout<<"Not stable"<<endl;
    selectionsort(c);
    show(c);
    if(is_stable(a,c))
        cout<<"Stable"<<endl;
    else
        cout<<"Not stable"<<endl;
    return 0;
}

Measured memory_bytes: 3152
import java.util.*;

class Main {
  public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    String out = "";
    while (scanner.hasNext()) {
      String[] a = new String[4];
      String[] b = new String[4];
      String line = scanner.nextLine();
      a = line.split(" ");
      line = scanner.nextLine();
      b = line.split(" ");
      int hit = 0;
      int blow = 0;
      for (int ii = 0; ii < a.length; ii++) {
        if (a[ii].equals(b[ii])) {
          hit++;
          continue;
        }
        for (int jj = 0; jj < b.length; jj++) {
          if (a[ii].equals(b[jj])) {
            blow++;
          }
        }
      }
      out += hit + " " + blow + "\n";
    }
  System.out.print(out);
  }
}

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

int main()
{
	int N;
	int min,max;
	int x;
	cin >> N;
	cin >> x;
	min=x;
	max=x;
	for(int i=0;i<N-1;i++){
		cin >>x;
		if(x<min){
			min=x;
		}else if(x>max){
			max=x;
		}
	}
	cout<< max-min <<endl;
}

Measured memory_bytes: 256
import itertools
def S(): return input()
S = S()
AKIBA_list = list(itertools.accumulate('AKIHABARA'))
for i,x in enumerate(AKIBA_list):
    if S[:i+1]==x:
        continue
    S = S[:i]+'A'+S[i:]
    if S[:i+1]==x:
        continue
    print('NO')
    break
else:
    if S=='AKIHABARA':
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 3060
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        String s = scanner.next().chars().mapToObj(ch -> String.valueOf((char)ch)).sorted().collect(Collectors.joining());
        String t = scanner.next().chars().mapToObj(ch -> String.valueOf((char)ch)).sorted(Comparator.reverseOrder()).collect(Collectors.joining());
        System.out.println(s.compareTo(t) < 0 ? "Yes" : "No");
    }
}

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

int main(){
  string s;
  cin>>s;
  if(s=="Sunny"){
    cout<<"Cloudy"<<endl;
  }else if(s=="Cloudy"){
    cout<<"Rainy"<<endl;
  }else{
    cout<<"Sunny"<<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
//#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
//#include <fstream>
//#include <list>
//#include <iomanip>
//#include <stdlib.h>
//#include <cctype>

using namespace std;

const int MAX_N = 1000000;
#define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define prec std::cout << std::fixed << std::setprecision(15);
#define endl "\n"
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define ssort(z) sort(z.begin(), z.end())
#define rsort(z) sort(z.rbegin(), z.rend())
#define eerase(z) z.erase(unique(z.begin(), z.end()), z.end())
#define ccnt(z, w) count(z.begin(), z.end(), w)

void printVec(std::vector<int> &vec) {
//    std::cout << "";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    cout << '\n';
}

void printVec1(std::vector<string> &vec) {
//    std::cout << "";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    cout << '\n';
}

void printVec2(std::vector<Int> &vec) {
//    std::cout << "";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    cout << '\n';
}

Int gcd(Int a, Int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

Int lcm(Int a, Int b) {
    return a / gcd(a, b) * b;
    //a*bは64bit integer overflow
}

bool integer(double num) {
    return floor(num) == num;
}

Int fact(int num) {
    if (num == 0)
        return 1;
    else
        return num * fact(num - 1);
}

int main() {
    IOS;
    string s, t;
    cin >> s>> t;
    for (int i = 0; i < s.size(); i++) {
        string temp=s.substr(s.size()-1,1);
        string temp2=s.substr(0,s.size()-1);
        s=temp+temp2;
        //cout<<s<<endl;
        if (s==t){
            cout<<"Yes"<<endl;
            return 0;
        }

    }
    cout<<"No";


    cout << endl;
    return 0;
}

/*
テレビも無ェ ラジオも無ェ
自動車もそれほど走って無ェ
ピアノも無ェ バーも無ェ
巡査 毎日ぐーるぐる
朝起ぎで 牛連れで
二時間ちょっとの散歩道
電話も無ェ 瓦斯も無ェ
バスは一日一度来る
俺らこんな村いやだ 俺らこんな村いやだ
東京へ出るだ 東京へ出だなら
銭コァ貯めで 東京でベコ(牛)飼うだ
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pii> vpi;
typedef vector<vector<pii> > vvpi;

const int maxn = 2e5;
const ll mod = 998244353LL;
const ll inf = 1e9;

int main() {
	int i, j, k, x;
	cin >> k >> x;
	for(i = max(x - k + 1, -1000000); i <= min(x + k - 1, 1000000); ++i) {
		cout << i << " ";
	}
	cout << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
  int i, mas, book;
  while(scanf("%d",&mas) && mas != 0) {
    for(i = 0; i < 9; i++) {
      scanf("%d",&book);
      mas -= book;
    }
    printf("%d\n",mas);
  }
  return(0);
}

Measured memory_bytes: 600
/**
 * @author yuzining
 * @date 2020/07/12 18:49
*/

#ifdef local
#include "D:\vscode\acm\local.hpp"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(...) do { } while(false)
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  Main();
  return 0;
}
#endif

void Main() {
  int n; cin >> n;
  vector<int> v(n);
  for(auto &x: v) cin >> x;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    if(~i & 1) {
      if(v[i] & 1) {
        ans++;
      }
    }
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3652
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100009;
int n,m;
int a[1002],b[1002];
int target;
int dp[1002][4100];
int solve(int pos,int msk)
{
    if(pos>m)
    {
        if(msk==target)return 0;
        else return inf ;
    }
    if(msk==target)return 0;
    int &ret=dp[pos][msk];
    if(ret!=(-1))return ret;
    ret=inf;
    ret=min(ret,a[pos]+solve(pos+1,msk | b[pos]));
    ret=min(ret,solve(pos+1,msk));
    return ret;
}
 main()

{
    fast
    memset(dp,-1,sizeof dp);
    cin>>n>>m;
    target=(1LL<<n)-1;
    f(i,1,m)
    {
        int x;
        cin>>a[i]>>x;
        f(j,1,x)
        {
            int y;
            cin>>y;y--;
            b[i]=b[i]|(1LL<<y);
        }
    }
    int ses=solve(1,0);
    if(ses>=inf)ses=-1;
    cout<<ses<<endl;
    return 0;

}





































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




int main() {
    Int N, Q;
    string s;
    cin >> N >> s >> Q;

    set<Int> S[26];

    rep(i,N) {
        S[s[i]-'a'].insert(i);  
    }
    rep(i,26) S[i].insert(N);

    rep(k,Q) {
        int a; cin >> a;
        if (a == 1) {
            Int i;
            char c;
            cin >> i >> c;
            i--;
            rep(j,26) {
                if (S[j].find(i) == S[j].end()) {}
                else S[j].erase(i);
            }
            S[c-'a'].insert(i);
        }
        else if (a == 2) {
            Int l, r;
            cin >> l >> r;
            l--;
            r--;
            int cnt = 0;
            rep(j,26) {
                if (*S[j].lower_bound(l) <= r) cnt++;
            }
            cout << cnt << endl;
        }
    }
    return 0;

}

Measured memory_bytes: 24324
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=2e6+5;
int n,m,a[N];
int used[N],ans[N];
struct ask{
    int l,r,id;
}asks[N];
bool cmp(ask a,ask b) {
    return a.r<b.r;
}
int t[N];
int lowbit(int x) {return x&(-x);}
void modify(int x,int val) {
    for(;x<=n;x+=lowbit(x)) t[x]+=val;
}
int query(int x) {
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=t[x];
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]);
    rep(i,1,m) asks[i].id=i,scanf("%d%d",&asks[i].l,&asks[i].r);
    sort(asks+1,asks+m+1,cmp);
    int now=1;
    rep(i,1,m) {
        rep(j,now,asks[i].r) {
            if(used[a[j]]) modify(used[a[j]],-1);
            modify(j,1);
            used[a[j]]=j;
        }
        ans[asks[i].id]=query(asks[i].r)-query(asks[i].l-1);
        now=asks[i].r+1;
    }
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

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

map<long long, int> cnt;

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

      int N;
      cin >> N;

      long long ans = 0, sum = 0;
      long long num;
      cnt[0] = 1;
      for(int i=0; i<N; i++) {
            cin >> num;
            sum += num;
            ans += cnt[sum];
            cnt[sum]++;
      }
      cout << ans << endl;
      return 0;
}

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

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

    int m[N];
    for (int i=0; i<N; ++i) cin >> m[i];

    int minm = 1001;
    int summ = 0;
    for (int i=0; i<N; ++i) {
        if (m[i] < minm) minm = m[i];
        summ += m[i];
    }

    cout << N + (X - summ) / minm << endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=[int(j) for j in input().split()]
ans=0
l=list(range(n+2))
r=list(range(n+2))

index=[0]*(n+1)
for i in range(n):
    index[a[i]]=i

for i in range(1,n+1)[::-1]:
    ind=index[i]
    x,y=l[ind],r[ind]
    ans+=i*(ind-x+1)*(y-ind+1)
    l[y+1],r[x-1]=x,y
print(ans)






Measured memory_bytes: 35728
#include<bits/stdc++.h>
#define llu unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define to_lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower);
#define to_upper(s) transform(s.begin(), s.end(), s.begin(), ::toupper);

using namespace std;

// scan vector
template <typename T> 
inline istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x : a) in >> x;
    return in;
}
// print vector
template <typename T> 
inline ostream &operator<<(ostream &out, vector<T> &a) {
    for(auto &x : a) out << x <<" ";
    return out;
}
// scan pair
template <typename T, typename U> 
inline istream &operator>>(istream &in, pair<T,U> &a) {
    in >> a.first >> a.second; 
    return in;
}
int n,k;
vector<ll> a;
vector<vector<ll> > dp;
vector<vector<bool> > visited;
ll solve(int first, int last)
{
    if(first>last)
        return 0;

    if(visited[first][last])
        return dp[first][last];
    
    visited[first][last]=true;

    if(first==last)
        return dp[first][last]=a[first];
    
    dp[first][last]=max(min(a[first]+solve(first+2,last),a[first]+solve(first+1,last-1)),min(a[last]+solve(first,last-2),a[last]+solve(first+1,last-1)));
    
    return dp[first][last];
}

int main()    
{
    #ifdef SANS
        freopen("ongoingin.txt","r",stdin);
        freopen("ongoingout.txt","w",stdout);
    #endif
    fast
    int t=1;
    // cin>>t;
    while(t--)
    {
        cin>>n;
        dp.resize(n,vector<ll>(n,-1));
        a.resize(n);
        cin>>a;
        visited.resize(n,vector<bool>(n,0));
        ll total=0;
        for(auto& i:a)
        {
            // cin>>i;
            total+=i;
        }
        ll X=solve(0,n-1);
        // cout<<X<<" "<<total<<endl;
        cout<<(X-(total-X));
    }
    #ifdef SANS
        cout<<"\nTime Elapsed:"<<1.0*clock()/CLOCKS_PER_SEC <<"sec\n";
    #endif
}

Measured memory_bytes: 75016
#include <iostream>

using namespace std;

int main(void) {
	int a, b;
	cin >> a >> b;
	
	int v = a * 100 + b;

	int num = 0;
	for (int i = 1; i <= 12; i++) {
		int v2 = i * 100 + i;
		if (v < v2) {
			break;
		}
		++num;
	}

	cout << num << endl;
	return 0;
}


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

struct node{
  int key;
  struct node *parent;
  struct node *left;
  struct node *right;
};

typedef struct node * Node;

Node root;

void Insert(int);
int treeSearch(Node, int);
void Preorder(Node);
void Inorder(Node);

int main(){
  int i, m, k, find;
  char in[20];

  scanf("%d",&m);
  for(i = 0; i < m; i++){
    scanf("%s",in);
    if(in[0] == 'i'){
      scanf("%d",&k);
      Insert(k);
    }
    if(in[0] == 'f'){
      scanf("%d",&k);
      find = treeSearch(root, k);
      if(find == 1) printf("yes\n");
      else printf("no\n");
    }
    if(in[0] == 'p'){
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }
  }

  return 0;
}

void Insert(int k){
  Node y = NULL;
  Node x = root;
  Node v;

  v = malloc(sizeof(struct node));
  v->key = k;
  v->parent = NULL; 
  v->left = NULL;
  v->right = NULL;

  while(x != NULL){
    y = x;
    if(v->key < x->key) x = x->left;
    else x = x->right;
  }

  v->parent = y;

  if(y == NULL) root = v;
  else if(v->key < y->key) y->left = v;
  else y->right = v;

}

int treeSearch(Node u, int k){
  int f = 0;
  Node x = u;
  
  while(x != NULL){
    if(k < x->key) x = x->left;
    else if(k > x->key) x = x->right;
    else{
      f = 1;
      break;
    }
  }

  return f;
  
}

void Preorder(Node u){
  printf(" %d", u->key);

  if(u->left != NULL) Preorder(u->left);
  
  if(u->right != NULL) Preorder(u->right);

}

void Inorder(Node u){

  if(u->left != NULL) Inorder(u->left);
  printf(" %d",u->key);

  if(u->right != NULL) Inorder(u->right);
}

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

int N;

int main(){
  vector <long long> L(100, 0);
  cin >> N;
  L.at(0) = 2;
  L.at(1) = 1;
  for (int i = 1; i < N ;i++){
    L.at(i+1) = L.at(i) + L.at(i-1);
  }
  cout << L.at(N) << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int ans = a-b-c;
  if(a-b-c<=0){
    cout<<abs(a-b-c)<<endl;
    return 0;
  }
  else{
    cout<<"0"<<endl;
    return 0;
  }
  return 0;
}

Measured memory_bytes: 256
s = gets.chomp.split('').map{ |c| c.ord - 97 }
t = gets.chomp.split('').map{ |c| c.ord - 97 }
graph = 26.times.map{ [false] * 26 }
s.length.times do |i|
    graph[s[i]][t[i]] = true
end
if graph.all?{ |arr| arr.count(true) <= 1 } && graph.transpose.all?{ |arr| arr.count(true) <= 1 }
  puts "Yes"
else
  puts "No"
end

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, x, y;
  cin >> n >> x >> y;
  --x, --y;
  vector<int> res(n);
  for (int j = 0; j < n; ++j) {
    for (int i = 0; i < j; ++i) {
      int d = min(j - i, abs(x - i) + 1 + abs(y - j));
      ++res[d];
    }
  }
  for (int k = 1; k < n; ++k) {
    cout << res[k] << '\n';
  }
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
# define pb push_back
# define ll long long
# define fi first
# define se second
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
# define mkp make_pair
//# define time cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

using namespace std;

ll q , w , e , z ;


int main()
{
	speed;

    int n , m ;
    cin >> n >> m ;
    int k = max( n , m );
    if(n == m){
        cout<< 2 * m << endl;
    }
    else{
        cout<<k + ( k -1 );
    }


	time;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  int A[N];
  for(int i = 0; i < N; ++i) cin >> A[i];
  int odd = 0, even = 0, four = 0;
  for(int i = 0; i < N; ++i){
    if(A[i]%2) ++odd;
    if(!(A[i]%4)) ++four;
    else if(!(A[i]%2)) ++even;
  }

  even %= 2;
  //cout << odd << " " << even << " " << four << endl;
  if(even + odd - four > 1) cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include <vector>
#include<map>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define vsort(v) sort(v.begin(), v.end())
#define rv(v) reverse(v.begin(), v.end())
#define ll long long
const ll MOD = 1e9 + 7;

int main() {
	int k, s;
	cin >> k >> s;
	int c = 0;
	for (int x = 0; x <= k; x++) {
		for (int y = 0; y <= k; y++) {
			int z = s - x - y;
			if (0 <= z && z <= k) c++;
		}
	}
	cout << c << endl;
}

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

int main() {
    ll T1, T2, A1, A2, B1, B2; 
    cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;

    ll P = T1*(A1-B1);
    ll Q = T2*(A2-B2);
    if(P+Q==0){
        cout << "infinity" << endl;
        return 0;
    } else if(P+Q<0){
        swap(A1, B1);
        swap(A2, B2);
    }

    if(A1>B1){
        cout << 0 << endl;
        return 0;
    }

    ll s = -P / (P+Q);
    ll t = -P % (P+Q);
    if(t==0) cout << 2*s  << endl;
    else cout << 2*s + 1 << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;
struct edge{int to,cost;};
const int INF = 1000000000;

int n,k,c[5000],r[5000];
vector<int> g[5000];
vector<edge> G[5000];
priority_queue<pii,vector<pii>,greater<pii> > q;

int main(){
  scanf("%d %d",&n,&k);
  for(int i=0;i<n;i++) scanf("%d %d",c+i,r+i);
  for(int i=0;i<k;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for(int i=0;i<n;i++){
    queue<pii> que;
    bool flag[n];
    fill(flag,flag+n,false);
    flag[i] = true;
    que.push(pii(i,r[i]));
    while(!que.empty()){
      int v = que.front().first;
      int ns = que.front().second;
      que.pop();
      if(ns==0) continue;
      for(int j=0;j<g[v].size();j++){
        if(flag[g[v][j]]) continue;
        edge e;
        e.to = g[v][j];
        e.cost = c[i];
        G[i].push_back(e);
        flag[g[v][j]] = true;
        que.push(pii(g[v][j],ns-1));
      }
    }
  }
  int d[n];
  fill(d,d+n,INF);
  d[0] = 0;
  q.push(make_pair(0,0));
  while(!q.empty()){
    pii p = q.top(); q.pop();
    int nv = p.second;
    if(d[nv]<p.first) continue;
    d[nv] = p.first;
    for(int i=0;i<G[nv].size();i++){
      if(d[G[nv][i].to]>d[nv]+G[nv][i].cost){
        d[G[nv][i].to] = d[nv]+G[nv][i].cost;
        q.push(make_pair(d[G[nv][i].to],G[nv][i].to));
      }
    }
  }
  printf("%d\n",d[n-1]);
  return 0;
}

Measured memory_bytes: 127028
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
f = np.array(list(map(int, input().split())))
a.sort()
f.sort()
f = f[::-1]
a_sum = a.sum()


def test(x):
    return a_sum - np.minimum(a, x // f).sum() <= k


left = -1
right = 10**13
while left + 1 < right:
    mid = (left + right) // 2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)


Measured memory_bytes: 37192
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"sort"
)

// github.com/EndlessCheng/codeforces-go
func run(_r io.Reader, _w io.Writer) {
	in := bufio.NewScanner(_r)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriter(_w)
	defer out.Flush()
	r := func() (x int) {
		in.Scan()
		for _, b := range in.Bytes() {
			x = x*10 + int(b&15)
		}
		return
	}

	n := r()
	a := make([]int, n)
	for i := range a {
		a[i] = r()
	}
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		v, w := r()-1, r()-1
		g[v] = append(g[v], w)
		g[w] = append(g[w], v)
	}
	ans := make([]int, n)
	dp := []int{}
	var f func(v, fa int)
	f = func(v, fa int) {
		if i := sort.SearchInts(dp, a[v]); i < len(dp) {
			old := dp[i]
			dp[i] = a[v]
			ans[v] = len(dp)
			for _, w := range g[v] {
				if w != fa {
					f(w, v)
				}
			}
			dp[i] = old
		} else {
			dp = append(dp, a[v])
			ans[v] = len(dp)
			for _, w := range g[v] {
				if w != fa {
					f(w, v)
				}
			}
			dp = dp[:len(dp)-1]
		}
	}
	f(0, -1)
	for _, v := range ans {
		Fprintln(out, v)
	}
}

func main() { run(os.Stdin, os.Stdout) }


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

bool dp[90][90][13600];

signed main(){

	lli h,w;
	cin>>h>>w;

	lli a[100][100];
	lli b[100][100];
	lli data[100][100];

	REP(i,0,h)REP(j,0,w)cin>>a[i][j];
	REP(i,0,h)REP(j,0,w)cin>>b[i][j];

	REP(i,0,h)REP(j,0,w)data[i][j] = abs(a[i][j]-b[i][j]);

	dp[0][0][data[0][0]]=true;
	REP(i,0,h){
		REP(j,0,w){
			REP(k,0,13600){
				if(dp[i][j][k]){
					dp[i+1][j][abs(k+data[i+1][j])] = true;
					dp[i+1][j][abs(k-data[i+1][j])] = true;
					dp[i][j+1][abs(k+data[i][j+1])] = true;
					dp[i][j+1][abs(k-data[i][j+1])] = true;
				}
			}
		}
	}

	REP(i,0,13600){
		if(dp[h-1][w-1][i]){
			cout<<i<<endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 97664
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node{
  int parent;
  int left;
  int right;
};

struct Node T[MAX];
int n,D[MAX],H[MAX];

void setDepth(int,int);
int setHeight(int);
int getSibling(int);
void print(int);

int main(){
  int v,l,r,root=0,i;
  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].parent=NIL;

  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].left=l;
    T[v].right=r;
    if(l!=NIL) T[l].parent=v;
    if(r!=NIL) T[r].parent=v;
  }

  for(i=0;i<n;i++) if( T[i].parent==NIL) root=i;

  setDepth(root,0);
  setHeight(root);

  for(i=0;i<n;i++) print(i);

  return 0;
}

void setDepth(int u,int d){
  if(u==NIL) return;
  D[u]=d;
  setDepth(T[u].left,d+1);
  setDepth(T[u].right,d+1);
}

int setHeight(int u){
  int h1=0,h2=0;
  if(T[u].left!=NIL) h1=setHeight(T[u].left)+1;
  if(T[u].right!=NIL) h2=setHeight(T[u].right)+1;
  return H[u]=(h1>h2 ? h1:h2);
}

int getSibling(int u){
  if(T[u].parent==NIL) return NIL;
  if(T[T[u].parent].left!=u && T[T[u].parent].left!=NIL)
    return T[T[u].parent].left;
  if(T[T[u].parent].right!=u && T[T[u].parent].right!=NIL)
    return T[T[u].parent].right;
  return NIL;
}
  
void print(int u){
      printf("node %d: ",u);
      printf("parent = %d, ",T[u].parent);
      printf("sibling = %d, ",getSibling(u));
      int deg =0;
      if(T[u].left!=NIL) deg++;
      if(T[u].right!=NIL) deg++;
      printf("degree = %d, ",deg);
      printf("depth = %d, ",D[u]);
      printf("height = %d, ",H[u]);

      if(T[u].parent==NIL){
	printf("root\n");
      }
      else if(T[u].left==NIL && T[u].right==NIL ){
	printf("leaf\n");
      } else
	{
	printf("internal node\n");
      }
}



Measured memory_bytes: 2044