akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int N; cin >> N;
    vector<vector<int>> child(N + 1);
    for (int i = 2; i <= N; i++) {
        int a; cin >> a;
        child[a].push_back(i);
    }
    vector<int> dp(N + 1);
    auto dfs = [&](auto&& f, int v) -> int {
        if (child[v].size() == 0) return 0;
        vector<int> cs;
        for (int u : child[v]) {
            cs.push_back(f(f, u));
        }
        sort(cs.begin(), cs.end());
        reverse(cs.begin(), cs.end());
        for (int i = 0; i < cs.size(); i++) {
            dp[v] = max(dp[v], cs[i] + i + 1);
        }
        return dp[v];
    };
    dfs(dfs, 1);
    cout << dp[1] << "\n";
    return;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 13952
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,D = MI()

cnt = 0
for i in range(N):
    X,Y = MI()
    ans = sqrt(X**2 + Y**2)
    if ans <= D:
        cnt += 1

print(cnt)


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

int main() {
	long long n,d,count = 0;
	cin >> n >> d;
	
	for (int i=0; i<n; ++i) {
		long long p,q; cin >> p >> q;
		if (p*p + q*q <= d*d) count++;
	}
	cout << count << endl;
}

Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	string S;
	cin>>S;
	int l=(int)S.length();
	if(l<4)cout<<"No";
	else if(S[0]=='Y'&&S[1]=='A'&&S[2]=='K'&&S[3]=='I')cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;

public final class Main
{
    public static void main (String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        int a= in.nextInt();
       int b= in.nextInt();
       int c= in.nextInt();
       int k= in.nextInt();
      
       while(b<=a && k>0) {
          b=b*2;
         k--;
       }
      
      while(c<=b && k>0){
        c= c*2;
        k--;
      }
      
       if(a<b && b<c){
          System.out.println("Yes");
       } else 
         System.out.println("No");

    }
}


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

typedef long long int ll;

int h, w;
char c[1005][1005];
const ll mod = 1000000007;

ll dp[1005][1005];

ll f(int H, int W)
{
    ll& x = dp[H][W];
    if(x != -1) return x;

    if(H == h && W == w) return 1;
    if(c[H][W] == '#') return x = 0;

    if(H+1 > h) return x = f(H, W+1) % mod;
    if(W+1 > w) return x = f(H+1, W) % mod;

    return x = (f(H, W+1) + f(H+1, W)) % mod;
}

int main()
{
    cin >> h >> w;
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j)
            { cin >> c[i][j]; dp[i][j] = -1; }
    dp[h][w] = 1;

    cout << f(1,1) << endl;    
    
}


Measured memory_bytes: 9216
#include <iostream>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> primeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(long i=s;i<e;i++)
#define repeq(i,s,e) for(long i=s;i<=e;i++)



int main() {
	ll n, d,ans;
	in(n);
	in(d);

	ans = n / (2 * d + 1);
	if (n % (2 * d + 1) != 0)	ans++;

	outn(ans);
	return 0;

}


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

using namespace std;

class Node {
public:
	int key;
	Node* prev;
	Node* next;
	Node(int _key, Node* _prev, Node* _next) {
		key = _key;
		prev = _prev;
		next = _next;
	}
};

class List {
public:
	Node* head;
	Node* last;
	List() {
		head = NULL;
		last = NULL;
	}
	void insert(int key) {
		auto node = head;
		head = new Node(key, NULL, node);
		if (node)
			node->prev = head;
		else
			last = head;
	}
	void deleteNode(Node* node) {
		if (! node)
			return;
		
		if (node == head)
			head = node->next;
		else
			node->prev->next = node->next;
		if (node == last)
			last = node->prev;
		else
			node->next->prev = node->prev;
		delete node;
	}
	Node* find(int key) {
		Node* current = head;
		while (current && current->key != key) {
			current = current->next;
		}
		return current;
	}
	void deleteFirst() {
		deleteNode(head);
	}
	void deleteLast() {
		deleteNode(last);
	}
};

