akhauriyash/Code-Regression huggingface dataset:
//package codeforces;

import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.TreeSet;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
import java.util.Set;

public class Main {
	// Integer.bitCount(i); count no of 1 bit in a given number
	static Scanner scn = new Scanner(System.in);
	static int mod = 1000000007;

	public static void main(String[] args) {
		// System.out.format("%.10f", ans);char c = sc.next().charAt(0);
		// code
		int n = scn.nextInt();
		long arr[] = new long[n];
		long memo[] = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = scn.nextLong();
		Arrays.fill(memo,-1);
		System.out.println(mincost(arr, 0, n,  memo));

	}

	public static long mincost(long arr[], int i, int n, long memo[]) {
		if (i == n - 1) {
			return 0;
		}
		if (i >= n) {
			return Integer.MAX_VALUE;
		}
		if (memo[i] != -1)
			return memo[i];

		long a = mincost(arr, i + 1, n,  memo)+ Math.abs(arr[Math.min(n - 1, i + 1)] - arr[i]);
		
		long b = mincost(arr, i + 2, n, memo)+ Math.abs(arr[i] - arr[Math.min(i + 2, n - 1)]);
		
		memo[i]=Math.min(a, b);
		return Math.min(a,b);
	}

	public static boolean[] sieveOfEratosthenes(int n) {

		boolean prime[] = new boolean[n + 1];
		for (int i = 0; i < n; i++)
			prime[i] = true;

		for (int p = 2; p * p <= n; p++) {
			// If prime[p] is not changed, then it is a prime
			if (prime[p] == true) {
				// Update all multiples of p
				for (int i = p * p; i <= n; i += p)
					prime[i] = false;
			}
		}

		for (int i = 2; i <= n; i++) {
			if (prime[i] == true) {
				// list.add(i);
			}

		}
		return prime;
	}

	public static class Pair implements Comparable {
		int x;
		int y;
		int z;

		Pair(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public int compareTo(Object o) {
			Pair pp = (Pair) o;
			if (pp.x == x)
				return 0;
			else if (x > pp.x)
				return 1;
			else
				return -1;
		}

	}

}


Measured memory_bytes: 75660
import java.util.*;
  
public class Main {
    Scanner sc = new Scanner(System.in);
  
    public static void main(String[] args) {
        new Main(); 
    }
  
