akhauriyash/Code-Regression huggingface dataset:
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 * 解説通りに作成したソースコード
 * 
 * https://atcoder.jp/contests/abc127/submissions/5869777 にも参考
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			long b = 0L, answer = 0L;
			Queue<Integer> leftQueue = new PriorityQueue<>(Comparator.reverseOrder());
			Queue<Integer> rightQueue = new PriorityQueue<>();
			for (int i = 0; i < n; i++) {
				int command = scanner.nextInt();
				if (1 == command) {
					int a = scanner.nextInt();
					b += scanner.nextInt();
					if (leftQueue.isEmpty()) {
						leftQueue.add(a);
					} else if (a < leftQueue.peek()) {
						leftQueue.add(a);
						answer += leftQueue.peek() - a;
					} else {
						rightQueue.add(a);
						answer += a - leftQueue.peek();
					}
					if (leftQueue.size() - rightQueue.size() > 1) {
						rightQueue.add(leftQueue.poll());
						answer += (rightQueue.peek() - leftQueue.peek()) * (rightQueue.size() - leftQueue.size());
					} else if (rightQueue.size() > leftQueue.size()) {
						answer += (rightQueue.peek() - leftQueue.peek()) * (leftQueue.size() - rightQueue.size());
						leftQueue.add(rightQueue.poll());
					}
				} else {
					System.out.println(leftQueue.peek() + " " + (answer + b));
				}
			}
		}
	}
}


Measured memory_bytes: 73472
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

using ll = long long;
using namespace std;

long long gcd(long long a, long long b) {
    if (a < b) {
        std::swap(a, b);
    }
    while (a%b > 0) {
        long long buf = b;
        b = a%b;
        a = buf;
    }
    return b;
}

int main() {
    int n = 0;
    ll k = 0;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i=0; i<n; i++) {
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    if (a.back() < k) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    for (int i=0; i<n; i++) {
        if (a.at(i) == k) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    ll buf = a.at(0);
    for (int i=1; i<n; i++) {
        buf = gcd(buf, a.at(i));
        if (buf == 1) {
            break;
        }
    }
    if (k%buf == 0) {
        cout << "POSSIBLE" << endl;
    }
    else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int i,j,min;
    int[] a = new int[3];

    for(i=0;i<3;i++){
      a[i] = sc.nextInt();    
    }
    
    min = 99999;

    for(i=0;i<3;i++){
      for(j=0;j<3;j++){
        if(i != j){
          if(min>a[i]+a[j]){
            min = a[i]+a[j];
          
          }
        }
      }
    }
    System.out.print(min);
  }
}

Measured memory_bytes: 21844
import sys

readline = sys.stdin.readline

n = int(input())
cnt = 0
for i in range(n):
    d1, d2 = map(int, readline().split())
    if d1 == d2:
        cnt += 1
        if cnt == 3:
            print("Yes")
            sys.exit()
    else:
        cnt = 0
print("No")

Measured memory_bytes: 9172
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Num 1000000007
// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

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

    rep(i, n)
    {
        set<char> left, right, result;
        rep(j, n)
        {
            if (j < i)
            {
                left.insert(str[j]);
            }
            else
            {
                right.insert(str[j]);
            }
        }

        set_intersection(left.begin(), left.end(),
                         right.begin(), right.end(),
                         std::inserter(result, result.end()));
        // for (auto item : result)
        //     cout << item;
        // cout << endl;
        ans = max(ans, (int)result.size());
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int W, H, x, y, r;
        W = sc.nextInt();
        H = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        r = sc.nextInt();
        if( x+r>W || y+r>H || x-r<0 ||y-r <0)
            System.out.println("No");
        else
            System.out.println("Yes");



    }
}



Measured memory_bytes: 26408
# ABC 069 D
H, W = map(int,input().split())
N = int(input())
a = list(map(int,input().split()))

grid = [[0 for k in range(W)] for l in range(H)]
now = 0
for k in range(H):
    for l in range(W):
        if a[now] == 0:
            now += 1
        if k%2 == 0:
            grid[k][l] = now+1
            a[now] -= 1
        else:
            grid[k][W-l-1] = now+1
            a[now] -= 1

for r in grid:
    print(" ".join(map(str,r)))

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

#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()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

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 (b<a) { a=b; return 1; } return 0; }