int main() {
	int n;
	scanf("%d", &n);
	
	auto list = List();
	char name[100];
	int key;
	for (int i=0; i<n; i++) {
		scanf("%s", name);
		if (! strcmp(name, "insert")) {
			scanf("%d", &key);
			list.insert(key);
		} else if (! strcmp(name, "delete")) {
			scanf("%d", &key);
			list.deleteNode(list.find(key));
		} else if (! strcmp(name, "deleteFirst")) {
			list.deleteFirst();
		} else if (! strcmp(name, "deleteLast")) {
			list.deleteLast();
		}
	}
	
	auto current = list.head;
	while (current) {
		if (current != list.head)
			printf(" ");
		printf("%d", current->key);
		current = current->next;
	}
	printf("\n");
}

Measured memory_bytes: 33876
using System;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            var ab = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var result = "";
            if (ab[0] > ab[1])
            {
                for (int i = 0; i < ab[0]; i++) result += ab[1].ToString();
            }
            else
            {
                for (int i = 0; i < ab[1]; i++) result += ab[0].ToString();
            }
            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 13140
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void)
{
	int i,j,n;
	long long kai,sum,hei;
	scanf("%d",&n);
	sum=0;
	for(i=0;i<n;i++)	{
		scanf("%lld",&kai);
		sum+=kai;
	}
	hei=sum/n;
	printf("%lld\n",hei);
	return 0;
}


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

typedef long long Int;
typedef pair<int,int> PII;
typedef vector<int> VInt;
 
#define FOR(i, a, b) for(i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(i = (a) - 1; i >= (b); --i)
#define EACH(it, a) for(auto it = (a).begin(); it != (a).end(); ++it)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define SIZE(a) int((a).size())
#define ALL(a) (a).begin(),(a).end()
#define MP make_pair

void solve(int test)
{
    int n, k;
    cin >> n >> k;
    VInt a(n);
    int i, j;
    FOR(i, 0, n) cin >> a[i];
    FOR(i, 0, k)
    {
        VInt s(n + 1, 0);
        FOR(j, 0, n)
        {
            int f = max(0, j - a[j]);
            int t = min(n, j + a[j] + 1);
            ++s[f];
            --s[t];
        }
        VInt b(n, 0);
        int sum = 0;
        FOR(j, 0, n)
        {
            sum += s[j];
            b[j] = sum;
        }

        if(a == b) break;
        a = b;
    }

    FOR(i, 0, n) cout << a[i] << ' ';
}

int main()
{
    int T = 1, t;
    //cin >> T;
    FOR(t, 0, T) solve(t);
    return 0;
}


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

int main(){
	int count = 0;
	string str;
	string str2;
	
	while(cin>>str){
		str2 = str;
		reverse(str.begin(),str.end());
		if(str == str2){count++;}
	}
	cout<<count<<endl;
}

Measured memory_bytes: 1196
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define all(c) (c).begin(), (c).end()
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int diff(int a, int b, int *x, int n) {
   if(n == -1) return abs(a-b);
   return min(diff(a+x[n], b, x, n-1), diff(a, b+x[n], x, n-1));
} 

