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

typedef long long ll;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    for (int i = 0; i < x; i++) cin >> a[i];
    for (int i = 0; i < y; i++) cin >> b[i];
    for (int i = 0; i < z; i++) cin >> c[i];
    sort(a.begin(), a.end(), greater<>());
    sort(b.begin(), b.end(), greater<>());
    sort(c.begin(), c.end(), greater<>());
    vector<ll> ab;
    for (int i = 0; i < min(k, x); i++) {
        for (int l = 0; l < min(k, y); l++) {
            ab.push_back(a[i] + b[l]);
        }
    }
    sort(ab.begin(), ab.end(), greater<>());
    vector<ll> abc;
    for (int i = 0; i < min(k, x * y); i++) {
        for (int l = 0; l < min(k, z); l++) {
            abc.push_back(ab[i] + c[l]);
        }
    }
    sort(abc.begin(), abc.end(), greater<>());
    for (int i = 0; i < k; i++) cout << abc[i] << endl;
    return 0;
}


Measured memory_bytes: 43240
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n + 1];
		Arrays.fill(arr, -1);
		arr[0] = sc.nextInt();
		int max = 1;
		for (int i = 1; i < n; i++) {
		    int x = sc.nextInt();
		    if (arr[0] < x) {
		        arr[0] = x;
		    } else {
		        int left = 0;
		        int right = max;
		        while(right - left > 1) {
		            int m = (left + right) / 2;
		            if (arr[m] >= x) {
		                left = m;
		            } else {
		                right = m;
		            }
		        }
		        arr[right] = x;
		        max = Math.max(max, right + 1);
		    }
		}
		System.out.println(max);
   }
}


Measured memory_bytes: 59832
/*{{{*/
#include<bits/stdc++.h>

typedef long long ll;

#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define FORR(i,a,b) for(ll i=b-1;i>=a;i--)

#define vl vector<ll>
#define pll pair<ll,ll>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;
/*}}}*/

int main() {
  ll n;
  cin >> n;
  ll ans = 10 - n/200;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
import numpy as np

n = int(input())
dp = [0] * 3

for i in range(n):
    a, b, c = map(int, input().split())
    _a = max(dp[1] + a, dp[2] + a)
    _b = max(dp[2] + b, dp[0] + b)
    _c = max(dp[0] + c, dp[1] + c)
    dp = [_a, _b, _c]

print(max(dp))

Measured memory_bytes: 14300
<?php
$n = fgets(STDIN);
$a = explode(" ",fgets(STDIN));
$ava = array_sum($a)/$n;
$min = [];
$i = 0;
foreach ($a as $val) {
	$min[] = abs($ava-$val);
}
$min1 = min($min);
foreach ($min as $vals) {
	if($vals == $min1){
		echo $i;
		break;
	}
	$i++;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
#define REP(i,n) for(int i=0;i<(int)n;++i)
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

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

    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i, N)  cin >> A[i];

    ll S = 0;
    REP(i, N) S += A[i];
    ll res = 0;
    REP(i, N){
        if(A[i]*4*M>=S) res++;
    }
    cout << (res>=M ? "Yes" : "No") <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){ 
    int a;
    cin>>a;
    int b[4];
    b[0]=a/1000;
    b[1]=(a/100)%10;
    b[2]=(a/10)%10;
    b[3]=a%10;
    if(((b[0]==b[2])&&(b[2]==b[1]))||((b[1]==b[2])&&(b[2]==b[3])))cout<<"Yes";
    else cout<<"No";
 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char** argv){
    long long int X, Y;
    cin >> X >> Y;

    long long int c = 1;
    while (1){
        X *= 2;
        if (X > Y) break;
        c++;
    }

    cout << c << "\n";

    return 0;
}


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

int main() {
  int N; cin>>N;
  
  int counter=0;
  for(int i=0; i<N; i++){
      int di1,di2;
      cin>>di1>>di2;
      if(di1==di2) {
          counter++;
          if(counter==3){
              cout<<"Yes\n";
              return 0;
          }
      }
      else counter=0;
  }
  cout<<"No\n";
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define int long
#define pii pair<int,int>
#define a first
#define b second
signed main(){
  int n,h,maxk,thr,dthr;
  cin>>n>>h;
  vector<pii> katana(n);
  for(int i=0;i<n;++i)cin>>katana[i].a>>katana[i].b;
  maxk=thr=dthr=0;
  for(int i=0;i<n;++i)maxk=max(maxk,katana[i].a);
  for(int i=0;i<n;++i){
    if(maxk<katana[i].b){
      thr++;
      dthr+=katana[i].b;
    }
  }
  sort(katana.begin(),katana.end(),[](pii ka,pii kb){return ka.b>kb.b;});
  int sum=0;
  for(int i=0;i<thr;++i){
    if((sum+=katana[i].b)>=h){
      cout<<i+1;
      return 0;
    }
  }
  cout<<(h>dthr?(h-dthr)/maxk+((h-dthr)%maxk?1:0)+thr:thr);
  return 0;
}

Measured memory_bytes: 1792
'use strict'
let maxnum = 109

const merge = (A, left, mid, right) => {
  let n1 = mid - left
  let n2 = right - mid
  let L = []
  let R = []
  for (let i = 0; i < n1; i++) L[i] = A[left + i]
  for (let i = 0; i < n2; i++) R[i] = A[mid + i]
  L[n1] = Infinity
  R[n2] = Infinity
  let i = 0
  let j = 0
  let k = 0
  for (let k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      A[k] = L[i++]
    } else {
      A[k] = R[j++]
    }
  }
}
const mergeSort = (A, left, right) => {
  if (left + 1 < right) {
    let mid = (left + right) >> 1
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)
  }
}