const ll INF=(ll)1e19;
//const int INF=(1<<30);

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

  vector<pair<ll,ll>> ab(n);
  REP(i,n){
    ll a,b;
    cin >> a >> b;
    ab.emplace_back(make_pair(a,b));
  }
  sort(ALL(ab));

  ll ans=0;
  for(auto v: ab){
    if(m <= v.second){
      ans += v.first * m;
      break;
    }else{
      ans += v.first * v.second;
      m -= v.second;
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 4608
N = int(input())
X = [int(d) for d in input().split()]

sort_x = X.copy()
sort_x.sort()

nn = N//2
low_ = sort_x[nn-1]
high_ = sort_x[nn]

for x in X:
	if x < high_:
		print(high_)
	else:
		print(low_)

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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    int n,m;
    cin >> n >> m;
    bool ant[200010]={};
    bool ball[200010]={};
    REP(i,m){
        int a,b;
        cin >> a >> b;
        if(a==1) ant[b]=true;
        if(b==n) ball[a]=true;
    }
    for(int i=0;i<200010;i++){
        if(ant[i]&&ball[i]){
            COUT("POSSIBLE");
            return 0;
        }
    }
    COUT("IMPOSSIBLE");
    return 0;
}  


Measured memory_bytes: 640
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(new BufferedInputStream(System.in));
		List<String> output = new ArrayList<String>();
		while (scan.hasNext()) {
			String input = scan.nextLine();
			String[] in = input.split(" ");
			int a = Integer.parseInt(in[0]);
			String op = in[1];
			int b = Integer.parseInt(in[2]);

			if ("?".equals(op)) {
				break;
			} else {
				if (a >= 0 && a <= 20000 && b >= 0 && b <= 20000) {
					if ("+".equals(op)) {
						int result = a + b;
						output.add(String.valueOf(result));
					} else if ("-".equals(op)) {
						int result = a - b;
						output.add(String.valueOf(result));
					} else if ("*".equals(op)) {
						int result = a * b;
						output.add(String.valueOf(result));
					} else if ("/".equals(op)) {
						if (b != 0) {
							int result = a / b;
							output.add(String.valueOf(result));
						}
					}
				}
			}
		}
		for (String out : output) {
			System.out.println(out);
		}
	}

}