    public Main() {
        new B().doIt();
    }
    class B{
    	int cn(int n,int m){
    		int a[] = new int [m];
    		for(int i = 0;i < m;i++){
    			a[i] = n % 10;
    			n = n / 10;
    		}
    		Arrays.sort(a);
    		for(int i = 0;i < m;i++){
    			n = n * 10;
    			n = n + a[m - i - 1] - a[i];
    		}
    		return n;
    	}
        void doIt(){
        	while(true){
        		TreeSet<Integer> ts = new TreeSet<Integer>();
        		ArrayList<Integer> array = new ArrayList<Integer>();
        		int n = sc.nextInt();
        		int m = sc.nextInt();
        		int cnt = 0;
        		if(n + m == 0)break;
        		while(ts.add(n)){
        			array.add(n);
//        			System.out.println(n);
        			n = cn(n,m);
        			cnt++;
        		}
        		for(int i = 0;i < n;i++){
        			if(n == array.get(i)){
        				System.out.println(i+" "+n+" "+(cnt-i));
        				break;
        			}
        		}
        		if(n == 0)System.out.println((array.size()-1)+" "+0+" "+(cnt-array.size()+1));
        	}
        }
    }
}

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

long long n,a,b,t1=0,t2=0,a1,a2,b1,b2;
//考虑相差为偶数,就直接输出 
int main(){
	cin>>n>>a>>b;
	if(abs(a-b)%2==0)cout<<abs(a-b)/2<<endl;
	else{
		//只能考虑一段去尽头,然后等待变偶的时候
		if(a>b)swap(a,b);
		a1=a,a2=a,b1=b,b2=b;
		//a去尽头 
		t1+=(a1-1);b1-=t1;a1=1;
		if(b1%2==0)b1--,t1++;
		t1+=abs(b1-a1)/2;
		//b去尽头
		t2+=(n-b2);a2+=t2;b2=n;
		if(b2%2!=a2%2)a2++,t2++;
		t2+=abs(b2-a2)/2;;
		cout<<min(t1,t2)<<endl;		
	}
}

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

int main() {
  int n; cin>>n;
  vector<int> x(n),y(n);
  rep(i, n) cin>>x[i]>>y[i];

  long double ans=0.0;
  int cnt=0;
  rep(i, n) {
    int t=i;
    while (t<n-1) {
      t++;
      cnt++;
      ans+=sqrt((x[i]-x[t])*(x[i]-x[t])+(y[i]-y[t])*(y[i]-y[t]));
    }
  }
  cout<<setprecision(10)<<ans*(long double)(n-1)/(long double)cnt<<endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main{
public static void main(String[]args){
 
  Scanner sc=new Scanner(System.in);
  
  int n =sc.nextInt();
  int[] l=new int[n*2];  
  
  for(int i=0; i<l.length; i++){
   l[i]=sc.nextInt();
}

sc.close();
  Arrays.sort(l);
  
  int ans=0;
  for(int i=0; i<l.length; i+=2){
    ans +=Math.min(l[i],l[i+1]);
}
System.out.println(ans);


}}

Measured memory_bytes: 9684
import sys
import math

def input():
    return sys.stdin.readline().strip()

def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def rinput():
    return map(int, tinput())

def rlinput():
    return list(rinput())

def pro(k, l, n):
    if l < n:
        if k == 0:
            return(n - l)
        return (n - l + 2)
    if l == n:
        if k == 0:
            return 0
        elif k == 1:
            return 1
        return 3
    else:
        l -= n - 1
        if l == k:
            return 1
        elif l > k:
            return 0
        if l < k - 1:
            return 2
        else:
            return 3
            

def rt(k, l , n):
    if k < n:
        if l == 0:
            return (k * 2 + n)
        return (n + k * 2 - 1)
    elif k == n:
        if l == 1:
            return (k * 3 - 2)
        elif l == 0:
            return (k * 3)
        return (k * 3 - 3)
    else:
        k -= n - 1
        if k == l:
            return (n * 3 - 2)
        elif k > l:
            return (n * 3)
        if k < l - 1:
            return ((n - 1) * 3 - 1)
        else:
            return ((n - 1) * 3)



def main():
    n = iinput()
    a = rlinput()
    res = a[0] + a[-1]
    for i in range(n - 2):
        if a[i] > a[i + 1]:
            res += a[i + 1]
        else:
            res += a[i]
    print(res)
    
    
    
    
    


main()



Measured memory_bytes: 38384
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>

using namespace std;

int main(){
	string s; cin >> s;
	int tmp1=0;
	for(int i=0; i<s.length(); i++){
		if(i%2 == 0) tmp1 += abs(s[i]-'0');
		else tmp1 += abs(s[i]-'1');
	}
	int tmp2=0;
	for(int i=0; i<s.length(); i++){
		if(i%2 == 0) tmp2 += abs(s[i]-'1');
		else tmp2 += abs(s[i]-'0');
	}

	cout << min(tmp1, tmp2) << endl;
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
	int n, i, a, min = 1000000, max = -1000000;
	long long sum = 0;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++) {
		scanf("%d", &a);
		
		if (min > a) min = a;
		if (max < a) max = a;
		sum += a;
	}
	
	printf("%d %d %ld\n", min, max, sum);
	
	return 0;
}

Measured memory_bytes: 600
A,B,C,X,Y = map(int,input().split())

CtoAB1 =0
CtoAB2 =0
AandB =0

if X >= Y:
    CtoAB1=2*C*Y+A*(X-Y)
    CtoAB2=2*C*X
else:
    CtoAB1=2*C*X+B*(Y-X)
    CtoAB2=2*C*Y

AandB=A*X+B*Y

print(min(CtoAB1,CtoAB2,AandB))

Measured memory_bytes: 9084
#include <algorithm>
#include <stdlib.h>
#include <string>
using namespace std;
using ll = long long;
using p = pair<int, int>;

int main(void){
  char N[4];
  scanf("%s", N);
  
  for (int i = 0; i < 3; ++i) {
    if(N[i] == '7' ) {
      printf("Yes\n");
      return 0;
    }
  }
  
  printf("No\n");
  
  return 0;
}


Measured memory_bytes: 1660
using System;
using System.Linq;

public class Test {
  public static void Main() {
    int N = int.Parse(Console.ReadLine().Trim());
    long[] H = Console.ReadLine().Trim().Split(' ')
		.Select(long.Parse)
		.ToArray();
    int count = 0;
    int maxCount = 0;
    
    for(var i = 1; i < H.Length; i++) {
      if(H[i - 1] >= H[i]) {
        count++;
      } else {
        if(count > maxCount) {
          maxCount = count;
        }
        count = 0;
      }
    }
    if(count > maxCount) {
      maxCount = count;
    }
    Console.WriteLine(maxCount);
  }
}

Measured memory_bytes: 31452
from collections import Counter


def main():
    n = int(input())
    aa = list(map(int, input().split()))
    cs_a0 = Counter(a for i, a in enumerate(aa) if i % 2 == 0)
    cs_a1 = Counter(a for i, a in enumerate(aa) if i % 2 == 1)
    vs_a0 = sorted(((v, k) for k, v in cs_a0.items()), reverse=True)
    vs_a1 = sorted(((v, k) for k, v in cs_a1.items()), reverse=True)
    if vs_a0[0][1] != vs_a1[0][1]:
        print(n - vs_a0[0][0] - vs_a1[0][0])
    else:
        res = 1 << 30
        if len(vs_a0) == 1 and len(vs_a1) == 1:
            res = n // 2
        if len(vs_a0) > 1:
            res = min(res, n - vs_a0[1][0] - vs_a1[0][0])
        if len(vs_a1) > 1:
            res = min(res, n - vs_a0[0][0] - vs_a1[1][0])
        print(res)


if __name__ == "__main__":
    main()


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

int main() {
  int n;
  double s;
  while (cin >> n, n) {
    vector<double> v(n);
    double sum = 0;
    for (auto& e : v) {
      cin >> e;
      sum += e;
    }
    double m = sum / n;
    sum = 0;
    for (auto& e : v) {
      sum += pow(e - m, 2);
    }
    double s = sqrt(sum / n);
    cout << fixed << setprecision(8) << s << "\n";
  }
}


Measured memory_bytes: 3292
import java.util.Scanner;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long n[] = new long[5];
		long min = 1000000000000000L;
		for(int i = 0; i < 5; i++){
			n[i] = sc.nextLong();
			if(n[i] < min){
				min = n[i];
			}
		}
		
		long x;
		if(N <= min){
			x = 1;
		}else if(N % min == 0){
			x = N / min;
		}else{
			x = N / min + 1;
		}
		
		System.out.println(4+x);
	}
}

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

int main(){
    int n = 0;
    int nmax = 0;
    string s;
    cin >> s;
    for(char c:s){
        if(c=='A' || c=='C' || c=='G' || c=='T') n++;
        else{
            nmax = max(nmax, n);
            n = 0;
        }
    }
    nmax = max(nmax, n);
    cout << nmax << endl;

    return 0;
}

Measured memory_bytes: 256
listal=[]
while True:
    try:
        listal.append(input())
    except:
        break