function countingSort(arr) {
  const sorted = []
  let tmp = Array.apply(null, { length: maxnum + 1 }).map(v => 0)
  // console.log(tmparr.length)
  for (let i in arr) {
    tmp[arr[i]]++
  }
  for (let i in tmp) {
    while (tmp[i] > 0) {
      sorted.push(~~i)
      tmp[i]--
    }
  }
  // console.log(sorted)

  return sorted
}

//'use strict'
function main(input) {
  input = input.split(/\n|\s/).map(v => ~~v)
  const n = input.shift()
  const arr = input.slice(0, -1)
  let sorted =  [...arr].slice(0)
  mergeSort(sorted, 0, n) //arr.slice(0).sort((a, b) => a - b) //countingSort(arr)
//   const sorted = [...arr].sort((a, b) => a - b) //countingSort(arr)
  const mid = sorted[n / 2]
  const mid2 = sorted[n / 2 - 1]
  //   console.log(arr, sorted, mid)

  const ans = []
  for (let i = 0; i < n; i++) {
    ans.push(arr[i] < mid ? mid : mid2)
  }
  console.log(ans.join('\n'))
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 66824
function main(input) {
  const a = parseInt(input.split(" ")[0], 10);
  const b = parseInt(input.split(" ")[1], 10);
  const c = parseInt(input.split(" ")[2], 10);
  const d = parseInt(input.split(" ")[3], 10);
  if(Math.abs(a-c)<=d||(Math.abs(a-b)<=d&&Math.abs(b-c)<=d)){
    console.log("Yes");
  }else{
    console.log("No");
  }

}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 11468
#include <stdio.h>

int main()
{
	char S[26];
	int a, b, k, len;
	int c = 0;	
	
	scanf("%s", S);
	
	for(a=0; S[a] != NULL; a++)
	{
		len++;
	}

	for(b=0; b < len; b++)
	{
		for(k=b+1; k<len;k++)
		{
			if (S[b] == S[k]) c++;
		}
	}
	
	if(c == 0) printf("yes");
	else printf("no");
	
	
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
 ll N,M;
  cin>>N>>M;
  if(N==M) {
cout<<"Yes"<<endl;
  }
  else {
cout<<"No"<<endl;
  }
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll INFl = 1e18;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n, a, b; cin >> n >> a >> b;
	int x = n;
	while (n <= b) {
		if (n >= a && n <= b) {
			cout << "OK\n";
			return 0;
		}
		n += x;
	}
	cout << "NG\n";
	
	return 0;
}


Measured memory_bytes: 3640
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

int n;
int solve1(int x, int y, int n) {
	for (int z = 1; 0 <= n - z * (x + y + z); z++)
		if (n == z * (x + y + z))
			return 1;
	return 0;
}
int solve0(int x, int n) {
	int r = 0;
	for (int y = 1; 0 < n - y * (x + y); y++)
		r += solve1(x, y, n - y * (x + y));
	return r;
}
int solve(int n) {
	int r = 0;
	for (int x = 1; 0 < n - x * x; x++)
		r += solve0(x, n - x * x);
	return r;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		printf("%d\n", solve(i));
}

Measured memory_bytes: 1652
//#define _GLIBCXX_DEBU
#include <bits/stdc++.h>

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

template <typename T>
void print(const vector<T> &v) {
    for (auto e : v) cout << e << ' ';
    cout << endl;
}

//------------------------- Libraries -------------------------//

//--------------------------- Solve ---------------------------//

using Graph = vector<vector<int>>; 
int N, M;

int rec(int v, Graph &g, vector<bool> &visit) {
    visit[v] = true;
    int res = 1;
    for (auto e : g[v]) {
        if (!visit[e]) res += rec(e, g, visit);
    }
    return res;
}
 

void solve() {
    cin >> N >> M;
    int a[M], b[M];
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }

    int ans = 0;
    for (int i = 0; i < M; i++) {
        Graph g(N);
        for (int j = 0; j < M; j++) {
            if (i == j) continue;
            g[a[j]].push_back(b[j]);
            g[b[j]].push_back(a[j]);
        }
        vector<bool> visit(N);
        if (rec(0, g, visit) != N)ans++;
    }

    cout << ans << '\n';
}

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

    solve();

    return 0;
}

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

int main() {

    double r;
    std::cin >> r;

    double a = M_PI * r * r;
    double c = M_PI * 2 * r;

    std::cout << std::fixed << std::setprecision(5);
    std::cout << a << " " << c << std::endl;

    return 0;
}



Measured memory_bytes: 3280
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2e5+5;
const int M = 1e4;
const int INF = 0x3f3f3f3f;

int sum[N];