Measured memory_bytes: 26068
#include<iostream>
#include<string>
using namespace std;
string S;
int N, A[10000], B[10000];
int main() {
	while (true) {
		cin >> N; if (N == 0) { break; }
		cin >> S;
		for (int i = 0; i < N; i++) {
			cin >> A[i] >> B[i];
		}
		for (int i = N - 1; i >= 0; i--) {
			swap(S[A[i] - 1], S[B[i] - 1]);
			for (int j = 0; j < B[i] - A[i]; j++) {
				S[A[i] - 1]++; S[B[i] - 1]++;
				if (S[A[i] - 1] > 'z') { S[A[i] - 1] = 'a'; }
				if (S[B[i] - 1] > 'z') { S[B[i] - 1] = 'a'; }
			}
		}
		cout << S << endl;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <set>
typedef long long ll;
using namespace std;
int main() {
    vector<ll> a;
    for (int i = 0; i < 3; i++) {
        ll _a; cin >> _a;
        a.push_back(_a);
    }
    sort(a.begin(), a.end());
    cout << a[0]*a[1]/2 << endl;
    return 0;
}


Measured memory_bytes: 888
if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    cnt = 0
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if A[j - 1] > A[j]:
                A[j - 1], A[j] = A[j], A[j - 1]
                cnt += 1
    for x in A:
        print x,
    print
    print cnt


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

int pertition(int *, int, int);

int partition(int *A, int p, int r)
{
  int x = A[r];
  int i = p - 1;
  int j, tmp;

  for(j = p;j < r;j++)
    {
      if(A[j] <= x)
	{
	  i = i + 1;
	  tmp = A[i];
	  A[i] = A[j];
	  A[j] = tmp;
	}
    }
  tmp = A[i + 1];
  A[i + 1] = A[r];
  A[r] = tmp;

  return i + 1;
}


int main()
{
  int n, i, r, *A;


  scanf("%d", &n);

  A = malloc(sizeof(int)*n);

  for(i = 0;i < n;i++)
    {
      scanf ("%d", A + i);
    }

  r = partition(A, 0, n - 1);

  for(i = 0;i < n;i++)
    {
      if(i == r) 
	{
	  printf("[%d]",A[i]);
	}
      else 
	{
	  printf("%d",A[i]);
	}

      if(i != n - 1)
	{
	  printf(" ");
	}
      else
	{
	  printf("\n");
	}

    }
      free(A);
      return 0;
}

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

using ll = long long;

ll fun( ll h ){
    if( h == 1 ){
        return 1;
    }
    return 1+2*fun(h/2);
}

int main(){
    ll h;
    while( cin >> h ){
        cout << fun(h) << endl;
    }
}


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

#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N   = 1e5 + 5;

int i,n,a,b,t,x,k;

signed main(){
    cin >> n >> a >> b;
    if(n < a+b-1 || n > 1LL*a*b){
        cout << -1;
        return 0;
    }
    
    for(t = n, k=0; t+k > b ; k++){
        x = min(a , t+k+1-b);
        for(i=t-x+1; i<=t; i++)
            cout << i << " ";
        t -= x;
     }
     
     for(; t ; t--) cout << t << " ";
    return 0;
}

Measured memory_bytes: 2176
n=input()
a=int(n[0])
b=int(n[1])
c=int(n[2])
d=int(n[3])

if a+b+c+d==7:
    print("{0}+{1}+{2}+{3}=7".format(a,b,c,d))
elif a+b+c-d==7:
    print("{0}+{1}+{2}-{3}=7".format(a,b,c,d))
elif a+b-c+d==7:
    print("{0}+{1}-{2}+{3}=7".format(a,b,c,d))
elif a+b-c-d==7:
    print("{0}+{1}-{2}-{3}=7".format(a,b,c,d))
elif a-b+c+d==7:
    print("{0}-{1}+{2}+{3}=7".format(a,b,c,d))
elif a-b+c-d==7:
    print("{0}-{1}+{2}-{3}=7".format(a,b,c,d))
elif a-b-c+d==7:
    print("{0}-{1}-{2}+{3}=7".format(a,b,c,d))
elif a-b-c-d==7:
    print("{0}-{1}-{2}-{3}=7".format(a,b,c,d))

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>

#define rep(i, n, m) for(int i=n;i<m;i++)

using namespace std;

const int num[5] = {5,7,5,7,7};

int main() {
    int n;
    while(scanf("%d", &n) && n){
        int a[n+1];
        rep(i, 0, n){
            string s;
            cin >> s;
            a[i+1] = s.length();
        }

        int ans = -1;
        rep(i, 1, n+1){
            int num_i = 0, cnt = 0;
            rep(j, i, n+1){
                cnt += a[j];
                if(num[num_i] == cnt){
                    num_i++;
                    cnt = 0;
                    if(num_i == 5){
                        ans = i;
                        break;
                    }
                }else if(cnt > num[num_i]){
                    break;
                }
            }
            if(ans != -1) break;
        }

        printf("%d\n", ans);
    }
}


Measured memory_bytes: 3172
h,w=map(int,input().split())
l_list=[]
v_list=[]
for i in range(h):
    sub_list=[0]*w
    l_list.append(sub_list)
    sub_list=[0]*w
    v_list.append(sub_list)
s_list=[]
for i in range(h):
    s=input()
    s_list.append(s)
for i in range(h):
    for j in range(w):
        if s_list[i][j]=='#':
            pass
        else:
            l_list[i][j]=l_list[i][j-1]+1
    for j in reversed(range(w)):
        if s_list[i][j]=='#':
            pass
        else:
            if not j==w-1 and not s_list[i][j+1]=='#':
                l_list[i][j]=l_list[i][j+1]
for j in range(w):
    for i in range(h):
        if s_list[i][j]=='#':
            pass
        else:
            v_list[i][j]=v_list[i-1][j]+1
    for i in reversed(range(h)):
        if s_list[i][j]=='#':
            pass
        else:
            if not i==h-1 and not s_list[i+1][j]=='#':
                v_list[i][j]=v_list[i+1][j]
Max=0
for i in range(h):
    for j in range(w):
        if s_list[i][j]=='.':
            Max=max(Max,l_list[i][j]+v_list[i][j]-1)
print(Max)
        



Measured memory_bytes: 123356
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;


using ll = long long;

#define int ll

using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;



const int N = 2e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 6e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-4;
const double PI = acos(-1.0);


//template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, a[N], pref[N], b[N], suff[N], x;
main() {
  file("lala");
  ios;
  cin >> n;
  fo(i, 1, n, 1) cin >> a[i], x ^= a[i];
  fo(i, 1, n, 1) b[i] = (x ^ a[i]);
  fo(i, 1, n, 1) pref[i] = (pref[i - 1] ^ b[i]);
  foo(i, n, 1, 1) suff[i] = (suff[i + 1] ^ b[i]);
  fo(i, 1, n, 1) cout << b[i] << " ";
  return 0;
}
/**

*/


Measured memory_bytes: 9796
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<algorithm>

using namespace std;

typedef long long int Int;

int main(void) {
    map<char,int> m;

    int n;
    cin>>n;
    for(int i = 0;i < n;i++) {
        char s;
        cin>>s;
        m[s]++;
    }

    if(m.size() == 3) {
        cout<<"Three"<<endl;
    } else {
        cout<<"Four"<<endl;
    }

    return 0;
}


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

int main(){
	int N, i, j, k, f;
	int alf[26];
	for(i = 0; i < 26; i++){
		alf[i] = 0;
	}
	char S[27];
	scanf("%s", S);
	for(i = 0; S[i] != '\0'; i++){
		alf[(int)S[i] - (int)'a'] = 1;
	}
	N = i;
	if(N < 26){
		for(i = 0; i < N; i++){
			printf("%c", S[i]);
		}
		for(i = 0; i < 26; i++){
			if(alf[i] == 0){
				printf("%c\n", (char)((int) 'a' + i));
				return 0;
			}
		}
	}
	else{
		for(i = N - 1; i >= 0; i--){
			for(j = (int)S[i] - (int)'a' + 1; j < 26; j++){
				f = 1;
				for(k = 0; k < i; k++){
					if((int)S[k] - (int)'a' == j){
						f = 0;
					}
				}
				if(f == 1){
					for(k = 0; k < i; k++){
						printf("%c", S[k]);
					}
					printf("%c\n", (char)((int) 'a' + j));
					return 0;
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	while( a > 0 && c > 0 )
	{
		c -= b;
		if( c <= 0 ) break;
		a -= d;
		if( a <= 0 ) break;
	}
	if( c <= 0 ) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	return 0;
}


Measured memory_bytes: 3128
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, P;
    cin >> N >> P;
    int A[51];
    rep(i, N) cin >> A[i];
    ll ans = 0;
    ll cnt0 = 0;
    ll cnt1 = 0;
    rep(i, N) if(A[i] % 2 == 0) cnt0++;
    cnt1 = N - cnt0;
    if(cnt0 == N) {
        if(P == 1)
            cout << 0 << endl;
        else
            cout << (1LL << cnt0) << endl;
        return 0;
    }
    cnt1--;
    cout << (1LL << cnt0) * (1LL << cnt1) << endl;


    return 0;
}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;

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

  ll sum = 0;

  rep(i, n + 1)
  {
    if (i % 3 != 0 && i % 5 != 0 && i % 15 != 0)
    {
      sum += i;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 3616
dropIf _ [] = []
dropIf op (x:xs) =
  if op x
  then dropIf op xs
  else (x:(dropIf op xs))

ans [] = []
ans (xa:ya:xb:yb:xc:yc:xd:yd:_) =
  let x1 = (xb-xa)
      y1 = (yb-ya)
      x2 = (xd-xc)
      y2 = (yd-yc)
      ip = x1 * x2 + y1 * y2
  in
    if ip == 0
    then "YES"
    else "NO"
ans x = "NO"

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Float]]
      i' = dropIf (== []) i
      o = map ans i'
  mapM_ putStrLn o

Measured memory_bytes: 4324
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end());
    if((n&1) || a[n/2]==a[n/2-1])
        cout<<0<<endl;
    else
        cout<<a[n/2]-a[n/2-1];
    return 0;
}


Measured memory_bytes: 640
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()
ans = 0
for i in range(n):
    if((i+1)%2!=0 and a[i]%2!=0):
        ans+=1
print(ans)

Measured memory_bytes: 68272
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Integer> list=new ArrayList<Integer>();
		int ans=0;
		for(int i = 0; i<n; i++){
			int a = sc.nextInt();
			int idx=Collections.binarySearch(list,a);
			if(idx>=0){
				ans++;
			}else{
				list.add(-idx-1,a);
			}
		}
		if(ans%2==1){
			ans++;
		}
		System.out.println(n-ans);
	}
}


Measured memory_bytes: 60460
<?php
$N = trim(fgets(STDIN));
$A = array_map('intval', explode(' ', trim(fgets(STDIN))));
$B = array_map('intval', explode(' ', trim(fgets(STDIN))));

$suff = 0;
$ovr = 0;
$S = 0;
$arr = [];
for ($i = 0; $i < $N; $i++) {
    if ($A[$i] < $B[$i]) {
        $suff++;
        $S += $B[$i] - $A[$i];
    } else {
        $arr[] = $A[$i] - $B[$i];
        $ovr += $A[$i] - $B[$i];
    }
}
if ($suff === 0) {
    $ans = 0;
} else if ($ovr < $S) {
    $ans = -1;
} else {
    sort($arr);
    $ans = $suff;
    while ($S > 0) {
        $ans++;
        $tmp = array_pop($arr);
        $S -= $tmp;
    }
}
echo $ans;


Measured memory_bytes: 23024
using System;

namespace aoj
{
    class Program
    {
        static void Main(string[] args)
        {
            var num = Console.ReadLine();
            int times =  int.Parse(num);

            int seconds = times % 60;
            int minutes = (times / 60) % 60;
            int hour = (times / 60) / 60;

            Console.WriteLine(hour + ":" + minutes + ":" + seconds);
        }
    }
}



Measured memory_bytes: 17944
#include<iostream>

using namespace std;

int main()
{
	int N,Q;
	int nAC[100001];
	string S;

	cin >> N >> Q >> S;

	for(int i=0;i<N+1;i++)
	{
		nAC[i] = 0;
	}
	nAC[0] = 0;
	nAC[1] = 0;
	int cnt = 0;
	for(int i=1;i<N;i++)
	{
		if(S[i-1] == 'A' && S[i] == 'C')
		{
			cnt++;
			
		}
		nAC[i+1] = cnt;
	}

	/*for(int i=1;i<N+1;i++)
	{
		cout << i << ":" << nAC[i] << endl;
	}*/

	for(int i=0;i<Q;i++)
	{
		int l,r;
		cin >> l >> r;
		cout << nAC[r] - nAC[l] << endl;
	}



	return 0;
}

Measured memory_bytes: 1408
import java.util.*;

class Main {

	static int days[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	static String name[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		for(;;){
			int m=in.nextInt(), d=in.nextInt();
			if(m==0&&d==0) break;
			System.out.println(solve(m,d));
		}
	}

	static String solve(int month, int date){
		int cur = 3;
		for(int i=0; i<month-1; i++) cur += days[i];
		cur += date-1;
		return name[cur%7];
	}

}

Measured memory_bytes: 12000
#include<cstdio>
int R,C,s[10000][10],f[10],N,i,j,n,m;void rec(int k){if(k<R){f[k]=0;rec(k+1);f[k]=1;rec(k+1);}else for(n=i=0;i<C;i++,n+=m>R-m?m:R-m,N=N>n?N:n)for(m=j=0;j<R;j++)m+=s[i][j]^f[j];}main(){for(;scanf("%d%d",&R,&C),R;rec(0),printf("%d\n",N))for(j=R;j-->0;)for(i=C;i-->0;)scanf("%d",s[i]+j);}

Measured memory_bytes: 1152
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    private static Queue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.dist - o2.dist;
        }
    });

    private static List<Node> nodeList = new ArrayList<Node>();

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int v = Integer.parseInt(scan.next());
        int e = Integer.parseInt(scan.next());
        int r = Integer.parseInt(scan.next());

        List<List<Edge>> edgeList = new ArrayList<List<Edge>>();
        for (int i = 0; i < v; i++) {
            List<Edge> list = new ArrayList<Edge>();
            edgeList.add(list);
        }

        for (int i = 0; i < e; i++) {
            int s = Integer.parseInt(scan.next());
            int t = Integer.parseInt(scan.next());
            int d = Integer.parseInt(scan.next());
            edgeList.get(s).add(new Edge(s, t, d));
        }
        scan.close();

        for (int i = 0; i < v; i++) {
            nodeList.add(new Node(i, Integer.MAX_VALUE));
        }

        addNode(nodeList.get(r), 0);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (Edge edge : edgeList.get(node.id)) {
                addNode(nodeList.get(edge.t), node.dist + edge.d);
            }
        }

        for (Node node : nodeList) {
            if (node.dist != Integer.MAX_VALUE) {
                System.out.println(node.dist);
            } else {
                System.out.println("INF");
            }
        }

    }

    private static void addNode(Node node, int newDist) {
        if (node.dist <= newDist) {
            return;
        }

        node.dist = newDist;
        queue.add(node);
    }

    static class Edge {
        int s;
        int t;
        int d;

        public Edge(int s, int t, int d) {
            this.s = s;
            this.t = t;
            this.d = d;
        }
    }

    static class Node {
        int id;
        int dist;

        public Node(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }

}



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

