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

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


fn solve(s: Vec<char>) -> usize {
    let mut a = std::usize::MAX;
    let mut z = 0;
    for i in 0..s.len() {
        match s[i] {
            'A' => {
                if i < a {
                    a = i;
                }
            }
            'Z' => {
                if z < i {
                    z = i;
                }
            }
            _ => {}
        }
    }
    z - a + 1
}

fn main() {
    input!{
        s: chars
    }
    println!{"{}", solve(s)};
}


Measured memory_bytes: 4352
from fractions import gcd
from functools import reduce

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def lcm_mod(a, mod=-1):
    x = a[0]
    if mod == -1:
        for i in range(1, len(a)):
            x = (x * a[i]) // gcd(x, a[i])
    else:
        for i in range(1, len(a)):
            x *= (a[i] * mod_inv(gcd(x, a[i]), P)) % P
    return x

_,a = [list(map(int, s.split())) for s in open(0)]

P = 10**9 + 7
N = max(a)

lcm_ = lcm_mod(a, P)

ans = 0
for x in a:
    ans += int((lcm_*mod_inv(x,P))%P)
print(int(ans%P))

Measured memory_bytes: 6140
#include<bits/stdc++.h>
using namespace std;
struct compare
{
    bool operator()(const int& first, const int& second)
    {
        return first>second;
    }
};
void solve()
{
   int a, b, c;
   cin>>a>>b>>c;
   if(c-(a-b)<0) cout<<0<<endl;else cout<<c-(a-b)<<endl;
}

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


Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: i128,
    }

    let mut sum = 0;

    for i in 1..=n {
        sum += i;
        if sum >= n {
            let diff = sum - n;

            for j in 1..=i {
                if j != diff {
                    println!("{}", j);
                }
            }
            break;
        }
    }
}

Measured memory_bytes: 2156
n = int(input())
s = input()
num = []
#Aは６５番,Zは90番
for i in s:
    num.append(ord(i))

for i in range(len(num)):
    if num[i]+n>90:
        num[i] = chr(num[i]+n-90+64)
    else:
        num[i] = chr(num[i]+n)
a = ""
for i in num:
    a += i
print(a)

Measured memory_bytes: 41948
#include<stdio.h>
int main(){
	int a,x,Max=-1000000,min=1000000;
	long long int sum=0;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",&x);
		sum = sum + x;
		if(Max<x){
			Max = x;
		}
		if(min>x){
			min = x;
		}
	}
	printf("%d %d %lld\n",min,Max,sum);
	return 0;
}

Measured memory_bytes: 2732
#include<iostream>
#include<list>
#include<string>

using namespace std;

int main(){
    list<char> list;

    string s;
    cin >> s;
    for(int i=0;i<s.size();i++)
        list.push_back(s[i]);

    long long q; cin >> q;

    int status = 0;
    for(long long i=0;i<q;i++){
        int t; cin >> t;
        if(t == 1){
            if(status == 0)status=1;
            else status = 0;
        }else{
            int f; char c;
            cin >> f >> c;
            if(status == 0){
                if(f == 1)list.push_front(c);
                else list.push_back(c);
            }else{
                if(f == 1)list.push_back(c);
                else list.push_front(c);
            }
        }
    }

    if(status == 0){
        for(auto itr = list.begin(); itr != list.end(); ++itr) {
            cout << *itr;
        }
    }else{
        std::list<char>::reverse_iterator it = list.rbegin();
        for(; it != list.rend(); ++it) {
            cout << *it;
        }      
    }
    puts("");


}

Measured memory_bytes: 9984
import java.util.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        long m = 0L;
        long a = 0L;
        long r = 0L; 
        long c = 0L;
        long h = 0L;
        long[] D = new long[5];
        int[] x = {0, 0, 0, 0, 0, 0, 1, 1, 1, 2};
        int[] y = {1, 1, 1, 2, 2, 3, 2, 2, 3, 3};
        int[] z = {2, 3, 4, 3, 4, 4, 3, 4, 4, 4};

        for(int i=0; i<N; i++){
            String s = sc.next();
            if(s.charAt(0)=='M') m++;
            if(s.charAt(0)=='A') a++;
            if(s.charAt(0)=='R') r++;
            if(s.charAt(0)=='C') c++;
            if(s.charAt(0)=='H') h++;
        }
        D[0] = m;
        D[1] = a;
        D[2] = r;
        D[3] = c;
        D[4] = h;

        long ans = 0L;
        for(int i=0; i<10; i++){
            ans += 0L + D[x[i]] * D[y[i]] * D[z[i]];
        }
        System.out.println(ans);
    }
}

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

typedef long long ll;

int main() {
    double A, B, H, M, P = 3.141592653589793238462643383279;
    cin >> A >> B >> H >> M;
    H = H * 2 * P / 12 + M * 2 * P / 720;
    M = M * 2 * P / 60;
    double t = abs(H - M);
    double x = cos(t) * A;
    double y = sin(t) * A;
    double d = sqrt((x - B) * (x - B) + y * y);
    cout << fixed << setprecision(20) << d << "\n";
}

Measured memory_bytes: 3996
N, M = map(int,input().split())

for x in range(0,N+1):
	for y in range(0,N+1):
		if x + y <= N:
			z = N - (x + y)
			if x + y + z == N:
				if x * 10000 + y * 5000 + z * 1000 == M:
					print(x,y,z)
					exit()
print(-1,-1,-1)

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

