akhauriyash/Code-Regression huggingface dataset:
/*Read the problem carefully before starting to work on it*/
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007

double PI = 3.1415926535897932384626;

template<typename T> T power(T x, T y, ll m = mod) {T ans = 1; while (y > 0) {if (y & 1LL) ans = (ans * x) % m; y >>= 1LL; x = (x * x) % m;} return ans % m;}

//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(x, y) uniform_int_distribution<ll>(x, y)(rng)

//struct custom_hash {
//    static uint64_t splitmix64(uint64_t x) {
//        // http://xorshift.di.unimi.it/splitmix64.c
//        x += 0x9e3779b97f4a7c15;
//        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//        return x ^ (x >> 31);
//    }
//    size_t operator()(uint64_t x) const {
//        static const uint64_t FIXED_RANDOM =
//            chrono::steady_clock::now().time_since_epoch().count();
//        return splitmix64(x + FIXED_RANDOM);
//    }
//};

#define fi first
#define se second

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	ll one = power(10LL, n);
	ll three = (power(9LL, n) * 2) % mod;
	ll two = power(8LL, n);
	one = (one % mod + two % mod) % mod;
	cout << (one - three + mod ) % mod << endl;
	return 0;
}


//252908XL

/*
comments:-

*/


Measured memory_bytes: 3648
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 200000 + 10;

int n, Q, sfa[maxn], cnt, sz[maxn];
ll m;
struct anode{
	int u, v;
	anode() {}
	anode(int _u, int _v):u(_u), v(_v) {}
}a[maxn];

int findfa(int u) { return (sfa[u] == u) ? (u) : (sfa[u] = findfa(sfa[u])); }

signed main() {
//	freopen("data.in","r",stdin);
  scanf("%lld%lld%lld", &n, &m, &Q); cnt = 0;
	for(int i = 1;i <= n;i ++) sfa[i] = i, sz[i] = 1;
	int flag = 1;
	for(int i = 1;i <= Q;i ++) {
		int u, v, kd;
		scanf("%lld%lld%lld", &u, &v, &kd);
		u ++; v ++;
		if(kd == 0) {
			int f1 = findfa(u);
			int f2 = findfa(v);
			if(f1 == f2) continue;
			else sfa[f1] = f2, sz[f2] += sz[f1];
		}
		else a[++ cnt] = anode(u,v);
	}
	if(!flag) {
		puts("No");
		return 0;
	}
	if(m == n - 1) {
		if(cnt) puts("No");
		else puts("Yes");
		return 0;
	}
	for(int i = 1;i <= cnt;i ++) {
		int u = a[i].u, v = a[i].v;
		int f1 = findfa(u), f2 = findfa(v);
		if(f1 == f2) flag = 0;
	}
	if(!flag) {
		puts("No");
		return 0;
	}
	int num = 0;
	for(int i = 1;i <= n;i ++) if(sfa[i] == i) num ++;
	m = m - n + num;
	if(num <= 2) {
		if(cnt) {
			puts("No");
			return 0;
		}
	}
	ll lim = (ll)max(0LL,1LL * num * (num - 1) / 2);
	if(m <= lim) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 5888
#include <stdio.h>

int match(int *face1, int *face2);

int table[7][6] = {{0},{1,2,3,5,4,6},{2,6,3,1,4,5},{3,6,5,1,2,4},
                     {4,6,2,1,5,3},{5,6,4,1,3,2},{6,5,3,2,4,1}};

int main(void)
{

    int a[7],b[7];
    int face1[5],face2[5];
    int flag;

    for (int i = 1; i < 7; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i < 7; i++){
        scanf("%d", &b[i]);
    }
    for (int i = 0; i < 5; i++){
        face1[i] = a[table[1][i + 1]];
    }

    flag = 0;
    for (int i = 1; i < 7; i++){
        if (a[1] == b[i]){
            for (int j = 0; j < 5; j++){
                face2[j] = b[table[i][j + 1]];
            }
            flag = match(face1, face2);
            if (flag == 1){
                break;
            }
        }
    }

    if (flag == 1){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return (0);
}

int match(int *face1, int *face2)
{
    int i,j,k;

    if (face1[4] != face2[4]){
        return (0);
    }

    for (i = 0; i < 4; i++){
        if (face1[0] == face2[i]){
            for (j = 0; j < 4; j++){
                if (face1[j] != face2[(i + j) % 4]){
                    break;
                }
            }
            if (j == 4){
                return (1);
            }
        }
    }

    return (0);
}



Measured memory_bytes: 2100
#include <iostream>
using namespace std;
typedef long long unsigned int ll;
 
int main() {
 
  char N;
  cin >> N;
  if(N=='a'||N=='i'||N=='u'||N=='e'||N=='o'){
	
  	cout << "vowel"<<endl;
  }else{
	cout << "consonant"<<endl;
  }
    return 0;
}


Measured memory_bytes: 504
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;

int main(){
int a,b,c,d;cin>>a>>b>>c>>d;

    cout<<max(0,min(b,d)-max(a,c));

}

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

int main() {
	// your code goes here
	string seq;
	cin >> seq;
	char curr = seq[0];
	int i = 1;
	int ans = 0;
	while(i < seq.length()){
	    if(curr != seq[i])
	        ans++;
	    curr = seq[i];
	    ++i;
	}
	cout << ans;
}

Measured memory_bytes: 512
<?php

$s = trim(fgets(STDIN));
$s = explode(' ',$s);
$a = $s[0];
$b = $s[1];

if ($a < $b) {
  echo 'a < b' . PHP_EOL;
} elseif ($a > $b) {
  echo 'a > b' . PHP_EOL;
} else {
  echo 'a == b' . PHP_EOL;
}
exit;

?>

Measured memory_bytes: 15244
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc =new Scanner(System.in);
		int line = sc.nextInt();
		if(line == 0){
			System.out.println(1);
		}else{
            System.out.println(0);
        }
		sc.close();
    }
}


