akhauriyash/Code-Regression huggingface dataset:
import java.math.BigInteger;
import java.util.*;

public class Main{
  public static long inved(long a, long modulo){
    long x = 1, y = 0, u = 0, v = 1, k = a, l = modulo;
    long tmp;
    while (l != 0){
      tmp = x;
      x = u;
      u = tmp - u * (k / l);
      tmp = y;
      y = v;
      v = tmp - v * (k / l);
      tmp = k;
      k = l;
      l = tmp % l;
    }
    return (x + modulo) % modulo;
  }
  public static BigInteger gcd(BigInteger a, BigInteger b){
    BigInteger x = a, y = b;
    BigInteger tmp;
    while (y != BigInteger.ZERO){
      tmp = x;
      x = y;
      y = tmp.mod(y);
    }
    return x;
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long modulo = (long)1e9 + 7;
    int n = sc.nextInt();
    long a[] = new long[n];
    BigInteger L = BigInteger.ONE;
    BigInteger t;
    for (int i=0;i<n;i++){
      a[i] = sc.nextLong();
      t = gcd(L, BigInteger.valueOf(a[i]));
      t = BigInteger.valueOf(a[i]).divide(t);
      L = L.multiply(t);
    }
    long S = 0l;
    for (int i=0;i<n;i++){
      S += inved(a[i], modulo);
      S %= modulo;
    }
    L = L.multiply(BigInteger.valueOf(S));
    System.out.println(L.mod(BigInteger.valueOf(modulo)));
  }
}

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

int main(){
  int n,mp[302][302],x[302][302]={},y[302][302]={};
  cin>>n;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)cin>>y[i][j],mp[i][j]=x[i][j]=y[i][j];
  
  int ans=max(y[0][n-1],y[n-1][0]);
  for(int i=0;i<n;i++)
    for(int j=n-2;j>=0;j--) {
      x[i][j]+=x[i][j+1];
      y[j][i]+=y[j+1][i];
      if(ans<x[i][j])ans=x[i][j];
      if(ans<y[j][i])ans=y[j][i];
    }


  int sum[302][302],K[2][302][302]={};


  for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++) sum[i][j]=-100000000;

  int t=0;
  while(1){
    t++;
    for(int i=0;i<n;i++) //yoko
      for(int j=i+1;j<n;j++) {//yoko
	int a=K[t%2][i][j];
	K[(t+1)%2][i][j]=a;
	sum[i][j]=-100000000;
	for(int k=a+1;k<n;k++) { //tate
	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);
	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);
	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;
	  ans=max(ans,sum[i][j]);
	}
      }

    int f=1;
    for(int i=0;i<n;i++) //yoko
      for(int j=i+1;j<n;j++) //yoko
	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){
	  f=0;
	  int X=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);
	  sum[i][j]+=X;
	  ans=max(ans,sum[i][j]);
	}
    if(f)break;
  }
  cout <<ans<<endl;
	  
  return 0; 
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> L(M), R(M);
    rep(i, M) cin >> L[i] >> R[i];

    // (L[i], R[i])の二次元累積和を求める
    vector<vector<int>> sum(N + 1, vector<int>(N + 1, 0));
    rep(i, M) sum[L[i]][R[i]]++;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            sum[i][j] += sum[i - 1][j];
            sum[i][j] += sum[i][j - 1];
            sum[i][j] -= sum[i - 1][j - 1];
        }
    }

    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        int ans = sum[r][r] - sum[r][l - 1] - sum[l - 1][r] + sum[l - 1][l - 1];
        cout << ans << endl;
    }
}

Measured memory_bytes: 3456
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

	public static void main(String[] arg) throws IOException
	{
		double a,b,degree,rad,revrad,cc,cx,cy;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");

		a = Double.parseDouble(str[0]);
		b = Double.parseDouble(str[1]);
		degree = Double.parseDouble(str[2]);

		rad = Math.PI * (degree/180);
		revrad = Math.PI * ( (180-degree)/180);

		cx = b * Math.cos(revrad) + a;
		cy = b * Math.sin(revrad);

		cc = Math.pow(cx, 2) + Math.pow(cy, 2);

		System.out.printf("%.5f\n",a*b*Math.sin(rad) / 2);
		System.out.printf("%.5f\n",Math.sqrt(cc) + a + b);
		System.out.printf("%.5f\n",cy);
	}
}

Measured memory_bytes: 24640
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define all(x) (x).begin() (x).end()
#define rall(x) (x).rbegin() (x).rend()
typedef pair<int,int> pii;
typedef long long ll;

int main(){
	int n; cin>>n;
	int arr[n];
	for(int i=0; i<n; i++){
		cin>>arr[i];
	}
	if(n<3)cout<<0<<endl;
	else{
		int nt=0;
		for(int i=0; i<n-1; i++){
			int a=arr[i];
			for(int j=i+1; j<n; j++){
				int b=arr[j];
				for(int k=j+1; k<n; k++){
					int c=arr[k];
					if(a!=b && b!=c && c!=a){
						if(a+b>c && a+c>b && c+b>a){
							nt++;
						}
					}
				}
			}
		}
		cout<<nt<<endl;
	}
}



Measured memory_bytes: 3648
K, A, B = map(int, input().split())