for i in listal:
    j=list(map(int,i.split()))
    y=(j[3]*j[2]-j[0]*j[5])/(j[1]*j[3]-j[0]*j[4])
    x=(j[2]-j[1]*y)/j[0]
    print('{:.3f}'.format(x),'{:.3f}'.format(y))
    



Measured memory_bytes: 5616
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SWAP(type, x, y) do { type tmp = x; x = y; y = tmp; } while (0)

#define MOD 1000000007 

//昇順
int asc(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}

int main(void){
    int N;
    scanf("%d",&N);

    //A[0]~A[N-1]に格納する
    int* A;
    NEW(A,N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    qsort(A,N,sizeof(int),asc);

    int ans=0;
    int tmp=1;
    for(int i=1;i<N;i++){
        if(A[i]==A[i-1]) tmp++;
        else{
            if(tmp%2==1) ans++;
            tmp=1;
        }
    }
    if(tmp%2==1) ans++;
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 892
import java.util.Scanner;

public class Main {
    int N;

    public static void main(String[] args) {
        Main m = new Main();
        m.read();
        m.solve();
    }

    private void read() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
    }

    private void solve() {
        long w = 0, n, h = 0;
        long a, b;
        for (n = 1; n <= 3500; n++) {
            for (h = 1; h <= 3500; h++) {
                a = 4 * h * n - N * (n + h);
                b = N * h * n;
                if (a > 0 && b > 0 && b % a == 0) {
                    w = b / a;
                    break;
                }
            }
            if (w != 0)
                break;
        }
        System.out.printf("%d %d %d\n", n, h, w);
    }
}


Measured memory_bytes: 22740
n=int(input())
l=list(map(int,input().split()))

c_4=0
even=0
odd=0

for i in l:
  if i%4==0:
    c_4+=1
  elif i%2==0:
    even+=1
  else:
    odd+=1
  
if even==0 and odd-1 <= c_4:
  ans="Yes"
else:
  ans="No"
  
if even>0 and odd <= c_4:
  ans="Yes"
else:
  "No"

print(ans)

Measured memory_bytes: 20000
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    S = input()
    res = S.count('.')
    c = res
    for s in S:
        if s == '.':
            c -= 1
            res = min(res, c)
        else:
            c += 1

    return str(res)

    
        

if __name__ == '__main__':
    print(solve())


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

int main() {
  
  int64_t N, T; cin >> N >> T;
  
  int64_t left = 0, right = T, ans = 0;
  
  for (int i = 0; i < N; i++) {
    
    int64_t t; cin >> t;
    
    if (i != 0 && left <= t && t <= right) ans -= right - t;
    
    ans += T; left = t; right = t + T;
    
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 3600
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)


N = int(input())

a = [[0]*10 for i in range(10)]

for i in range(1,N+1):
    n = str(i)
    a[int(n[0])][int(n[-1])] += 1

ans = 0
for i in range(1,10):
    for j in range(1, 10):
        ans += a[i][j]*a[j][i]

print(ans)





Measured memory_bytes: 93312
<?php
  list($h,$w,$m) = explode(" ", trim(fgets(STDIN)));
  $bh=[];
  $bw=[];
  $bm=[];
  for($i=0;$i<$m;$i++){
    list($a,$b) = explode(" ", trim(fgets(STDIN)));  
    if(!isset($bh[$a])) $bh[$a]=0;
    $bh[$a]++;
    if(!isset($bw[$b])) $bw[$b]=0;
    $bw[$b]++;
    if(!isset($bm[$a])) $bm[$a]=[];
    $bm[$a][$b]=true;
  }

  arsort($bh);
  arsort($bw);
  $ans=0;
  $i=0;
  $k1list=[];
  $k2list=[];
  $max=0;
  foreach($bh as $k => $v){
    if($i==0){
      $ans+=$v;
      $max=$v;
      $i++;
    }else{
      if($max > $v){
        break;
      }
    }
    $k1list[] = $k;
  }
  $i=0;
  foreach($bw as $k => $v){
    if($i==0){
      $ans+=$v;
      $max=$v;
      $i++;
    }else{
      if($max > $v){
        break;
      }
    }
    $k2list[] = $k;
  }
  $isBom=true;
  for($i=0;$i<count($k1list);$i++){
    for($j=0;$j<count($k2list);$j++){
//      echo $k1list[$i]." ".$k2list[$j].PHP_EOL;
      if(!isset($bm[$k1list[$i]][$k2list[$j]])){
        $isBom=false;
        break;
      }
    }
  }
  if($isBom) $ans--;
  echo $ans;

Measured memory_bytes: 193368
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
using namespace std;
void solve(){
  int n; cin >> n;
  vector<int> t(n);
  int sum = 0;
  for(int i = 0; i < n; i++){
    cin >> t[i];
    sum += t[i];
  }
  int m; cin >> m;
  vector<int> p(m), x(m);
  for(int i = 0; i < m; i++){
    cin >> p[i] >> x[i];
  }
  for(int i = 0; i < m; i++){
    cout << sum - t[p[i] - 1] + x[i] << endl;
  }
  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
const int N=2e5+5;
ll n,m,ans,last,shun[N],ni[N];
pll p[N];
bool f[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>p[i].F>>p[i].S;
	for(int i=1;i<=n;i++)shun[i]=shun[i-1]+p[i].S-p[i].F+p[i-1].F;
	for(int i=1;i<=n;i++)shun[i]=max(shun[i-1],shun[i]);
	p[n+1].F=m;
	for(int i=n;i>=1;i--)ni[i]=ni[i+1]+p[i].S-p[i+1].F+p[i].F;
	for(int i=n;i>=1;i--)ni[i]=max(ni[i],ni[i+1]);
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,shun[i]);
		ans=max(ans,ni[i]);
		ans=max(ans,shun[i]-p[i].F+ni[i+1]);
		ans=max(ans,ni[i]-(m-p[i].F)+shun[i-1]);
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

int main(){
  int n, c = 1;
  while(scanf("%d", &n) && n){
    double res = 0;
    vector<int>x(n+1), y(n+1), x1(n), y1(n);
    
    rep(i, n) scanf("%d%d", &y[i], &x[i]);
    x[n] = x[0]; y[n] = y[0];
    rep(i, n) x1[i] = x[i]-x[i+1], y1[i] = y[i]+y[i+1];

    rep(i, n) res += x1[i]*y1[i];
    res /= 2;
    printf("%d %.1lf\n", c, res);
    c++;
  }
  return 0;
}

Measured memory_bytes: 1220
//ABC118C
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include<stdio.h>
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> x(m), l(m);
	int ans =0;
	for(int i=0;i<m;i++){
		cin >> x.at(i);
	}
	if(n >= m){
		ans = 0;
	}else{
		sort(x.begin(),x.end());
		for(int i=0;i<m-1;i++){
			l.at(i) = x.at(i+1) - x.at(i);
		}
		sort(l.begin(),l.end());
		for(int i=0;i<m-n+1;i++){
			ans += l.at(i);
		}
	}
	cout << ans << endl;
}

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

static int cmp_int (const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

static int cmp_int_r (const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

int main (void) {
    int i;
    int n, m;
    scanf("%d%d", &n, &m);
    int x[m];
    for ( i=0; i<m; i++ )
        scanf("%d", &x[i]);

    qsort(x, m, sizeof(int), cmp_int);

    int all_diff = x[m-1] - x[0];
    int diff[m-1];
    for ( i=1; i<m; i++ )
        diff[i-1] = x[i] - x[i-1];
    qsort(diff, m-1, sizeof(int), cmp_int_r);
    for ( i=0; i<n-1 && i<m-1; i++ )
        all_diff -= diff[i];

    printf("%d\n", all_diff);
    return EXIT_SUCCESS;
}


Measured memory_bytes: 1268
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
nzero = s.count("0")
none = s.count("1")
print(len(s) - abs(nzero-none))


Measured memory_bytes: 3564
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
        if(i%k==0)
        {
            cout<<"OK\n";
            return 0;
        }
    cout<<"NG\n";
    return 0;
}


Measured memory_bytes: 3652
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXM 100000
#define MO 1000000007
using namespace std;
struct Matrix
{
	int M[4][4];
	Matrix operator * (const Matrix &b)
	{
		Matrix ret;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
			{
				ret.M[i][j]=0;
				for(int k=1;k<=3;k++)
					ret.M[i][j]=(1LL*ret.M[i][j]+1LL*M[i][k]*b.M[k][j]%MO)%MO;
			}
		return ret;
	}
};
int x[MAXM+5],N,M;
int finans[4],d[4];
Matrix PowMod(Matrix a,int b)
{
	Matrix ret;
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			if(i==j)
				ret.M[i][j]=1;
			else
				ret.M[i][j]=0;
		}
	while(b)
	{
		if(b&1)
			ret=ret*a;
		a=a*a;
		b>>=1;
	}
	return ret;
}
int main()
{
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++)
		scanf("%d",&x[i]),x[i]++;
	sort(x+1,x+1+M);
	Matrix ans,usu,ususpe;
	//===========================================
	usu.M[1][1]=1,usu.M[1][2]=0,usu.M[1][3]=0;
	usu.M[2][1]=1,usu.M[2][2]=1,usu.M[2][3]=0;
	usu.M[3][1]=1,usu.M[3][2]=2,usu.M[3][3]=1;
	//===========================================
	ususpe.M[1][1]=1,ususpe.M[1][2]=0,ususpe.M[1][3]=1;
	ususpe.M[2][1]=1,ususpe.M[2][2]=1,ususpe.M[2][3]=1;
	ususpe.M[3][1]=1,ususpe.M[3][2]=2,ususpe.M[3][3]=2;
	//===========================================
	d[1]=d[2]=d[3]=1;
	int pre=1;
	for(int i=1;i<=M;i++)
	{
		ans=PowMod(ususpe,x[i]-pre-1);
		memset(finans,0,sizeof(finans));
		for(int j=1;j<=3;j++)
			for(int k=1;k<=3;k++)
				finans[j]=(1LL*finans[j]+1LL*ans.M[j][k]*d[k]%MO)%MO;
		d[1]=finans[1],d[2]=finans[2],d[3]=finans[3];
		ans=usu;
		memset(finans,0,sizeof(finans));
		for(int j=1;j<=3;j++)
			for(int k=1;k<=3;k++)
				finans[j]=(1LL*finans[j]+1LL*ans.M[j][k]*d[k]%MO)%MO;
		d[1]=finans[1],d[2]=finans[2],d[3]=finans[3];
		pre=x[i];
	}
	ans=PowMod(ususpe,N-pre);
	memset(finans,0,sizeof(finans));
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			finans[i]=(1LL*finans[i]+1LL*ans.M[i][j]*d[j]%MO)%MO;
	printf("%d\n",finans[3]);
	return 0;
}

Measured memory_bytes: 512
using System;


    class Program
    {
        static void Main(string[] args)
        {

            for(int i = 1; i<10 ; i++)
            {
                for(int j = 1; j < 10; j++)
                {
                    Console.WriteLine("{0}x{1}={2}",i,j,i*j);
                }
            }
        }
    }

Measured memory_bytes: 9076
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;

int main(){
  int n, m;
  string lottery[101];
  int value[101];

  while(cin >> n >> m){
    if(n == 0 && m == 0) break;
    
    for(int i = 0 ; i < n ; i++){
      cin >> lottery[i] >> value[i];
    }
    string check;
    int ans = 0;
    while(m--){
      cin >> check;
      int a;
      for(int i = 0 ; i < n ; i++){
	for(a = 0 ; a < lottery[i].size() ; a++) if(lottery[i][a] != '*') break;
	
	if(lottery[i].substr(a) == check.substr(a)) ans += value[i];
      }
    }
    cout << ans << endl;    
  }
  return 0;
}

Measured memory_bytes: 928
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n, r;
  cin >> n >> r;
  if (10 <= n) {
    cout << r << endl;
  } else {
    cout << r + 100 * (10 - n) << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int a, b, c, x, answer = 0;
	scanf("%d\n%d\n%d\n%d", &a, &b, &c, &x);
	
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if (500 * i + 100 * j + 50 * k == x) {
					answer++;
				}
			}
		}
	}

	printf("%d\n", answer);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>