int main(){
	int n,x;
	scanf("%d",&n);
	memset(sum,0,sizeof(sum));
	for(int i = 2;i <= n;++i) scanf("%d",&x),sum[x]++;
	for(int i = 1;i <= n;++i) printf("%d\n",sum[i]);
    return 0;
}

Measured memory_bytes: 4608
import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] a = new char[n][n];
        char[][] b = new char[m][m];
        String s;
        for (int i = 0; i < n; i++) {
            s = sc.next();
            for (int j = 0; j < n; j++) {
                a[i][j] = s.charAt(j);
            }
        }


        for (int i = 0; i < m; i++) {
            s = sc.next();
            for (int j = 0; j < m; j++) {
                b[i][j] = s.charAt(j);
            }
        }
        for (int i = 0; i <= n-m; i++) {
            for (int j = 0; j <= n-m; j++) {
                boolean f = true;
                for (int k = 0; k < m; k++) {
                    for (int l = 0; l < m; l++) {
                        if(b[k][l] != a[i+k][j+l]){
                            f = false;
                        }
                    }
                }
                if(f){
                    io.YesNo(true);
                    return;
                }
            }
        }
        io.YesNo(false);

    }
}

class io{
    public static void br(){
        System.out.println("");
    }

    public static void YesNo(boolean f) {
        System.out.println(f?"Yes":"No");
    }
    public static void YESNO(boolean f) {
        System.out.println(f?"YES":"NO");
    }

}

class Algo{
    public static boolean isOdd(int n){
        return n % 2 == 1;
    }
    public static boolean isEven(int n){
        return n % 2 == 0;
    }


}



Measured memory_bytes: 23636
import qualified Data.Map as M
import Data.List

f :: [String]->[(Int,Int)]
f []=[]
f (x:xs) =let (a:b:[])=map read (words x)::[Int]
          in (a,b):f xs

f3 ::[Int]->Int->Int
f3 xs rx=if null (dropWhile (>= rx) xs) then (-1) else head (dropWhile (>= rx) xs)  

f2::[Int]->[(Int,Int)]->[(Int,Int)]->[Int]
f2 _ _ [] =[]
f2 xs [] ((_,rx):rs)=let tx=f3 xs rx
                     in if tx==(-1) then 0:f2 xs [] rs else 1:f2 (delete tx xs) [] rs
f2 xs allbs@((by,bx):bs) allrs@((ry,rx):rs)
        |by<ry=f2 (reverse (sort (bx:xs))) bs allrs
        |otherwise=let tx=f3 xs rx
                   in if tx==(-1) then 0:f2 xs allbs rs else 1:f2 (delete tx xs) allbs rs


main = do
        e<-getLine
        e2<-getContents
        let n=read e::Int
            xs=lines e2
            bs=take n xs
            rs=drop n xs
            bs2=sort $ f bs
            rs2=sort $ f rs
        putStrLn $ show $ sum $ f2 [] bs2 rs2 

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

# カードがあるマスと周囲を合わせた9マスに存在するカードの数だけ裏返る
# 裏返る回数が奇数回数になるのは、端以外の全てのカード

if N == 1 and M == 1:
    print(1)
elif N == 1:
    print(M-2)
elif M == 1:
    print(N-2)
else:
    print(N*M - 2*N -2*M + 4)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rt "\n"
#define sp " "
#define test1 cout << "test1" << endl;
#define test2 cout << "test2" << endl;
#define fixprecision(n) fixed; cout << setprecision(n)
#define kyopro ios::sync_with_stdio(false);cin.tie(NULL);
#define MOD 1000000007
#define rep(i, s, N) for(ll i{s}; i < N; i++)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

vector<ll> iro;
vector<vector<vector<ll>>> uvw;

void tansaku(ll kodomo, ll oya, ll kodomonoiro){
  iro.at(kodomo) = kodomonoiro;
  //cout << kodomo << sp << oya << kodomonoiro << rt;
  for(auto&& magokouho : uvw.at(kodomo)){
    ll &mago = magokouho.at(0);
    ll &magotonokyori = magokouho.at(1);
    if(mago != oya){
      if(magotonokyori % 2){
        tansaku(mago, kodomo, 1-kodomonoiro);
      }
      else{
        tansaku(mago, kodomo, kodomonoiro);
      }
    }
  }
}

int main(){
  kyopro;
  ll N;
  cin >> N;
  iro.assign(N, 0);
  uvw.assign(N, vector<vector<ll>>(0,vector<ll>(2)));
  rep(i, 0, N-1){
    ll u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    uvw.at(u).push_back({v, w});
    uvw.at(v).push_back({u, w});
  }
  tansaku(0, -114514, 0);
  for(auto&& i : iro){
    cout << i << rt;
  }
}

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

typedef long long ll;

