akhauriyash/Code-Regression huggingface dataset:
import java.util.Stack;
import java.util.Scanner;

public class Main{
	public static void main(String [] args) {
		Scanner scan = new Scanner(System.in);
		String[] tokenStrings = scan.nextLine().split(" ");
		scan.close();
		Stack<Integer> tokens = new Stack<Integer>();
		for(int i = 0; i < tokenStrings.length; i++) {
			String token = tokenStrings[i];
			if(token.equals("*") || token.equals("/") || token.equals("+") || token.equals("-")) {
				int operand1 = tokens.pop();
				int operand2 = tokens.pop();
				if(token.equals("*"))
					tokens.push(operand2 * operand1);
				else if(token.equals("/"))
					tokens.push(operand2 / operand1);
				else if(token.equals("+"))
					tokens.push(operand2 + operand1);
				else
					tokens.push(operand2 - operand1);
			}
			else
				tokens.push(Integer.parseInt(token));
			
		}

		int answer = tokens.pop();
		System.out.println(answer);
	}
}



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

int main(){
    int N,D,X;
    int A[100]={};
    int i=0;
    int j=0;
    int num=0;
    
    scanf("%d\n",&N);
    scanf("%d %d\n",&D,&X);
    while(1){
        scanf("%d\n",&A[i]);
        if(A[i]==1){
            num=D;    
        }else{
            if(D%A[i]==0){
                num=D/A[i];
            }else{
                num=1+D/A[i];
            }
        }
        X=X+num;
        //printf("%d\n",num);
        i++;
        if(N==i){
            break;
        }
    }

    /*for(i=0;i>=D;i++){
        num = D / A[i];
        cnt = cnt + num;
    }*/
    
    //printf("%d\n",N);
    //printf("%d\n",D);
    //printf("%d\n",X);
    //printf("%d\n",num);
    printf("%d\n",X);
    //printf("%d\n",num);
    
    return 0;
}

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

int partition(int s,int k,int n){
	if(s<0) return 0;
	if(s>9 && n==1) return 0;
	
	if((s>=0 && s<=min(9,s)) && n==1)return 1;
	int ret=0;
	int x=k;
	for(x=0;x<=min(9,s);x++){
		ret+=partition(s-x,x,n-1);
	}
	return ret;
}

int main(void){
int s;

//	for(s=1;s<=50;s++)cout<<s<<":"<<partition(s,0,4)<<endl;
	while(cin>>s && s!=EOF){
		if(s>18)s=36-s;
		cout<<partition(s,0,4)<<endl;
	}


return 0;
}


Measured memory_bytes: 3000
def main():

  U = 2*10**5
  MOD = 10**9+7

  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)
  two = [1]*(U+1)
  two_inv = [1]*(U+1)

  for i in range(1,U+1):
      fact[i] = (fact[i-1]*i)%MOD
      two[i] = (two[i-1]*2)%MOD
  fact_inv[U] = pow(fact[U], MOD-2, MOD)
  two_inv[U] = pow(two[U], MOD-2, MOD)

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD
      two_inv[i-1] = (two_inv[i]*2)%MOD

  def comb(n, k):
      if k < 0 or k > n:
          return 0
      z = fact[n]
      z *= fact_inv[k]
      z %= MOD
      z *= fact_inv[n-k]
      z %= MOD
      return z

  B, W = map(int, input().split())
  p = 0
  q = 0
  for i in range(1, B+W+1):
    ans = 1 - p + q
    ans %= MOD
    ans *= two_inv[1]
    ans %= MOD
    print(ans)
    p += comb(i-1, B-1) * two_inv[i] % MOD
    p %= MOD
    q += comb(i-1, W-1) * two_inv[i] % MOD
    q %= MOD
    
if __name__ == "__main__":
  main()

Measured memory_bytes: 36768
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
b_list = []
c_list = []
for _ in range(M):
    b, c, = list(map(int, input().split()))
    b_list.append(b)
    c_list.append(c)

data = dict()
for a in A:
    if a in data:
        data[a] += 1
    else:
        data[a] = 1

for i in range(M):
    if c_list[i] in data:
        data[c_list[i]] += b_list[i]
    else:
        data[c_list[i]] = b_list[i]

key = list(data.keys())
key.sort(reverse=True)
num = 0
ind = 0
ans = 0
while True:
    if num + data[key[ind]] <= N:
        ans += data[key[ind]]*key[ind]
        num += data[key[ind]]
    else:
        ans += (N - num)*key[ind]
        break
    ind += 1
print(ans)


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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

vector<int> pos[30];