using namespace std;

#define ll long long
#define _ABS(x) (((x) < 0) ? (-(x)):(x))

int main()
{
	int W, H, x, y;

	scanf("%d %d %d %d", &W, &H, &x, &y);
	printf("%.10f ", 1.0*W*H / 2);
	
	if (x*1.0 == W*1.0 / 2 && y*1.0 == H*1.0 / 2) printf("1\n");
	else printf("0\n");

	return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a=set(a)
MOD=1000000007

dp=[0]*(n+1)
for i in range(1,n+1):
  if i in a:
    dp[i]=0
  else:
    if i==1:
      dp[i]=1
    elif i==2:
      dp[i]=dp[1]+1
    else:
      dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%MOD)

Measured memory_bytes: 460020
#include <cstdio>
#include <algorithm>

using namespace std;

struct Fr
{
  int n;
  int d;

  Fr (
    int n = 0,
    int d = 1
    )
  {
    this->n = n;
    this->d = d;
  }

  int
  operator>= (
    const struct Fr &x
    )
  const
  {
    return ( n * x.d >= x.n * d );
  }

  int
  operator== (
    const struct Fr &x
    )
  const
  {
    return ( d * x.n == n * x.d );
  }

  struct Fr
  operator+ (
    const struct Fr &x
    )
  const
  {
    return ( Fr ( d * x.n + n * x.d, d * x.d ) );
  }
};
typedef struct Fr Fr;