int main()
{
    ll x, k, d;
    scanf("%lld%lld%lld", &x, &k, &d);

    x = abs(x);
    ll temp1 = x / d;
    ll temp2 = x % d;

    if(temp2 == x)
    {
        if(k % 2 == 0)
        {
            printf("%lld", x);
        }

        else
        {
            printf("%lld", (ll)abs(x-d));
        }
    }

    else //temp2 != x
    {
        if(k >= temp1)
        {
            x -= temp1 * d;
            if(x >= 0)
            {
                if((k-temp1) % 2 == 0)
                {
                    printf("%lld", x);
                    return 0;
                }

                else
                {
                    printf("%lld", (ll)abs(x-d));
                    return 0;
                }
            }

            else
            {
                if((k-temp1) % 2 == 0)
                {
                    printf("%lld", (ll)abs(x));
                    return 0;
                }

                else
                {
                    printf("%lld", (ll)abs(x+d));
                    return 0;
                }
            }
        }

        else
        {
            printf("%lld", x-k*d);
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 3864
package main

import (
	"fmt"
	"math"
)

func main() {
	var A, B int
	fmt.Scan(&A, &B)

	ans := -1
	for i := 1; i < B*15; i++ {
		pa := float64(i) * 0.08
		pb := float64(i) * 0.1

		sa := math.Floor(pa)
		sb := math.Floor(pb)

		if sa == float64(A) && sb == float64(B) {
			ans = i
			break
		}
	}

	fmt.Println(ans)
}


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

const long long INF = 1e15 + 1;

int main() {
  long long n, mn = INF;
  cin >> n;
  for ( int i = 0; i < 5; i++ ) {
    long long caryy;
    cin >> caryy;
    mn = min(caryy, mn);
  }

  long long ans = ( n%mn == 0 ) ? (n/mn) + 4 : (n/mn) + 5;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
import sys
import bisect

input = sys.stdin.readline
N = int(input().strip())
A = sorted(map(int, input().strip().split()))

if A[0] < 0:
    zero_i = bisect.bisect_left(A, 0)
    if zero_i == N:
        print(A[N-1] - sum(A[0:N-1]))
        i = 0
        now = A[N-1]
        while i < N-1:
            print(now, A[i])
            now -= A[i]
            i += 1
    else:
        print(sum(A[zero_i:N])-sum(A[0:zero_i]))
        i = zero_i
        now = A[0]
        while i < N-1:
            print(now, A[i])
            now -= A[i]
            i += 1
        print(A[N-1], now)
        now = A[N-1] - now
        i = 1
        while i < zero_i:
            print(now, A[i])
            now -= A[i]
            i += 1
else:
    print(sum(A[1:N])-A[0])
    i = 1
    now = A[0]
    while i < N-1:
        print(now, A[i])
        now -= A[i]
        i += 1
    print(A[N-1], now)


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

int main(){
	int N, i;
	cin >> N;
	int a[N];
	for(i=0; i<N; i++){
		cin >> a[i];
	}
	
	int count=0, j=0;
	i=0;
	do{
		i += j;
		j=0;
		do{
			j++;
		}while(a[i]==a[i+j]);
		if(j%2==0)	count += j/2;
		else		count += (j-1)/2;
	}while(i<N);
	
	cout << count << endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LLI long long int


using namespace std;

LLI left(LLI here,LLI lsum);
LLI right(LLI here,LLI rsum);
LLI po();
LLI ko();
LLI ans,sum,x,k,n,num[110000];

int main(){

    while(1){

    cin >> n >> k;
    if(n==0&&k==0)break;

    for(int i=0;i<k;i++){
        cin >> x;
        num[x]=1;
    }

    cout << po() << endl;

    ans=0;sum=0;

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


    }

return 0;

}

LLI po(){

    if(num[0]==1){

    for(int i=0;i<n;i++){
        if(num[i]==0){
            sum=left(i-1,0)+right(i+1,0)+1;
            if(ans<sum)ans=sum;
        }
    }

    }else ans=ko();

    return ans;

}

LLI right(LLI here,LLI rsum){
    if(num[here]==1)return right(here+1,rsum+1);
    else return rsum;
}

LLI left(LLI here,LLI lsum){
    if(num[here]==1)return left(here-1,lsum+1);
    else return lsum;

}

LLI ko(){

    LLI a=0;

    for(int i=1;i<n+1;i++){

        if(num[i]==1)sum++;
        else {
            if(a<sum)a=sum;
            sum=0;
        }

    }

    return a;
}

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define endl '\n'
#define all(x) x.begin(), x.end()

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
using vvll = vector< vector<ll> >;
using vll = vector<ll> ;
using vb = vector<bool> ;
using pll = pair<ll, ll> ;

const ll maxs = 1e6+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e15;


ll fast(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        y >>= 1;
    }
    return res;
}

ll inv(ll n){
    return fast(n,mod-2);
}

void pre(){

    

}

ll add(ll a,ll b){
    return ((a+b)%mod+mod)%mod;
}

ll mul(ll a,ll b){
    return ((a*b)%mod+mod)%mod;
}

ll sub(ll a,ll b){
    return ((a-b)%mod+mod)%mod;
}

void solve(){

    ll n,k;
    cin >> n >> k;
    ll a[n+1];
    vll pos,neg;
    for(ll i=1;i<=n;i++){
        cin >> a[i];
        if(a[i]>=0){
            pos.pb(a[i]);
        }else{
            neg.pb(a[i]);
        }
    }    
    sort(a+1,a+n+1);
    sort(all(pos),greater<ll>());
    sort(all(neg));
    if(k == n){
        ll ans=1;
        for(ll i=1;i<=n;i++){
            ans = mul(ans,a[i]);
        }
        cout << ans;
        return;
    }
    if( neg.size() == n){
        ll ans=1;
        if(k%2==0){
            // ans is pos;
            for(ll i=0;i<k;i++){
                ans  = mul(ans,neg[i]);
            }
        }else{
            // ans is neg;
            reverse(all(neg));
            for(ll i=0;i<k;i++){
                ans = mul(ans,neg[i]);
            }
        }
        cout << ans;
        return;
    }
    // always pos
    vll prepos(pos.size()+1),preneg(neg.size()+1);
    prepos[0] = preneg[0] = 1;
    ll pre=1;
    for(ll i=1;i<=pos.size();i++){
        pre = mul(pre,pos[i-1]);
        prepos[i] = pre;
    }
    pre=1;
    for(ll i=1;i<=neg.size();i++){
        pre = mul(pre,neg[i-1]);
        preneg[i] = pre;
    }

    ll nPos = min((ll)pos.size(),k);
    ll nNeg = k - nPos;
    if(nNeg&1){
        nNeg++;
        nPos--;
    }
    while(nNeg+2 <= neg.size() and nPos >= 2 ){
        ll val1 = pos[nPos-1]*pos[nPos-2];
        ll val2 = neg[nNeg]*neg[nNeg+1];
        if(val1 >= val2)
            break;
        nPos -= 2;
        nNeg += 2;
    }
    ll ans = mul(prepos[nPos],preneg[nNeg]);
    cout << ans;

}

int main(){
    // #ifndef ONLINE_JUDGE
    // freopen("input00.txt","r",stdin);
    // #endif
    IOS;
    pre();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();   
    }
    return 0;
}

Measured memory_bytes: 7984
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }

main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i : a) cin >> i;
    set <int> c(all(a));
    if (sz(c) == n) {
        cout << "YES\n";
    }
    else cout << "NO\n";
}