int main(){
  int N;
  cin >> N;
  string W[N];
  for(int i=0;i<N;i++){
    cin >> W[i];
  }

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(W[i]==W[j]&&i!=j){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  for(int i=1;i<N;i++){
    int d=W[i-1].size()-1;
    if(W[i-1][d]!=W[i][0]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
function Main(s){
	s=s.split(/\n|\s/);
	s.forEach(function(e,i,a){a[i]=Number(a[i]);});
	
	var a=0;
	for(var i=1;i<=s[0];i=(i+1)|0){
		while(s[i]%2==0){
			s[i]/=2;
			a++;
		}
	}
	
	console.log(a);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21448
#include<iostream>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N,Q;
    cin>>N>>Q;
    string S;
    cin>>S;
    char t[Q],d[Q];
    int ts=-1,te=N;
    for(int i=0;i<Q;i++){
        cin>>t[i]>>d[i];
    }
    for(int i=Q-1;i>=0;i--){
        if(te-ts<=1)break;
        if(d[i]=='L'){
            if(ts<N-1 && S[ts+1]==t[i])ts++;
            if(te<N && S[te]==t[i])te++;
        }else if(d[i]=='R'){
            if(0<=ts && S[ts]==t[i])ts--;
            if(0<te && S[te-1]==t[i])te--;
        }
    }
    cout<<N-(ts+1+N-te)<<endl;
    return 0;
}


Measured memory_bytes: 976
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<initializer_list>
#include<map>
#include<set>
#include<utility>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define llong long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()

string akiba(string s) {
	vector<string> can = {
		"KIHBR",
		"KIHBRA",
		"KIHBAR",
		"KIHBARA",
		"KIHABR",
		"KIHABRA",
		"KIHABARA",
		"AKIHBR",
		"AKIHBRA",
		"AKIHBAR",
		"AKIHABR",
		"AKIHABRA",
		"AKIHABAR",
		"AKIHABARA" };
	auto it = find(all(can), s);
	if (it != can.end())return "YES";
	else return "NO";
}
string akiba2(string s) {
	string s2(s);
	s2 = string(s2.begin(), remove(all(s2), 'A'));
	if (s2 != "KIHBR") return "NO";
	if (s.find("KIH") == string::npos) return "NO";
	int n = s.length();
	rep(i, n - 1) if (s[i] == s[i + 1])return "NO";

	return "YES";

}
string akiba3(string s) {
	regex reg("A?KIHA?BA?RA?");
	return regex_match(s, reg) ? "YES" : "NO";

}
int main() {
	string s;
	cin >> s;
	cout << akiba3(s) << endl;
	return 0;
}





Measured memory_bytes: 256
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())

        dic = {}
        for i in range(1,N+1):
            dic[i] = int(input())

        current_b = 1
        cnt = 1
        for _ in range(N):
            if dic[current_b] == 2:
                print(cnt)
                exit()
            else:
                cnt += 1
                current_b = dic[current_b]
        print(-1)


# Run main
if __name__ == '__main__':
    AtCoder().main()


Measured memory_bytes: 50776
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

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

    int n;cin>>n;
    string s;
    cin>>s;
    if(s.substr(0,n/2)==s.substr(n/2))yes;
    else no;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
sorted_ab = sorted(ab)

now = m
money = 0
for a,b in sorted_ab:
    if b <= now:
        now -= b
        money += a*b
    else:
        money += a*now
        break
print(money)

Measured memory_bytes: 28648
W, H, N = map(int, input().split())
P = [list(map(int, input().split())) for i in range(N)]
P.sort()
st = []
for x, y in P:
    while st and (st[-1][0] == x or st[-1][1] <= y):
        st.pop()
    st.append((x, y))

ans = 10**9
prv = 0
for x, y in st:
    ans = min(ans, prv+y)
    prv = x
ans = min(ans, prv)
print(ans)


Measured memory_bytes: 23552
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
using namespace __gnu_pbds;
typedef tree<pair<ll,pair<ll,ll> >, null_type, less<pair<ll,pair<ll,ll> > >, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
#define me BOSS
#define bug() cout<<"AIkahne aise"<<endl
#define PI acos(-1)
/* Precode Start Here *\
     Sieve
void sieve()
{
    for(ll i=3; i<=2000; i+=2)
    {
        for(ll j=i*i; j<=4000000; j+=i)
            A[j]=1;
    }
    v.push_back(2);
    for(ll i=3; i<=4000000; i+=2)
        if(A[i]==0)
            v.push_back(i);
}

     Power Function Modulo P

ll modPow(ll a, ll x, ll p) {
    //calculates a^x mod p in logarithmic time.
    long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}


   factorial

ll fact(ll n)
{
    ll ans=1;
    for(ll i=1;i<=n;i++)
    {
        ans=(ans*i)%mod;
    }
    return ans;
}
     Calculating nCr using Fermats law Theorem

ll modInverse(ll a, ll p) {
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p-2, p);
}


ll modBinomial(ll n, ll k, ll p) {
// calculates C(n,k) mod p (assuming p is prime).

    ll numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (ll i=0; i<k; i++) {
        numerator = (numerator * (n-i) ) % p;
    }

    ll denominator = 1; // k!
    for (ll i=1; i<=k; i++) {
        denominator = (denominator * i) % p;
    }

    // numerator / denominator mod p.
    return ( numerator* modInverse(denominator,p) ) % p;
}
     num of divisor and euler totient

ll phi[1000001],mark[1000001],divi[1000001];;
void divisorPhi(ll n)
{
    for(int i=1;i<=n;i++)
        phi[i]=i;
    for(int i=2;i<=n;i++)
    {
        if(!mark[i])
        {
            for(int j=i;j<=n;j+=i)
            {
                mark[j]=1;
                phi[j]*=(1-1/(double)i);
            }
        }
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i;j<=n;j+=i)
            divi[j]++;
    }
}
/* Precode Ends */
#define mod 1000000007
ll A[5000001],B[5000001];
vector<ll>v;
map<ll,ll>myMap;
set<ll>mySet;
vector<pair<ll,ll> >vp;
priority_queue<ll> pq;
priority_queue<ll, vector<ll>, std::greater<ll> > first;
ll po(ll a,ll n)
{
  ll ans=1;
  for(int i=1;i<=n;i++)
       ans*=a;
    return ans;
}

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

 ll n,ok=0;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
     cin>>A[i];
     ok^=A[i];
 }
 for(int i=1;i<=n;i++)
 {
     cout<<(ok^A[i])<<" ";
 }
return 0;
}



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

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(){
    int n;
    cin>>n;
    int a[100100],b[100100],c[100100];
    int da[100100],db[100100],dc[100100];
    rep(i,n) cin>>a[i]>>b[i]>>c[i];
    for(int i=0;i<n;++i){
        if(i==0){
            da[i]=a[i];
            db[i]=b[i];
            dc[i]=c[i];
        }
        else{
        da[i]=a[i]+max(db[i-1],dc[i-1]);
        db[i]=b[i]+max(da[i-1],dc[i-1]);
        dc[i]=c[i]+max(db[i-1],da[i-1]);
    }
    }
    int ans = max(da[n-1],db[n-1]);
    ans = max(ans,dc[n-1]);

    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	string str;
	cin >> str;
	if (str[str.size() - 1] == 's') {
		str.append("es");
	} else {
		str.append("s");
	}
	cout << str << endl;
}

Measured memory_bytes: 3628
s = str(input())

q = int(input())

d_list=[]
for i in range(q):
  s2 = ''
  
  d = list(map(str, input().split()))
  if d[0] == 'print':
    print( s[ int(d[1]): int(d[2])+1 ] )
    
  elif d[0] == 'reverse':
    S = list(s)
    S[int(d[1]):int(d[2])+1] = reversed(S[int(d[1]):int(d[2])+1])
    for i in S:
      s2 += i
    s = s2
   
  elif d[0] == 'replace':
    S = list(s)
    S[int(d[1]):int(d[2])+1] = list(d[3])
    for i in S:
      s2 += i
    s = s2


Measured memory_bytes: 5632
n = int(input())
num_list = [int(input()) for _ in range(n)]
ans_cnt = 1
end_cnt = 0
btn_idx = 0

while end_cnt < len(num_list):
    if num_list[btn_idx] == 2:
        print(ans_cnt)
        exit()
    else:
        btn_idx = num_list[btn_idx]-1
        ans_cnt += 1
    end_cnt += 1
print(-1)

Measured memory_bytes: 7084
import sys
input = sys.stdin.readline

# 自分の解答(模範解答と同じ)
def answer(N,M,A):
    total = N
    for a in A:
        total -= a
    return total if(total >= 0) else -1

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    print(answer(N,M,A))

if __name__ == '__main__':
   main()

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

Measured memory_bytes: 4336
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
int main (){
    string a1, b;
    cin >> a1 >> b;
    string a = a1+a1;
    int count;
    bool ans = false;
    for (int i = 0; i < a1.size(); i++){
        count = 0;
        for (int j = i; j < i+a1.size(); j++){
            if (b[j-i] == a[j]) count++;
        }
        if (count == a1.size()) ans = true;
    }
    if (ans == true) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
//vector<int> g1;
//g1.push_back(i);

using namespace std;

int main()
{
	int N;
	cin >> N;
	int tmp = N%1000;
	cout << (1000-tmp)%1000 << endl;
	return 0;
}



Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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; }
const int INF = 1e9;
const LL LLINF = 1e16;

using Graph = vector<vector<int>>;

LL now = 0;
int used[201010];
int ct[201010];
int ans[201010];
void dfs(Graph &G, int v){
    used[v] = 1;
    now += ct[v];
    repe(u, G[v]){
        if(!used[u]){
            dfs(G, u);
        }
    }
    ans[v] = now;
    now -= ct[v];

}


int main(){
    int n, q;
    cin >> n >> q;
    Graph G(n);
    rep(i, n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);

    }
    rep(i, q){
        int p, x;
        cin >> p >> x;
        p--;
        ct[p] += x;
    }
    dfs(G, 0);
    rep(i, n){
        cout << ans[i] << (i==n-1 ? "\n" : " ");
    }


    
}