void solve() {
  string s, t; cin >> s >> t;
  for (int i = 0; i < s.size(); ++i) {
    pos[s[i]-'a'].push_back(i);
  }
  long long ans = 0, reps = 0, cur = -1;
  for (char c: t) {
    int d = c-'a';
    if (pos[d].empty()) {
      printf("-1");
      return;
    }
    auto spos = upper_bound(pos[d].begin(), pos[d].end(), cur);
    if (spos == pos[d].end()) {
      ++reps;
      cur = *pos[d].begin();
    } else {
      cur = *spos;
    }
    ans = reps*s.size() + cur;
  }
  printf("%lld", ans+1);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4132
n,k=map(int,input().split())
i=0
d=[]
a=[]
while i<k:
    d.append(int(input()))
    a.extend(list(map(int,input().split())))
    i+=1
i=1
count=0
while True:
    if((i in a)!=True):
        count+=1
    i+=1
    if(i>n):
        break

print(count)


Measured memory_bytes: 9128
#include <iostream>
 using namespace std;
  
   int main(){
           int A[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2    , 2, 5, 4, 1, 4, 1, 51};
  
           int k;
           cin >> k;
           printf("%d\n", A[k-1]);
 
 
          }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Nmax = 3000;
int N, A[Nmax];
ll fact[200000];

// Extended Euclid's greatest common divisor algorithm
// Find (x, y, g)
// where $a*x + b*y = g$ and g is the greatest common divisor of (a, b)
ll ext_gcd(ll a, ll b, ll &x, ll &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	ll nx, ny;
	ll g = ext_gcd(b, a%b, nx, ny);
	x = ny;
	y = nx - a/b *ny;
	return g;
}

// Modular inverse of x given modulo p, y
// x*y = 1 mod p
// <=> x*y + z*p = 1
ll inv_mod(ll x, ll p){
	ll y,z;
	ext_gcd(x, p, y, z);
	return y>=0 ? y : p+(y%p);
}


// Modular factorial of n, also counting p's appearance e
// n! = a * p^e
// return: a % p
// n! = n * (n-1) * ... * (k*p+1) *
//      (k*p) * (k*p-1) * ... ((k-1)*p+1) *
//      ...
//      p * (p-1) * ... * 2 * 1   (k = floor(n/p))
//    = (n%p) * ... * 1 *
//      (k*p) * (p-1) * ... * 1 *
//      p * (p-1) * ... * 1       (mod p, preserving p's multiples)
//    = (n%p)! * p^k * k! * (p-1)^k
//    = (n%p)! * p^k * k! * (p-1)^(k%2)
//
// From the facts:
//   (p-1)! = p-1 (mod p) (c.f. Willson's theorem)
//   (p-2)**2 = 1 (mod p)
ll fact_mod(ll n, ll p, ll &e){
	if(n == 0){
		e = 0;
		return 1;
	}

	ll na = fact_mod(n/p, p, e);

	e += n/p;
	ll a = na * fact[n%p] % p;

	if((n/p)%2) a = a * (p-1)%p;
	return a;
}


// Modular combination (n, m) given module p
// (n, m) = n!/(n-m)!m!
//        = (a_n * p^(e_n)) / ((a_{n-m} * p^(e_{n-m}) * (a_m * p^e_m))
//        = a_n / (a_{n-m} * a_m) * p^(e_n - e_{n-m} - e_m)
ll comb_mod(ll n, ll m, ll p){
	ll e1,e2,e3;
	ll a1 = fact_mod(n, p, e1);
	ll a2 = fact_mod(m, p, e2);
	ll a3 = fact_mod(n-m, p, e3);

	if(e1 > e2+e3) return 0;
	else return a1*inv_mod(a2*a3%p, p)%p;
}

ll pow_mod(ll n, ll k, ll p){
	if(k==0) return 1;
	if(k%2) return n*pow_mod(n, k-1, p)%p;
	ll z = pow_mod(n, k/2, p);
	return z*z%p;
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++) cin >> A[i];

	fact[0] = fact[1] = 1;
	for(int i=2; i<200000; i++) fact[i] = fact[i-1]*i%N;

	vector<int> inv(N);
	for(int i=1; i<N; i++) inv[i] = inv_mod(i, N);

	vector<int> ans(N);
	for(int i=0; i<N; i++){
		if(A[i]==0) continue;
		ans[0] += 1;
		int exp = 1;
		for(int j=0; j<N; j++){
			ans[N-1-j] += N-exp*fact[N-1]%N*inv[fact[j]*fact[N-1-j]%N]%N;
			ans[N-1-j] %= N;
			exp = exp*(N-i)%N;
		}
	}

	for(int i=0; i<N; i++) cout << ans[i] << (i==N-1?'\n':' ');

	return 0;
}


Measured memory_bytes: 1920
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
using namespace std;

int main() {
	int n; cin >> n;
	int l[200];
	for (int i = 0; i < 2 * n; i++) {
		cin >> l[i];
	}
	sort(l, l + 2*n);
	int ans = 0;
	for (int i = 0; i < 2 * n; i+=2) {
		ans += min(l[i], l[i + 1]);
	}
	cout << ans << 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++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  double n, k;
  cin >> n >> k;
  double ans = 0;
  for(int i=1; i<=n; i++){
    int score = i;
    double p = 1/n;
    while(score < k){
      p *= 0.5;
      score *= 2;
    }
    ans += p;
  }
  printf("%.10f\n", ans);   
}


Measured memory_bytes: 3788
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

stack = list()
num_tc = int(sys.stdin.readline())