int main() {
  int n;
  while(cin >> n, n) {
    int x[n];
    rep(i, n) cin >> x[i];
    cout << diff(0, 0, x, n-1) << endl;
  }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int mo = 1e9+7;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<62;

int main(){
    string str;
    cin>>str;
    bool ok = true;
    for(int i=0;i<(int)str.size();++i){
        if(i%2){
            if(str[i] == 'R')ok = false;
        }else {
            if(str[i] == 'L')ok = false;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}
#define trace1(x)			 	 cerr<<#x<<": "<<x<<endl
#define trace2(x, y)		 	 cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)		 	 cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)	 	 cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)	 cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

ll freq1[100001],freq2[100001];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	rep(i,0,n){
		ll x;
		cin >> x;
		if(i%2){
			freq1[x]++;
		}
		else{
			freq2[x]++;
		}
	}
	vpii u,v;
	for(ll i=0; i<100001; i++){
		u.push_back({freq1[i],i});
		v.push_back({freq2[i],i});
	}
	sort(all(u));
	sort(all(v));
	if(u[100000].S!=v[100000].S){
		cout << n-(u[100000].F+v[100000].F);
	}
	else{
		cout << min(n-(u[100000].F+v[99999].F),n-(u[99999].F+v[100000].F));
	}
	return 0;
}
/* The judge is never wrong! Your code is buggy
   Look for:
 * * Read the problem carefully.
 * * Don't forget to sort(), mod, ll!!!!
 * * Initial value = +/- infinity instead of zero!!!
 * * an easier and alternate approach
 * * read the problem statement carefully
 * * if concept is correct and still WA, try with a different implementation
 * * special cases (n=1?)
 * * if you have no idea just guess the appropriate well-known algorithm instead of doing nothing :/
 */


Measured memory_bytes: 5220
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder.ABC091.A
{
    class Program
    {
        static void Main ()
        {
            var sc = new Scanner ();
            int a = sc.nextInt ();
            int b = sc.nextInt ();
            int c = sc.nextInt ();
            Console.WriteLine (a + b >= c ? "Yes" : "No");
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner ()
        {
            s = new string[0];
            i = 0;
        }

        public string next ()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine ();
            while (st == "") st = Console.ReadLine ();
            s = st.Split (cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next ();
            i = 0;
            return s[i++];
        }

        public int nextInt ()
        {
            return int.Parse (next ());
        }
        public int[] ArrayInt (int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt () + add;
            }
            return Array;
        }

        public long nextLong ()
        {
            return long.Parse (next ());
        }

        public long[] ArrayLong (int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong () + add;
            }
            return Array;
        }

        public double nextDouble ()
        {
            return double.Parse (next ());
        }

        public double[] ArrayDouble (int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble () + add;
            }
            return Array;
        }

        public decimal nextDecimal ()
        {
            return decimal.Parse (next ());
        }

        public decimal[] ArrayDecimal (int N, decimal add = 0)
        {
            decimal[] Array = new decimal[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDecimal ();
            }
            return Array;
        }
    }
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

typedef pair< long long, long long > P;
typedef pair< long long, P > PP;
typedef pair< P, P > PPP;

const long long MOD = 1e9 + 7;
const  long long  INF = 5e18;
const double DINF = 5e14;
const double eps = 1e-10;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second

ll n, m, a, b, c;
string s[101];
map<string, bool>mp;

int main() {
	cin >> a >> b;
	if ((a*b) % 2 == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def solve():
    s = input()
    if s == "ABC":
        print("ARC")
    else:
        print("ABC")

    return 0

if __name__ == "__main__":# {{{
    solve()

# vim: set foldmethod=marker: }}}


Measured memory_bytes: 79392
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ab=[]
bc=[]
for i in range(n):
    ab.append([a[i],n])
    bc.append([b[i],n])
    ab.append([b[i],i])
    bc.append([c[i],i])
numa=1
numb=1
numc=1
la=[1]*n
lb=[1]*n
lc=[1]*n
for i in range(1,n):
    if a[i-1]!=a[i]:
        la[i]=i+1
        numa=i+1
    else:
        la[i]=numa
    if b[i-1]!=b[i]:
        lb[i]=i+1
        numb=i+1
    else:
        lb[i]=numb
    if c[i-1]!=c[i]:
        lc[i]=i+1
        numc=i+1
    else:
        lc[i]=numc
ab.sort(key=lambda x: x[0])
numab=1
lab=[1]*(n+1)
for i in range(1,n*2):
    if ab[i-1][0]!=ab[i][0]:
        lab[ab[i][1]]=i+1
        numab=i+1
    else:
        lab[ab[i][1]]=numab
ansb=[0]*n
numb=0
for i in range(n):
    numb+=lab[i]-lb[i]
    ansb[i]=numb
bc.sort(key=lambda x: x[0])
numbc=1
lbc=[1]*(n+1)
for i in range(1,n*2):
    if bc[i-1][0]!=bc[i][0]:
        lbc[bc[i][1]]=i+1
        numbc=i+1
    else:
        lbc[bc[i][1]]=numbc
ansc=[0]*n
for i in range(n):
    ansc[i]=lbc[i]-lc[i]
ans=0
for i in range(n):
    if ansc[i]!=0:
        ans+=ansb[ansc[i]-1]
print(ans)


Measured memory_bytes: 88848
#include<map>
#include<iostream>
using namespace std;
typedef unsigned long long inter;
const inter m=1e9+7;
map<inter,inter> dick;
inter f(inter x)
{
    if(dick[x])
        return dick[x];
    else
    return dick[x]=((f(x/2)+f((x-1)/2)+f((x-2)/2)))%m;
}
void work()
{
    dick[0]=1;
    dick[1]=2;
    inter n;
    cin>>n;
    cout<<f(n);
}
int main()
{
    work();
}

Measured memory_bytes: 256
//============================================================================
// Name        : e.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

//(a^n)mod(MOD)
long long modPow(long long a, long long n,long long MOD) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * a % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        a = a * a % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}
int main() {
	int n,k;cin>>n>>k;
	vector<long long> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	long long def=1;
	for(int i=0;i<9;i++)def*=10;
	def+=7;
	vector<long long> f(n),rf(n);
	f[0]=1;
	rf[0]=1;
	for(int i=1;i<n;i++){
		f[i]=f[i-1]*i;
		f[i]%=def;
		rf[i]=modPow(f[i],def-2,def);
	}
	long long ans=0;
	for(int i=0;i+k-1<n;i++){
		long long add=0;
		add=a[i]*f[n-1-i];
		add%=def;
		add*=rf[k-1];
		add%=def;
		add*=rf[n-i-k];
		ans-=add;
		ans%=def;
//		cout<<i<<' '<<ans<<endl;
	}
	for(int i=n-1;i-k+1>=0;i--){
		long long add=0;
		add=a[i]*f[i];
		add%=def;
		add*=rf[k-1];
		add%=def;
		add*=rf[i-k+1];
		ans+=add;
		ans%=def;
	}
	ans+=def;
	ans%=def;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2560
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}


//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

int main() {

    long long N, M;
    cin >> N >> M;
    vector<vector<long long>> A(N, vector<long long>(3));
    for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) cin >> A[i][j];

    long long ans = LONG_LONG_MIN;
    for (int bit = 0; bit < (1 << 3); bit++) {
        long long sum = 0;
        vector<long long> a(N, 0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                if (bit & (1 << j)) a[i] += A[i][j];
                else a[i] += -A[i][j];
            }
        }
        sort(a.begin(), a.end());
        reverse(a.begin(), a.end());
        for (int i = 0; i < M; i++) sum += a[i];
        ans = max(ans, sum);
    }

    cout << ans <<endl;

    return 0;
}


























































