Measured memory_bytes: 35612
#include <iostream>
#include <vector>

#define ll long long
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> v(n);
    for (int i = 0; i < n; i++)cin >> v[i];

    ll ret = 0;
    bool found = true;
    while (found) {
        found = false;
        for (int i = 0; i < n; i++) {
            if (v[i] >= n) {
                found = true;
                ll x = v[i] / n;
                v[i] %= n;
                ret += x;
                for (int j = 0; j < n; j++) {
                    if (i == j)continue;
                    v[j] += x;
                }
            }
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

class UnionFind {
public:
	vector < ll > par;
	vector < ll > siz;
	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;
	}
	ll root(ll x) {
		while (par[x] != x) {
			x = par[x] = par[par[x]];
		}
		return x;
	}
	bool unite(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		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() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i, m){
        int x, y, z;
        cin >> x >> y >> z;
        uf.unite(x-1, y-1);
    }
    int ans = 0;
    map<int, int> mp;
    rep(i, n){
        if(!mp[uf.root(i)]){
            ans++;
            mp[uf.root(i)] = 1;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 6528
//=============================================================
// Name        : a
// Date        : Mon Jun 10 11:26:35 CST 2019
// Author      : landcold7
// Description : Actions speak louder more than words
//=============================================================
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define sz(x) ((int)(x).size())
#ifndef _has_trace
#define trace(...)
#endif
typedef long long ll;

void solve() {
  int a, b;
  cin >> a >> b;
  cout << (a * 3 + b) / 2 << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int, int>;
typedef vector<int> vit;

//最大公約数
lol gcd(lol x, lol y){
  if(x < y) swap(x, y);
  lol r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }
  return y;
}

//最小公倍数
lol lcm(lol x, lol y){
  lol a = x * y;
  return (a / gcd(x, y));
}

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

  int n;
  cin >> n;
  string s[n + 5];
  rep(i, n){
    cin >> s[i];
  }
  sort(s, s +n);
  lol ans = 1;
  for(int i = 1;i < n;i ++){
    if(s[i] != s[i - 1]){
      ans ++;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 9908
n=int(input())
e0=[]
l=[]
for i in range(n):
  t=int(input())
  if(t%10==0):
    e0.append(t)
  else:
    l.append(t)
if(l==[]):
  print(0)
else:
  l.sort()
  ans=sum(e0)+sum(l)
  if(ans%10==0):
    ans-=l[0]
  print(ans)

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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e6 + 5;
const ll INF = 1e17 + 7 , mod = 1e9 + 7;
const double eps = 1e-9 , PI = acos(-1);

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

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

int n;
ll mem[N][2][2];

ll dp(int i , bool zero , bool nine) {
    if(i == 0) {
            return zero && nine;
    }

    ll &ret = mem[i][zero][nine];
    if(ret != -1) return ret;

    ret = 0;

    for(int k = 0 ; k < 10 ; k ++) {
            ret = add(ret , dp(i - 1 , zero | k == 0 , nine | k == 9));
    }

    return ret;
}

void solve(int testCase){

    scanf("%d" , &n);

    memset(mem , -1 , sizeof mem);

    for(int i = 0 ; i < n ; i ++) {
            dp(i , 0 , 0);
    }

    printf("%lld\n" , dp(n , 0 , 0));
}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 66292
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef tuple<ll, ll, ll> ti;
ll mod=1E9+7;
 
#define REP(a,b,c) for(ll a=b;a<(c);a++)
#define PER(a,b,c) for(ll a=b;a>=(c);a--)

ll ii(){ ll x; cin >> x; return x; }
string is(){ string x; cin >> x; return x; }
ld id(){ ld x; cin >> x; return x; }
void oi(ll x){ cout << x; }
void od(ld x){ cout << fixed << setprecision(10) << x; }
void os(string x){ cout << x; }
void oe(){ cout << endl; }
void oie(ll x){ oi(x); oe(); }
void ode(ld x){ od(x); oe(); }
void ose(string x){ os(x); oe(); }

int main(){
    ll N=ii();
    multiset<pii> add, del;
    REP(i,0,N){
        string s=is();
        ll m=0, v=0;
        for(char c : s){
            if(c=='('){
                v++;
            }else{
                v--;
            }
            m=min(m,v);
        }
        if(v>=0){
            add.insert({-m,v});
        }else{
            del.insert({-(m-v),-v});
        }
    }

    ll cur=0;
    for(auto [m, v]:add){
        if(cur-m<0){
            ose("No");
            return 0;
        }
        cur+=v;
    }
    ll a=cur;

    cur=0;
    for(auto [m, v]:del){
        if(cur-m<0){
            ose("No");
            return 0;
        }
        cur+=v;
    }
    ll b=cur;

    if(a!=b){
        ose("No");
        return 0;
    }
    ose("Yes");

    return 0;
}

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

int main(){
    int x = 0;
    int n = 0;
    std::cin >> x;
    std::cin >> n;

    std::vector<bool> answers(101);
    std::fill(answers.begin(),answers.end(),false);
    std::vector<int> array(n);
    for(int i=0;i<n;i++){
        std::cin >> array[i];
        answers[array[i]] = true;
    }

    int up = x+1;
    int down = x-1;
    if(!answers[x]){

        std::cout <<  x << std::endl;
        return 0;
    }
    for(;;){
        if(down <= 0){
            std::cout <<down  << std::endl;
            return 0;
        }
        if(!answers[down]){
            std::cout <<  down  << std::endl;
            return 0;
        }
        //上の確認
        if(up >= 101){
            std::cout << up  << std::endl;
            return 0;
        }
        if(!answers[up]){
            std::cout << up  << std::endl;
            return 0;
        }
        down--;up++;
    }

    return 0;
}

Measured memory_bytes: 3628
import java.util.*;
public class Main{
	static long Comb(long t, long r){
		r = Math.min(r, t-r);
		if(r==0)return 1;
		if(r==1)return t;
		long ans = (((Fact(t, 1000000007) * revFact(r, 1000000007)) % 1000000007) * revFact(t-r, 1000000007)) % 1000000007;
		return ans;
	}

	static long Fact(long n, long mod){
		long ans = 1;
		for(int i=1; i<=n; i++){
			ans = (ans * i) % mod;
		}
		return ans;
	}

	static long revFact(long n, long mod){
		long ans = PowMod(Fact(n, mod), mod-2, mod);
		return ans;
	}

	static long PowMod(long x, long n, long mod){
		long ans = 1;
		x = x % mod;
		while(n!=0){
			if(n%2==0){
				x = (x * x) % mod;
				n /= 2;
			}else{
				ans = (ans * x) % mod;
				n -= 1;
			}
		}
		return ans;
	}

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int p = 0;
		long ans = 1;
		if(m==1)ans = 1;
		else{
			int[] num = new int[30];
			int k = m;
			while(k%2==0){
				num[p]++;
				k /= 2;
			}
			p++;
			for(int i=3; i*i<=k; i+=2){
				while(k%i==0){
					num[p]++;
					k /= i;
				}
				if(num[p]!=0)p++;
			}
			if(k!=1)num[p]++;
			for(int i=0; i<=p; i++){
				ans = (Comb(num[i]+n-1, num[i]) * ans) % 1000000007;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 22868
sub prime {
	my $n = shift;

	for (2..$n) {
		if ($_ * $_ > $n) {
			last;
		}
		if (($n % $_) == 0) {
			return 0;
		}
	}
	return 1;
}

my $x = <>;
chomp($x);
for (2..55555) {
	if (prime($_) && ($_%5 == 1)) {
		print $_." ";
		$x--;
	}
	if ($x == 0) {
		print "\n";
		last;
	}
}


Measured memory_bytes: 640
import java.util.Scanner;

class Main{
     public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	double r = scan.nextDouble();
    	double pi = 3.141592653589;
    	
    	System.out.println(String.format("%.8f", r*r*pi) + " " + String.format("%.8f", 2.0*r*pi));
    	
     }
}

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

char s1[2000];
char s2[2000];

int LCS(int, int);

int main()
{
  int sumstr;
  int i, j, k;
  scanf("%d", &sumstr);

  for (i = 0; i < sumstr; i++)
  {
    scanf("%s", s1);
    scanf("%s", s2);
    printf("%d\n", LCS(strlen(s1), strlen(s2)));
  }

  return 0;
}

int LCS(int length1, int length2)
{

  int i, j, x;
  int answer[1001][1001];

  x = 0;

  for (i = 0; i < length1; i++)
  {
    answer[i][0] = 0;
  }

  for (i = 0; i < length2; i++)
  {
    answer[0][i] = 0;
  }
  for (i = 0; i < length1; i++)
  {
    for (j = 0; j < length2; j++)
    {
      if (s1[i] == s2[j] && s1[i] != ' ' && s2[i] != ' ')
      {
        if (i == 0 || j == 0)
        {
          answer[i][j] = 1;
        }
        else
        {
          answer[i][j] = answer[i - 1][j - 1] + 1;
        }
      }

      else
      {
        if (i == 0 && j != 0)
        {
          answer[i][j] = answer[0][j - 1];
        }
        else if (i != 0 && j == 0)
        {
          answer[i][j] = answer[i - 1][0];
        }
        else if (i == 0 && j == 0)
        {
          answer[0][0] = 0;
        }
        else if (i != 0 && answer[i - 1][j] > answer[i][j - 1])
        {
          answer[i][j] = answer[i - 1][j];
        }
        else if (answer[i - 1][j] <= answer[i][j - 1])
        {
          answer[i][j] = answer[i][j - 1];
        }
      }
    }
  }
  return answer[length1 - 1][length2 - 1];
}



Measured memory_bytes: 5640
#include <iostream>
using namespace std;
using ll = long long;
int main()
{
	// A - Table Tennis Training
	ll n, a, b;
	cin >> n >> a >> b;
	ll diff = a - b;
	ll ans;
	if (diff < 0)	diff = -diff;
	if (diff % 2 == 0) {
		ans = diff / ll(2);
	}
	else {
		ll dist_1 = a < b ? b - 1 : a - 1;
		ll dist_n = a < b ? n - a : n - b;
		if (dist_1 < dist_n)	ans = dist_1;
		else {
			ans = dist_n;
		}

		ll ans2 = 0;
		dist_1 = a < b ? a - 1 : b - 1;
		dist_n = a < b ? n - b : n - a;
		if (dist_1 < dist_n) {
			a = 1;
			b = b - dist_1 - 1;
			ans2 += dist_1 + 1;
		}
		else {
			b = n;
			a = a + dist_n + 1;
			ans2 += dist_n + 1;
		}
		diff = b - a;
		ans2 += diff / ll(2);
		if (ans > ans2)	ans = ans2;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
	#include <iomanip>
	#include<math.h>
	#include<list>
	#include <algorithm>
	#include<set>
	#include<vector>
	#include<math.h>
	#include<map>
	#include<string>
	#include <numeric>
	#include <queue>
	#include <sstream>
	#include <bitset>
	#include<stack>

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


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

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

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

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

		return true;
	}

	long long modinv(long long a, long long m) {
		long long b = m, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= m;
		if (u < 0) u += m;
		return u;
	}

	// 繰り返し二乗法
	ll pow2(ll n, ll p, ll mod) {
		if (p == 0 || n == 1) {
			return 1;
		}
		else {
			ll ret = pow2(n * n % mod, p / 2, mod);
			if (p % 2 == 1) {
				ret *= n;
			}
			return ret % mod;
		}
	}


	#define rep(i,s,e) for(ll i=s;i<e;i++)
	#define repeq(i,s,e) for(ll i=s;i<=e;i++)

	int main() {
		const ll mod = 1e9 + 7;
		ll N, K;
		std::cin >> N >> K;
		vll A(N);
		rep(i, 0, N) {
			std::cin >> A[i];
		}
		sort(A.begin(), A.end());
		ll idx_min = N - K;
		ll idx_max = K - 1;
		ll cnt = 1;
		ll k = K;
		ll max_s = 0;
		ll min_s = 0;
		ll ans = 0;
		repeq(i, 1, N - K + 1) {

			ans += (A[idx_max] * cnt) % mod;
			ans -= (A[idx_min] * cnt) % mod;
			ans %= mod;
			idx_max++;
			idx_min--;

			cnt *= k;
			cnt %= mod;
			k++;
			cnt *=modinv(k - K,mod);
			cnt %= mod;

		}
		std::cout << ans << endl;

		return 0;
	}


Measured memory_bytes: 3936
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val array = readLine()!!.split(" ").map(String::toInt).toMutableList()
    if (n != array.size) return

    (0..(n - 1)).forEach { index1 ->
        if (index1 == 0) {
            array.forEachIndexed { index, num ->
                if (index == array.size - 1) println(num.toString()) else print(num.toString() + " ")
            }
            return@forEach
        }
        (1..index1).forEach { index2 ->
            val num = index1 - index2
            if (array[num] > array[num + 1]) {
                val temp = array[num]
                array[num] = array[num + 1]
                array[num + 1] = temp
            }
        }
        array.forEachIndexed { index, num ->
            if (index == array.size - 1) println(num.toString()) else print(num.toString() + " ")
        }
    }
}


Measured memory_bytes: 40220
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}
func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0
	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}
	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	s := getNextInt(scanner)
	aa := make([]int, n)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt(scanner)
	}
	dp := make([]mint, s+1)
	dp[0] = 1
	for i := 0; i < n; i++ {
		for j := s; j >= 0; j-- {
			dp[j].mulAs(2)
			if j-aa[i] >= 0 {
				dp[j].addAs(dp[j-aa[i]])
			}
		}
	}
	fmt.Fprintln(writer, dp[s])
}

type mint int64

func (mt mint) mod() mint {
	m := mint(998244353)
	mt %= m
	if mt < 0 {
		return mt + m
	}
	return mt
}
func (mt mint) inv() mint {
	var m, y mint
	m.subAs(2)
	dbl := mt
	y = 1
	for i := 0; i < 31; i++ {
		if m%2 == 1 {
			y.mulAs(dbl)
		}
		m >>= 1
		dbl.mulAs(dbl)
	}
	return y
}
func (mt mint) add(x mint) mint {
	return (mt + x).mod()
}
func (mt mint) sub(x mint) mint {
	return (mt - x).mod()
}
func (mt mint) mul(x mint) mint {
	return (mt * x).mod()
}
func (mt mint) div(x mint) mint {
	return mt.mul(x.inv())
}
func (mt *mint) addAs(x mint) *mint {
	*mt = mt.add(x)
	return mt
}
func (mt *mint) subAs(x mint) *mint {
	*mt = mt.sub(x)
	return mt
}
func (mt *mint) mulAs(x mint) *mint {
	*mt = mt.mul(x)
	return mt
}
func (mt *mint) divAs(x mint) *mint {
	*mt = mt.div(x)
	return mt
}


Measured memory_bytes: 1912
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, A, B = MAP()

print("Alice" if (B-A)%2 == 0 else "Borys")


Measured memory_bytes: 5200
#include <iostream>
using namespace std;
 
int main()
{
	int N, M;
	cin >> N >> M;
	int a[50][2];
	for (int i = 0; i < M; i++) {
		cin >> a[i][0] >> a[i][1];
	}
	int b[50] = { 0 };
	for (int i = 0; i < M; i++) {
		b[a[i][0] - 1]++;
		b[a[i][1] - 1]++;
	}
	for (int i = 0; i < N; i++) {
		cout << b[i] << endl;
	}
}

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

import static java.lang.Integer.parseInt;

/**
 * Irreducible Fractionalization
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] units;

		int an, ad, bn, bd;
		an = 0; //非循環節分子
		ad = 1; //非循環節分母
		bn = 0; //循環節分子
		bd = 1; //循環節分母

		line = br.readLine();

		//
		units = line.split("[()]");

		if (units.length == 2) {
			bn = parseInt(units[1]);
			bd = ((int) Math.pow(10, units[1].length())) - 1;
		}

		//
		units = units[0].split("\\.");

		if (units.length == 2) {
			bd *= (int) Math.pow(10, units[1].length());
			an = parseInt(units[0] + units[1]);
			ad = (int) Math.pow(10, units[1].length());
		} else {
			an = parseInt(units[0]);
		}

		//
		int n, d, g;
		d = lcm(ad, bd);
		n = an * (d / ad) + bn * d / bd;
		g = gcd(n, d);
		n /= g;
		d /= g;

		System.out.printf("%d/%d\n", n, d);
	}

	static int gcd(int a, int b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

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


Measured memory_bytes: 24640
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> P;
typedef long long int ll;

int main()
{
	string S;
	cin >> S;
	bool up=(S.size()%2==0);
	for(int i=0;i<S.size();i++)
	{
		if(i%2==0&&S[i]!='h') up=false;
		else if(i%2==1&&S[i]!='i') up=false;
	}
	puts(up?"Yes":"No");
	return 0;
}

Measured memory_bytes: 764
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://arc089.contest.atcoder.jp/tasks/arc089_a>
問題文============================================================
 シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。
 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、
 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi,yi) を訪れる予定です。
 
 AtCoDeerくんが時刻 t に 点 (x,y) にいる時、
 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。
 その場にとどまることは出来ないことに注意してください。
 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

=================================================================

解説=============================================================

================================================================
*/
struct plan{
    int t,x,y;
    plan():t(0),x(0),y(0){}
};
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<plan> P(N+1);
    for(int i = 1; i <= N;i++) cin >> P[i].t >> P[i].x >> P[i].y;
    for(int i = 1; i <= N;i++){
        int diff = abs(P[i].x - P[i-1].x) + abs(P[i].y - P[i-1].y);
        if(diff > P[i].t - P[i-1].t){
            cout << "No" << endl;
            return 0;
        }else{
            if((P[i].t - P[i-1].t - diff )% 2 != 0){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 1408
/*
 *           AUTHOR: Maria Theresa M. Padayhag
 *             DATE: 20160326
 *  PRE-REQUIREMENT: JDK 1.8
 */
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main
{
	public static boolean isPalindrome(String input)
	{
		StringBuilder sb = new  StringBuilder(input);
        if(input.equals(sb.reverse().toString()))
			return true;
        else
			return false;
	}
	
	public static void main( String args[] ) throws IOException
	{
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		String input;
		ArrayList<String> list = new ArrayList<String>();
		
		READ: 
		while( ( input = br.readLine() ) != null && input.length() !=0 ) {
			if(isPalindrome(input))
				list.add(input);					
		}
		
		System.out.println(list.size());
	}
}

Measured memory_bytes: 24088
#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-9;
const int maxn = 1e6+9;
const double pi=3.14159265358979323846264;
const int inf = 1e9;
const ll mod = 998244353;
string op[maxn];
pii pq[maxn],ui[maxn*3];
void ch(int pos,int x,int k,int l,int r){
    if(l==r-1){
        ui[k]=mp(x,pos);
        return;
    }
    int mid=(l+r)/2,cl=2*k+1,cr=2*k+2;
    if(pos<mid) ch(pos,x,cl,l,mid);
    if(pos>=mid) ch(pos,x,cr,mid,r);
    ui[k]=max(ui[cr],ui[cl]);
}
pii sol(int a,int b,int k,int l,int r){
    if(a>=b) return mp(-inf,0);
    if(a<=l&&b>=r) return ui[k];
    int mid=(l+r)/2,cl=2*k+1,cr=2*k+2;
    pii p1(-inf,0),p2(-inf,0);
    if(a<mid) p1=sol(a,b,cl,l,mid);
    if(b>mid) p2=sol(a,b,cr,mid,r);
    return max(p1,p2);
}
int main()
{
    ios::sync_with_stdio(false);
    int n,num=0,a=0,b=0;
    cin>>n;
    for(int i=0;i<n;++i) cin>>op[i];
    for(int i=0;i<n;++i){
        vector<int> tmp;
        tmp.clear();
        int jk=0,pos=0,kl=op[i].length();
        while(pos<kl){
            if(op[i][pos++]=='(') ++jk;
            else --jk;
            while(jk<0&&pos<kl&&op[i][pos]==')') --jk,++pos;
            if(jk<0){
                tmp.push_back(-jk);
                jk=0;
            }
        }
        int io=0;
        for(int j=0;j<tmp.size();++j) io+=tmp[j];
        jk=max(jk,0);
        if(!io) a+=jk;
        else if(!jk) b+=io;
        else pq[num++]=mp(io,jk);
    }
    sort(pq,pq+num);
    for(int i=0;i<num;++i) ch(i,pq[i].second-pq[i].first,0,0,num);
    int cnt=0,fg=1;
    while(cnt<num){
        int pos=lower_bound(pq,pq+num,mp(a,-inf))-pq;
        pii tmp=sol(0,pos,0,0,num);
        if(tmp.first==-inf||a+tmp.first<0){
            fg=0;
            break;
        }
        a+=tmp.first;
        ch(tmp.second,-inf,0,0,num);
        ++cnt;
    }
    if(fg&&a-b==0) cout<<"Yes";
    else cout<<"No";
    return 0;
}


Measured memory_bytes: 40464
i=int(input())
j=list(map(int,input().split()))
f=True
for k in j:
  if 2*(k//2)==k:
    if 3*(k//3)!=k:
      if 5*(k//5)!=k:
        f=False
        break
if f:
  print("APPROVED")
else:
  print("DENIED")

Measured memory_bytes: 3060
A,B,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=10**7
for i in range(m):
    x,y,c=map(int,input().split())
    price=a[x-1]+b[y-1]-c
    if price<ans:
        ans=price
a.sort()
b.sort()
p=a[0]+b[0]
if p<ans:
    ans=p
print(ans)


Measured memory_bytes: 18736
import sys,random

rand = random.randint

def prime(n):
	if n == 2:
		return True
	if n < 2 or n & 1 == 0:
		return False
	d = (n-1) >> 1
	while d & 1 == 0:
		d >>= 1
	
	for i in range(10):
		a = rand(1,n-1)
		t = d
		y = pow(a,t,n)
		while t != n-1 and y != 1 and y != n-1:
			y = pow(y,2,n)
			t <<= 1
		if y != n-1 and t & 1 == 0:
			return False
	return True

a = [prime(i) for i in range(1000000)]

for s in sys.stdin:
	i = int(s)
	print(a[:i+1].count(True))

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

int main() {
	int h, w, i, j;
	while (1) {
		cin >> h >> w;
		if (h == 0 && w == 0) {
			break;
		}
		else {
			for (i = 1; i <= h; i++) {
				for (j = 1; j <= w; j++) {
					if (i%2 == 1) {
						if (j % 2 == 1) {
							cout << "#";
						}
						else {
							cout << ".";
						}
					}
					else {
						if (j % 2 == 1) {
							cout << ".";
						}
						else {
							cout << "#";
						}
					}
				}cout << endl;
			}
			cout << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3096
import java.lang.reflect.Array;
import java.util.*;
import java.util.function.*;
import java.util.stream.Collectors.*;
public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }
    IO io = new IO();

    /// ********** 本体 ********** ///

    void solve() {
        int n = io.Int();
        int[] a = new int[n];
        REP(n,integer -> a[integer]=io.Int());
        long cost1=0,cost2=0;
        long sum1=0,sum2=0;
        //sum is +-+...
        for(int i=0;i<n;++i){
            if(i%2==0){
                //sum is +
                sum1+=a[i];
                long addVal =
                        sum1<0?(-sum1)+1:
                        sum1==0?1:0;
                sum1+=addVal;
                cost1+=Math.abs(addVal);
            }else{
                //sum is -
                sum1+=a[i];
                long addVal =
                        sum1>0?(-sum1)-1:
                        sum1==0?-1:0;
                sum1+=addVal;
                cost1+=Math.abs(addVal);
            }
        }
        //sum is -+-...
        for(int i=0;i<n;++i){
            if(i%2!=0){
                //sum is +
                sum2+=a[i];
                long addVal =
                        sum2<0?(-sum2)+1:
                                sum2==0?1:0;
                sum2+=addVal;
                cost2+=Math.abs(addVal);
            }else{
                //sum is -
                sum2+=a[i];
                long addVal =
                        sum2>0?(-sum2)-1:
                                sum2==0?-1:0;
                sum2+=addVal;
                cost2+=Math.abs(addVal);
            }
        }
        //result
        long ans = Math.min(cost1,cost2);
        System.out.println(ans);
    }

    void FOR(int a, int b, Consumer<Integer>act) { for(int i = a; i < b; ++i) act.accept(i); }
    void REP(int a, Consumer<Integer>act) { FOR(0, a, act); }
}
class IO{
    String[] nextBuff;
    int      buffCnt;
    Scanner  sc = new Scanner(System.in);
    public IO(){
        nextBuff = new String[0];
        buffCnt = 0;
    }
    String next() {
        if (buffCnt < nextBuff.length) return nextBuff[buffCnt++];
        String line = sc.nextLine();
        while (line == "") line = sc.nextLine();
        nextBuff = line.split(" ");
        buffCnt = 0;
        return nextBuff[buffCnt++];
    }
    public String String() { return next(); }
    public char   Char()   { return next().charAt(0);}
    public int    Int()    { return Integer.parseInt(next());}
    public long   Long()   { return Long.parseLong(next());}
    public double Double() { return Double.parseDouble(next());}
}

Measured memory_bytes: 49328
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rep2(i,k,n) for(int i=k;i>=n;i--)
#define mod 998244353
using namespace std;
inline void upd(int& x,int y){
	x+=y;
	x-= (x>=mod) ? mod : 0;
}
const int N=305;
int pw[N<<1],f[N],a[N][N],n,m;
int main(){
	pw[0]=1;rep(i,1,600)pw[i]=pw[i-1],upd(pw[i],pw[i-1]);
	rep(i,1,N-1)f[i]=pw[(i-1)<<1],upd(f[i],f[i-1]),upd(f[i],f[i-1]);
	scanf("%d%d",&n,&m);
	rep(i,1,n)rep(j,1,m)scanf("%d",&a[i][j]);
	int r=0;
	rep(i,1,m){
		int t=0;
		rep(j,r+1,n)if(a[j][i]){t=j;break;}
		if(!t)continue;
		r++;
		rep(j,1,m)swap(a[r][j],a[t][j]);
		rep(j,r+1,n)if(a[j][i]){
			rep(k,i,m)a[j][k]^=a[r][k];
		}
	}
	int ans=1ll*f[r]*pw[n-r]%mod*pw[m-r]%mod;
	printf("%d\n",ans);
} 

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define ALL(x) (x).begin(),(x).end()
int ctoi(const char c){
    if('0' <= c && c <= '9') return (c-'0');
    return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main(){
    ll N,A[100007],msum=0,psum=0,mct,pct;
    cin >> N;
    rep(i,N){
        cin >> A[i];
    }
    rep(i,N){
        if(i%2==0){
            if(A[i]+psum>0){
                psum+=A[i];
            }
            else{
                pct+=-(A[i]+psum)+1;
                psum=1;
            }
            if(A[i]+msum>=0){
                mct+=A[i]+msum+1;
                msum=-1;
            }
            else{
                msum+=A[i];
            }
        }
        else{
            if(A[i]+msum>0){
                msum+=A[i];
            }
            else{
                mct+=-(A[i]+msum)+1;
                msum=1;
            }
            if(A[i]+psum>=0){
                pct+=A[i]+psum+1;
                psum=-1;
            }
            else{
                psum+=A[i];
            }
        }
    }
    cout << min(pct,mct) << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
using ll = long long int;

int n;
vector<ll> a;

int main(void) {
	cin >> n;
	for (int i = 0; i < n * 3; i++) {
		ll ai;
		cin >> ai;
		a.push_back(ai);
	}
	sort(a.begin(), a.end());
	ll ret = 0;
	for (int i = n; i < 3 * n; i+=2) {
		ret += a[i];
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 6128
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define INF 10000
#define N 10
typedef pair<double,double> P;
typedef vector<P> V;
int n;
double w[N];

int getW(int bit){
  int res = 0;
  for(int i=0;i<n;i++) if(bit>>i&1) res += w[i];
  return res;
}

P Merge(P a,P b){
  double l = min(a.first,b.first);
  double r = max(a.second,b.second);
  return P(l,r);
}

V dfs(double x,int bit){

  if(__builtin_popcount(bit)==1) return V(1,P(x,x));
  if(__builtin_popcount(bit)==0) return V(1,P(-INF,INF));
  
  vector<P> res;
  for(int i=0;i<(1<<n);i++){
    if( (i | bit) != bit ) continue;
    int lbit = i;
    int rbit = bit ^ i;
    double lw = getW(lbit);
    double rw = getW(rbit);
    if(lw == 0 || rw == 0) continue;
    double lx = x - rw/(lw+rw);
    double rx = x + lw/(lw+rw);
    V L = dfs(lx,lbit);
    V R = dfs(rx,rbit);

    for(P l:L)
      for(P r:R) res.push_back(Merge(l,r));
  }
  
  return res;
}


signed main(){
  int q;
  cin>>q;
  while(q--){
    double len;
    cin>>len;
    cin>>n;
    for(int i=0;i<n;i++) cin>>w[i];

    V v = dfs(0,(1<<n)-1);
    double ans = -1;
    for(P p:v)
      if(p.second-p.first<len)ans = max(ans,p.second - p.first);
    
    if(ans<0) printf("-1\n");
    else printf("%.10Lf\n",ans);
  }
  return 0;
}

Measured memory_bytes: 5068
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll k,ans=0;
int32_t main(){
CODE_START;
cin>>k;
for(ll i=1;i<=k;i++)
for(ll j=1;j<=k;j++)
    for(ll c=1;c<=k;c++)
    ans=ans+__gcd(__gcd(i,j),c);
cout<<ans<<endl;
}



Measured memory_bytes: 3668
#if !defined(ONLINE_JUDGE)
    #include "prettyprint.hpp" 
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define d(...) 1729
    #define cer(x) 13
#endif
const bool testcase=0;
typedef long long int ll;
#define INF LONG_MAX
#define MINF LONG_MIN 
#define MAXR 111111
const ll mod1 = 1000000007;
const ll mod2 = 998244353;



//loop 
#define loop(i,L,R) for (int i = L; i < R; i++) //next four are for "for loops"
#define loope(i,L,R) for (int i = L; i <= R; i++)
#define rloop(i,L,R) for (int i = L; i > R; i--)
#define rloope(i,L,R) for (int i = L; i >= R; i--)
#define nl cout<<'\n'



//misc
#define sz(x) ((int)((x).size()))
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL) 
#define checkbit(n,b) ( (n >> b) & 1)
#define test int _T_=1;if(testcase){cin>>_T_;}while(_T_--)



//vector
#define lastEle(vec) vec[vec.size()-1]
#define all(ve) ve.begin(),ve.end()
#define rall(x) x.rbegin(),x.rend()
#define fi first
#define se second



template<typename T>inline T mmod(T a,T b,T mod){return ((a%mod)*(b%mod))%mod;}
template<typename T>inline T smod(T a,T b,T mod){return ((a%mod)+(b%mod))%mod;}
template<typename T>bool isPrime(T n){for(T i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;}
template<typename TAIL>inline void inp(TAIL& T){cin>>T;}
template<typename HEAD,typename... TAIL>inline void inp(HEAD &H,TAIL&... T){cin>>H;inp(T...);}
template<typename T>inline bool in_range(T a,T l,T r){return (a>=l&&a<=r);}
template<typename T,typename U>inline istream& operator >>(istream& in,pair<T,U> &a){in>>a.fi>>a.se;return in;}
template<typename T>inline istream& operator >>(istream& in,vector<T> &a){for(auto &x : a)in>>x;return in;}

ll lcm(ll a,ll b){return (max(a,b)/__gcd(a,b))*min(a,b);} 

// MAIN
void solve();
int main(){
    std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
    start = std::chrono::high_resolution_clock::now();
    fast;
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
        // for debug in error.txt
        freopen("error.txt", "w", stderr);
    #endif
    test {
        solve();
    }
    end = std::chrono::high_resolution_clock::now();
    ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cerr << "\nElapsed Time: " << elapsed_time << "ms\n";
    return 0;
}


// SOLVE 

void solve() {
    ll n, k;
    cin >> n >> k;
    std::vector<ll> v(n);
    cin >> v;
    auto f = [&](ll len){
        ll cnt = 0;
        for(auto it: v) {
            ll x = (it + len - 1)/len;
            cnt = cnt + (x-1);
        }
        return cnt;
    };
    ll l = 0, r = 1e9;   
    while((l+1) < r) {
        ll mid = (l+r)/2;
        ll tmp = f(mid);
        if(tmp <= k) {
            r = mid;
        }else{
            l = mid;
        }
    }
    cout << r << '\n';
}



Measured memory_bytes: 4764
/*
  AtCoder Beginner Contest 104
  C - All Green
*/

#include<iostream>
#include<limits>
using namespace std;

int D, G;
int p[10], c[10];

int main() {
  scanf("%d%d", &D, &G);
  G /= 100;

  for (int i = 0; i < D; ++i) {
    scanf("%d%d", &p[i], &c[i]);
    c[i] /= 100;
  }

  int ans = numeric_limits<int>::max();
  for (int i = 0; i < (1 << D); ++i) {
    // i: 使いきったか否かを表すビット
    int sum = 0;
    int cnt = 0;

    for (int j = 0; j < D; ++j) {
      if ((i >> j) & 1) {
        sum += p[j] * (j + 1) + c[j];
        cnt += p[j];
      }
    }

    for (int j = D - 1; j >= 0; --j) {
      if (sum >= G) break;
      if ((i >> j) & 1) continue;
      
      int buf = min((G - sum + j) / (j + 1), p[j]);
      cnt += buf;
      sum += (j + 1) * buf;
      if (buf == p[j]) sum += c[j];
    }

    if (G <= sum) ans = min(ans, cnt);
  }

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void){
  int n;
  cin >> n;
  
  vector<long long>a(n,0);
  vector<long long>b(n,0);
  
  for(int i=0;i<n;i++){
    cin >> a[i];
    cin >> b[i];
  }
  
  long long ans = 0;
  
  for(int i=n-1;i>=0;i--){
    a[i] += ans;
    if(a[i] % b[i] == 0) continue;
    else
      ans += b[i] - a[i] % b[i];
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
typedef long long ll;
#define repp(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
long long modpow(long long a,long long n,long long p)
{
    if(n==1)
    {
        return a%p;
    }
    if(n%2==1)
    {
        return a*modpow(a,n-1,p)%p;
    }
    long long t = modpow(a,n/2,p);
    return t*t%p;
}
int main()
{
    int n,k;
    cin>>n>>k;
    vector <char> a(n);
    rep(i,n)
    {
        cin>>a[i];
    }
    a[k-1]=a[k-1]+32;

    rep(i,n)
    {
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "stdio.h"

int main()
{

  int a[4][13],n,b,i,j;
  char m;
  for (i = 0; i < 4; i++)
  {

      for (j = 0; j < 13; j++)
      {
        a[i][j]=0;
      }

  }

  scanf("%d\n",&b );

 for ( i = 0; i < b; i++)
 {
 scanf("%c %d\n",&m,&n );

 switch (m)
 {
   case 'S':
      a[0][n-1]=1;
   break;


   case 'H':
    a[1][n-1]=1;
   break;


   case 'C':
    a[2][n-1]=1;
   break;


   case 'D':
    a[3][n-1]=1;
   break;

 }

 }

 for (i = 0; i < 4; i++)
 {

     for (j = 0; j < 13; j++)
     {
       if (a[i][j]==0)
       {

         switch (i)
         {
           case 0:
            printf("S %d\n",j+1 );
            break;

           case 1:
            printf("H %d\n",j+1 );
            break;

           case 2:
            printf("C %d\n",j +1);
            break;

           case 3:
            printf("D %d\n",j +1);
            break;

         }











       }

     }

 }





  return 0;
}



Measured memory_bytes: 2032
#include <stdio.h>

struct _log {
	int i;
	long t;
};
typedef struct _log log;

int main() {
	while(1) {
		int n, j, k;
		int count = 0;
		long t;
		scanf("%d",&n);
		if (n == 0) break;
		for (j = 0; j < n; j++) {
			log l[4000];
			int i, p, q;
			int idx = -1;

			scanf("%d %d %d",&i, &p, &q);
			t = (long)p * (long)q;
			for (k = 0; k < j; k++) {
				if (l[k].i == i) {
					idx = k;
					break;
				}
			}
			if (idx >= 0) {
				if (l[idx].t < 1000000) {
					l[idx].t += t;
					if (l[idx].t >= 1000000) {
						printf("%d\n", i);
						count++;
					}
				}
			} else {
				l[j].i = i;
				l[j].t = t;
				if (t >= 1000000) {
					printf("%d\n", i);
					count++;
				}
			}
		}
		if (count == 0) {
			printf("NA\n");
		}
	}
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }

  ll sum = 0;
  int max = a.at(0);
  for (int i = 1; i < n; i++) {
    int current = a.at(i);

    if (current < max) {
      sum += max - current;
    } else if (current > max) {
      max = current;
    }
  }

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

Measured memory_bytes: 4048
N = int(input())
A = [int(i) for i in input().split()]

ans = 0
while any(a > N - 1 for a in A):
    S = sum(a // N for a in A)
    A = [a + (S - a // N) - (a // N) * N for a in A]
    ans += S

print(ans)

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

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 100005;

int a[N], cnt[N];

int n, q;

int main() {

	FAST;

	cin >> n;
	intt ans = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		cnt[a[i]] ++;
		ans += a[i];
	}
	cin >> q;
	while (q -- ) {
		int x, y;
		cin >> x >> y;
		ans += (y - x) * cnt[x];
		cnt[y] += cnt[x];
		cnt[x] = 0;
		cout << ans << '\n';
	}
	return 0;
}

Measured memory_bytes: 4388
pd = input()
after_pd=""
for i in pd:
    if i=="?":
        after_pd += "D"
    else:
        after_pd += i
count = 0
# if after_pd[0]=="D":
#     count +=1
# else:
#     flg=1
# for i in range(1,len(after_pd)):
#     if after_pd[i-1]=="P" and after_pd[i]=="D":
#         count +=1
#     if after_pd[i]=="D":
#         count +=1
# print(count)
print(after_pd)

Measured memory_bytes: 9320