int main(){
	char text[81],yeah[81];
	int i,j,over=0,last,ans=-1,ans2=-1,ans3=-1,the[3],that[4],thiss[4];
	while(scanf("%[^\n]%*c",text)!=EOF){
		int ouch=0,ans=-1,ans2=-1,ans3=-1;
		for(i=0;i<=80;i++){
			if(text[i]==NULL)
				break;
			}
		last=i;
		int box[last];
		i=0;
	
		for(i=0;i<=last-1;i++){
			box[i]=text[i];
		}
	
		i=0;
		for(i=0;i<=25;i++){
			if(i>6)
				over=26;
			the[0]=116+i-over;
			over=0;
			
			if(i>18)
				over=26;
			the[1]=104+i-over;
			over=0;
			
			if(i>21)
				over=26;
			the[2]=101+i-over;
			over=0;
			
			for(j=0;j<=last-3;j++){
				if((the[0]==box[j])&&(the[1]==box[j+1])&&(the[2]==box[j+2])&&(isalpha(box[j+3])==0))
				ans=i;
			}
		}
		i=0;
		for(i=0;i<=25;i++){
			
			if(i>6)
				over=26;
			that[0]=116+i-over;
			over=0;
			
			if(i>18)
				over=26;
			that[1]=104+i-over;
			over=0;
			
			if(i>25)
				over=26;
			that[2]=97+i-over;
			over=0;
			
			if(i>6)
				over=26;
			that[3]=116+i-over;
			over=0;
			
			for(j=0;j<=last-4;j++){
				if((that[0]==box[j])&&(that[1]==box[j+1])&&(that[2]==box[j+2])&&(that[3]==box[j+3])&&(isalpha(box[j+4])==0))
					ans2=i;
			}
		}
				
				
		for(i=0;i<=25;i++){
			
			if(i>6)
				over=26;
			thiss[0]=116+i-over;
			over=0;
			
			if(i>18)
				over=26;
			thiss[1]=104+i-over;
			over=0;
			
			if(i>17)
				over=26;
			thiss[2]=105+i-over;
			over=0;
			
			if(i>7)
				over=26;
			thiss[3]=115+i-over;
			over=0;
			
			for(j=0;j<=last-4;j++){
				if((thiss[0]==box[j])&&(thiss[1]==box[j+1])&&(thiss[2]==box[j+2])&&(thiss[3]==box[j+3])&&(isalpha(box[j+4])==0))
				ans3=i;
			}
		}
	
		if(ans!=-1){
			for(i=0;i<=last-1;i++){
				if((box[i]<(ans+97))&&(isalpha(box[i])!=0))
					box[i]=box[i]-ans+26;
				else
					box[i]-=ans;
			}
			ouch=-1;
		}
	
		if((ans2!=-1)&&(ouch!=-1)){
			for(i=0;i<=last-1;i++){
				if((box[i]<(ans2+97))&&(isalpha(box[i])!=0)){
					box[i]=box[i]-ans2+26;
				}
				else{
					box[i]-=ans2;
				}
			}
			ouch=-1;
		}
		
		if((ans3!=-1)&&(ouch!=-1)){
			for(i=0;i<=last-1;i++){
				if((box[i]<(ans3+97))&&(isalpha(box[i])!=0)){
					box[i]=box[i]-ans3+26;
				}
				else{
					box[i]=box[i]-ans3;
				} 
			}
		}
	
		for(i=0;i<=last-1;i++){
			yeah[i]=box[i];
			if(isalpha(yeah[i])!=0)
				printf("%c",yeah[i]);
			else
				printf("%c",text[i]);
		}
		printf("\n");
	}
	
	return 0;
}



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

int main(){
  int n;
  while(cin>>n && n){
    int mp=0;
    int md=0;
    for(int i=0;i<n;i++){
      int p,d1,d2;
      cin>>p>>d1>>d2;
      if(md < d1+d2){
	mp=p;
	md=d1+d2;
      }
    }
    cout<<mp<<" "<<md<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || '9'<ch)ch=getchar();
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x;
}

const int N=200009;

int n,k,a[N],buc[N];