Measured memory_bytes: 24832
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i=0; i<n; i++) cin >> h[i];
    vector<int64> dp(n,INT_MAX);

    dp[0] = 0;
    for (int i=0; i<n; i++) {
        for (int j=1; j<=k; j++) {
            if (i+j >= n) break;
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
        }
    }

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

Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
#define PI 3.1415926535897932384626433832795
using namespace std;

int main()
{
	int64 aa, bb, xx;
	cin >> aa >> bb >> xx;
	long double mm, cc = 90.0, dd = 0.0, tmp;
	while(cc - dd >= 0.0000001)
	{
		mm = (cc + dd) / 2.0;
		if(bb * tanl(PI * (90.0 - mm) / 180.0) <= aa)
		{
			tmp = bb * bb * tanl(PI * (90.0 - mm) / 180.0) * aa / 2.0;
		}
		else
		{
			tmp = aa * aa * bb - aa * aa * aa * tanl(PI * mm / 180.0) / 2.0;
		}
		if(tmp < xx)
		{
			cc = mm;
		}
		else
		{
			dd = mm;
		}
	}
	cout << fixed << setprecision(15);
	cout << mm << endl;
	return 0;
}


Measured memory_bytes: 3984
a = list(input())
b = list(input())
c = list(input())
turn = "a"
flag = True
while flag:
    if turn == "a":
        if not a == []:
            turn = a.pop(0)
        else:
            print("A")
            flag = False
    elif turn == "b":
        if not b == []:
            turn = b.pop(0)
        else:
            print("B")
            flag = False
    elif turn == "c":
        if not c == []:
            turn = c.pop(0)
        else:
            print("C")
            flag = False