if B - A <= 2:
    print(K + 1)
else:
    time = max(0, (K - (A - 1)) // 2)
    ans = A + (B - A) * time
    if (K - (A - 1)) % 2 == 1:
        ans += 1
    print(ans)




Measured memory_bytes: 38384
N  = gets.to_i
sum = 0.0
$<.read.split(/\n/).each do |m|
  s = m.split
  case s[1]
  when 'JPY'
    sum += s[0].to_f
  when 'BTC'
    sum += s[0].to_f * 380_000.0
  end
end
puts sum



Measured memory_bytes: 1788
import Control.Monad
import Control.Applicative
import Data.List

toInt :: (String -> Int)
toInt x = read x ::Int

getInts = do
  x <- getLine
  let y = (map$toInt)$words x 
  return y

getStr = do
  x <- getLine
  let y = words x 
  return y  

main :: IO ()
main = do
  x <- getInts 
  let a = sort x
  let b = splitAt 1 a
  let f = fst b
  let s = snd b
  print $ (foldl (+) 0 $ map (\x -> snd x * 10^(fst x)) $ zip [0..((length s)-1)] s) + head f


Measured memory_bytes: 508
def gcd(x,y):
    if x==0:return y
    else:return gcd(y%x,x)
def lcm(x,y):
    return x*y//gcd(x,y)
 
a,b,c,d = map(int,input().split())
a -= 1
# print(gcd(c,d),lcm(c,d))
ba = b - b//c - b//d + b//lcm(c,d)
aa = a - a//c - a//d + a//lcm(c,d)
print(ba - aa)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main() {
        double w,h,x,y,area,cx,cy;
        int different_ways = 0;
        cin >> w >> h >> x >> y;
        area = w * h / 2.0;
        cx = w / 2.0;
        cy = h / 2.0;
        if (cx == x && cy == y)
                different_ways = 1;
        printf("%f %d \n", area, different_ways);  
        return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mod 1000000007LL
#define eps 0.0001

#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // ---------------------
    // コーディング開始
    // ---------------------
    ll a,b,x;

    cin >> a >> b >> x;
    ll ans ;
    if (b!=0) ans = b/x;

    if (a>0) ans-=((a-1)/x);
    else ans++;

    pri(ans);
    return 0;
}



Measured memory_bytes: 256
def is_correct(a, b, c, i):
    assert len(a) == N
    assert len(a[i]) == M
    return (sum([a[i][j] * b[j] for j in range(M)]) + c) > 0


if __name__ == "__main__":

    N, M, C = [int(x) for x in input().split(" ")]
    B = [int(x) for x in input().split(" ")]
    A = []
    for _ in range(N):
        A.append([int(x) for x in input().split(" ")])
    count = 0
    for i in range(N):
        if is_correct(A, B, C, i):
            count += 1

    print(count)


Measured memory_bytes: 3064
#! /usr/bin/env python3

import sys
import math
from functools import reduce
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def gcd(numbers):
    return reduce(math.gcd, numbers)


N, K, *A = map(int, read().split())

G = gcd(A)

if (K % G == 0) & (K <= max(A)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Measured memory_bytes: 35924
import itertools
import numpy as np
N, M, X = map(int, input().split())

book = []
for _ in range(N):
    tmp = [int(i) for i in input().split()]
    book.append(tmp)

# print(book)


lis = list(range(N))
result = []
for n in range(1, len(lis)+1):
    for conb in itertools.combinations(lis, n):
        result.append(list(conb))  # タプルをリスト型に変換
# print(result)

ans = []

for com in result:
    # print(com)
    l = len(com)
    s_skill = np.array([0] * M)
    money = 0
    for idx in com:
        money += book[idx][0]
        s_skill += np.array(book[idx][1:])

    flg = True
    for i in s_skill:
        if i < X:
            flg = False
    ans.append([flg, money])

# print(ans)

output = -1
b_flg = False
for i in ans:
    b = i[0]
    money = i[1]
    if b:
        b_flg = True
        if output == -1:
            output = money
        output = min(output, money)

if not b_flg:
    print(-1)
else:
    print(output)


Measured memory_bytes: 27744
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll  long long 
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=2e5+9;
const ll MOD=1e9+7;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
int pexp[MAX];
ll dp[1000];
int main() 
{

	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    int n;
    cin>>n;
    ll arr[n+1];
    for(int i=1;i<=n;i++)
    	cin>>arr[i];
    dp[1]=1000;
    for(int i=2;i<=n;i++){
    	dp[i]=dp[i-1];
    	for(int j=1;j<=i-1;j++){
    		ll b= dp[j]/arr[j];
    		ll cur = dp[j]+(arr[i]-arr[j])*(b);
    		dp[i]=max(dp[i], cur);
    	}
    }
    cout<<dp[n];
}

Measured memory_bytes: 3568
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int max = 0;
        int maxnum = 0;
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
            if (max < A[i]) {
                max = A[i];
                maxnum = i;
            }
        }
        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (i == maxnum) ans += (A[i] / 2);
            else ans += A[i];
        }
        System.out.println(ans);
        sc.close();
    }
}

Measured memory_bytes: 23764
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>