int main()
{
	if(fopen("vj.in","r"))
	{
		freopen("vj.in","r",stdin);
		freopen("vj.out","w",stdout);
	}

	n=read();k=read();
	for(int i=1;i<=n;i++)
		buc[a[i]=read()]++;
	sort(buc+1,buc+200000+1);
	reverse(buc+1,buc+200000+1);

	int ans=0;
	for(int i=k+1;i<=200000;i++)
		ans+=buc[i];
	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 1792
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	var H int
	var W int
	var K int
	fmt.Scan(&H)
	fmt.Scan(&W)
	fmt.Scan(&K)
	sc.Split(bufio.ScanWords)
	tmp := make([][]bool, H)
	for i := 0; i < H; i++ {
		str := nextLine()
		l := []bool{}
		for j := 0; j < W; j++ {
			if string(str[j]) == "#" {
				l = append(l, true)
			} else {
				l = append(l, false)
			}
		}
		tmp[i] = l
	}
	test := [][][]bool{tmp}
	for i := 0; i < H; i++ {
		for _, t := range test {
			tt := chc(t, i)
			test = append(test, tt)
		}
	}
	for i := 0; i < W; i++ {
		for _, t := range test {
			test = append(test, chl(t, i))
		}
	}
	count := 0
	for _, t := range test {
		if helper(t) == K {
			count++
		}
	}
	fmt.Print(count)
}
func chc(m [][]bool, p int) [][]bool {
	ret := make([][]bool, len(m))
	for i, l := range m {
		tmp := []bool{}
		for _, c := range l {
			if i == p {
				tmp = append(tmp, false)
			} else if c == true {
				tmp = append(tmp, true)
			} else {
				tmp = append(tmp, false)
			}
		}
		ret[i] = tmp
	}
	return ret
}
func chl(m [][]bool, p int) [][]bool {
	ret := make([][]bool, len(m))
	for j, l := range m {
		tmp := []bool{}
		for i, c := range l {
			if i == p {
				tmp = append(tmp, false)
			} else if c == true {
				tmp = append(tmp, true)
			} else {
				tmp = append(tmp, false)
			}
		}
		ret[j] = tmp
	}
	return ret
}
func helper(ma [][]bool) int {
	count := 0
	for _, l := range ma {
		for _, c := range l {
			if c == true {
				count++
			}
		}
	}
	return count
}
func nextLine() string {
	sc.Scan()
	return sc.Text()
}
func nextInt() int64 {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return int64(i)
}
func MySort(a []int) {
	sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })

}
func SortedBinaryAppend(sortedArr []int, targetValue int) []int {
	return []int{}
}
func SortedBinaryDelete(sortedArr []int, targetValue int) []int {
	return []int{}
}
func SortedBinarySearch(sortedArr []int, targetValue int) int {
	post := len(sortedArr) - 1
	pre := 0
	for {
		div := (post + pre) / 2
		tim := sortedArr[div]
		if tim == targetValue {
			return pre + div
		} else if tim > targetValue {
			post = tim
		} else {
			pre = tim
		}
		if pre == post {
			return -1
		}
	}
}
func Abs(i int) int {
	if i < 0 {
		return -1 * i
	}
	return i
}
func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func CalcNum(tate int, yoko int, A int, B int, dp *map[[2]int]int) int {
	if (*dp)[[2]int{tate, yoko}] != 0 {
		return (*dp)[[2]int{tate, yoko}]
	}
	return yoko*CalcNum(tate-1, yoko, A, B, dp) + tate*CalcNum(tate, yoko-1, A, B, dp)
}
func arrSum(arr []int) int {
	sum := 0
	for _, a := range arr {
		sum += a
	}
	return sum
}
func scanNums(len int) (nums []int) {
	var num int
	for i := 0; i < len; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	return
}
func scanStrings(len int) (strings []string) {
	var str string
	for i := 0; i < len; i++ {
		fmt.Scanf("%s", &str)
		strings = append(strings, str)
	}
	return
}


Measured memory_bytes: 3024
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <limits.h>

int cmp(const void* p, const void* q) {
	return *(int*)p - *(int*)q;
}

int main(void) {
	int n;
	char s[300000];
	int cnt[300000] = { 0 };
	int temp = 0;

	scanf("%d", &n);
	scanf("%s", s);
	for (int i = 1; i < n ; i++) {
		if (s[i - 1] == 'W')temp ++;
		cnt[i] = temp;
	}
	temp = 0;
	for (int i = n - 2; i >= 0; i--) {
		if (s[i + 1] == 'E')temp++;
		cnt[i] += temp;
	}
	qsort(cnt, n, sizeof(int), cmp);
	printf("%d", cnt[0]);
	return 0;
}


Measured memory_bytes: 2812
#include<bits/stdc++.h>
#define fi first
#define se second
#define bug cout<<"--------------"<<endl
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=1e9;
const ll llf=1e18;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
vector<int>g[maxn];
int c[maxn];
int d[maxn],b[maxn];
int a[maxn];
ll ans=0;
void dfs1(int u,int fa){
	d[u]=d[fa]+1;
	for(int x:g[u]){
		if(x==fa) continue;
		dfs1(x,u);
	}
}
void dfs2(int u,int fa){
	for(int x:g[u]){
		if(x==fa) continue;
		ans+=min(a[x],a[u]);
		dfs2(x,u);
	}
}
int cmp(int x,int y){
	return d[x]<d[y];
}
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n;
	for(int i=1,a,b;i<n;i++){
		cin>>a>>b;
		g[a].push_back(b); 
		g[b].push_back(a);
	}
	dfs1(1,0);
	for(int i=1;i<=n;i++){
		cin>>c[i];
		b[i]=i;
	}
	sort(c+1,c+n+1);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++){
		a[b[i]]=c[n-i+1];
	}
	dfs2(1,0);
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 3584
// Aizu Vol-1 0113: Period
// 2017.10.23 bal4u@uu

#include <stdio.h>
#include <string.h>