for i in range(num_tc):
    query = list(map(int, sys.stdin.readline().split()))
    if query[0] == 0:   # push data
        stack.append(query[1])
    elif query[0] == 1:
        print(stack[query[1]])   # random access
    elif query[0] == 2:
        stack.pop()     # pop last element
    else:
        raise ValueError



Measured memory_bytes: 13620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;

//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

ll a[200010];

void solve() {
  set<int> v;
  vector<int> ans;
  int n;
  cin >> n;
  REP(i,n) cin >> a[i];
  for (int i = n; i >= 1; i--) {
    int sum = 0;
    for (int j = i + i; j <= n; j += i) {
      sum += v.count(j);
    }
    if (sum % 2 != a[i-1]) {
      v.insert(i);
      ans.pb(i);
    }
  }
  cout << ans.size() << endl;
  REP(i,sz(ans)) {
    cout << ans[i] << " \n"[i == sz(ans) - 1];
  }
}

int main(int argc, char *argv[]){

  /* Regular */
  int case_num = 1;
  if (argc > 1 && stoi(argv[1])) cin >> case_num;
  REP(case_no, case_num) {
    cerr << endl << "case " << case_no + 1 << endl;
    solve();
  }
  
  // /* AOJ */
  // solve();
  return 0;
}

Measured memory_bytes: 8952
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define inf 1000000000
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
int main(){
IOS;
string s1,s2;
cin>>s1>>s2;
int i,j;
int dp[s1.length()+1][s2.length()+1];
for(i=0;i<=s2.length();i++){
    dp[0][i]=0;
}
for(i=0;i<=s1.length();i++){
    dp[i][0]=0;
}
for(i=0;i<s1.length();i++){
    for(j=0;j<s2.length();j++){
        if(s1[i]==s2[j]){
            dp[i+1][j+1]=dp[i][j]+1;
        }
        else
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
    }
}
i=s1.length();
j=s2.length();
string s;
while(i!=0&&j!=0){
    if(dp[i-1][j]!=dp[i][j]&&dp[i][j-1]!=dp[i][j]){
        s.pb(s1[i-1]);
        i--;
        j--;
    }
    else if(dp[i-1][j]!=dp[i][j]){
        j--;
    }
    else{
        i--;
    }
}
for(i=s.length()-1;i>=0;i--){
    cout<<s[i];
}
cout<<endl;
}


Measured memory_bytes: 35456
#include <stdio.h>

int X (int* ,int);
int count;
int main()
{
  int i,n,hi[100];
  scanf ("%d",&n);
  for (i=0;i<n;i++){
    scanf ("%d",&hi[i]);
  }
  count=X(hi,n);

  for (i=0;i<n;i++){
    printf ("%d",hi[i]);
    if (i!=n-1)
      printf (" ");
  }
  printf ("\n");
  printf ("%d\n",count);

  return 0;
}

int X (int* A,int N){
  int j,p,count=0;
  int flag;
  flag=1;
  while (flag==1){
    flag=0;
    for (j=N-1;j>=1;j--){
      if (A[j]<A[j-1]){
	/*交換*/
	p=A[j];
	A[j]=A[j-1];
	A[j-1]=p;
	flag=1;
	count++;
      }
      
    }
  }
  return count;
}



Measured memory_bytes: 2104
n=int(input())
plist=list(map(int,input().split()))

cnt=0
for i in range(1,n-1):
  p0 = plist[i-1]
  p1 = plist[i]
  p2 = plist[i+1]
  
  if p0 < p1 and p1 < p2:
    cnt += 1
  elif p0 > p1 and p1 > p2:
    cnt += 1
    
print(cnt)

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

long long d[300020];
bool visited[300020];
typedef struct{
	int to,head,next;
	long long cost;
}edge;
edge tree[300030];


void dfs(int v,int p, long long cost){
	d[v]=cost;
	visited[v]=true;
	for (int e=tree[v].head; e!=-1; e=tree[e].next){
		if (!visited[tree[e].to]){
			if (tree[e].to==p)continue;
			dfs(tree[e].to,v,tree[e].cost+cost);
			visited[tree[e].to]=false;
		}
	}
}

int main(void){
	int n,m=0;
	scanf("%d",&n);
	for (int i=0; i<n; i++)tree[i].head=-1;
	for (int i=0; i<n-1; i++){
		int a,b;
		long long c;
		scanf("%d%d%lld",&a,&b,&c);
		a--;
		b--;
		tree[m].next=tree[a].head;
		tree[a].head=m;
		tree[m].to=b;
		tree[m].cost=c;
		m++;
		tree[m].next=tree[b].head;
		tree[b].head=m;
		tree[m].to=a;
		tree[m].cost=c;
		m++;
	}
	int q,k;
	scanf("%d%d",&q,&k);
	dfs(k-1,-1,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",d[x-1]+d[y-1]);
	}
	return 0 ;
}

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

#define fst first
#define snd second
#define ll long long
#define ld long double
#define pb push_back
#define emp emplace_back
#define pii pair<int, int>
#define usg unsigned
#define sg signed
#define mp make_pair

using namespace std;

void setIO(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
}

const ld PI = 4*atan((ld)1);
const int INF = 1e9+7;
const ll _INF = 1e18+7;