using namespace std;
/*
 * a(mod 1<<i) + b(mod 1<<i)
 * 000
 * 001 <- これ
 * 010
 * 011 <- これ
 * 100
 *
 * a(mod 1<<i) + b(mod 1<<i) + 1<<i にすると
 * 011 <- これだけで両方数えられる。
 */

void solve(long long N, vector<long long> a, vector<long long> b){
    int ans = 0;
    for (int i = 0; i < 29; i++) {
        vector<long long> v;
        for (long long bm : b) {
            v.push_back(bm % (1 << (i+1)));
            v.push_back((1 << (i+1)) + bm % (1 << (i+1)));
        }
        sort(v.begin(), v.end());
        int cnt = 0;
        for (long long am : a) {
            int low1 = lower_bound(v.begin(), v.end(), (3 << i) - (am% (1<<(i+1)))) - v.begin();
            int low2 = lower_bound(v.begin(), v.end(), (4 << i) - (am% (1<<(i+1)))) - v.begin();
            cnt += low2 - low1;
        }
        if (cnt%2 != 0) {
            ans += 1<<i;
        }
    }
    std::cout << ans << std::endl;
}

int main(){	
    struct timeval start,end;
    long long span;
    gettimeofday(&start,NULL);

    long long N;
    scanf("%lld",&N);
    vector<long long> b(N-1+1);
    vector<long long> a(N-1+1);
    for(int i = 0 ; i <= N-1 ; i++){
    	scanf("%lld",&a[i]);
    }
    for(int i = 0 ; i <= N-1 ; i++){
    	scanf("%lld",&b[i]);
    }
    solve(N, a, b);

    gettimeofday(&end,NULL);
    span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
    std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
    return 0;
}


Measured memory_bytes: 15720
use whiteread::Reader;

fn main() {
    let mut rdr = Reader::from_stdin_naive();
    let (n, k): (usize, usize) = rdr.p();
    const SIZE: usize = 300_000;
    let mut st = data::SegmentTree::new(SIZE, 0, std::cmp::max);
    for _ in 0..n {
        let a: usize = rdr.p();
        let m = st.get(a.saturating_sub(k), a.saturating_add(k + 1)) + 1;
        st.set(a, m);
        //println!("{:?}", st);
    }
    println!("{}", st.get(0, SIZE));
}

mod data {
    pub struct SegmentTree<F, T> {
        size: usize,
        tree: Vec<T>,
        element: T,
        o: F,
    }

    impl<F, T> std::fmt::Debug for SegmentTree<F, T>
    where
        T: std::fmt::Debug,
    {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{:?}", self.tree)
        }
    }

    impl<F, T> SegmentTree<F, T>
    where
        F: Fn(T, T) -> T,
        T: Copy + Eq,
    {
        pub fn new(size: usize, element: T, o: F) -> Self {
            let size = size.next_power_of_two();
            Self {
                size,
                tree: vec![element; size * 2],
                element,
                o,
            }
        }

        /// get [a, b)
        pub fn get(&self, a: usize, b: usize) -> T {
            self._get(a, b, 1, 0, self.size)
        }

        fn _get(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
            if r <= a || b <= l {
                self.element
            } else if a <= l && r <= b {
                self.tree[k]
            } else {
                (self.o)(
                    self._get(a, b, k * 2, l, (l + r) / 2),
                    self._get(a, b, k * 2 + 1, (l + r) / 2, r),
                )
            }
        }

        pub fn set(&mut self, index: usize, value: T) {
            let mut i = self.size + index;
            while i != 0 {
                let v = (self.o)(value, self.tree[i]);
                if v == self.tree[i] {
                    break;
                }
                self.tree[i] = v;
                i /= 2;
            }
        }
    }
}


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


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e16;
typedef array<int, 3>arr3;
void die(string s) { cout << s << endl; exit(0); }


vector<int>G[200020];
int deg[200020];