static Fr   f;
static int  a;

int
FSA (
  const Fr &sf,
  const int s,
  const int r
  )
{
  int res = 0;
  int i;

  if ( r <= 0 ) return ( 0 );

  for ( i = min ( s, a / sf.d ); i > 0; --i )
  {
    Fr nf = Fr ( 1, i ) + sf; 

    if ( nf == f ) ++res;
    if ( nf >= f ) break ;
    res += FSA ( nf, i, r - 1 );
  }

  return ( res );
}

int
main (
  )
{
  for ( ; ; )
  {
    int n;

    scanf ( "%d%d%d%d", &f.n, &f.d, &a, &n );
    if ( !( f.n | f.d | a | n ) ) break ;

    printf ( "%d\n", FSA ( Fr ( 0, 1 ), a, n ) );
  }

  return ( 0 );
}

Measured memory_bytes: 756
//code at gfg

#include <bits/stdc++.h>
using namespace std;

// Function to find the minimum number of
// characters to be replaced in string S2, such
// that S1 is a substring of S2
int minimumChar(string S1, string S2)
{
    // Get the sizes of both strings
    int n = S1.size(), m = S2.size();

    int ans = INT_MAX;

    // Traverse the string S2
    for (int i = 0; i < m - n + 1; i++) {
        int minRemovedChar = 0;

        // From every index in S2, check the number of
        // mis-matching characters in substring of
        // length of S1
        for (int j = 0; j < n; j++) {
            if (S1[j] != S2[i + j]) {
                minRemovedChar++;
            }
        }

        // Take minimum of prev and current mis-match
        ans = min(minRemovedChar, ans);
    }

    // return answer
    return ans;
}

// Driver Code
int main()
{
    string s,t;
    cin>>s>>t;
    
    cout << minimumChar(t, s);

    return 0;
}



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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int n;
bool visited[8];
bool p[8][8];

int dfs(int v) {
    bool all = true;
    rep (i, n) {
        if (visited[i] == false) all = false;
    }
    if (all) return 1;
    int res = 0;
    rep (i, n) {
        if (p[v][i] == false) continue;
        if (visited[i]) continue;
        visited[i] = true;
        res += dfs(i);
        visited[i] = false;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int m;
    cin >> n >> m;
    rep (i, n) {
        rep (j, n) {
            p[i][j] = false;
        }
        visited[i] = false;
    }
    rep (i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        p[a][b] = true, p[b][a] = true;
    }
    visited[0] = true;
    cout << dfs(0) << endl;
    
    return 0;
}



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

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

    int h[n];
    for(int i = 0; i < n; i++) cin >> h[i];

    bool good[n] = {};
    for(int i = 0; i < n; i++) good[i] = true;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        if(h[a] <= h[b]) {
            good[a] = false;
            // cout << a + 1 << " is no good" << endl;
        }
        if(h[a] >= h[b]) {
            good[b] = false;
            // cout << b + 1 << " is no good" << endl;
        }
    }

    int ans = accumulate(good, good + n, 0);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4124
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()

	fmt.Printf("ABC%3.3d\n", N)
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef string st;
typedef double db;
typedef vector<long long> vecll;
typedef vector<char> vechar;
typedef vector<string> vecst;