Measured memory_bytes: 3064
#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
    int mountain[10];
    
    for(int i=0;i<10;i++)
        //scanf("%d",&mountain[i]);
	cin>>mountain[i];
    for(int i=0;i<10;i++){
        for(int j=9;j>i;j--){
	    if(mountain[j]>mountain[j-1]){
            int temp = 0;
			temp = mountain[j];
			mountain[j] = mountain[j-1];
			mountain[j-1] = temp;
	    }
	}
    }

    //結果出力
    for(int i=0;i<3;i++)
         cout<<mountain[i]<<'\n';
    return 0;
}

Measured memory_bytes: 1160
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

def main():
    while True:
        W, H = map(int, input().split())
        if W == 0:
            break
        board = [list(map(int, input().split())) for i in range(H)]
        check = [[False] * W for i in range(H)]

        def dfs(x, y):
            check[y][x] = True
            for nx, ny in [(x, y-1), (x+1, y-1), (x+1, y), (x+1, y+1), (x, y+1), (x-1, y+1), (x-1, y), (x-1, y-1)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if not check[ny][nx] and board[ny][nx] == 1:
                        dfs(nx, ny)

        ans = 0
        for y in range(H):
            for x in range(W):
                if not check[y][x] and board[y][x] == 1:
                    ans += 1
                    dfs(x, y)
        print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9896
import math

N = int(input())


def prime_factorization(n):
    from collections import Counter
    counter = Counter()

    if n < 2:
        return counter

    for i in range(2, int(n ** 0.5) + 1):
        if i * i > n:
            break

        while n % i == 0:
            counter[i] += 1
            n //= i

    if n > 1:
        counter[n] += 1

    return counter


p_fact = prime_factorization(N)

cnt = 0
for _, e in p_fact.items():
    val = math.sqrt(2 * e + 0.25) - 0.5
    val = int(val)
    cnt += val

print(cnt)



Measured memory_bytes: 9704
import java.util.*;

class Main{
    static boolean[] visited;
    static HashSet<Integer>[] map;
    static int ans;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        ans = 0;
        visited = new boolean[N+1];
        map = new HashSet[N+1];
        for(int i=0;i<map.length;i++) map[i]=new HashSet<Integer>();
        for(int i=0;i<M;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            map[a].add(b);
            map[b].add(a);
        }
        visited[1] = true;
        dfs(1);
        System.out.println(ans);
    }
    static void dfs(int i){
        boolean flag = true;
        for(int j=1;j<visited.length;j++) flag = flag&visited[j];
        if(flag) {
            ans++;
            return;
        }
        for(Integer w:map[i]){
            if(!visited[w]){
                visited[w] = true;
                dfs(w);
                visited[w] = false;
            }
        }
    }
}


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

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
// #define int long long