int main(){
	setIO();
	int mx = 0;
	string s, t;
	cin >> s >> t;
	for (int i = 0; i < (int)s.size()-(int)t.size()+1; i++){
		int ct = 0;
		for (int j = 0, k = i; j < (int)t.size(); j++, k++){
			if (t[j] == s[k]) ct++;
		}
		mx = max(mx, ct);
	}
	cout << (int)t.size()-mx << endl;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

void FIO()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
	FIO();
	string s1, s2; cin >> s1 >> s2;

	int n = s1.length();
	int m = s2.length();

	int t[n + 1][m + 1];
	memset(t, 0, sizeof(t));

	for (int i = 1; i < n + 1; ++i)
	{
		for (int j = 1; j < m + 1; ++j)
		{
			if (s1[i - 1] == s2[j - 1])
				t[i][j] = 1 + t[i - 1][j - 1];
			else
				t[i][j] = max(t[i - 1][j], t[i][j - 1]);
		}
	}

	int i = n, j = m;
	string ans = "";

	while (i > 0 && j > 0)
	{
		if (s1[i - 1] == s2[j - 1])
		{
			ans += s1[i - 1];
			i--;
			j--;
		}
		else
		{
			if (t[i - 1][j] > t[i][j - 1])
				i--;
			else
				j--;
		}
	}

	reverse(ans.begin(), ans.end());

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

Measured memory_bytes: 74028
#pragma region macro
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

namespace std {
template <typename A, typename B>
string to_string(pair<A, B> p);

string to_string(const string &s) {
    return '"' + s + '"';
}

string to_string(const char *s) {
    return to_string((string)s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for(int i = 0; i < static_cast<int>(v.size()); i++) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for(size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
};  // namespace std
#pragma endregion

void solve() {
    int n, l;
    std::cin >> n >> l;
    std::vector<std::string> s(n);
    rep(i, n) std::cin >> s[i];
    std::sort(s.begin(), s.end());
    rep(i, n) std::cout << s[i];
    std::cout << std::endl;
}

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

Measured memory_bytes: 256
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
lns=len(s)
lst=[0]*(lns+1)

start=[]
if s[0]=="<":
    start.append(0)
for i in range(lns-1):
    if s[i]==">" and s[i+1]=="<":
        start.append(i+1)
if s[lns-1]==">":
    start.append(lns)

for i in start:
    d=deque([[i,0],[i,1]])
    while d:
        now,lr=d.popleft()
        # print(now)
        if now-1>=0 and lr==0 and s[now-1]==">":
            lst[now-1]=max(lst[now-1],lst[now]+1)
            d.append([now-1,0])
        if now+1<=lns and lr==1 and s[now]=="<":
            lst[now+1]=max(lst[now+1],lst[now]+1)
            d.append([now+1,1])
    # print(lst)
# print(start)
# print(lst)
print(sum(lst))

Measured memory_bytes: 87328
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define rep(i, n) for(int i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
using vi = vector<int>;
const int MOD = 1e9+7;
 
bool IsPrime(int num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) { if (num % i == 0) return false; }
    return true;
}
 
int main() {
	int x;
  	cin >> x;
  	if(x < 1200) cout << "ABC" << endl;
  	else cout << "ARC" << endl;
}

Measured memory_bytes: 256
//#pragma GCC optimize "trapv"
//-D_GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define all(x) x.begin(),x.end()
#define Max 100000+5
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
#define pb push_back
int mod = 1000000007;
vector<int> g[Max];
bool vis[Max];
int d, x, y;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
void ex(int A, int B) {
    if(B == 0) {
        d = A;
        x = 1;
        y = 0;
    }
    else {
        ex(B, A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}


void dfs(int u){

	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(vis[v]!=1)
			dfs(v);
	}
}



int power(int a,int b){
    if(b==1)return a;
    if(a>mod)a%=mod;
    int r=1;
    while(b){
        if(b&1)r=r%mod*a%mod;
        a=a%mod*a%mod;
        b/=2;
    }
    return r;
}
class uf{
    vector<int> v;
    vector<int> sz;
    
    
    public :
    uf(int n){
        v.resize(n+1);
        iota(v.begin()+1,v.end(),1);
        sz.resize(n+1,1);
        //1 to sz
    }
    int root(int b){
        while(v[b]!=b){
            b = v[b];
        }   
        return b;
    }
    void u(int a, int b){
        //combine a and b
        
        int ra=root(a);
        int rb=root(b);
        if(ra==rb)return ;
        if(sz[ra]<sz[rb]){
            v[ra] = v[rb];
            sz[rb]+=sz[ra];
        }else{
            v[rb]=v[ra];
            sz[ra]+=sz[rb];
        }
    }
    bool f(int a,int b){
        //same set
        return (root(a)==root(b));
    }
   
    
};


int32_t main(){
	IO
	string s;
  cin>>s;
   if(s[2]==s[3] and s[4]==s[5])cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 2560
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ in >> p.first >> p.second; return in; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
template <char d = ' ', class T>
ostream& operator << (ostream& out, vector<T>& v){ for(auto& e : v){ out << e << d; } return out; }

struct UnionFind {
	vector<int> elems;
	UnionFind(int n):elems(n){
		for(int i = 0; i < n; i++){
			elems[i] = i;
		}
	}
	bool same(int a, int b){
		return parent(a) == parent(b);
	}
	void unite(int a, int b){
		elems[parent(a)] = parent(b);
	}
	int parent(int a){
		if(a == elems[a]){ return a; }
		return elems[a] = parent(elems[a]);
	}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> ps(n); cin >> ps;
    UnionFind uf(n);
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        uf.unite(x, y);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += uf.same(i, ps[i] - 1);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_input;
  set<string> set1;
  string input;
  cin >> no_of_input;
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    set1.insert(input);
  }
  cout << set1.size();
}

Measured memory_bytes: 19232
#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265359

int main(){
   int H1,M1,H2,M2,K;
   int total=0;
   cin >>H1>>M1>>H2>>M2>>K;

   if(K>M2){
      int m = K%60;
      int h = K/60;
      total = (H2-H1-h)*60+(M2-M1-m);
   }
   else{
      total = (H2-H1)*60+M2-M1-K;
   }

   if (total <=0)
      cout << 0;
   else
      cout << total;
}

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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

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> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec)
    is >> x;
  return is;
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  int n;
  cin >> n;
  string s;
  cin >> s;

  int r = 0;
  int b = 0;

  REP(i, n) {
    if (s[i] == 'R')
      r++;
    else
      b++;
  }

  if (r > b)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
n = int(input())
ps = list(map(int, input().split()))
ans = 0

for i in range(1, len(ps)-1):
    s1 = ps[i-1] < ps[i] and ps[i+1] > ps[i]
    s2 = ps[i-1] > ps[i] and ps[i+1] < ps[i]
    if s1 or s2:
        ans += 1

print(ans)


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


def main():
    H, W = map(int, input().split())
    INF = 10**12
    c = [None for _ in range(10)]
    for i in range(10):
        c[i] = list(map(int, input().split()))

    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k]+c[k][j])
    
    ans = 0
    for i in range(H):
        A = list(map(int, input().split()))
        for j in range(W):
            if A[j] != -1:
                ans += c[A[j]][1]
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 40428
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  int N;
  cin >> N;
  vector<int> a(N);

  ll ans=0;
  for(int i=0;i<N;++i){
    cin >> a.at(i);
    while(a.at(i)%2==0){
      ++ans;
      a.at(i)/=2;
    }
  }

  cout << ans << endl;

  return 0;
}


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

const int mxn=1e5+5;

ll dp[105][mxn];
int n,W,v[mxn],w[mxn];

int main()
{
    cin>>n>>W;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];

    for(int i=0;i<mxn;i++)
        dp[0][i]=1e18;
    dp[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int h=1;h<=mxn;h++)
        {
            dp[i][h]=dp[i-1][h];

            if(v[i]<=h)
                dp[i][h]=min(dp[i][h],dp[i-1][h-v[i]]+1ll*w[i]);
        }
    }
    for(int i=mxn-1;i>=0;i--)
        if(dp[n][i]<=W)
        {cout<<i; return 0;}

    return 0;
}


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

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,arr,n) for(int i=arr;i<=n;i++)
#define repd(i,arr,n) for(int i=arr;i>=n;i--)
#define trav(arr,x) for(auto& arr:x)
#define all(c) c.begin(), c.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(arr) arr.size()
#define pi 3.14159265358979323846
#define MAX (1000*1000*1000+7)
#define vi vector<int>
#define pii pair<int,int>
#define pqueue priority_queue<int>
#define pdqueue priority_queue<int,vi,greater<int> >