int main(){
    ll N;
    cin >> N;
    ll NN = N;
    ll sumN;
    while(N > 0){
        ll rem = N % 10;
        sumN += rem;
        N /= 10;
    }
    cout << (NN % sumN  ==0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string s;
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s; bool ok=1;
for (int i=0; i<s.size(); i++){
	if (i%2 and s[i]!='i') ok=0;
	if (i%2==0 and s[i]!='h') ok=0;
} if (s.size()%2) ok=0;
if (ok) cout << "Yes";
else cout << "No";
return 0;
}


Measured memory_bytes: 256
n,m,x = map(int, input().split())
data = []
for i in range(n):
    a = list(map(int, input().split()))
    data.append([a[0],a[1:]])
ans = 10**18
for i in range(pow(2,n)):
    i = list(("{:b}".format(i).zfill(n)))
    cost = 0
    learn = [0 for i in range(m)]
    for index,flag in enumerate(i):
        if int(flag):
            for j in range(m):
                learn[j] += data[index][1][j]
            cost += data[index][0]
    flag = True
    for j in range(m):
        if learn[j] < x:
            flag = False
    if flag:
        ans = min(ans, cost)
if ans == 10**18:
    print(-1)
else:
    print(ans)




Measured memory_bytes: 68976
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokenizer = null;
    int totalCases, testNum;

    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    void solve() throws IOException {

    }

    public static void main(String[] args) throws IOException {
        new Main().execute();
    }

    void debug(Object... os) {
        System.out.println(Arrays.deepToString(os));
    }

    int ni() throws IOException {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException {
        return Long.parseLong(ns());
    }

    double nd() throws IOException {
        return Double.parseDouble(ns());
    }

    String ns() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(br.readLine());
        }
        return tokenizer.nextToken();
    }

    String nline() throws IOException {
        tokenizer = null;
        return br.readLine();
    }

    void execute() throws IOException {
        int a = ni();
        int b = ni();
        out.println(a * b);
        
        out.close();
    }

    boolean input() throws IOException {
        return true;
    }

}