using namespace std;

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

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define eprintf(...) 42
#define dump(x) 42
#define debug(x) 42
#endif

typedef long long ll;

const ll MOD = 1e9 + 7;

bool solve(int N, int A, int B, int C, int D, string& S) {
    for (const auto pair : {make_pair(A, C), make_pair(B, D)}) {
        int left = pair.first - 1;
        int right = pair.second - 1;
        for (int i=left; i<right; i++) {
            if (S[i] == '#' && S[i+1] == '#') return false;
        }
    }
    if (D < C) {
        for (int i=B-1; i<=D-1; i++) {
            if (S[i-1] == '.' && S[i] == '.' && S[i+1] == '.') return true;
        }
        return false;
    }

    return true;
}

signed main() {
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;

    string S;
    cin >> S;

    bool answer = solve(N, A, B, C, D, S);

    cout << (answer ? "Yes" : "No") << '\n';
    
    return 0;
}



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

int main(){
  int a,b,k,n;
  cin >> a >> b >> k;
  for(int i = a;i >= 1;--i){
    if(a % i == 0 && b % i == 0){
      ++n;
      if(n == k)cout << i;
    
    }
  }
  return 0;
}

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

vector<ll> s,t;


int main(){
    ll N,Q;
    cin >> N;
    s.assign(N,0);
    for(ll i = 0;i < N;i++){
        cin >> s[i];
    }
    cin >> Q;
    t.assign(Q,0);
    for(ll i = 0;i < Q;i++){
        cin >> t[i];
    }
    
    int ans = 0;
    
    for(int i = 0;i < Q;i++){
        for(int j = 0;j < N;j++){
            if(t[i] == s[j]){
                ans++;
                break;
            }
        }
    }
    
    cout << ans << endl;
    
}


Measured memory_bytes: 3104
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;

int main(){
	int N; cin>>N;
	ll ans = 0;
	vector<ll> facts(N+1, 0);
	REP(i,N){
		for(int k = 1; i*k<= N; ++k){
			facts[i*k] ++;
		}
		ans += (facts[i]) * i;
		// cout<<facts[i]+1<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 81380