Measured memory_bytes: 13512
#include <math.h>
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX / 2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vb = vector<bool>;
using vvb = vector<vb>; 
using vvvb = vector<vvb>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using psi = pair<string, int>;


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

  ll A, B, X; cin >> A >> B >> X;
  
  double ans = 0;
  if ((A*B/2.0)*A >= X) { // 三角形に収まるなら
    ans = atan2(B, 2.0*X/(A*B));
  } else { // 台形になる
    ans = atan2(2.0*B-2.0*X/(A*A), A);
  }

  ans *= 180.0/M_PI;
  printf("%.10f\n", ans);

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<queue>

using namespace std;

int main(){
	string s;
	cin >> s;
	const int n = s.size();
	s = "." + s;
	bool exist = true;
	if(s[1] == '0' || s[n] == '1'){
		exist = false;
	}
	for(int i = 1; i < n; ++i){
		if(s[i] != s[n - i]){
			exist = false;
		}
	}
	if(!exist){
		cout << -1 << endl;
		return 0;
	}

	s[n] = '1';
	queue<int> ones;
	for(int i = 1; i <= n; ++i){
		if(s[i] == '1'){
			ones.push(i);
		}
	}
	for(int i = 1; i < n; ++i){
		if(i == ones.front()){
			ones.pop();
		}
		cout << i << " " << ones.front() << endl;
	}
	return 0;
}


Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<long long> vl;
typedef vector<vector<ll>> vll;
typedef vector<bool> vb;
typedef set<int> si; 
typedef queue<int> qi;
typedef stack<int> sti;
typedef priority_queue<int> pqi;
#define fori(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,b,a) for(int i = (b); i >= (a); --i)
#define all(a) (a).begin(), (a).end()
//#define __builtin_popcountll bitCountLL
//#define __builtin_popcount bitCount
//__builtin_ctz 末尾0的个数, __builtin_clz 前导0的个数
//__builtin_ffs 最后一个1的位置
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//std::uniform_int_distribution<long long> rg(1,1e18);
#define maxn 100005
#define Mod 1000000007
const int INF = 2e9;
const ll ML = 4e18;
    