bool vis[200010];
bool act[200010];
int s = -1, t = -1;
bool dfs(int n, int pre) {

	for (auto nxt : G[n]) {
		if (nxt == pre)continue;
		if (nxt == s)return true;
		if (nxt == t)return false;
		if (dfs(nxt, n))return true;
	}

	return false;
}
void solve() {
	int N, M; cin >> N >> M;
	REP(i, M) {
		int u, v; cin >> u >> v;
		u--, v--;
		deg[u]++;
		deg[v]++;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int mx = 0;
	REP(i, N) {
		chmax(mx, deg[i]);
		if (deg[i] & 1)die("No");
	}
	if (mx >= 6)die("Yes");
	if (mx <= 2)die("No");
	int cnt = 0;
	REP(i, N) {
		if (deg[i] == 4)cnt++;
	}
	if (cnt >= 3)die("Yes");
	if (cnt <= 1)die("No");
	REP(i, N) {
		if (deg[i] == 4) {
			if (s == -1)s = i;
			else t = i;
		}
	}
	//pe(s + 1); print(t + 1);
	if (dfs(s, s))die("Yes");
	else die("No");
}

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



Measured memory_bytes: 9088
N = int(input())
B = list(map(int, input().split()))

A = [None]*N

A[0] = B[0]

for i in range(1, N-1):
    if B[i-1]<B[i]:
        A[i]=B[i-1]
    else:
        A[i]=B[i]

A[N-1] = B[N-2]

print(sum(A))

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

int main(){
    int r,c;
    cin >> r >> c;
    int data[r+1][c+1];
    
    for (int k=0;k<c+1;k++){
        data[r][k] =0;
    }
    
    for (int i=0;i<r;i++){
        data[i][c] = 0;
        for (int j=0;j<c;j++){
            cin >> data[i][j];
            data[i][c] +=data[i][j];
            data[r][j] +=data[i][j];
            data[r][c] +=data[i][j];
            
        }

    }
    for (int l=0;l<r+1;l++){
        for (int m=0;m<c+1;m++){
            if(m!=0) cout << " " <<data[l][m];
            else cout << data[l][m];
        }
        cout <<endl;
    }

    

    return 0;
}




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

int main() {
    int     tmp;
    int     cnt_5 = 0, cnt_7 = 0;
    
    for ( int ii = 0; ii < 3; ii++ ) {
        scanf("%d", &tmp);
        if ( tmp == 5 ) {
            cnt_5++;
        } else if ( tmp == 7 ) {
            cnt_7++;
        }
    }
    
    if ( cnt_5 == 2 && cnt_7 == 1 ) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 3656
S = int(input())

x1 = 1
y1 = 10 ** 9
x2 = (S + (10 ** 9 - 1)) // (10 ** 9)
y2 = 10 ** 9 * x2 - S
x3 = 0
y3 = 0

print(x1, y1, x2, y2, x3, y3)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define int long long
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
    FASTIO;
    int k;
    cin>>k;
    vector<int>v;
    int z=0;
    string str="";
    int cnt=1;
    int x=7;
    int ok=0;
    while(x%k!=0)
    {
        x*=10;
        x+=7;
        x=x%k;
        cnt++;
        z++;
        if(z>k)
            break;
    }
    if(z<=k)
    {
        cout<<cnt;
    }
    else
        cout<<-1;
    return 0;
}


Measured memory_bytes: 3608
from collections import defaultdict
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, k = LI()
d = defaultdict(int)
for _ in range(n):
    a, b = LI()
    d[a] += b

d = sorted(d.items(), key=lambda x: x[0])
# print(d)
i = 0
ans = 1
cnt = 0
while cnt < k:
    ans = d[i][0]
    cnt += d[i][1]
    i += 1
print(ans)


Measured memory_bytes: 86676
import heapq
#import random
# n = random.randint(1, 10)
# k = random.randint(1, n)
# A = [random.randint(-10, 10) for _ in range(n)]
# print(n, k)
# print(A)

n, k = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10**9+7

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if not neg:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if not pos:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

    if pos[0]<=neg[0]:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if pos[0]>neg[0]:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Measured memory_bytes: 31688
#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> g[101010];
int n,k;

int v=0;

int dfs(int x){
	int md=0;
	for (int nx:g[x]){
		int asd=dfs(nx);
		if (asd>=k&&x!=1){
			v++;
		}
		else{
			md=max(md, asd);
		}
	}
	return md+1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	
	for (int i=1;i<=n;i++){
		int a;
		cin>>a;
		if (i==1){
			if (a!=1) v++;
		}
		else{
			g[a].push_back(i);
		}
	}
	dfs(1);
	cout<<v<<endl;
}

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

void solve() {
    int n;
    cin >> n;

    deque<int> dq;
    for (int i = 1; i <= 9; i++)dq.push_back(i);
    int ct = 0;
    while (ct < n) {
        int top = dq.front();
        dq.pop_front();
        ct++;
        if (ct == n) {
            cout << top << endl;
            return;
        }
        if (top % 10 != 0)dq.push_back(top * 10 + top % 10 - 1);
        dq.push_back(top * 10 + top % 10);
        if (top % 10 != 9)dq.push_back(top * 10 + top % 10 + 1);
    }
}

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

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

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

int main()
{
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	auto B = A;
	sort(B.begin(), B.end());
	B.erase(unique(B.begin(), B.end()), B.end());
	if (A == B) {
		cout << 1 << endl;
		return 0;
	}
	int lb = 1, ub = 2e5;
	while (ub - lb > 1) {
		int d = (lb + ub) >> 1;
		bool ng = false;
		map<int, int> mp;
		for (int i = 1; i < N; i++) {
			if (A[i] > A[i - 1]) continue;
			if (mp.empty()) {
				mp[A[i] - 1] += 1;
			}
			else {
				while (!mp.empty() && mp.rbegin()->first > A[i] - 1) {
					mp.erase(mp.rbegin()->first);
				}
				mp[A[i] - 1] += 1;
				int tmp = A[i] - 1;
				while (tmp >= 0 && mp[tmp] >= d) {
					mp[tmp] -= d;
					--tmp;
					mp[tmp] += 1;
				}
				if (tmp < 0) {
					ng = true;
					break;
				}
			}
		}
		(!ng ? ub : lb) = d;
	}
	cout << ub << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>
int main(void)
{
	int cnt1,cnt2;
	int i,j,len;
	char a[10000];
	
	while(scanf("%s",a)!=EOF){
		len=strlen(a);
		cnt1=0;
		cnt2=0;
		for(i=0;i<len;i++){
			if(a[i]=='J' && a[i+1]=='O' && a[i+2]=='I'){
				cnt1++;
			}
			if(a[i]=='I' && a[i+1]=='O' && a[i+2]=='I'){
				cnt2++;
			}
		}
		printf("%d\n%d\n",cnt1,cnt2);
	}
	return 0;
}

Measured memory_bytes: 980
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    ll k, a, b;
    cin >> k >> a >> b;

    long long bs = 1;
    if(2 < b - a){
        
        for(ll i = 0; i < k; i++){
            if(a <= bs){
                if(i == k-1){
                    bs++;
                }else{
                    bs += b - a;
                    i += 1;
                }

            }else{
                bs++;
            }
        }
        
    }else{
        bs += k;
    }

    cout << bs << endl;

    return 0;
}

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

int ctoi(char c) {
    int n = c - '0';
    return n;
}

int pow_int(int x, int n) {
    if (n == 0) {
        return 1;
    }else {
        int y = x;
        for (int i = 0; i < n-1; i++) {
            x *= y;
        }
        return x;
    }
}

int main() {
    int a, b, ans;
    cin >> a >> b;
    ans = 10 * b;
    bool flag = false;
    rep(i, 10) {
        if (floor(ans * 0.08) == a) {
            flag = true;
            break;
        }else {
            ans++;
        }
    }
    if (flag) {
        cout << ans << endl;
    }else {
        cout << -1 << endl;
    }
}

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

int hyou[410][410];
int room[410];
int used[11];
int D[11];
int cnt, ans,N;

void init() {
	for(int i = 0; i < 410; i++) {
		for(int j = 0; j < 410; j++) {
			hyou[i][j] = 100000;
		}
		room[i] = 100000;
	}
	cnt = 0;
	ans = 3200000;
	for(int i = 0; i < 11; i++) {
		used[i] = false;
		D[i] = false;
	}
}

void dfs(int p) {
	bool f = false;
	for(int i = 0; i < N; i++) {
		if(used[i] == false) {
			f = true;
			used[i] = true;
			cnt += hyou[p][D[i]];
			dfs(D[i]);
			cnt -= hyou[p][D[i]];
			used[i] = false;
		}
	}
	if (!f) {
		ans = min(cnt, ans);
	}
	return;
}


int main() {
	int h,w;
	while(cin >> w >> h, h | w) {
		int p = 0;
		char c;
		init();
		int s;
		for(int i = 0; i < h * w; i++) {
			cin >> c;
			if (c == '.') room[i] = 1;
			else if (c == 'x') room[i] = 100000;
			else if (c == '*') {
				room[i] = 1;
				D[p] = i;
				p++;
			}
			if (c == 'o') {
				room[i] = 1;
				s = i;
			}
		}
		N = p;
		for(int i = 0; i < h*w;i++) {
			if(i % w == 0) {
				hyou[i][i + 1] = room[i + 1];
			}
			else if (i % w == w - 1) {
				hyou[i][i - 1] = room[i - 1];
			}
			else {
				hyou[i][i - 1] = room[i - 1];
				hyou[i][i + 1] = room[i + 1];
			}
			if(i + w < h * w){
				hyou[i][i + w] = room[i + w];
			}
			if (i - w >= 0) {
				hyou[i][i - w] = room[i - w];
			}
		}
		for (int k = 0; k < h * w; k ++) {
			for(int i = 0; i < h*w; i++) {
				for(int j = 0; j < h * w; j++) {
					hyou[i][j] = min(hyou[i][k] + hyou[k][j],hyou[i][j]) ;
				}
			}
		}
		dfs(s);
		if (ans > 90000) {
			cout << -1 << endl;
		} else {
		cout << ans << endl;
		}
	}
}





Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
const ll mod=1000000007;

int main(int argc, char const *argv[])
{
	int a,x,y;
	while(cin>>a>>x>>y){
		if(abs(a-x)<abs(a-y)){
			printf("A\n");
		}
		else{
			printf("B\n");
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;


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

	int num=0;
	rep(i,n){
		int id=n-i;
		int cur=id*2;
		int cnt=0;
		while(cur <= n){
			if(b[cur] == 1)cnt++;
			cur+=id;
		}

		if(cnt%2==0){
			if(a[id]==1){
				b[id]=1;
				num++;
				/*cout<<"a[id]=1&cnt=0"<<endl;
				cout<<b[id]<<endl;
				cout<<"----------"<<endl;*/
			}
			else b[id]=0;
			
		}
		else{
			if(a[id]==1)b[id]=0;
			else{
				b[id]=1;
				num++;
			}	
			//cout<<"else"<<endl;	
		}
		/*cout<<id<<endl;
		cout<<"cnt="<<cnt<<endl;
		cout<<"b="<<b[id]<<endl;*/
	}
	cout<<num<<endl;
	rep(i,n){
		if(b[i+1]==1)cout<<i+1<<endl;
		//cout<<b[i+1]<<endl;
	}
	return 0;
}


Measured memory_bytes: 2432
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <vector>

using namespace std;
using namespace chrono;

#ifdef DEBUG
	//~ #define LOCAL_INPUT_FILE
#else
	//#define USE_FILE_IO
#endif

#ifdef USE_FILE_IO
	#define INPUT_FILE "input.txt"
	#define OUTPUT_FILE "output.txt"
	#define cin ____cin
	#define cout ____cout
	ifstream cin(INPUT_FILE);
	ofstream cout(OUTPUT_FILE);
#else
	#ifdef LOCAL_INPUT_FILE
		#define cin ____cin
		ifstream cin("input.txt");
	#endif
#endif

const int infinity = (int)1e9 + 42;
const int64_t llInfinity = (int64_t)1e18 + 256;
const int module = (int)1e9 + 7; 
const long double eps = 1e-8;

mt19937_64 randGen(system_clock().now().time_since_epoch().count());

inline void raiseError(string errorCode) {
	cerr << "Error : " << errorCode << endl;
	exit(42);
}

signed main() {
	#ifndef USE_FILE_IO
		ios_base::sync_with_stdio(false);
	#endif
	int n; cin >> n;
	if (!(n & (n-1))) {
		cout << "No\n";
		return 0;
	}
	cout << "Yes\n";
	int q = (n+1) / 4;
	assert(q >= 1);
	for (int i = 1; i < 4*q-1; ++i) {
		cout << i << " " << i+1 << "\n";
	}
	cout << 4*q-1 << " " << n+1 << endl;
	for (int i = 1; i < 4*q-1; ++i) {
		cout << n+i << " " << n+i+1 << "\n";
	}
	int w = (n / 4) * 4;
	if (n % 4 == 3) {
		return 0;
	}
	if (n % 4 == 1 || n % 4 == 2) {
		cout << 2 << " " << w+1 << "\n";
		cout << w << " " << w+1 << "\n";
		cout << 3 << " " << n+w << "\n";
		cout << n+w << " " << n+w+1 << "\n";
		if (n % 4 == 2) {
			cout << w+2 << " " << w+1 << "\n";
			cout << 1 << " " << n+w+2 << "\n";
		}
		return 0;
	}
	assert(n % 4 == 0);
	vector<int> pxor;
	pxor.push_back(0);
	for (int i = 1; i < n; ++i) {
		pxor.push_back(pxor.back() ^ i);
	}
	map<int, int> mp;
	for (int i = 0; i < n; ++i) {
		if (mp.count(pxor[i] ^ n)) {
			int d = mp[pxor[i] ^ n];
			cout << i << " " << n << "\n";
			cout << d << " " << 2*n << "\n";
			return 0;
		}
		mp[pxor[i]] = i+1;
	}
	assert(false);
	return 0;
}


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

using namespace std;
typedef long long ll;

void YesNo(bool x) {
    cout << (x ? "Yes" : "No") << endl;
}

int main() {
    int n, d;
    cin >> n >> d;
    d = d * 2 + 1;
    cout<<(n+d-1)/d<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

int main(void) {
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    for (int i=0;i<N;i++) cin >> A[i];
    for (int i=0;i<N;i++) cin >> B[i];
    for (int i=0;i<N;i++) cin >> C[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    vector<ll> NA(N,0), NB(N,0);
    for (int i=0;i<N;i++) {
        auto itr = upper_bound(C.begin(), C.end(), B[i]);
        if (itr != C.end()) NB[i] = N-(itr-C.begin());
    }
    vector<ll> CNB(N+1,0);
    for (int i=1;i<=N;i++) CNB[i] = CNB[i-1] + NB[i-1];
    for (int i=0;i<N;i++) {
        auto itr = upper_bound(B.begin(), B.end(), A[i]);
        if (itr != B.end()) NA[i] = CNB[N] - CNB[(itr-B.begin())];
        if (i>0) NA[i] += NA[i-1];
    }
    cout << NA[N-1] << endl;

    return 0;
}


Measured memory_bytes: 3712
import java.util.*;
class Main{
	public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String word = scan.next();
        int k = scan.nextInt();
        
        String x = word.substring(k-1,k);
        String ans = "";
        for(int i=0;i < n;i++){
        	if(word.substring(i,i+1).equals(x)){
            	ans = ans+x;
            } else {
            	ans = ans+"*";
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
#!/usr/bin/env python
from collections import deque

def main():
    n, m, k = map(int, input().split())
    a_lst = list(map(int, input().split()))
    b_lst = list(map(int, input().split()))
    if n < m:
        a_lst, b_lst = b_lst, a_lst
        n, m = m, n

    a_time = [0]
    b_time = [0]

    t = 0
    for a in a_lst:
        t += a
        if t > k:
            break
        a_time.append(t)
    t = 0
    for b in b_lst:
        t += b
        if t > k:
            break
        b_time.append(t)

    ret = 0
    j = len(b_time) - 1
    for i, a in enumerate(a_time):
        while a + b_time[j] > k:
            j -= 1
        ret = max(ret, i+j)

    print(ret)

if __name__ == '__main__':
    main()


Measured memory_bytes: 42184
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using T = tuple<ll,ll,ll>;
using Map = map<char,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;

class UnionFind {
public:
    vector < ll > par; // 各元の親を表す配列
    vector < ll > siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool same(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main(){
    ll ans=0;
    ll N;
    cin >> N;
    vector<ll> x(N,0);
    vector<ll> y(N,0);
    vector<P> xsort(N);
    vector<P> ysort(N);
    for(ll i=0;i<N;i++){
        cin>>x[i]>>y[i];
        xsort[i]=P(x[i],i);
        ysort[i]=P(y[i],i);
    ;}
    sort(xsort.begin(), xsort.end());
    sort(ysort.begin(), ysort.end());
    priority_queue<T, vector<T>, greater<T>> pq;
    for(ll i=0;i<N-1;i++){
        pq.push(T(xsort[i+1].first-xsort[i].first,xsort[i].second,xsort[i+1].second));
        pq.push(T(ysort[i+1].first-ysort[i].first,ysort[i].second,ysort[i+1].second));
    ;}
    UnionFind tree(N);
    ll k=pq.size();
    for(ll i=0;i<k;i++){
        T j=pq.top();
        pq.pop();
        if(!tree.same(get<1>(j),get<2>(j))){
            ans+=get<0>(j);
            tree.unite(get<1>(j),get<2>(j));
        }
    ;}
    cout<<ans<<endl;

    
return 0;
}


Measured memory_bytes: 13168
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int n;
    int m;
    int l;
 
   cin >> n >> m >> l;
   int ans = n*100+m*10+l;
   
  
  if (ans%4==0){
    
     cout << "YES" << endl;
    
  }else{
    
     cout << "NO" << endl;
    
  }

  
  return 0;
}

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

#define pb push_back
#define mp make_pair

typedef long long ll;
typedef long double ld;

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int n, a, b;
	cin>>n>>a>>b;

	if(a-b == 1 && b == n)
		cout<<"Alice";
	else if((a-b)%2)
		cout<<"Borys";
	else
		cout<<"Alice";
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,w,a,b;
    cin>>n>>w;
    ll dp[w+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
    	cin>>a>>b;
    	for(int j=b;j<=w;j++){
    		dp[j]=max(dp[j],dp[j-b]+a);
    	}
    }
    cout << dp[w] <<endl;
    return 0;
}



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

int main()
{
    map<string, ll> M;
    string key;
    ll q, que, x;

    cin >> q;
    for(int i=0; i<q;i++)
    {
        //input
        cin >> que >> key;
        if (!que)
            cin >> x;

        //que
        switch (que) {
        case 0:
            M[key] = x;
            break;
        case 1:
            try
            {
                cout << M.at(key) << endl;
            }
            catch (out_of_range&)
            {
                cout << '0' << endl;
            }
            break;
        case 2:
            M.erase(key);
            break;
        }
    }
}



Measured memory_bytes: 27676
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
n = int(input())
d = input()
d_list = d.split(" ")
d_int_list = []

for item in d_list:
    d_int_list.append(int(item))

ret = 0
for i in range(len(d_int_list)):
    for j in range(i+1, len(d_int_list)):
        ret += d_int_list[i] * d_int_list[j]

print(ret)


Measured memory_bytes: 2940
#include<iostream>
#include<string>
using namespace std;
int main(){
int n, a = 0; string s;cin>> n >> s;
if(n%2!=0){
cout<<"No"<<endl;
}
else{
for(int h=0; h<n/2; h++){
if(s[h]!=s[h+n/2]){
cout<<"No"<<endl; a++;
}
}
if(a == 0){
cout<<"Yes"<<endl;
}
}
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n=0,a[100001],f[100001],d[100001],ans=1,t=0;
int main() 
{
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
    ans=1;
    t=0;
    for(int i=1; i<=n; i++) 
    {
        f[i]=1;
        for(int j=t; j>0; j--)
            if(a[i]<=a[d[j]]) 
            {
                f[i]=f[d[j]]+1;
                break;
            }
        t=max(t,f[i]);
        d[f[i]]=i;
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
}

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

using namespace std;

#define fastio ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;

// int change(string str1, string str2)
// {
// 	int calc = 0;
// 	for(int i = 0; i < str1.size(); i++)
// 	{
// 		if(str1[i] != str2[i])
// 		{
// 			calc++;
// 		}
// 	}
// 	return calc;
// }

// bool carry(string temp, string str, int& min)
// {
// 	int calc = change(temp, str);
// 	if(calc < min)
// 		return true;
// 	return false;
// }

int solve(string str, string check, vector<string>& vec)
{
	int s_size = str.size(), mini = 1000;

	for(int i = 0; i < s_size; i++)
	{
		for(int j = 1; j < s_size+1-i; j++)
		{
			if(str.substr(i, j).size() == check.size())
				vec.push_back(str.substr(i, j));
			else if(str.substr(i, j).size() > check.size())
				break;
		}
	}

	for(int i = 0; i < vec.size(); i++)
	{
		string s = vec[i];
		int calc = 0;
		for(int i = 0; i < s.size(); i++)
		{
			if(s[i] != check[i])
				calc++;
		}
		mini = min(mini, calc);
	}
	return mini;
}

int main()
{
	#ifndef ONLINE_JUDGE 
	freopen("input.txt", "r", stdin); 
	freopen("output.txt", "w", stdout); 
	#endif	
	
	fastio;

	string s, t;
	cin >> s >> t;
	vector<string> v;
	
	cout << solve(s, t, v);

	// for(int i = 0; i < v.size(); i++)
	// {
	// 	cout << v[i] << endl;
	// }

	return 0;

}

Measured memory_bytes: 3864
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  int n, d;
  cin >> n >> d;
  int x[11][11];
  int cnt = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<d; j++){
      cin >> x[i][j];
    }
  }
  for(int i=0; i<n-1; i++){
    for(int j=i+1; j<n; j++){
      int tmp = 0;
      for(int k=0; k<d; k++){
        tmp += pow(x[i][k] - x[j][k], 2);
      }
      double t = sqrt(tmp);
      if(ceil(t) == floor(t))cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (A, B, C) = readLine()!!.split(" ").map(String::toInt)
    val K = readLine()!!.toInt()

    val max = Math.max(Math.max(A, B), C)

    var sum = max
    repeat(K) {
        sum *= 2
    }

    println(sum + A + B + C - max)
}



Measured memory_bytes: 35948
def run_length_compress(S):
  l = []
  left = 0
  for right in range(1,len(S)):
    if right != len(S) - 1:
      if S[right] != S[right - 1]:
        l.append([S[right-1], right - left])
        left = right
      else:
        pass
    else:
      if S[right] != S[right - 1]:
        l.append([S[right-1], right - left])
        l.append([S[right], 1])
      else:
        l.append([S[right], right - left + 1])
  return l

def main():
  s = input()
  n = len(s)
  res = [0]*n
  l = run_length_compress(s)
  if len(l) % 2 != 0:
    print('Invalid Input')
    quit()
  else:
    index = l[0][1] - 1
    for i in range(0, len(l)-1, 2):
      if l[i][1] % 2 == 0:
        res[index] += int(l[i][1] / 2)
        res[index + 1] += int(l[i][1] / 2)
      else:
        res[index] += int(l[i][1] / 2) + 1
        res[index + 1] += int(l[i][1] / 2)
      if l[i+1][1] % 2 == 0:
        res[index] += int(l[i+1][1] / 2)
        res[index + 1] += int(l[i+1][1] / 2)
      else:
        res[index] += int(l[i+1][1] / 2)
        res[index + 1] += int(l[i+1][1] / 2) + 1
      
      if i < len(l) - 2:
        index += l[i+1][1] + l[i+2][1]
      else:
        pass
  
  res_str = []
  for i in range(n):
    res_str.append(str(res[i]))
  print(" ".join(res_str))

if __name__ == "__main__":
  main()

Measured memory_bytes: 21296
#include<stdio.h>

#define N 100
#define INF 1000000

int min(int a,int b){
  if(a > b){
    return b;
  }
  else if(b > a){
    return a;
  }
}


int main(){
  int i,j,k,l,n,r[N + 1],c[N + 1][N + 1];

  scanf("%d",&n);
  for(i = 1;i <= n;i++){
    scanf("%d%d",&r[i - 1],&r[i]);
  }

  for(i = 1;i <= n;i++){
    c[i][i] = 0;
  }

  for(j = 2;j <= n;j++){
    for(i = 1; i <= n - j + 1;i++){
      k = i + j - 1;
      c[i][k] = INF;
      for(l = i;l <= k - 1;l++){
	c[i][k] = min(c[i][k],c[i][l] + c[l + 1][k] + r[i - 1] * r[l] * r[k]);
      }
    }
  }

  printf("%d\n",c[1][n]);

  return 0;
}


Measured memory_bytes: 2108
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int H, W, D;
    cin >> H >> W >> D;

    P table[H * W + 1];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int a;
            cin >> a;
            table[a] = make_pair(i, j);
        }
    }

    int sum[H * W + 1];
    for (int i = 0; i <= D; i++) {
        sum[i] = 0;
    }
    for (int i = D + 1; i <= H * W; i++) {
        sum[i] = sum[i - D] + abs(table[i].first - table[i - D].first) + abs(table[i].second - table[i - D].second);
    }

    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R;
        cout << sum[R] - sum[L] << endl;

    }

    return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int MAXN = 210;

int N;
bool edge[MAXN][MAXN];
bool used[MAXN];
bool nused[MAXN];

int roll (int x)
{
    for (int i = 0; i < MAXN; i++)
        used[i] = false;

    vector <int> plist;
    plist.push_back(x);
    used[x] = true;

    int nround = 1;
    while (true)
    {
        for (int i = 0; i < MAXN; i++)
            nused[i] = false;
        for (int k : plist)
            for (int i = 0; i < N; i++)
                if (edge[k][i])
                    nused[i] = true;

        plist.clear();
        for (int i = 0; i < N; i++)
            if (nused[i] && !used[i])
            {
                plist.push_back(i);
                used[i] = true;
            }
        if (!plist.size()) break;

        for (int j : plist)
            for (int k : plist)
                if (edge[j][k])
                    return -1;

        nround++;
    }
    return nround;
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            char c; cin >> c;
            edge[i][j] = (c == '1');
        }
    }

    int ans = -1;
    for (int i = 0; i < N; i++)
        ans = max (ans, roll (i));
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
map<ll, int> prime_factor(ll n)
{
    map<ll, int> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            res[i]++;
            n /= i;
        }
    }
    if (n != 1)
    {
        res[n] = 1;
    }
    return res;
}

int main()
{
    ll N;
    cin >> N;
    auto div = prime_factor(N);
    ll ans = 0;
    for (auto &&i : div)
    {
        int c = 1;
        while (i.second > 0 and c <= i.second)
        {
            i.second -= c;
            c++;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3628