Measured memory_bytes: 25424
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    void solve() throws IOException {
        String s = ns();
        if(s.charAt(s.length()-1)=='s') s = s+"es";
        else s = s + "s";

        out.println(s);
    }

    final int mod = 1000000007;
    final BigInteger MOD = BigInteger.valueOf(mod);

    int mul(int x, int y){
        int val = (int)((x * 1L * y) % mod);
        return val>=0 ? val : val+mod;
    }
    int add(int x, int y) {
        x += y;
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    int sub(int x, int y){
        x = add(x,mod-y);
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }
 
    int ni() throws IOException {
        return Integer.parseInt(ns());
    }
 
    long nl() throws IOException {
        return Long.parseLong(ns());
    }
 
    double nd() throws IOException {
        return Double.parseDouble(ns());
    }
 
    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }
 
    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }
 
    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }
 
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
 
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 36872
#include<bits/stdc++.h>
#define M  1000005
#define LL long long
using namespace std;
int A[M];
int main(){
	int n,K;
	cin>>K>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
		A[i+n]=A[i];
	}
	int ans=2e9;
	for(int i=1;i<=n;i++){
		int j=i+n-1; 
		if(A[i]<=A[j])ans=min(ans,A[j]-A[i]);
		else ans=min(ans,K-A[j]+A[i]);
	}
	for(int i=n;i<=n+n;i++){
		int j=i-n+1;
		if(A[i]>=A[j])ans=min(ans,A[i]-A[j]);
		else ans=min(ans,A[i]+K-A[j]);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1792
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
use = [0, 2,5,5,4,5,6,3,7,6]


dp = [None  for _ in range(n+1)]
dp[0] = 0
for i in range(0, n+1):
  for j in a:
    if i+ use[j] < n+1 and dp[i] != None:
      if dp[i+use[j]] == None:
        dp[i+use[j]] = dp[i]*10+j
      else:
        dp[i+use[j]] = max(dp[i]*10+j, dp[i+use[j]])

print(dp[n])
    
  

Measured memory_bytes: 14692
package main

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

const (
	initialBufSize = 1e4
	maxBufSize     = 1e8
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	buf := make([]byte, initialBufSize)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func min(x, y int) int {
	if x > y {
		return y
	} else {
		return x
	}
}

func main() {
	A, B, C := nextInt(), nextInt(), nextInt()
	fmt.Println(min(C, B/A))
}


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

int n;
int v[100][100];
int d[100], f[100], r[202];

void stamp(int id, int t) {
	if (t > 2 * n)
		return;

	if (d[id - 1] == 0) {
		d[id - 1] = t;
		r[t] = id;
		int i = 0;
		while (v[id - 1][i] == 0)
			i++;
		if (i < n && d[i] == 0)
			stamp(i + 1, t + 1);
		else
			stamp(id, t + 1);
	}
	else if (f[id - 1] == 0) {
		int i;
		for(i = 0; i < n; i++)
			if (v[id - 1][i] == 1 && d[i] == 0) {
				stamp(i + 1, t);
				break;
			}
		if (i > n - 1) {
			f[id - 1] = t;
			for(int j = 1; j < d[id - 1]; j++)
				if (r[d[id - 1] - j] != 0) {
					if (f[r[d[id - 1] - j] - 1] == 0)
						stamp(r[d[id - 1] - j], t + 1);
				}

			int k = 0;
			while (d[k] != 0)
				k++;
			if (k < n)
				stamp(k + 1, t + 1);
		}
	}	
	return;
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++) {
		d[i] = 0;
		f[i] = 0;
	}

	for(int i = 0; i < 202; i++)
		r[i] = 0;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			v[i][j] = 0;

	for (int i = 0; i < n; i++) {
		int u, k, s;

		cin >> u >> k;

		for (int j = 0; j < k; j++) {
			cin >> s;
			v[u - 1][s - 1] = 1;
		}
	}

	stamp(1, 1);

	for (int i = 0; i < n; i++)
		cout << i + 1 << " " << d[i] << " " << f[i] << endl;

	return 0;
}


Measured memory_bytes: 3148
def solve():
    for row in range(H):
        for col in range(W):
            if (row < B and col < A) or (B <= row and A <= col):
                print(0, end='')
            else:
                print(1, end='')
        print()

if __name__ == "__main__":
    H, W, A, B = map(int, input().split())
    solve()

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

int sum(int n) {
  if(n==0 || n==1)
    return n;
  else
    return (n*(n+1))/2;
}

int main() {
  int N,L,c;
  cin >> N >> L;

  if(L>0)
    c=sum(N+L-1)-sum(L);
  else if(L==0)
    c=sum(N-1);
  else
    if(N<=-L)
      c=-sum(-L)+sum(-L-N+1);
    else
      c=-sum(-L)+sum(N+L-1);

  cout << c << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

bool flag = false;
int N, A[1 << 18];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		if (A[i] % 2 == 0 && (A[i] % 3 != 0 && A[i] % 5 != 0)) flag = true;
	}
	if (flag == true) cout << "DENIED" << endl;
	else cout << "APPROVED" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
//#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
//#include<set>
//#include<map>
//#include<list>

int main(void) {
	using namespace std;
	bool res = false;
	string N;
	cin >> N;
	if (N[0] == N[1] && N[1] == N[2] ) {
		res = true;
	}
	else if (N[1] == N[2] && N[2] == N[3]) {
		res = true;
	}

	if (res) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

int main(){
    int N;
    cin >> N;
    int A[N], B[N];
    for (int i=0; i<N; i++) {
        cin >> A[i];
        B[i] = A[i] - (i+1);
    }

    sort(B, B+N);
    int b;
    b = B[N/2];

    long ans = 0;
    for (int i=0; i<N; i++){
        ans += abs(B[i]-b);
    }
    cout << ans << endl;

}

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


void solve(long long A, long long B, long long K){
    REP(i, K){
        if(i % 2 == 0){
            A -= A % 2;
            B += A / 2;
            A /= 2;
        }else{
            B -= B % 2;
            A += B / 2;
            B /= 2;
        }
    }
    cout << A << ' ' << B << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long K;
    scanf("%lld",&K);
    solve(A, B, K);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

#define rep(i, N) for(int i = 0; i < (int)(N); i++)

int main(){
  int N, K;
  scanf("%d %d", &N, &K);
  
  int a[N];
  rep(j, N) scanf("%d", a + j);
  
  int dp[K + 1];
  rep(i, K + 1) dp[i] = 0;
  dp[0] = 0;
  rep(i, K) rep(j, N){
      if(i + a[j] <= K && dp[i] == 0) dp[i + a[j]] = 1;
  }
  
  if(dp[K]) puts("First");
  else puts("Second");
  
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <list>
#include <algorithm>
#include <map>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <list>
#include <string.h>
#include <unordered_map>
#include <ctype.h>
#include <queue>
#include <numeric>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <stack>
#include <ctime>
#define  lld  long long int
#define rep(i,start,end) for(lld i = start;i<end;i++)
#define newline cout << endl
#define fastio ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define in insert
#define mp make_pair
#define se second
#define fi first
#define starttime chrono::time_point<chrono::system_clock> start, end; start = chrono::system_clock::now()
#define showtime end = chrono::system_clock::now();  chrono::duration<double> elapsed_seconds = end - start; time_t end_time = chrono::system_clock::to_time_t(end); cout << "elapsed time: " << elapsed_seconds.count() << "s\n"
#define INF 1e17
lld MOD =  (lld)(1e19+7);
#define mh make heap
#define ph push_heap
#define poph pop_heap
#define openf   freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
using namespace std;
lld add(long long a, long long b){return ((a%MOD)+(b%MOD))%MOD;}
lld mul(long long a, long long b){return ((a%MOD)*(b%MOD))%MOD;}
lld sub(long long a, long long b){lld ans = ((a%MOD-b%MOD))%MOD; if(ans<0) ans += MOD; return ans;}
lld modInverse(lld a ){   lld m = MOD,m0 = m, y = 0, x = 1;  if (m == 1) return 0;   while (a > 1) {  lld q = a / m, t = m;  m = a % m, a = t, t = y;          y = x - q * y, x = t;   } if (x < 0)  x += m0; return x; } 
lld gcd(lld a, lld b){if (b == 0) return a; return gcd(b, a % b);}
void MAIN(lld i,lld t);
int get(){lld t;cin>>t; ; return t;}
template<class T> int logd(T name){cout<<name<<endl; return 0;}
void test(int t) { for(lld i = 0;i<t;i++){MAIN(i,t); cout <<endl;} }
lld power(lld x, lld y) { lld res = 1; x = x%MOD; if(x==0) return 0;   while (y > 0) {   if (y & 1)      res = (res*x)%MOD; y = y>>1; x = (x*x)%MOD;} return res; }
#define all(v) (v).begin(),(v).end()
lld popcount(lld x){return __builtin_popcountll(x);}
lld lcm(lld a,lld b){ return (a*b)/gcd(a,b);}
vector<lld>::iterator minmax(vector<lld> &a,lld i ,lld x){
    auto it = upper_bound(a.begin()+i,a.end(),x);
    return it;
}
void MAIN(lld current_test_case,lld total_test_cases){
    lld n,m,k;
    cin >> n >> m >> k;
    vector<lld> a(n),b(m);
    for(int i= 0 ;i<n;i++) cin >> a[i];
    for(int i = 0;i<m;i++) cin >> b[i];
    

    vector<lld> prefix_a,prefix_b;
    prefix_a = a; prefix_b = b;
    for(int i = 1;i<n;i++)
        prefix_a[i] +=prefix_a[i-1];
    for(int i = 1;i<m;i++)
        prefix_b[i] += prefix_b[i-1];
    lld sum = 0;
    lld ans = minmax(prefix_b,0,k) - prefix_b.begin();
    for(int i = 0;i<n;i++){
        sum += a[i];
        lld temp = 0;
        if(k-sum>=0) temp = i+1;
        ans = max(ans,(lld)(minmax(prefix_b,0,k-sum)-prefix_b.begin()+temp));
    }
    cout << ans << endl;
}  
int main(){  
    fastio;
    #ifndef ONLINE_JUDGE
     openf
    #endif
    test(1);
    return 0;
}




Measured memory_bytes: 9488
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		sc.close();
		if (S.charAt(0) == S.charAt(1) || S.charAt(1) == S.charAt(2) || S.charAt(2) == S.charAt(3))
			System.out.println("Bad");
		else
			System.out.println("Good");
		
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

struct Bridge {
	int l;
	int r;
	int64_t c;
};

class SegTree {

public:
	SegTree(int n, int64_t idt) {
		int m = 1;
		while (m < n) m *= 2;
		this->data_ = vector<int64_t>(2 * m, idt);
		this->idt_ = idt;
		this->m_ = m;
	}

	int64_t query(int i) {
		int64_t v = this->idt_;
		int idx = i + m_ - 1;
		v = min(v, this->data_[idx]);
		while (idx != 0) {
			bool from_left = (idx & 1);
			idx = (idx - 1) / 2;
			if (!from_left) continue;
			v = min(v, this->data_[idx]);
		}

		return v;
	}

	void update(int i, int64_t v) {
		if (v < query(i)) {
			int idx = i + m_ - 1;
			this->data_[idx] = v;

			while (idx != 0) {
				bool from_left = (idx & 1);
				idx = (idx - 1) / 2;
				if (!from_left) this->data_[idx] = min(this->data_[idx], v);
			}
		}
	}

private:
	vector<int64_t> data_;
	int     m_;
	int64_t idt_;
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int n, m; cin >> n >> m;
	vector<Bridge> bs(m);
	for (auto& b : bs) {
		cin >> b.l >> b.r >> b.c;
	}

	sort(bs.begin(), bs.end(), [](auto& lhs, auto& rhs) {
		if (lhs.l != rhs.l) return lhs.l < rhs.l;
		return lhs.r > rhs.r;
		});

	SegTree segt(n + 1, INT64_MAX);
	segt.update(1, 0);
	for (auto& b : bs) {
		int64_t v = segt.query(b.l);
		if (v == INT64_MAX) {
			continue;
		}

		segt.update(b.r, v + b.c);
	}

	int64_t v = segt.query(n);
	if (v == INT64_MAX) {
		cout << -1 << endl;
	}
	else {
		cout << v << endl;
	}

	return 0;
}

Measured memory_bytes: 3840
#include <stdio.h>
#define v 500000
#define V 2000000000

int L[v/2+2], R[v/2+2];
int c;

void merge(int A[], int n, int l, int m, int r)
{
  int i,j,k,n1,n2;

  n1 = m-l;
  n2 = r-m;
  for(i=0; i<n1; i++)
    L[i] = A[l+i];
  for(i=0; i<n2; i++)
    R[i] = A[m+i];

  L[n1] = R[n2] = V;

  i = 0;
  j = 0;
  for(k=l; k<r; k++){
    c++;
    if(L[i]<=R[j]) A[k] = L[i++];
    else A[k] = R[j++];
  }
}

void mergeSort(int A[], int n, int l, int r)
{
  int m;

  if(l+1<r){
    m = (l+r)/2;
    mergeSort(A, n, l, m);
    mergeSort(A, n, m, r);
    merge(A, n, l, m, r);
  }
}

int main()
{
  int n,i,A[v];

  scanf("%d",&n);
  c = 0;
  for(i=0; i<n; i++){
    scanf("%d",&A[i]);
  }
  mergeSort(A, n, 0, n);

  for(i=0; i<n-1; i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[n-1]);
  printf("%d\n",c);

  return 0;
}


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

int main() {
    int a, b;
    cin >> a >> b;

    if (a < b) cout << "a < b" << endl;
    if (a > b) cout << "a > b" << endl;
    if (a == b) cout << "a == b" << endl;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define f(i,a,b) for(ll i=a;i<b;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ii pair<ll,ll>
#define vii vector<ii>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define MAX 1e9

ll modpow(ll base, ll exp, ll modulus) {base %= modulus;ll result = 1;while (exp > 0) {if (exp & 1) result = (result * base) % modulus;base = (base * base) % modulus;exp >>= 1;}return result;}
const ld pi=acos(-1);

int main(){
    IOS;
    ll a,b,c;
    cin>>a>>b>>c;
    ll lefta=a-b;
    ll leftc=c-lefta;
    if(leftc<=0)cout<<0;
    else cout<<leftc;
    return 0;  
} 


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

int n, most;
vector<int> h;

void func(int index, int height) {
  if (index < 0) return;
  if (h[index-1] >= h[index]) {
    most = max(height+1, most);
    return func(index-1, height+1);
  } else {
    return func(index-1, 0);
  }

}

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

  func(n-1, 0);

  cout << most << endl;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define sz(v) (int)(v).size()
using namespace std;
using P = pair<int, int>;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, ans = 0;
	cin >> N;
	rep2(i, 1, N+1)
	{
		string s;
		s = to_string(i);
		if (sz(s) % 2 == 1) ans++;
	}
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define Sort(v, n) sort(v, v+n);
#define VSort(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define cY cout<<"Yes";
#define cN cout<<"No";
#define cA(a) cout<<a;
const ll MOD = 1000000007;



int main() {
    int n;string s;cin>>n>>s;
    int ans = 0;  
    for(int i = 2;i<n;i++) {
        if(s[i-2] == 'A' &&s[i-1] == 'B' && s[i] == 'C') ans++;
    }
    cout << ans;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
dList = list(map(int,input().split()))
result = deque()

for i in range(n):
  if (i % 2 == 0 and n % 2 == 0) or (i % 2 != 0 and n % 2 != 0):
   result.append(dList[i])
  else:
   result.appendleft(dList[i])

for i in result:
  print(i,end=" ")

print()


Measured memory_bytes: 25532