void solve() {
    int n;
    cin >> n;
    vl a(n);
    fori(i,0,n) cin >> a[i];
    ll sum = 0;
    fori(i,0,n) {
        sum += a[i];
    }
    ll ans = 0;
    fori(i,0,n) {
        sum -= a[i];
        ans = (ans + a[i] * (sum % Mod)) % Mod;
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	//cout.precision(30); cout << fixed;
	//freopen("D:\\data_in.txt", "r", stdin);
   
    solve();
   
    /*
    clock_t start,finish;
    start = clock();
    
    finish = clock();
    cout << "\n" << (double)(finish - start) / (double)(CLOCKS_PER_SEC) * 1000 << "ms" << endl;
    */
    return 0;
}

/***************************************************************
 question:
 idea:
 tag:
 record:
 ***************************************************************/


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

using namespace std;

using ll = int64_t;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = 2147483647;
constexpr ll L_INF = 9223372036854775807LL;

//===


ll bpow(ll a, int n)
{
	ll res = 1;
	for (; n > 0; n >>= 1) {
		if (n & 1) res *= a;
		a *= a;
	}
	return res;
}



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

	priority_queue<ll> pq;
	for (int i = 0; i < N; ++i) {
		int a;
		cin >> a;
		pq.push(a);
	}

	for (int i = 0; i < M; ++i) {
		ll tmp = pq.top();
		pq.pop();
		pq.push(tmp / 2);
	}

	ll ans = 0;
	for (int i = 0; i < N; ++i) {
		ans += pq.top();
		pq.pop();
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1400
use std::io;

fn main() {
    let numbers = input_number();
    let a = numbers[0];
    let b = numbers[1];
    let c = numbers[2];
    
    let mut counter = 0;
    for index in a..b + 1 {
        if c % index == 0 { 
            counter += 1 
        }
    }  

    println!("{}", counter);
}

#[allow(dead_code)]
fn input_number() -> Vec<i32> {
    let mut input = String::new();

    io::stdin().read_line(&mut input)
        .expect("Failed to read line");

    let vec: Vec<i32> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap_or(0))
        .collect();
    vec
}



Measured memory_bytes: 5028
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b.begin(), b.end());

	int t = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) {
			t++;
		}
	}
	if (t > 2) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}

	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 rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    int n; cin >> n;
    vi v(n);
    ll tot = 0;
    rep(i, n){
        int a, b; cin >> a >> b;
        tot -= b;
        v[i] = a + b;
    }
    sort(rall(v));
    rep(i, n) {
        if(i % 2 == 0) tot += v[i];
    }
    cout << tot << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    unordered_set<int> adj[n];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }

    n--;
    for (int x : adj[0]) {
        if (adj[x].find(n) != adj[x].end()) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}


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

int main(){
	int N,M,shukudai=0;
  	cin>>N>>M;
  	int A[M];
  	for(int i=0;i<M;i++){
    	cin>>A[i];
      	shukudai=shukudai+A[i];
    }
  	if(shukudai>N) {
    	cout<<"-1";
      	return 0;
    }
  	cout<<N-shukudai;
  	return 0;
}

Measured memory_bytes: 3624
S=list(map(int,input().split()))
n=int(input())

for i in range(n):
  q=list(map(int,input().split()))
  if q in [[S[3],S[1]],[S[1],S[2]],[S[2],S[4]],[S[4],S[3]]]:
           print(S[0])
           
  if q in [[S[0],S[3]],[S[3],S[5]],[S[5],S[2]],[S[2],S[0]]]:
           print(S[1])
           
  if q in [[S[0],S[1]],[S[1],S[5]],[S[5],S[4]],[S[4],S[0]]]:
           print(S[2])
           
  if q in [[S[4],S[5]],[S[5],S[1]],[S[1],S[0]],[S[0],S[4]]]:
           print(S[3])
           
  if q in [[S[0],S[2]],[S[2],S[5]],[S[5],S[3]],[S[3],S[0]]]:
           print(S[4])
  
  if q in [[S[2],S[1]],[S[1],S[3]],[S[3],S[4]],[S[4],S[2]]]:
           print(S[5])


Measured memory_bytes: 5612
N = int(input())
L = list(map(int, input().split()))
 
money = 1000
stocks = 0
 
for i in range (0, N-1):
    if L[i+1] > L[i]:
        stocks+= money//L[i]
        money = money%L[i]
    elif L[i+1] == L[i]:
        continue
    else:
        money+= stocks*L[i]
        stocks = 0

print(money+stocks*L[-1])

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

int main() {
  string s, t;
  cin >> s;
  cin >> t;

  bool succ = (t.length() == s.length() + 1);
  for (int i = 0; i < s.length(); i++)
    succ = succ && (s[i] == t[i]);
  
  if (succ)
    printf("Yes\n");
  else
    printf("No\n");

  return 0;
}

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

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;

using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;


/**
 * @brief
 * 単一始点最短路(ダイクストラ)
 * 二分ヒープ(priority_queue)を使ってO((E+V)logV)
 * @author ?
 * @date 2019/12
 *
 * @param[in] g グラフ
 * @param[in] s 始点
 * @param[in] inf 到達不可能を表す無限値
 * @return vector<T> sからそれぞれの頂点への最短路
 *
 * @details
 * 2020/04/07 コメント追加、テスト有無のチェック by Md
 * 2020/05/04 inf に使う値を明示的に渡す. by haraba-k
 */


int main() {

    int H, W, K; cin >> H >> W >> K;

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    --x1, --y1, --x2, --y2;

    vector<string> c(H);
    REP(i, H) cin >> c[i];

    using vvvi = vector<vvi>;
    vvvi dist(4, vvi(H, vi(W, INF)));

    using T = tuple<int,int,int,int>;
    priority_queue<T, vector<T>, greater<>> que;
    REP(l, 4) {
        dist[l][x1][y1] = 0;
        que.emplace(0, l, x1, y1);
    }

    int dirx[] = {0, 1, 0, -1}, diry[] = {1, 0, -1, 0};

    while (!que.empty()) {
        int d, l, x, y;
        tie(d, l, x, y) = que.top(); que.pop();
        if (dist[l][x][y] < d) continue;

        // 方向転換
        REP(l1, 4) {
            int alt = dist[l][x][y];
            if (alt % K) alt += K - alt % K;
            if (dist[l1][x][y] > alt) {
                dist[l1][x][y] = alt;
                que.emplace(alt, l1, x, y);
            }
        }

        // l方向に1マス進む
        int nx = x + dirx[l], ny = y + diry[l];
        if (nx < 0 or ny < 0 or nx >= H or ny >= W or c[nx][ny] == '@') continue;
        if (dist[l][nx][ny] > dist[l][x][y] + 1) {
            dist[l][nx][ny] = dist[l][x][y] + 1;
            que.emplace(dist[l][nx][ny], l, nx, ny);
        }
    }

    int ans = INF;
    REP(l, 4) {
        if (dist[l][x2][y2] != INF) chmin(ans, (dist[l][x2][y2] + K - 1) / K);
    }

    cout << (ans == INF ? -1 : ans) << endl;

    return 0;
}