char buf[130], *p;
int getInt(void)
{
	int n;
	if (*p == ' ') p++;
	n = 0; while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

#define MAX 1000000
int rr[MAX+2];
char sps[100], hat[100];

int main()
{
	int a, b, r, k;
	int i, w;

	memset(sps, ' ', sizeof(sps)), memset(hat, '^', sizeof(hat));
	while (fgets(p=buf, 128, stdin) != NULL) {
		a = getInt(), b = getInt();
		memset(rr, -1, sizeof(int)*b);
		for (rr[a] = 0, k = 1; ; k++) {
			a *= 10;
			putchar('0' + a / b);
			if ((r = a % b) == 0) { putchar('\n'); break; }
			if (rr[r] >= 0) {
				putchar('\n');
				i = w = rr[r];
				sps[i] = 0, printf(sps), sps[i] = ' ';
				hat[k-w] = 0, puts(hat), hat[k-w] = '^';
				break;
			}
			rr[r] = k, a = r;
		}
	}
	return 0;
}

Measured memory_bytes: 5592
#include <iostream>
using namespace std;
int main(void){
    int n;
    int i;
    int j;
    int tmp;
    int ans;
    
    cin >> n;
    int nums[n];
    i = -1;
    while (++i < n)
        cin >> nums[i];
    i = -1;
    while (++i < n)
    {
        j = i;
        while (++j < n)
        {
            if (nums[i] < nums[j])
            {
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
    }
    ans = 0;
    i = -1;
    while (++i < n)
    {
        if (i % 2 == 0)
            ans += nums[i];
        else
            ans -= nums[i];
    }
    cout << ans << endl;
}


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

const int maxn = 3005;

double dp[maxn][maxn];

double p[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n ; i++)
    {
        scanf("%lf",&p[i]);
    }

    dp[0][0] = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            dp[i+1][j+1] += dp[i][j] * p[i];
            dp[i+1][j]   += dp[i][j] * (1 - p[i]);
        }
    }

    double ans = 0;
    
    // for(int i = 0; i <= n; i++)
    // {
    //     for(int j = 0; j <= n; j++)
    //     {
    //         printf("%.3lf ", dp[i][j]);    
    //     }
    //     puts("");
    // }

    for(int i = n/2 + 1; i <= n; i++)
    {
        ans += dp[n][i];
    }

    printf("%.9lf\n",ans);

    return 0;
}

Measured memory_bytes: 70656
#include<stdio.h>
int main(){
  int s[10000],t[500],n,q,i,j,count=0,k;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
   scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&t[i]);
  }
  for(i=0;i<q;i++){
    k=t[i];
      for(j=0;j<n;j++){
	if(k==s[j]){
	  count++;
	  break;
	}
      }
  }
  printf("%d\n",count);
  return 0;
}
		    
	  



Measured memory_bytes: 2104
import sys
batch = 0
lines = 0
ans = []
for line in sys.stdin:
    if line == None or line == '\n':
        break
        
    cur = line.split(" ")
    if len(cur) == 1:
        lines = int(cur[0])
        batch = 0
        continue
    
    else:
        batch += 1
        if int(cur[0]) < int(cur[1]) + int(cur[2]):
            ans.append(0)
        elif (int(cur[0]) - int(cur[1]) - int(cur[2])) % 2 == 0:
            ans.append(1)
        else:
            ans.append(0)
        
        if batch == lines:
            prod = 1
            for n in ans:
                prod *= n
            if prod == 0:
                print("No")
            else:
                print("Yes")

Measured memory_bytes: 3936
N = int(input())
A = list(map(int, input().split()))

ball = [0] * N
ans = []

for i in range(1, N+1) :
    ballCount = sum(ball[N-i::N-i+1])
    if ballCount % 2 == A[N-i] :
        pass
    else :
        ball[N - i] = 1
        ans.append(N - i + 1)
print(len(ans))
print(*ans)


Measured memory_bytes: 14012
#include<stdio.h>
int main(void)
{
	int n;
	int a[100];
	int x,y,z,f,i,j;
	int asum,bsum,sum;
	asum=0;
	bsum=0;
	sum=0;
	f=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(x=0;x<n-1;x++){
		for(y=x+1;y<n;y++){
			if(a[x]<a[y]){
				f=a[x];
				a[x]=a[y];
				a[y]=f;
			}
		}
	}
	for(j=0;j<n;j++){
		if(j%2==0){
			asum+=a[j];
		}
		else{
			bsum+=a[j];
		}
	}
	sum=asum-bsum;
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>

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

  long long int ans = 0;

  for(long int i = 1;i <= N;i++){
    if((i%3 != 0)&&(i%5) != 0){
      ans += i;
    }
  }

  printf("%lld",ans);
  return 0;
}

Measured memory_bytes: 1724
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = k()
if N % 1000 == 0:
    print(0)
    sys.exit()
a = N // 1000
print(1000*(a+1)-N)


Measured memory_bytes: 9952
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
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; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 998244353; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;

void y(bool c) {
	if (c)print("Yes");
	else print("No");
}

struct edge {
	int to, cost;
};
vector<edge>G[200020];
ll dist[200020];
void dfs(int n, int pre,int res) {
	dist[n] = res;
	for (auto e : G[n]) {
		if (e.to == pre)continue;
		dfs(e.to, n, res + e.cost);
	}
}
void solve() {
	int N; cin >> N;
	REP(i, N - 1) {
		int u, v, c; cin >> u >> v >> c;
		u--, v--;
		G[u].push_back({ v,c });
		G[v].push_back({ u,c });
	}
	int Q, K; cin >> Q >> K;
	K--;
	dfs(K, K, 0);
	while (Q--) {
		int x, y; cin >> x >> y;
		x--, y--;
		print(dist[x] + dist[y]);
	}
}



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



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