Measured memory_bytes: 256
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fill(x,c) memset(x,c,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int SIZE = 1e6+10;
ll a[SIZE];
int main() {
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll n,k,s;
	cin>>n>>k>>s;
	if(s==1000000000){
		if(k==0){
			cout<<s-1;
			rep(i,1,n){
				cout<<" "<<s-1;
			}
		}else{
			cout<<s;
			rep(i,0,k-1)cout<<" "<<s;
			rep(i,0,n-k)cout<<" "<<s-1;
		}
		return 0;
	}
	if(k==0){
		cout<<s+1;
		rep(i,1,n){
			cout<<" "<<s+1;
		}
	}else{
		cout<<s;
		rep(i,0,k-1)cout<<" "<<s;
		rep(i,0,n-k)cout<<" "<<s+1;
	}
  	return 0;
}


Measured memory_bytes: 1280
def cal(a,b,c):
    return abs(b-a)+abs(c-b)

a,b,c=map(int,input().split())


print( min( cal(a,b,c),cal(a,c,b),cal(b,a,c),cal(b,c,a),cal(c,a,b),cal(c,b,a) ) )

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  ll r = 0, g = 0, b = 0;
  rep(i, n){
    if(s[i] == 'R') r++;
    if(s[i] == 'G') g++;
    if(s[i] == 'B') b++;
  }
  int rgb = int('R') + int('G') + int('B');
  ll ans = r * g * b;
  for(int i = 0; i < n - 1; i++){
    for(int j = i + 1; j < n; j++){
      int k = j * 2 - i;
      if(k >= n) continue;
      if(int(s[i]) + int(s[j]) + int(s[k]) == rgb) ans--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3540
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Weight = sc.nextInt();
        int[] w = new int[N];
        int[] v = new int[N];
        long[][] dp = new long[Weight+1][N+1];

        for(int i = 0; i<N; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        for(int i = 1; i<Weight+1; i++) {
            if(w[0] <= i) dp[i][1] = v[0];
        }

        for(int j = 2; j<N+1; j++) {
            for(int i = 1; i<Weight+1; i++){

                if(i>=w[j-1]) {
                    dp[i][j] = Math.max(dp[i - w[j - 1]][j - 1] + v[j - 1], dp[i][j - 1]);

                }else{
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[Weight][N]);

    }
}

Measured memory_bytes: 127824
var
 x,y,i,s:longint;
 st:string;
begin
 readln(x,y);
 readln(st);
 for i:=1 to x+y+1 do if (i<>x+1)and(not(st[i] in ['0'..'9'])) then s:=1;
 if (s=1) or (st[x+1]<>'-') then writeln('No') else writeln('Yes');
end.

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

using namespace std;
int a[10];

int main()
{
    for(int i = 0;i<5;i++) cin >> a[i];
    sort(a , a + 5);
    int Ans = 1e9;
    do{
        int Res = 0;
        for(int i = 0;i<5;i++)   {
                Res+=a[i];
                if(Res % 10 != 0 && i < 4) Res+=10 - (a[i] % 10);
        }
        Ans = min(Ans , Res);

    }while(next_permutation(a , a + 5));
    cout << Ans;
    return 0;
}


Measured memory_bytes: 256
import math
#import numpy as np 

#参照
#https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E7%95%AA%E5%A4%96%E7%B7%A8
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


X,Y =map(int,input().split())
#x,y = np.sum(1/3*(np.array([[ 2., -1.],[-1.,  2.]])*np.array([X,Y])),axis=1).astype(np.int32)
#print(x)
x = int(X-(X+Y)//3)
y = int(Y-(X+Y)//3)
if (X+Y)%3==0 and x>=0 and y>=0:
    print(cmb(x+y,x,mod))
else:
    print(0)
    


Measured memory_bytes: 129164
eval'N,M,*A='+`dd`.split*?,
h=0,*A.sort.reverse,*[0]*2e5
M.times{v=h[i=1]/2;h[i/2]=h[i]while v<h[i=h[i*=2]>h[i+1]?i:i+1];h[i/2]=v}
p eval h*?+

Measured memory_bytes: 336732
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string n; cin >> n;
    rep(i, n.size()) {
        if (n[i] == '7') {
            puts("Yes");
            return 0;
        }
    }
    puts("No");
    return 0;
}

Measured memory_bytes: 3648
/*
 * atcoder/abc118_2nd/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int N;
vector<ll> A;

void solve() {
  cin >> N;
  ll a;
  loop(n,0,N) {
    cin >> a;
    A.push_back(a);
  }

  ll min_ = A[0];
  loop(n,1,N) {
    min_ = gcd(min_, A[n]);
  }
  cout << min_ << endl;
}
int main() {
  // cout.precision(15);
  // cout << fixed << double

  solve();

  return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
#define ll long long
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n , k, s= 0;
	cin>>n>>k;
	if(n==k)
	cout<<"Yes";
	else
	cout<<"No";
	
	return 0;
}

Measured memory_bytes: 3628
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

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

const int MOD = 1000000007;

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

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

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

void debug(VS &board){
	int h = board.size();
	rep(i,h){
		cout<<board.at(i)<<endl;
	}
	return;
}

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

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

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	int n,m;
	cin>>n>>m;
	VI h(n,0);
	rep(i,n){
		cin>>h[i];
	}
	VI hm(n,-1);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		chmax(hm[a],h[b]);
		chmax(hm[b],h[a]);
	}
	int ans=0;
	rep(i,n){
		if(h[i]>hm[i])ans++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4076
#include <iostream>

int main()
{
	int m, f, r, total;
	std::cin >> m >> f >> r;

	while (m != -1 || f != -1 || r != -1) {

		total = m + f;
		if (m == -1 || f == -1)
			std::cout << "F\n";
		else if (total >= 80)
			std::cout << "A\n";
		else if (total >= 65)
			std::cout << "B\n";
		else if (total >= 50)
			std::cout << "C\n";
		else if (total >= 30) {
			if (r >= 50)
				std::cout << "C\n";
			else
				std::cout << "D\n";
		}
		else
			std::cout << "F\n";

		std::cin >> m >> f >> r;
	}

    return 0;
}




Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;


int main(){
    double t, x;cin >> t >> x;
    printf("%.6f", t/x);

    return 0;

}


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

int main() {
  int d,g;cin>>d>>g;
  vector<int> p(d),c(d);
  rep(i,d)cin>>p[i]>>c[i];
  int ans=1e9;
  rep(bit,1<<d){
    int sum=0,cnt=0,a=-1;
    rep(i,d){
      if(bit&(1<<i)){
        //ボーナスポイントを取るか取らないかでbit全探索
        sum+=100*(i+1)*p[i]+c[i];
        cnt+=p[i];
      }
      else a=i;//ボーナスポイントを取らないとき少ない問題数で目標を達成するなら高い点数の問題を解くのがベスト
    }
    if(sum<g){//ボーナスポイントを取ってもまだg点を超えていないとき
      int sum1=100*(a+1);
      int x=(g-sum+sum1-1)/sum1;//g点を超えるときの問題数
      if(x>=p[a])continue;/*p[a]はa番目の問題でボーナスポイントを取っていないときの問題数で、
      xがp[a]以上の時はa番目の問題でボーナスポイントを取っていることになるので矛盾*/
      cnt+=x;
    }
    ans=min(ans,cnt);
  }
  cout<<ans<<endl;
}

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

int main(){
    int n, x, t;
    cin >> n >> x >> t;
    int ans;
    if(n%x == 0) ans = t*(n/x);
    else ans = t*(n/x + 1);
    cout << ans << endl;
}

Measured memory_bytes: 3632
using System;
class p
{
  static void Main()
  {
    int N = int.Parse(Console.ReadLine()) % 10;
    if (N == 3) {
      Console.WriteLine("bon");
      return;
    } else if (N == 0 || N == 1 || N == 6 || N == 8) {
      Console.WriteLine("pon");
      return;
    } else {
      Console.WriteLine("hon");
      return;
    }
  }
}


Measured memory_bytes: 27484
n,k = gets.split.map(&:to_i)
s = gets.chomp!

count = 1
pre = s[0]
s.each_char do |c|
    next if c == pre
    count += 1
    pre = c
end

if count <= 2*k then
    ans = n - 1
else
    ans = n + 2*k - count
end

puts ans

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[200005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> A[i];
    }

    ll ans = 0;
    ll s = 0;
    ll si = 0;
    REP(i, N) {
        while ((s & A[i]) != 0) {
            s -= A[si++];
        }
        ans += i - si + 1;
        s += A[i];
        continue;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<ctime>
#define ll long long
#define pr(x) cerr<<#x<<"="<<x<<endl
using namespace std;
#define N 210000
int n,i,a[N],j,last[30],ans[N],dp[N],nxt[N][30];
char s[N];
int main()
{
	scanf("%s",s);
	n=strlen(s);
	for (i=1;i<=n;i++)
	a[i]=s[i-1]-'a'+1;
	for (i=1;i<=26;i++) last[i]=n+1;
	for (i=n;i>=1;i--)
	{
		last[a[i]]=i;
		for (j=1;j<=26;j++) nxt[i][j]=last[j];
	}
	for (i=1;i<=n+1;i++) dp[i]=10000000;
	for (i=n;i>=1;i--)
	{
		for (j=1;j<=26;j++)
		{
			if (dp[nxt[i][j]+1]+1<dp[i])
			dp[i]=dp[nxt[i][j]+1]+1,ans[i]=j;
		}
	}
	//printf("%d\n",dp[1]);
	int now=1;
	while (now<=n)
	{
		printf("%c",ans[now]+'a'-1);
		now=nxt[now][ans[now]]+1;
	}
	return 0;
}

Measured memory_bytes: 27520
#include<bits/stdc++.h>
using namespace std;
 
bool visit[100001];
const int MN = 1e5;
int pa[MN+1],de[MN+1];

void Init(){
   for(int i=1;i<=MN;i++)
      de[pa[i]=i]=1;
}
int Find(int x){
   return x==pa[x]?x:pa[x]=Find(pa[x]);
}
void Union(int x,int y){
   x=Find(x);y=Find(y);
   if(x!=y){
      if(de[x]<de[y])    swap(x,y);
      pa[y]=x;
      if(de[x]==de[y])    de[x]++;
   }
} 

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Init();
	int n,m;
	cin>>n>>m;
	for(int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		Union(x,y);
	}
	for(int i=1;i<=n;i++)
		visit[Find(i)]=true;
	int ans=0;
	for(int i=1;i<=n;i++)
		if(visit[i])
			ans++;
	cout<<ans<<endl;
}

Measured memory_bytes: 1152
// https://atcoder.jp/contests/abc086/tasks/arc089_b
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define REP(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
const int MAX_N = 2003;
int r[MAX_N][MAX_N], s[MAX_N][MAX_N];

int query(int x1, int y1, int x2, int y2) {
    // return sum(x1<=x<=x2,y1<=y<=y2)
    if (x1 > x2 || y1 > y2)
        return 0;
    else
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    REP(i, N) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        if (c == 'B')
            y += K;
        x %= 2 * K;
        y %= 2 * K;
        r[x + 1][y + 1]++;
    }
    // 2次元累積和
    REP(x, 1, 2 * K + 2)
    REP(y, 1, 2 * K + 2)
    s[x][y] = r[x][y] + s[x - 1][y] + s[x][y - 1] - s[x - 1][y - 1];

    int ans = 0;
    REP(x, 1, K + 1) REP(y, 1, K + 1) {
        int temp = query(x, y, x + K - 1, y + K - 1) +
                   query(x + K, y + K, 2 * K, 2 * K) +
                   query(1, 1, x - 1, y - 1) + query(x + K, 1, 2 * K, y - 1) +
                   query(1, y + K, x - 1, 2 * K);
        ans = max(ans, max(temp, N - temp));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 31616
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;

Vec fac, finv;

ll PowMod(ll a, ll n){
	if(n == 1) return a;
	if(n%2 == 0) return PowMod(a*a%MOD, n/2);
	return a*PowMod(a*a%MOD, n/2)%MOD;
}

ll combi(ll n, ll k){
	return fac[n]*finv[k]%MOD*finv[n-k]%MOD;
}

void init(ll n = 2e6){
	fac.resize(n+1);
	fac[0] = 1;
	repn(i, n) fac[i] = (fac[i-1]*i)%MOD;
	finv.resize(n+1);
	finv[n] = PowMod(fac[n], MOD-2);
	repr(i, n) finv[i] = (finv[i+1]*(i+1))%MOD;
	finv[0] = 1;
}

int main(void){
	ll n;
	cin >> n;
	Vec a(n+1);
	rep(i, n+1) cin >> a[i];

	unordered_map<ll, ll> ump;
	for(ll i : a) ump[i]++;

	ll same = 0;
	for(P i : ump){
		if(i.sc == 2) same = i.fs;
	}

	init();

	ll t = 0;
	rep(i, n+1){
		if(a[i] == same){
			t += i;
			break;
		}
	}
	repr(i, n+1){
		if(a[i] == same){
			t += n-i;
			break;
		}
	}

	ll ans = 0;
	repn(i, n+1){
		if(i == 1){
			co(n);
			continue;
		}
		ans = combi(n+1, i);
		if(t >= i-1) ans -= combi(t, i-1);
		if(ans < 0) ans += MOD;
		co(ans);
	}

	return 0;
}


Measured memory_bytes: 37412
def main():
  n = int(input())
  A = list(map(int, input().split()))
  A.append(0)

  money = 1000
  kabu = 0
  for i in range(n):
    a = A[i]
    nxt = A[i + 1]

    if a < nxt:
      cnt = money // a
      money -= cnt * a
      kabu += cnt
    elif a > nxt:
      money += kabu * a
      kabu = 0

  print(money)


main()


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

bool ar[110000]={true};

int prime(int x){
	int sump=0;
	int i=110000;
	
	for(int a=0;a<i;a++){ar[a]=true;}
	
	for(int b=2;b*b<=i;b++){
		if(ar[b]){
			for(int c=b*b;c<=i;c+=b){
				ar[c]=false;
				}
			}
		}

int ca=0;
		for(int d=2;d<=i;d++){
			if(ar[d]){
				sump+=d;
				ca++;
				}
			if(ca==x){break;}	
			}
			return sump;
	}

int main(){
	int s;
	while(cin>>s,s){
		cout<<prime(s)<<endl;
		}
		return 0;
	}

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

using namespace std;

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

    vector<int> A(M);
    for(int i = 0; i < M; ++i){
        cin >> A[i];
    }

    int lft = 0, rgt = 0;
    for(int i = 0; i < M; ++i){
        if(A[i] < X)    lft++;
        else    rgt++;
    }

    cout << min(rgt, lft);
    
    return 0;
}

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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int x,a;cin>>x>>a;
  if(x<a)cout<<0<<endl;
  else cout<<10<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <deque>
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}


#define INF 1e9+7
#define LLINF 1e18+7
const ll MOD=1e9+7;
const int N=500000;

main(){
    int x=in(),y=in();
    int ans=0;
    if(x==3){
        ans+=100000;
    }
    if(x==2){
        ans+=200000;
    }
    if(x==1)ans+=300000;
    if(y==3)ans+=100000;
    if(y==2)ans+=200000;
    if(y==1)ans+=300000;
    if(ans==600000)ans=1000000;
    cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    int p[n],q[m];
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    for(int i=0;i<m;i++){
        cin>>q[i];
    }
    sort(p,p+n);
    sort(q,q+m);
    for(int i=x+1;i<=y;i++){
        if(p[n-1]<i && i<=q[0]){
            cout<<"No War"<<endl;
            exit(0);
        }
    }
    cout<<"War"<<endl;
}


Measured memory_bytes: 256
n, k = list(map(int, input().split()))
v = list(map(int, input().split()))

total_all = []
for a in range(min(n, k) + 1):
    for b in range(min(k - a, n - a) + 1):
        if b == 0:
            tmp = v[:a]
        else:
            tmp = v[:a] + v[-1 * b:]
        tmp.sort()

        n_tmp_negative = sum(1 for x in tmp if x < 0)
        cd = k - a - b
        if cd > 0:
            total = sum(tmp[min(cd, n_tmp_negative):])
        else:
            total = sum(tmp)

        total_all.append(total)
print(max(total_all))


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

int main()
{
    int D,G;
    cin >> D>>G;

    vector<int> p(D);
    vector<int> c(D);

    for (int i=0;i<D; i++){
        cin >> p[i] >> c[i];
    }

    int minnum = 1<<16;
    for(int bit=0; bit<(1<<D); ++bit){
        long long sum = 0;
        int num = 0;
        for(int i=0; i<D; i++){
            if(bit&(1<<i)){
                sum += (i+1)*100*p[i]+c[i];
                num += p[i];
            }
        }
      	//cout << bitset<10>(bit) << " " << sum << " " << num  << endl;
        if (sum >= G){
            minnum = min(minnum, num);
        }
        else{
            for(int i=D-1; i>=0; i--){
                if (bit&(1<<i)) continue;
                for(int j=0; j<p[i]; j++){
                    if (sum >= G) break;
                    sum += (i+1)*100;
                    num ++;
                }
            }
            minnum = min(minnum, num);
        }
    }


    cout << minnum <<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    int a, b, c;
    int r;
    int d;
    cin >> n >> d;
    out((n + (2 * d + 1) - 1) / (2 * d + 1));
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;

using namespace std;



signed main(){
    
   int n,t,a[111111];
   cin>>n>>t;
   int min=INF,b,max=0,ans;
   rep(i,n){
       cin>>a[i];
       min=std::min(min,a[i]);
       if(min!=a[i])b=a[i]-min;
       else b=-114514;
       
       if(b>max){
           max=b;
           ans=1;
       }
       else if(b==max)ans++;
   }
   cout<<ans<<endl;
    
    
}

Measured memory_bytes: 1024