Measured memory_bytes: 32372
import Control.Applicative
import Control.Monad

main = do
  _ <- getLine
  xs <- (map read . words) <$> getLine
  putStrLn $ show $ solve xs 0
  
solve :: [Int] -> Int -> Int
solve xs acc =
  if dividable xs then
    solve (map (\n -> n `div` 2) xs) (acc+1)
  else
    acc
    
dividable :: [Int] -> Bool
dividable xs =
  if (flag == 0) then True else False
  where
    flag = foldr (+) 0 (map (\n -> n `mod` 2) xs)

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string input; getline(cin, input);
    string res;
    for(int i = 0; i < input.size(); i++) {
        char tmp = input[i];
        if ('a' <= tmp && tmp <= 'z') cout << (char)(tmp-'a'+'A');
        else if ('A' <= tmp && tmp <= 'Z') cout << (char)(tmp-'A'+'a');
		else cout << tmp;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3056
#include <iostream>

using namespace std;
using ull =unsigned long long;
class Human
{
public:
	Human(ull money):
		money(money)
	{}
private:
	ull money;
public:
	ull CalcHappy()
	{
		int result = 0;

		ull remainder = money % 500;
		ull divided = money / 500;

		result += divided * 1000;

		divided = remainder/ 5;
		result += divided * 5;
		return result;
	}

};


int main()
{
	ull n;
	cin >> n;

	Human* h = new Human(n);
	cout << h->CalcHappy();

	delete h;
    return 0;
}


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

using namespace std;

#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define sz(x) (int)(x).size()
#define f(n) for(int i=0;i<n;++i)
#define f2(n) for(int j=0;j<n;++j)
#define f3(n) for(int k=0;k<n;++k)
#define F(i,x,n,y) for(i=x;i<n;i+=y)
#define fi(i) for(i=0;i<n;++i)
#define fa(x,y) for(auto x:y)

//Warsaw debug template
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
    enable_if<sizeof dud<c>(0) x 1,debug&>::type operator<<(c i){
sim > struct rge {c b,e;};
sim > rge<c> range(c i, c j) {return rge<c>{i,j};}
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug{
#ifdef LOCAL
~debug() {cerr<<endl; }
eni(!=) cerr<< boolalpha << i; ris;}
eni(==) ris <<range(begin(i),end(i)); }
sim, class b dor(pair<b,c> d){
ris<<"("<<d.first<<","<<d.second<<")";
}
sim dor(rge<c> d){
    *this << "[";
    for(auto it=d.b;it!=d.e;++it)
        *this <<"," +(it==d.b)<< *it;
    ris<<"]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) "["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"
//End of debug template        
    

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    if(s[0]!='A'){
        cout<<"WA"<<endl;
        return 0;
    }
    if(s[0]!='A'){
        cout<<"WA"<<endl;
        return 0;
    }
    int cnt=0;
    int i;
    int oc=-1;
    F(i,2,sz(s)-1,1){
        if(s[i]=='C'){
             ++cnt;
             if(oc==-1) oc=i;

        }
    }
    if(cnt!=1){
        cout<<"WA"<<endl;
        return 0;
    }
    f(sz(s)){
        if(i==oc||i==0) continue;
        if((int)s[i]<=90){
            cout<<"WA"<<endl;
            return 0;
        }
    }
    cout<<"AC"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N, min = 2e9, cost = 0;
    cin >> N;
    vector<int> a(N);
    for (int& i : a) cin >> i;
    for (int i = -100; i <= 100; i++, cost = 0) {
        for (int j : a) cost += (j - i) * (j - i);
        if (cost < min) min = cost;
    }
    cout << min << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

vi g[100000];
int dp[100000][11];
int v[100000],d[100000],c[100000];
void f(int a,int b,int c){
  if(dp[a][b])return;
  dp[a][b]=c;
  if(b==0)return;
  f(a,b-1,c);
  int i;
  rep(i,g[a].size())
    f(g[a][i],b-1,c);
}
int main(void) {
  int i,j;

  int n,m;
  cin>>n>>m;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  int q;
  cin>>q;
  rep(i,q)cin>>v[i]>>d[i]>>c[i];

  rep(i,100000)rep(j,11)dp[i][j]=0;
  for(i=q-1;i>=0;i--){
    f(v[i]-1,d[i],c[i]);
  }

  rep(i,n)cout<<dp[i][0]<<endl;
}


Measured memory_bytes: 12024
// ARC087
// D - FT Robot

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_S = 8000;

string s;
int xy[2];

bool solve() {
    int t_cnt = 0, f_cnt = 0;
    vector<int> mv[2];
    for (char c : s) {
        if (c == 'T') {
            mv[t_cnt % 2].push_back(f_cnt);
            f_cnt = 0;
            t_cnt++;
        } else {
            f_cnt++;
        }
    }
    mv[t_cnt % 2].push_back(f_cnt);

    for (int k = 0; k <= 1; k++) {
        bool dp[2][2 * MAX_S + 1];
        memset(dp[0], 0, sizeof(dp[0]));
        dp[0][0 + MAX_S] = true;
        for (int j = 1; j <= (int)mv[k].size(); j++) {
            memset(dp[j % 2], 0, sizeof(dp[j % 2]));
            int d = mv[k][j - 1];
            for (int i = 0; i < 2 * MAX_S + 1; i++) {
                if (i + d < 2 * MAX_S + 1) {
                    dp[j % 2][i + d] = dp[j % 2][i + d] || dp[(j - 1) % 2][i];
                }
                if (i - d >= 0 && !(k == 0 && j == 1)) {
                    dp[j % 2][i - d] = dp[j % 2][i - d] || dp[(j - 1) % 2][i];
                }
            }
        }
        if (!dp[(int)mv[k].size() % 2][xy[k] + MAX_S]) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> s;
    cin >> xy[0] >> xy[1];

    cout << (solve() ? "Yes" : "No") << endl;

    return 0;
}


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

using namespace std;
using ll = long long;

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

    ll N, W; cin >> N >> W;

    vector<ll> w(N), v(N);
    for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

    vector<ll> dp(W + 1, 0), temp;
    for (int j = w[0]; j <= W; ++j) dp[j] = v[0] > 0 ? v[0] : 0;

    for (int i = 1; i < N; ++i) {
        temp = dp;
        for (int j = 0; j <= W; ++j)
            if (j >= w[i] && temp[j - w[i]] + v[i] > temp[j])
                dp[j] = temp[j - w[i]] + v[i];
    }

    cout << dp[W] << "\n";

    return 0;
}


Measured memory_bytes: 1792
//
// ALDS1_1_B GCD
// implementation-2 ユークリッドの互除法
//


#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (x<y) swap(x,y);
	if (y==0) return x;
	return gcd(y, x % y ); 
}


int main() {
	int x,y;
	cin >> x >> y;

	int ans=gcd(x,y);
	cout << ans << endl;
}



Measured memory_bytes: 3096
#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

struct Node {
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;


void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    z = (Node *) malloc(sizeof(Node));

    z->key = k;
    z->left = NIL;
    z->right = NIL;

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

    z->parent = y;

    if (y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }

}

void inorder(Node *u) {
    if (u == NIL) {
        return;
    }
    inorder(u->left);
    cout << " " << u->key;
    inorder(u->right);
}

void preorder(Node *u) {
    if (u == NIL) {
        return;
    }
    cout << " " << u->key;
    preorder(u->left);
    preorder(u->right);
}

Node *find(int k) {
    Node *x = root;
    while (x != NIL && k != x->key) {
        if (k < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    return x;
}

int main() {
    int n, x;
    string com;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> com;
        if (com == "insert") {
            cin >> x;
            insert(x);
        } else if (com == "print") {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        } else {
            cin >> x;
            Node *t = find(x);
            if (t != NIL) {
                cout << "yes" << endl;
            } else {
                cout << "no" << endl;
            }
        }
    }
    return 0;
}


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

int main(){
    int n;
    cin>>n;
    int c[n],s[n],f[n];
    for(int i=0;i<n;i++) cin>>c[i]>>s[i]>>f[i];

    int ans=0;

    for(int i=0;i<n-1;i++){
        ans=s[i]+c[i];
        for(int j=i+1;j<n-1;j++){
            int k=0;
            if(ans!=s[j]){
                while(ans>s[j]+k*f[j]){
                    k++;
                }
                ans=s[j]+k*f[j];
            }
            ans+=c[j];
        }
        cout<<ans<<endl;

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


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

int top,s[1000];

void push(int x){
	s[++top]=x;
}

int pop(){top--;
	return s[top+1];
}

int main(){
	int a,b;
	char s[100];
	
	top=0;
	
	while(scanf("%s",s)!=EOF){
		if(s[0]=='+'){
			a=pop();
			b=pop();
			push(a+b);
		}else if(s[0]=='-'){
			b=pop();
			a=pop();
			push(a-b);
		}else if(s[0]=='*'){
			a=pop();
			b=pop();
			push(a*b);
		}else{
			push(atoi(s));
		}
	}
	
	printf("%d\n",pop());
	
	return 0;
}

Measured memory_bytes: 548
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;

int main() {
  int n, m, X, Y;
  cin >> n >> m >> X >> Y;
  rep(i, n) {
    int x;
    cin >> x;
    X = max(X, x);
  }
  rep(i, m) {
    int y;
    cin >> y;
    Y = min(Y, y);
  }
  if (X < Y) cout << "No War" << endl;
  else cout << "War" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1LL << 60;
const int MOD = 1000000007;

template <typename T>
void print(const T &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

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;
}

const int MAX = 100010;

int n, k;
ll h[MAX];
ll dp[MAX];

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

Measured memory_bytes: 5152