const int mod=998244353;
const long double inf=1e14;
int power(int a,int b,int p)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

vi adj[100005];
bool vis[100005];
void dfs(int val)
{
    vis[val]=true;
    trav(i,adj[val])
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }
}
int32_t main()
{
    int n,m,x,y,w,ans=0;
    cin>>n>>m;
    rep(i,m)
    {
        cin>>x>>y>>w;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    rep(i,n+2)
    vis[i]=false;
    
    repa(i,1,n)
    {
        if(!vis[i])
        {
            ans++;
            dfs(i);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8960
#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.at(i);

  int ans=0;
  for(int x:a){
    while(x%2==0){
      ans++;
      x/=2;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long n,a,b,k,tong,u[300005],x;
long long modd = 998244353;
long long poww(long long i,long long j)
 {
  	if(j==0) return 1ll;
  	  else 
  	   {
  	   	 long long them;
  	   	 them=poww(i,j/2);
  	   	 if(j%2==0) return ((them*them) % modd);
  	   	 else return (( ((them*them) % modd)*i)%modd);
	   }
 }
long long c(long long i)
 {
 	if(i==0) return 1ll;
 	  else return (((x*u[i])%modd)*u[n-i])%modd;
 }
int main()
{
 cin>>n>>a>>b>>k;
 long long i,j,h;
 tong=0;
 x=1;
 u[0]=1;
 for(i=1;i<=n;i++)
                   {
				   x=(x*i) % modd;
                   u[i]=(u[i-1]*poww(i,modd-2)) % modd;
                   }

 for(i=0;i<=n;i++)
  if(k>=a*i)
   if((k-a*i) % b == 0)
    if( ((k-a*i)/b)<=n )
     {
     tong=( tong +  ( c(i) * c((k-a*i)/b) )%modd)  % modd;
     }
 cout<<tong<<endl;
}

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

int main() {
  int x;cin>>x;
  for(int i=1;i<=x/100;i++){
    if(100*i<=x&&x<=105*i){
      cout<<1<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
}

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Text;

class TEST{
	static void Main(){
		while(true){
			var d=int.Parse(Console.ReadLine());
			if(d==0)break;
			
			var arr=Console.ReadLine().Split(' ');
			int a=0;
			for(int i=0;i<d*(d-1)/2;i++){a+=int.Parse(arr[i]);}
			Console.WriteLine(a/(d-1));
		}
	}
}

Measured memory_bytes: 6164
using System;

namespace AOJ.ITP
{
    public class TogglingCases
    {
        public static void Main()
        {
            string input = Console.ReadLine();
            string output = "";
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] >= 'a' && input[i] <= 'z') { output += input.Substring(i, 1).ToUpper(); }
                else if (input[i] >= 'A' && input[i] <= 'Z') { output += input.Substring(i, 1).ToLower(); }
                else { output += input.Substring(i, 1); }
            }
            Console.WriteLine(output);
        }
    }
}

Measured memory_bytes: 5764
#include<bits/stdc++.h> 
using namespace std;
#define  LL long long int
int main() 
{ 
   
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    LL N;
    cin>>N;
    vector<LL> arr(N);
    for(auto &it:arr)
    {
        cin>>it;
    }
    sort(arr.begin(),arr.end(),greater<LL>());
    LL total=1;
    LL sum=arr[0];
    LL index=1;
    while(total<N-1)
    {
        if(total==N-2)
        {
            total+=1;
            sum+=arr[index++];
            break;
        }
        else
        {
            total+=2;
            sum=sum+(2*arr[index++]);
        }
    }
    cout<<sum;
}


Measured memory_bytes: 4784
# coding: utf-8
# Your code here!
INF = 10000000000

def merge(A, left, mid, right):
    global ctr

    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    i,j = 0,0
    for k in range(left,right):
        ctr += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        

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

mergeSort(A,0,n)

print(*A)
print(ctr)


Measured memory_bytes: 63432
let n = read_int ()
let m = Array.(fold_left (fun m a -> if m + 1 = a then m + 1 else m) 0 @@ init n @@ fun _ -> Scanf.scanf " %d" (+) 0)
let _ = Printf.printf "%d\n" @@ if m = 0 then -1 else n - m

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

long long  pow5(long long a){
  return a*a*a*a*a;
}

int main(){
  long long X,Am,a,b,i,j;
  cin >> X;
  Am=1;
  while(pow5(Am)-pow5(Am-1) < X) Am++;
  for(i=0;i<=Am;i++){
    a = pow5(i);
    for(j=-Am;j<=Am;j++){
      b = pow5(j);
      if (a-b == X){
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
      
  
  return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
struct edge{ll to,cost;};
const int inf = 1<<28;
const ll INF = 1LL<<53;
const int COMBMAX = 500005;
const ll MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
#define repf(i,n) for(int i=0;i<=n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eachdo(v, e) for(const auto& v : e)
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance(v.begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance(v.begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n,ll mod=MOD){ll res=1;while(n>0){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v,a)-lower_index(v,a);} 
template<class T> bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
template<class T> void debug2(T v){rep(i,v.size()){rep(j,v[i].size())cout<<v[i][j]<<" ";cout<<endl;}}
template<class T> void rdv(T &v){rep(i,v.size())cin>>v[i];}
template<class T> void rdvv(T &v){rep(i,v.size()){rep(j,v[i].size())cin>>v[i][j];}}

struct mint {
ll x;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint& operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}
    mint& operator-=(const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD;return *this;}
    mint& operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}
    mint operator+(const mint a) const {mint res(*this);return res+=a;}
    mint operator-(const mint a) const {mint res(*this);return res-=a;}
    mint operator*(const mint a) const {mint res(*this);return res*=a;}
    mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}
    mint inv() const {return pow(MOD-2);}
    mint& operator/=(const mint a) {return (*this) *= a.inv();}
    mint operator/(const mint a) const {mint res(*this);return res/=a;}
};

struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < MOD);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (COMBMAX < n){
            mint ret = 1;
            rep1(i,k){
                ret *= (n-i+1);
                ret /= i;
            }
            return ret;
        }
        return fact[n]*ifact[k]*ifact[n-k];
    }
} com(COMBMAX);

int main(){
    ll N,a,b;cin >> N >> a >> b;
    mint ans = mpow(2,N);
    ans -= 1;
    ans -= com(N, a);
    ans -= com(N, b);
    cout << ans.x << endl;
    return 0;
}

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

using ll = long long;
using vi = vector<int>;
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)
#define pb push_back

const ll mod = 1e9+7;
ll lo,hi;

ll ans = 0;

const int m = 62;

// dp[i][yet][y > lo][y < hi][x > lo][x < hi]
ll dp[m][2][2][2][2][2];

void add(ll &a, ll b) {
  a += b;
  if (a>=mod) a-=mod;
}

void prop(int i, int yet, int ylo, int yhi, int xlo, int xhi) {
  f(y,ylo?0:(lo>>i&1),(yhi?1:(hi>>i&1))+1)
  f(x,xlo?0:(lo>>i&1),(xhi?1:(hi>>i&1))+1) {
    if ( x<=y && (yet||(x==y))) {
  	if (!i) add(ans,dp[i][yet][ylo][yhi][xlo][xhi]);
    else add(dp[i-1][yet|x][ylo|(y!=(lo>>i&1))][yhi|(y!=(hi>>i&1))]
             [xlo|(x!=(lo>>i&1))][xhi|(x!=(hi>>i&1))], dp[i][yet][ylo][yhi][xlo][xhi]);
    }
  }
}

int main() {
  cin>>lo>>hi;
  f(i,0,m) f(yet,0,2) f(ylo,0,2) f(yhi,0,2) f(xlo,0,2) f(xhi,0,2) 
    dp[i][yet][ylo][yhi][xlo][xhi] = 0;
  dp[m-1][0][0][0][0][0] = 1;
  fr(i,0,m) f(yet,0,2) f(ylo,0,2) f(yhi,0,2) f(xlo,0,2) f(xhi,0,2) 
    if (dp[i][yet][ylo][yhi][xlo][xhi])
    	prop(i,yet,ylo,yhi,xlo,xhi);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAX = 300001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}
long long N, A, B, K;
int f(int na, int nb)
{
    return COM(N, na) * COM(N, nb) % MOD;
}
int main()
{
    COMinit();
    cin >> N >> A >> B >> K;
    long long ans = 0;
    for (int i = 0; i <= N; i++) {
        if ((K - A * i) % B == 0) {
            int j = (K - A * i) / B;
            if (j <= N) {
                ans += f(i, j);
            }
        }
    }
    cout << ans % MOD << endl;
    return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Rep(i, N) for(int i = 0; i < N; i++)

signed main()
{
  int N;
  int A[300005];

  cin >> N;

  Rep(i, N * 3) cin >> A[i];

  sort(A, A + N * 3);

  int sum = 0;
  for(int i = N; i < 3 * N; i += 2) sum += A[i];

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
#define MIN 10000000000

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

int abs(int num){
    if(num<0) num=-num;
    return num;
}

int main(void){
    int n,k,h[101000];
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&h[i]);
    int cost[101000];
    cost[0]=0;
    for(int i=1;i<n;i++) cost[i]=MIN;
    for(int i=1;i<n;i++){
        for(int j=1;j<=k;j++){
            if(i-j<0) break;
            cost[i]=min(cost[i],cost[i-j]+abs(h[i]-h[i-j]));
        }
    }
    printf("%d",cost[n-1]);
    return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

ll N,M;

int main(){
    cin >> N >> M;
    ll m = 1;
    for(ll l=1;l*l<=M;l++){
        if(M%l == 0){
            ll a = M / l;
            if(m < a && a * N <= M){
                m = a;
            }
            if(m < l && l * N <= M){
                m = l;
            }
        }
    }
    cout << m << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd


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


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    n, m = MAP()
    a = LIST()
    b = [x for x in a if x * 4 * m >= sum(a)]

    if len(b) < m:
        print('No')
    else:
        print("Yes")


if __name__ == '__main__':
    main()


Measured memory_bytes: 5200
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--)
#define Rep(i,a) for(int i = 0; i < a; i ++)
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> pii;
#define mp(a,b) make_pair(a,b)
multiset<pii> to[N];
typedef multiset<pii>::iterator sit;

int f[N];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

void add_edge(int a, int b, int c);

pii q[N]; int l = 0, r = 0;

void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (to[a].size() < to[b].size()) swap(a, b);
	f[b] = a;
	for(sit it = to[b].begin(); it != to[b].end(); it++) {
		int v = it->first, c = it->second;
		sit tmp = to[v].find(mp(b, c));
		to[v].erase(tmp);
		add_edge(v, a, c);
	}
}

void add_edge(int a, int b, int c) {
	sit it = to[a].find(mp(b, !c));
	if (it == to[a].end()) 
		to[a].insert(mp(b, c)), to[b].insert(mp(a, c));
	else {
		to[a].erase(it);
		it = to[b].find(mp(a, !c)); to[b].erase(it);
		q[r++] = mp(a, b);
	}
}

int main() {
	int n; scanf("%d",&n);
	rep(i,1,n) f[i] = i;
	rep(i,1,n - 1) {
		int a, b;
		scanf("%d%d",&a,&b);
		a = find(a), b = find(b);
		add_edge(a, b, 0);
	}
	rep(i,1,n - 1) {
		int a, b;
		scanf("%d%d",&a,&b);
		a = find(a), b = find(b);
		add_edge(a, b, 1);
	}
	while (l < r) merge(q[l].first, q[l].second), l++;
	rep(i,1,n) if (find(i) != find(1)) {
		printf("NO\n"); return 0;
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 25088
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  ll N, A, B;
  cin >> N >> A >> B;
  ll d = N / (A + B);
  ll r = N % (A + B);
  cout << d * A + min(r, A) << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

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

int n, sif, a[N];
ll ans;
set < int > s;

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",a + i);
	}
	if(a[1] != 0){
		printf("-1\n");
		return 0;
	}
	for(int i = n; i >= 1; i--){
		if(!s.empty() and *s.rbegin() > a[i] + sif){
			printf("-1\n");
			return 0;
		}
		s.insert(a[i] + sif);
		s.erase(sif);
		ans += (ll)s.size();
		sif++;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 5760
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort()
    m_list.sort(reverse=True)


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list.pop()
            k -= 1
        else:
            m_list.sort()
            ans = m_list.pop()
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list.pop() * m_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[-1] * p_list[-2]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[-1] * m_list[-2]
            else:
                mval = 0

            if pval > mval:
                p_list.pop()
                p_list.pop()
                ans = ans * pval % 1000000007
            else:
                m_list.pop()
                m_list.pop()
                ans = ans * mval % 1000000007
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()




Measured memory_bytes: 31964
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  if(s=="SUN"){cout<<7<<"\n";}
  else if(s=="MON"){cout<<6<<"\n";}
  else if(s=="TUE"){cout<<5<<"\n";}
  else if(s=="WED"){cout<<4<<"\n";}
  else if(s=="THU"){cout<<3<<"\n";}
  else if(s=="FRI"){cout<<2<<"\n";}
  else if(s=="SAT"){cout<<1<<"\n";}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using Graph = vector<vector<LL>>;

long long gcd(long long a, long long b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
long long chmax(long long a,long long b){
  a = max(a,b);
}
long long chmin(long long a, long long b){
  a = min(a,b);
}
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true;

    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v);
    }
}



int main() {
  LL n,k,sum=0,a=0,b=0,c=0,d=0,ans=0;
  LL MOD = 1000000007;
  LL INF = 1LL << 60;
  string S="";
  cin >> k >> a >> b;
  if(a - a%k + k <= b || a%k==0) S = "OK";
  else S = "NG";
  cout << S << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

struct edge {
    int to, cost;
};

using P = pair<int, int>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    vector<vector<edge>> g(k);
    for(int i = 0; i < k; i++) {
        g[i].emplace_back(edge{(i + 1) % k, 1});
        g[i].emplace_back(edge{i * 10 % k, 0});
    }
    vector<int> d(k, INF);
    d[1] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(P(0, 1));
    while(!que.empty()) {
        int nd = que.top().first;
        int from = que.top().second;
        que.pop();
        if(nd > d[from]) {
            continue;
        }
        for(const auto &e : g[from]) {
            if(d[e.to] > d[from] + e.cost) {
                d[e.to] = d[from] + e.cost;
                que.emplace(P(d[e.to], e.to));
            }
        }
    }
    print(d[0] + 1);
}

Measured memory_bytes: 6780
#include <iostream>
using namespace std;
 
int main() {
 
	int N,M,D[1000]{},C[1000]{};
	int DP[1000][1000]{};
 
	int r=0,t=0;
	int s=0,a=0,b=0;
 
	cin >> N >> M;
 
	for(int i=1;i<=N;i++){
		cin >> D[i];
		//cout << D[i] << endl;
	}
	for(int i=1;i<=M;i++){
		cin >> C[i];
		//cout << C[i] << endl;
	}
 
 
	DP[0][0]=0;
	for(int i=0;i<=N;i++){
 
		for(int t=0;t<=M-N+1;t++){
			DP[i][a]=DP[i-1][a-1]+D[i]*C[a];
			a=a+1;
		}
		a=s;
		for(int r=0;r<=M-N;r++){
			if(DP[i][a]<=DP[i][a+1])DP[i][a+1]=DP[i][a];
			a=a+1;
		}
		s=s+1;
		a=s;
 
	}
 
	cout << DP[N][M] << endl;
 
	return 0;
}

Measured memory_bytes: 5080
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000007;
const ll inv2 = (mod + 1) / 2;
int n;
ll a, b;
ll c0, ans = 1;
typedef pair<ll, ll>pii;
map<pii, pii>mp;
ll Pow(ll a, ll b) {
	ll res = 1ll;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld", &a, &b);
		if (a == 0 && b == 0)c0++;
		else {
			if (b < 0)a = -a, b = -b;
			ll g = abs(gcd(a, b));
			a /= g; b /= g;
			if (a > 0)mp[pii(a, b)].first++;
			else mp[pii(b, -a)].second++;
		}
	}
	for (auto p : mp) {
		ll tmp = (Pow(2, p.second.first) + Pow(2, p.second.second) + mod - 1) % mod;
		ans = ans * tmp%mod;
	}
	printf("%lld\n", (ans + mod - 1 + c0) % mod);
	return 0;
}

Measured memory_bytes: 19312