long modpow(long a, long n, long mod) {
    long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long modinv(long a, long mod) {
    return modpow(a, mod - 2, mod);
}

int main()
{
    int N, M;
    cin >> N >> M;
    int s[10], c[10];
    REP(i, M)
        cin >> s[i] >> c[i];
    bool flag = true;
    int temp1 = -1;
    REP(i, M)
        if(s[i] == 1 + N - 3 && temp1 == -1)
            temp1 = c[i];
        else if(s[i] == 1 + N - 3 && temp1 != c[i]){
            cout << -1 << endl;
            flag = false;
        }
    int temp2 = -1;
    REP(i, M)
        if(s[i] == 2 + N - 3 && temp2 == -1)
            temp2 = c[i];
        else if(s[i] == 2 + N - 3 && temp2 != c[i]){
            cout << -1 << endl;
            flag = false;
        }
    int temp3 = -1;
    REP(i, M)
        if(s[i] == N && temp3 == -1)
            temp3 = c[i];
        else if(s[i] == N && temp3 != c[i]){
            cout << -1 << endl;
            flag = false;
        }
    if(flag){
    if(N == 3){
        if(temp1 == 0)
            cout << -1 << endl;
        else{
            if(temp1 == -1)
                temp1 = 1;
            if(temp2 == -1)
                temp2 = 0;
            if(temp3 == -1)
                temp3 = 0;
            cout << temp1 * 100 + temp2 * 10 + temp3 << endl;
        }
    }else if(N == 2){
        if(temp1 != -1 || temp2 == 0)
            cout << -1 << endl;
        else{
            if(temp2 == -1)
                temp2 = 1;
            if(temp3 == -1)
                temp3 = 0;
            cout << temp2 * 10 + temp3 << endl; 
        }
    }else{
        if(temp1 != -1 || temp2 != -1)
            cout << -1 << endl;
        else{
            if(temp3 == -1)
                temp3 = 0;
            cout << temp3 << endl; 
        }
    }
    }

    return 0;
}



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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=3.141592653589793;
const ll MOD=1e9+7;

int main() {
    int k;
    cin>>k;
    ll ans=0;
    for (int i=1;i<k+1;i++){
        for (int j=1;j<k+1;j++){
            for (int l=1;l<k+1;l++){
                ll ans1=__gcd(i,__gcd(j,l));
                ans+=ans1;
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3596
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

vector<vector<int>> xs;

int main(void) {
    int N, D;
    cin >> N >> D;

    xs.resize(N);
    for (int i = 0; i < N; i++) {
        xs[i].resize(D);
        for (int j = 0; j < D; j++) {
            cin >> xs[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            ll acc = 0;
            for (int k = 0; k < D; k++) {
                int x = (xs[i][k] - xs[j][k]);
                x *= x;
                acc += x;
            }

            for (int d = 1; d <= 200; d++) {
                if (acc == d * d) {
                    ans++;
                    break;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
     public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	int H;
    	int W;
    	
    	for(;;){
    		H = scan.nextInt();
        	W = scan.nextInt();
        	if(H == 0 && W == 0){
        		break;
        	}
        	
        	for(int y = 0; y < H; y++){
        		for(int x = 0; x < W; x++){
        			System.out.print("#");
        		}
        		System.out.println("");
        	}
         System.out.println("");
        	
    	}
    	
     }
}

Measured memory_bytes: 33260
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int t = scanner.nextInt();
		int total = 0;
		int now = scanner.nextInt();//0
		for(int i = 0; i < n - 1; i++){
			int next = scanner.nextInt();
			if((next - now) < t){
				total += next - now;
			} else {
				total += t;
			}
			now = next;
		}
		total += t;
		System.out.println(total);
	}
}

Measured memory_bytes: 63592
n , m , q = map(int,input().split())
p = []
for i in range(q):
    a , b , c , d = map(int,input().split())
    p.append([a,b,c,d])
ans = 0
for a1 in range(1,m+1):
    for a2 in range(a1,m+1):
        for a3 in range(a2,m+1):
            for a4 in range(a3,m+1):
                for a5 in range(a4,m+1):
                    for a6 in range(a5,m+1):
                        for a7 in range(a6,m+1):
                            for a8 in range(a7,m+1):
                                for a9 in range(a8,m+1):
                                    for a10 in range(a9,m+1):
                                        tyu = [0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10]
                                        kar = 0
                                        for x,y,z,w in p:
                                            if tyu[y] - tyu[x] == z:
                                                kar += w
                                        ans = max(kar,ans)
print(ans)

Measured memory_bytes: 9260
n = int(input())
w = [input() for i in range(n)]
for i in w:
    if w.count(i) > 1:
        print('No')
        exit()
for i in range(n-1):
    if w[i][-1] != w[i+1][0]:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 3060
#include <stdio.h>

int main() {
	int A,B;
	scanf("%d %d", &A, &B);
	if(A + B < 24) {
		printf("%d\n", A + B);
	} else if(A + B >= 24) {
		printf("%d\n", A + B - 24);
	}
	return 0;
}

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

using namespace std;
using ll = long long;

int main() {
	int n, a, b, c;
	scanf("%d %d %d %d", &n, &a, &b, &c);
	map<char, int> cnt;
	cnt['A'] = a;
	cnt['B'] = b;
	cnt['C'] = c;

	string ans;
	vector<string> inp(n);
	for(int i = 0; i < n; i++) {
		char str[4];
		scanf(" %s", str);
		inp[i] = str;
	}
	for(int i = 0; i < n; i++) {
		char t1 = inp[i][0], t2 = inp[i][1];
		if(cnt[t1] == 0 and cnt[t2] == 0) {
			return printf("No\n"), 0;
		}
		if(cnt[t1] < cnt[t2]) {
			swap(t1, t2);
		}
		char t3 = 'A';
		while(t3 == t1 or t3 == t2) t3++;
		if(cnt[t1] == 1 and cnt[t2] == 1 and cnt[t3] == 0) {
			if(i + 1 < n) {
				if(t1 == inp[i+1][0] or t1 == inp[i+1][1]) {
					swap(t1, t2);
				}
			}
		}
		ans += t2;
		cnt[t2]++;
		cnt[t1]--;
	}
	
	printf("Yes\n");
	for(char ch : ans) printf("%c\n", ch);
}


Measured memory_bytes: 6692
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

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

    ll dp[110][2][5];
    for(int j=0; j<2; j++){
        for(int k=0; k<5; k++){
            dp[0][j][k] = 0;
        }
    }
    dp[0][1][1] = 1;
    dp[0][0][1] = N[0] - '0' - 1;
    dp[0][0][0] = 1;

    for(int i=1; i<N.size(); i++){
        int n = N[i] - '0';
        for(int k=0; k<5; k++){
            dp[i][1][k] = 0;
            dp[i][0][k] = dp[i-1][0][k];
            if(n == 0){
                dp[i][1][k] = dp[i-1][1][k];
            }
            else{
                dp[i][0][k] += dp[i-1][1][k];
            }
            if(k > 0){
                dp[i][0][k] += dp[i-1][0][k-1] * 9;
                if(n != 0){
                    dp[i][1][k] += dp[i-1][1][k-1];
                    dp[i][0][k] += dp[i-1][1][k-1] * (n-1);
                }
            }
        }
    }

    cout << dp[N.size()-1][0][K] + dp[N.size()-1][1][K] << endl;

    // for(int i=0; i<N.size(); i++){
    //     for(int j=0; j<2; j++){
    //         for(int k=0; k<5; k++){
    //             cout << dp[i][j][k] << " ";
    //         }
    //         cout << endl;
    //     }
    //     cout << endl;
    // }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
import numpy as np

def main():
    N,T = map(int,input().split())
    food = []
    for _ in range(N):
        a,b = map(int,input().split())
        food.append((a,b))
        
    dp = np.zeros(T,dtype=int)
    food.sort(key = itemgetter(0))
    
    ans = 0
    for a,b in food:
        ans = max(ans,dp[-1]+b)
        dp[a:] = np.maximum(dp[a:],dp[:-a]+b)

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

Measured memory_bytes: 12500
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define rrep(i,s,e) for(int (i) = (s);(i) >= (e);(i)--)



signed main() {
  int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
  int x3 = x2 - (y2-y1);
  int y3 = y2 + (x2-x1);
  int x4 = x3 - (y3-y2);
  int y4 = y3 + (x3-x2);
  cout << x3 << " " << y3 <<" "<<x4 <<" "<<y4<<endl;
}


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

int main(){
	int n,k;
	cin >> n >> k;
	char S[n+1];
	for(int i = 0;i < n;i++){
		cin >> S[i];
	}
	char t = S[k-1];
	S[k-1] = tolower(t);
	for(int i=0;i<n;i++){
		cout << S[i];
	}
	return 0;
}


Measured memory_bytes: 256
import sys

n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
lst = [set() for _ in range(n+1)]
for a, b in edge:
    lst[a].add(b)
    lst[b].add(a)

if m % 2 == 1:
    print(-1)
    sys.exit()

check = [0] * (n+1)
q = [1]
next_q = []
tree = [set() for _ in range(n+1)]
top = [1]
while q:
    for oya in q:
        check[oya] = 1
        for ko in lst[oya]:
            if check[ko] == 0:
                check[ko] = 1
                top.append(ko)
                next_q.append(ko)
                tree[oya].add(ko)
                tree[ko].add(oya)
    q = next_q.copy()
    next_q = []

ecount = [0] * (n+1)
for a, b in edge:
    if a in tree[b]:
        continue
    print(a, b)
    ecount[a] += 1

for i in top[::-1][:-1]:
    j = list(tree[i])[0]
    if ecount[i]%2 == 0:
        print(j, i)
        ecount[j] += 1
    else:
        print(i, j)
        ecount[i] += 1
    tree[i].remove(j)
    tree[j].remove(i)

Measured memory_bytes: 79048
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    String ans = "Yes";
    char[][] s = new char[h][w];
    for(int i = 0; i < h; i++) {
      String str = sc.next();
      for(int j = 0; j < w; j++) {
        s[i][j] = str.charAt(j);
      }
    }
    for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++) {
        if(s[i][j] == '#') {
          int p = 0;
          if((i >= 1) && (s[i - 1][j] == '#')) p++;
          if((i < (h - 1)) && (s[i + 1][j] == '#')) p++;
          if((j >= 1) && (s[i][j - 1] == '#')) p++;
          if((j < (w - 1)) && (s[i][j + 1] == '#')) p++;
          if(p == 0) ans = "No";
        }
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 200005;

int n, q, cnt;
int in[N], re[N], sz[N], a[N];
vector<int> G[N];

void dfs(int u, int p) {
    in[u] = ++cnt;
    sz[u] = 1;
    for (int v : G[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1, 0);
    while (q--) {
        int p, x;
        cin >> p >> x;
        a[in[p]] += x;
        a[in[p] + sz[p]] -= x;
    }
    for (int i = 1; i <= n; ++i)
        a[i] += a[i - 1];
    for (int i = 1; i <= n; ++i)
        cout << a[in[i]] << " \n" [i == n];
}

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

int main()
{
    int a,b,c,ans;
    cin>>a>>b>>c;
    a = a - b;
    if(a<c)
    {
        ans = c - a;
        cout<<ans<<endl;
    }
    else if(a>=c)
    {
        cout<<"0"<<endl;
    }

    return 0;
}


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

int find(int X,vector<int>&P){
  if(P.at(X)<0){
    return X;
  }
  return P.at(X)=find(P.at(X),P);
}
void unite(int X,int Y,vector<int> &P){
  X=find(X,P);
  Y=find(Y,P);
  if(X==Y){
    return;
  }
  if(P.at(X)<P.at(Y)){
    swap(X,Y);
  }
  P.at(X)+=P.at(Y);
  P.at(Y)=X;
}

int main(){
  int N,M,count=0;
  cin >> N >> M;
  vector<int> P(N,-1);
  for(int i=0;i<M;i++){
    int A,B;
    cin >> A >> B;
    unite(A-1,B-1,P);
  }
  for(int i=0;i<N;i++){
    if(P.at(i)<0){
      count++;
    }
  }
  cout << count-1 << endl;
}

  

Measured memory_bytes: 3712
N = int(input())
data = list(map(int, input().split()))
count = 0

for i in range(1, N):
    for j in range(N-i):
        if data[N-1-j] < data[N-1-j-1]:
            data[N-1-j], data[N-1-j-1] = data[N-1-j-1], data[N-1-j]
            count += 1
            
print("%d" %data[0], end="")
for i in range(1, N):
    print(" %d" %data[i], end="")
print()
print(count)


Measured memory_bytes: 5608
/*
Author : N_o_o_B
Created : December 03 2019 15:16:12 
*/
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vll;
typedef vector<vl> vvl;
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define fori(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define ford(i,n)  for(int i=n-1;i>=0;i--)
#define trav(x,a) for(auto& x:a)
#define all(x) x.begin(),x.end()
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define fi first
#define se second
clock_t time_p=clock();
void time_taken()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
//const ll mod=998244353;
const ll mod=1e9+7;
const ll INF=1e18;
bitset<10> a;
bool chk(int n){
    bool ok=1;
    while(n){
        int r=n%10;
        ok &= (a[r]==0);
        n/=10;
    }
    return ok;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cout.precision(12);cout << fixed;
    int n,k;
    cin >> n >> k;
    fori(i,k){
        int x;
        cin >> x;
        a[x] = 1;
    }
    for(int i=n;;i++){
        if(chk(i)){
            cout << i << endl;
            return 0;
        }
    }


    time_taken();
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include <queue>
#include<algorithm>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
const ll MOD = 1000000007;
    ll X,sum=0,ans;

int main(){
    scanf("%lld",&X);
    for(int i=1;;i++){
        sum+=i;
        if(sum>=X){ans=i;break;}
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
dp = [[0 for j in range(N)] for i in range(N)]
if N%2==0:
    for i in range(N):
        dp[i][i] = -A[i]
    for k in range(1,N):
        for i in range(N-1):
            if i+k<N:
                if k%2==0:
                    dp[i][i+k]= min(-A[i]+dp[i+1][i+k],-A[i+k]+dp[i][i+k-1])
                else:
                    dp[i][i+k] = max(A[i]+dp[i+1][i+k],A[i+k]+dp[i][i+k-1])
else:
    for i in range(N):
        dp[i][i] = A[i]
    for k in range(1,N):
        for i in range(N-1):
            if i+k<N:
                if k%2==0:
                    dp[i][i+k]= max(A[i]+dp[i+1][i+k],A[i+k]+dp[i][i+k-1])
                else:
                    dp[i][i+k] = min(-A[i]+dp[i+1][i+k],-A[i+k]+dp[i][i+k-1])
print(dp[0][N-1])                

Measured memory_bytes: 119900
N, M = map( int, input().split())
Q = [[int(s) for s in input().split()] for _ in range(M)]
Q = sorted(Q)
ans = 1
LQ = len(Q)
stan = Q[0][1]
while LQ != 0:
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        stan = Q[0][1]
print(ans)

Measured memory_bytes: 23240
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int gcd(int a,int b)
{
	int t;
	if(a<b)
	{
		t=a;
		a=b;
		b=t;
	}
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
		
}
int main()
{
	int n,m;
	int ans;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&m);
		if(!i)
			ans=m;
		if(ans==1)
			continue;
		ans=gcd(ans,m);
		
			
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

string ABCD;


int main() {
#ifdef __APPLE__
    freopen("input0.txt", "r", stdin);
#endif
    cin >> ABCD;
    int A, B, C, D;

    A = ABCD[0] - '0';
    B = ABCD[1] - '0';
    C = ABCD[2] - '0';
    D = ABCD[3] - '0';

    for (int i = 0; i < 8; ++i) {
        // i's bit == 1 then +, 0 then -
        int plus_minus[3] = {0};
        for (int j = 0; j < 3; ++j) {
            if (i & 1 << j) {
                // +
                plus_minus[j] = 1;
            } else {
                plus_minus[j] = -1;
                // -
            }
        }
        if (A + plus_minus[0] * B + plus_minus[1] * C + plus_minus[2] * D == 7) {
            cout << A;
            cout << (plus_minus[0] == 1 ? '+' : '-') <<  B;
            cout << (plus_minus[1] == 1 ? '+' : '-') << C;
            cout << (plus_minus[2] == 1 ? '+' : '-') << D;
            cout << "=7" << endl;
            return 0;
        }

    }

    return 0;
}

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

using namespace std;

char s[100005];
int main() {
    scanf("%s", s);

    long long res = 0;
    int len = strlen(s);
    for (int b = 0; b < (1 << (len - 1)); ++b) {
        long long cum = s[0] - '0';
        for (int i = 0; i < len - 1; ++i) {
            if (b & (1 << i)) res += cum, cum = 0;
            cum = cum * 10 + (s[i + 1] - '0');
        }
        res += cum;
    }
    printf("%lld\n", res);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a,b,c,d;
    scanf("%d %d %d",&a,&b,&c);
    if(a > c){
        d = a;
        a = c;
        c = d;
    }
    if(a > b){
        d = a;
        a = b;
        b = d;
    }
    if(b > c){
        d = b;
        b = c;
        c = d;
    }

    printf("%d %d %d\n",a,b,c);

return 0;
}

Measured memory_bytes: 596
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String S=sc.next();
        String T=sc.next();
        int A=sc.nextInt();
        int B=sc.nextInt();
        String U=sc.next();
        if(S.equals(U)) A--;
        else B--;
        System.out.println(A+" "+B);
    }
}

Measured memory_bytes: 38624
n, q = gets.split.map(&:to_i)
s = gets.chomp
c = Array.new(s.size, 0)
1.upto(s.size - 1) do |i|
  if s[i] == 'C' && s[i - 1] =='A'
    c[i] = c[i - 1] + 1
  else
    c[i] = c[i - 1]
  end
end

q.times do
  l, r = gets.split.map(&:to_i)
  ans = c[r - 1] - c[[l - 2, 0].max]
  ans -= 1 if l >= 2 && c[l - 2] < c[l - 1]
  puts ans
end



Measured memory_bytes: 3324
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

long long mod_inv(long long n)
{
    long long left=MOD-2;  // define MOD!
    long long num=n;
    long long ans=1;
    while(left!=0)
    {
        if(left%2==1)ans=(ans*num)%MOD;
        left/=2;
        num=(num*num)%MOD;
    }
    return ans;
}

int main()
{
  long long n,k;cin>>n>>k;
  long long ans=1;
  long long combn=1;
  long long combn1=1;
  int i;
  for(i=1;i<=min(k,n-1);i++)//check
  {
    combn=combn*((n-i+1)*mod_inv(i)%MOD);
    combn%=MOD;
    combn1=combn1*((n-i)*mod_inv(i)%MOD);
    combn1%=MOD;
    ans=(ans+(combn*combn1%MOD))%MOD;
    //cout<<ans<<endl;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  string s;
  cin >> s;
  if (s == "BBB" || s == "AAA") cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=2001000;
int n,a[maxn],nxt[maxn],flag[maxn];
long long k,f[maxn][100];
vector<int> pos[maxn];
vector<int> ans;
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",a+i),pos[a[i]].push_back(i);
	for(int i=1;i<=200000;i++) for(int j=0;j<(int)pos[i].size();j++)
	{
		if(j+1==(int)pos[i].size()) nxt[pos[i][j]]=pos[i][0]+n-pos[i][j]+1;
		else nxt[pos[i][j]]=pos[i][j+1]-pos[i][j]+1;
	}
	for(int i=1;i<=n;i++) f[i][0]=nxt[i];
	for(int j=1;j<70;j++) for(int i=1;i<=n;i++)
		f[i][j]=min(n*k+1,f[i][j-1]+f[(i+f[i][j-1]-1)%n+1][j-1]);
	long long now=1;
	for(int i=69;i>=0;i--) if(f[(now-1)%n+1][i]+now<=n*k+1) now+=f[(now-1)%n+1][i];
	for(long long i=now;i<=n*k;i++)
	{
		int val=a[(i-1)%n+1];
		if(flag[val])
		{
			while(ans[ans.size()-1]!=val) flag[ans[ans.size()-1]]=0,ans.pop_back();
			ans.pop_back();flag[val]=0;
		}
		else{ans.push_back(val);flag[val]=1;}
	}
	for(int i=0;i<(int)ans.size();i++) cout<<ans[i]<<' ';
}

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

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    int h[N];
    for (int i = 0; i < N; i++)
    {
        cin >> h[i];
    }
    long long INF = 1e+10;
    vector<long long> cost(N + K + 10, INF);
    cost[0] = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < K; j++)
        {
            cost[i + j + 1] = min(cost[i + j + 1], cost[i] + abs(h[i + j + 1] - h[i]));
        }
    }
    cout << cost[N - 1] << endl;
}


Measured memory_bytes: 1408
def is_ATCG(str):
    for i in range(len(str)):
        chr=str[i]
        if(not(chr=='A' or chr=='T' or chr == 'C' or chr=='G')):
            return 0
    return 1

i_str=input()
max_len=0
len_str=len(i_str)

for i in range(len_str): #０行目から最後の行まで
    for j in range(i,len_str): #それぞれの文字数目から行末までのそれぞれの部分単語を取り出す
        strA=i_str[i:j+1:1]
        if max_len < len(strA) and is_ATCG(strA):
            max_len = len(strA)
print(max_len)


Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include <iomanip>
#include<algorithm>
#include<vector>
#include <map>
#define rep(i,N) for(int (i)=0;(i) < (N); ++(i))

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, x;
  cin >> n >> x;
  int l[n];
  rep(i, n) {
    cin >> l[i];
  }
  int dis = 0;
  int res = 0;
  while(dis <= x) {
    dis += l[res];
    ++res;
  }
  cout << res << "\n";
  return 0;

}


Measured memory_bytes: 256