akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

signed main() {
	int n;
	cin >> n;
	cout << (n / 2) + n % 2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector> 
#include <algorithm> 
using namespace std;
bool cmp(pair<int,int> i,pair<int,int> j){
    return i.first<j.first;
}
int main() {
    int n,w;
    cin>>n>>w;
    vector<pair<long long int,long long int>> v(n+1);
    for(int i=1;i<n+1;++i) cin>>v[i].first>>v[i].second;
    long long int dp[w+1][n+1];
    for(int i=0;i<w+1;++i) for(int j=0;j<n+1;++j) dp[i][j]=0;
    for(int i=1;i<w+1;++i){
        for(int j=1;j<n+1;++j){
            dp[i][j] = dp[i][j-1];
            if(v[j].first<=i) dp[i][j]=max(dp[i-v[j].first][j-1]+v[j].second,dp[i][j]);
        }
    }
    cout<<dp[w][n];
}


Measured memory_bytes: 82060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, K, A[101010];
int dist[101010];
vector<int> ch[101010];

int ans;

int solve(int p)
{
	if (dist[p] != -1) return dist[p];
	if (p == 0) return dist[p] = 0;
	return dist[p] = solve(A[p]) + 1;
}

int visit(int p)
{
	int t = 0;
	for (int q : ch[p]) t = max(t, visit(q));
	++t;

	if (p != 0 && A[p] != 0 && (K == 1 || t == K))
	{
		++ans;
		t = 0;
	}
	return t;
}

int main()
{
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; ++i) {
		scanf("%d", A + i);
		--A[i];
	}

	ans = 0;

	if (A[0] != 0) {
		++ans;
		A[0] = 0;
	}

	for (int i = 1; i < N; ++i) ch[A[i]].push_back(i);

	for (int i = 0; i < N; ++i) dist[i] = -1;
	for (int i = 0; i < N; ++i) solve(i);

	visit(0);

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


Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
const int inf=1e9+7;

int main(){
    int n;cin>>n;
    set<string> s;
    rep(i,n){
        string t;cin>>t;
        s.insert(t);
    }
    cout<<s.size()<<endl;
}

Measured memory_bytes: 19220
fun main(args: Array<String>) {
    val (H, W) = listOfInt()
    val A = Array(H) { listOfInt() }.flatMap { it }.toIntArray()
    fun rc(v: Int) = "${(v / W) + 1} ${(v % W) + 1}" //row-col
    val wh = W * H
    val wh0 = W * (H - 1)
    var N = 0
    val ans = StringBuilder()
    for (src in 0 until wh - 1) {
        if (A[src] % 2 != 0) {
            val dst =  if (src < wh0) src + W else src + 1
            A[src] -= 1
            A[dst] += 1
            ans.append("\n${rc(src)} ${rc(dst)}")
            N += 1
        }
    }
    println("${N}${ans.toString()}")
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }


Measured memory_bytes: 84052
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<P, int> PP;
int t[100];
int v[100];
int main() {
	int N;
	cin >> N;
	vector<PP> vec;
	for (int i = 0; i < N; i++) cin >> t[i];
	for (int i = 0; i < N; i++) cin >> v[i];
	int T = 0;
	vec.push_back(PP(P(0, 0), 0));
	for (int i = 0; i < N; i++) {
		vec.push_back(PP(P(T, T + t[i]), v[i]));
		T += t[i];
	}
	vec.push_back(PP(P(T, T), 0));
	double p_max_v = 0;
	double ans = 0;
	for (int i = 1; i <= 2 * T; i++) {
		double max_v = 1e9;
		double t = i / 2.0;
		for (int j = 0; j < vec.size(); j++) {
			if (t <= vec[j].first.first) max_v = min(max_v, vec[j].second + (vec[j].first.first - t));
			else if (t >= vec[j].first.second) max_v = min(max_v, vec[j].second + (t - vec[j].first.second));
			else max_v = min(max_v, (double)vec[j].second);
		}
		ans += 0.25*(max_v + p_max_v);
		p_max_v = max_v;
	}
	printf("%.15lf\n", ans);
}

Measured memory_bytes: 256
def bi(s, a, l, r):
    if l > r:
        return 0
    
    m = (l + r) // 2
    if s[m] == a:
        return 1
    elif s[m] > a:
        return bi(s, a, l, m-1)
    elif s[m] < a:
        return bi(s, a, m+1, r)
    
n1 = int(input())
s = list(map(int, input().split()))
n2 = int(input())
t = list(map(int, input().split()))

s.sort()

ans = 0
for ti in t:
    ans += bi(s, ti, 0, n1)
print(ans)


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

int main()
{
    int M;
    cin >> M;
    ll digitsLength = 0;
    ll sum = 0;
    for (int i = 0; i < M; i++)
    {
        ll d, c;
        cin >> d >> c;
        digitsLength += c;
        sum += d * c;
    }
    cout << (digitsLength - 1) + (sum - 1) / 9 << endl;
    return 0;
}

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

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pr;

const ll MAX = 2e18;
const ld inf = 2e18;
const int N = 3e6 + 10;
const int maxn = 200020;
const ll mod = 1e9 + 7;

inline ll power(ll x,ll y){
	y = ((y % (mod - 1)) + (mod - 1)) % (mod - 1);
//	if ( y < 0 ) return power(power(x,-y),mod - 2);
	ll res = 1;
	while ( y ){
		if ( y & 1 ) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

int len,s[maxn],fail[maxn];
int trans[maxn][10];
void getfail(){
	fail[1] = 0;
	int p = 0;
	rep(i,2,len){
		while ( p && s[i] != s[p + 1] ) p = fail[p];
		if ( s[i] == s[p + 1] ) fail[i] = ++p;
		else fail[i] = 0;
	}
}
struct node{
	ll len,cnt[50];
	node() { len = 0 , memset(cnt,0,sizeof(cnt)); }
	node operator + (node a){
		node cur;
		rep(i,0,25) cur.cnt[i] = a.cnt[i] + cnt[i];
		cur.len = len + a.len;
		if ( cur.len > MAX ) cur.len = MAX;
		return cur;
	}
}g[100];
char ch[maxn];
ll l,r;

void init(){
	len /= 2;
	rep(i,1,len) s[i] = ch[i] - 'a';
	getfail();
	g[0].len = len;
	rep(i,1,len) g[0].cnt[s[i]]++;
	g[1] = g[0];
	g[1].len += len - fail[len];
	rep(i,1,len - fail[len]) g[1].cnt[s[i]]++;
	rep(i,2,100){
		g[i] = g[i - 1] + g[i - 2];	
	}
}
node calc(ll n){
	node res;
	if ( !n ) return res;
	repd(i,100,0){
		if ( n >= g[i].len ) res = res + g[i] , n -= g[i].len;
	}
	rep(i,1,n) res.cnt[s[i]]++;
	return res;
}
int main(){
	scanf("%s",ch + 1);
	cin>>l>>r;
	len = strlen(ch + 1);
	init();
	node ans1 = calc(r),ans2 = calc(l - 1);
	rep(i,0,25) cout<<ans1.cnt[i] - ans2.cnt[i]<<" ";
	cout<<endl;
}


Measured memory_bytes: 3200
import java.util.*;
public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int N  =sc.nextInt();
        int [] List = new int[N];
        for(int i=0;i<N;i++) List[i]=sc.nextInt();
        Arrays.sort(List);
        int num=0;
        for(int i=0;i<N-2;i++){
            for(int j=i+1;j<N-1;j++) {
                for(int k=j+1;k<N;k++){
                    if(List[i]+List[j]>List[k])num++;
                    else break;
                }
            }
        }
        System.out.println(num);
    }
}

Measured memory_bytes: 26800
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;

vector<int> G[200000];
int color[200000]={};

bool dfs(int v,int c){
  color[v]=c;
  for(int i=0;i<G[v].size();++i){
    if(color[G[v][i]]==c) return false;
    if(color[G[v][i]]==0 && !dfs(G[v][i],-c)) return false;
  }
  return true;
}

int main(){
  long long N,M,A,B,ans,tmp;
  cin>>N>>M;
  for(int i=0;i<M;++i){
    cin>>A>>B;
    G[A-1].push_back(B-1);
    G[B-1].push_back(A-1);
  }
  bool divide=dfs(0,1);
  ans=0;
  tmp=0;
  //2部グラフの場合
  if(divide){
    for(int i=0;i<N;++i){
      if(color[i]==1){
        tmp+=1;
      }
    }
    ans=tmp*(N-tmp)-M;
  }
  else{
    ans=N*(N-1)/2-M;
  }
  cout<<ans<<"\n";
return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  string S;
  cin >> S;
  int ans = 0;
  rep(i, S.size())
  {
    int tmp = 0;
    for (int j = i; j < S.size(); j++)
    {
      if ((S.at(j) == 'A') || (S.at(j) == 'C') || (S.at(j) == 'G') || (S.at(j) == 'T'))
      {
        tmp++;
       // cout << S.at(j) << endl;
      }
      else
      {
        break;
      }
    }
    ans = max(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define  maxn 200005  
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
ll fac[maxn];
ll qpow(ll a,ll n)
{
    ll ret =1;
    while(n)
    {
        if(n&1) ret=ret*a%MOD;
          a=a*a%MOD;
          n>>=1;
    }
    return ret;
}
void init(){ 
    fac[0]=1;
    for(int i=1;i<maxn;i++)
    {
        fac[i]=fac[i-1]*i%MOD;
    }
}
ll C(ll x, ll y){
    return fac[x]*qpow(fac[y]*fac[x-y]%MOD,MOD-2)%MOD;
}
//ll inv(ll a)
//{
//	return a == 1l ? 1l : (ll)(MOD - MOD / a) * inv(MOD % a) % MOD;
//}
//ll C(ll n, ll m)
//{
//	if (m < 0)return 0;
//	if (n < m)return 0;
//	if (m > n - m)m = n - m;
//	ll up = 1, down = 1;
//	for (ll i = 0; i < m; i++)
//	{
//		up = up * (n - i) % MOD;
//		down = down * (i + 1) % MOD;
//	}
//	return up * inv(down) % MOD;
//}
int main(){
	init();
	ll n,k;
	cin>>n>>k;
	ll sum = 0;
	for(ll i=0;i<=min(n,k);i++){
		sum+=(C(n,i)*C(n-1,i)%MOD);
		sum%=MOD;
	}
	cout<<(sum+MOD)%MOD<<endl;
}

Measured memory_bytes: 1792
N = int(input())
ARR = list(map(int,input().split()))

def calculate(n, arr):
    arr = sorted(arr, reverse=True)
    ans = 0

    ans += arr[0]
    endIndex = 1
    for i in range(1, n - 1):

        if endIndex < (n-1):
            endIndex += 1
            ans += arr[i]
        else:
            break

        if endIndex < (n-1):
            endIndex += 1
            ans += arr[i]
        else:
            break

    print(ans)


calculate(N, ARR)



Measured memory_bytes: 31500
/* kadai2_2
   reo012 */

#include <stdio.h>

int main(void){
  int n, a;
  // 二つの整数(一列のマス数、白マス数)n,aを受け取り
  scanf("%d", &n);
  scanf("%d", &a);
  // 黒く塗るマス数を計算し、出力
  printf("%d\n", n*n-a);
  
  return 0;
}

Measured memory_bytes: 128
N = int(input())
rem = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
for i in range(1,N+1):
    sti = str(i)
    rem[int(sti[0])][int(sti[-1])] += 1
count = 0
for k in range(10):
    for j in range(10):
        count += rem[k][j]*rem[j][k]
        
print(count)

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

using namespace std;

long long int a[1000000];

int main(){
	int n;
	cin>>n;
	a[0]=2;
	a[1]=1;
	for(int i=2;i<=n;i++)
	a[i]=a[i-1]+a[i-2];
	cout<<a[n];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <numeric>
#include <ctype.h>
#include <cstdlib>
#include <string.h>
#include <cmath>
#include <cstdio>





using namespace std;

int main()
{
	int w, n, a, b;
	char comma;
	vector<int> vec;

	cin >> w;
	cin >> n;

	for (int i = 1; i <= w; i++)
	{
		vec.push_back(i);
	}

	for (int i = 0; i < n; i++)
	{
		cin >> a >> comma >> b;
		
		swap(vec[a - 1], vec[b - 1]);
	}

	for (auto a : vec)
	{
		cout << a << endl;
	}


	return 0;
}

Measured memory_bytes: 3128
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
/*----------------------------------------------------------------------------------*/


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

    map<ll, ll> m;
    auto prime_factrize = [&](ll a) -> void {
        for (ll i = 2; i*i <= a; i++) {
            if (a%i != 0) continue;
            ll cnt = 0;
            while (a%i == 0) {
                cnt++;
                a /= i;
            }
            m[i] += cnt;
        }
        if (a > 1) m[a]++;
    };

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

    auto rec = [&](auto &&rec, auto a, int b) -> int {
        if (a == m.end()) {
            if (b == 1) return 1;
            else return 0;
        }

        int res = 0;
        for (int i = 1; i <= a->second+1; i++) {
            if (b%i!=0) continue;
            a++;
            res += rec(rec, a, b/i);
            a--;
        }
        return res;
    };
    
    cout << rec(rec, m.begin(), 75) << endl;
    return 0;
}


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

int main(){
  int n; cin >>n;
  map<int, int> mp;
  rep(i,n){
    int a; cin >>a;
    mp[a]++;
  }
  int ans = 0;
  for(auto p : mp){
    if(p.second %2 != 0) ans++;
  }
  cout << ans << endl;
  return 0; 
}


Measured memory_bytes: 8280
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x) cout << #x << " = " << (x) << endl;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define P pair<int, int>
#define V vector<int>
#define M map<int, int>

void solve()
{
}
int N, W[200], S[200];
signed main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N;
    FOR(i, 1, N + 1)
    {
        cin >> W[i];
        S[i] += S[i - 1] + W[i];
    }
    int ans = INF;
    FOR(i, 1, N)
    {
        ans = min(ans, abs(S[N] - 2 * S[i]));
    }
    cout << ans << endl;
    solve();
    return 0;
}


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

int main()
{
	int N, a, b, c;
	cin >> N;
	while (N--) {
		cin >> a >> b >> c;
		if (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int N, A, B;
    cin >> N >> A >> B;

    int cnt[3] = {0, 0, 0};
    for (int i = 0; i < N; ++i) {
        int p;
        cin >> p;
        if (p <= A) {
            ++cnt[0];
        } else if (p <= B) {
            ++cnt[1];
        } else {
            ++cnt[2];
        }
    }
    cout << min({cnt[0], cnt[1], cnt[2]}) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define INF 1<<31-1
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
#define NUM 100001

void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int GCD(int a,int b){int c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
int LCM(int a,int b){return a*b/GCD(a,b);}
int POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return (int)ans;}
int icmp(const void* a,const void* b){return *(int*)a-*(int*)b;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int scmp(const void* a,const void* b){return strcmp(*(char**)a,*(char**)b);}
LL fac[NUM],finv[NUM],inv[NUM];
void comi(){int i;fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fac[i]=fac[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
int com(int n,int k){if(n<k||n<0||k<0)return 0;return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;}

typedef struct{int s,e,c;}Edge;
int par[NUM];
int UF(){for(int i=0;i<NUM;i++)par[i]=-1;}
int Root(int x){if(par[x]<0)return x;else return par[x]=Root(par[x]);}
int Size(int x){return -par[Root(x)];}
bool Same(int x,int y){return Root(x)==Root(y);}
void Unite(int x,int y){x=Root(x);y=Root(y);if(x!=y){if(Size(x)<Size(y))swap(&x,&y);par[x]+=par[y];par[y]=x;}}
int cmpc(const void* a,const void* b){return ((Edge*)a)->c-((Edge*)b)->c;}
int Kruscal(Edge* edge,int n){int i,ans=0;Edge e;qsort(edge,n,sizeof(Edge),cmpc);UF();FOR(i,0,n){e=edge[i];if(!Same(e.s,e.e)){Unite(e.s,e.e);ans+=e.c;}}return ans;}


int main(){
  int A,B,K,i,j,a=0,g,ans=0;
  scanf("%d%d%d",&A,&B,&K);
	g=GCD(A,B);
	FOR(i,1,g+1){
		if(g%i==0)a++;
		if(a==K){
			ans=g/i;
			break;
		}
	}

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


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    int max=-50000000,min=5000000;
    long long sum=0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(max<a[i])max=a[i];
        if(min>a[i])min=a[i];
        sum+=a[i];
        }
        cout << min << " " << max << " " << sum << endl;

}



Measured memory_bytes: 3124
n=int(raw_input())
t=map(int,raw_input().split())
m=int(raw_input())
pt=[map(int,raw_input().split()) for _ in xrange(m)]
ans=[0]*m
for i in xrange(m):
    tmp=list(t)
    tmp[pt[i][0]-1]=pt[i][1]
    for j in xrange(n):
        ans[i]+=tmp[j]
for i in xrange(m):
    print(ans[i])

Measured memory_bytes: 2568
use std::io;
use std::str::FromStr;

fn input_int_tuple() -> (i32, i32) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<i32> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1])
}

fn main() {
    let (n, y) = input_int_tuple();
    for i in 0..(n+1) {
        for j in 0..(n+1-i) {
            if 10000 * i + 5000 * j + 1000 * (n - i - j) == y {
                println!("{} {} {}", i, j, (n - i - j));
                return;
            }
        }
    }
    println!("-1 -1 -1");
}


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

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];

    int num = 0;
    for (int i = 1; i + 1 < n; ++i) {
        if ((p[i - 1] < p[i] && p[i] < p[i + 1]) ||
            (p[i + 1] < p[i] && p[i] < p[i - 1])) ++num;
    }

    cout << num << endl;

    return 0;
}


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

int main(){
  int N, L;
  cin >> N >> L;
  int taste=0;
  int Min=100000;
  int k=-1;
  for(int i=0; i<N; i++){
    taste+=L+i;
    if(abs(L+i)<Min){
      k=i;
      Min=abs(L+i);
    }
  }
  cout << taste-(L+k) << endl;
}

Measured memory_bytes: 256
#include<functional>
#include<algorithm>
#include<iostream>
#include<utility>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define pf push_front
#define int long long
using namespace std;
const int INF=1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


signed main(){
  int n;
  cin>>n;
  if(n>=64)cout<<64<<endl;
  else if(n<64&&n>=32)cout<<32<<endl;
  else if(n<32&&n>=16)cout<<16<<endl;
  else if(n<16&&n>=8)cout<<8<<endl;
  else if(n<8&&n>=4)cout<<4<<endl;
  else if(n<4&&n>=2)cout<<2<<endl;
  else cout<<1<<endl;

  return 0;
}




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

int main() {
  int n;
  string str; 
    
  std::cin >> n;
  std::cin >> str;
  
  if (n % 2 == 1 ){
    std::cout << "No";
  } else if (str.substr(0,n/2) == str.substr(n/2,n/2)){
    std::cout << "Yes";
  } else {
    std::cout << "No";
  }
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/









ll N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    if (K == 0) {
        ll ans = N * N;
        cout << ans << endl;
        return;
    }

    ll ans = 0;
    rep(b, K + 1, N + 1) {
        // K <= x % b

        // [K, b-1]
        // [K+b, 2b-1]

        // nb-1=N
        // nb = N + 1
        // n = (N + 1) / b

        ll n = (N + 1) / b;
        ll d = 0;
        
        d += 1LL * (b - K) * n;
        
        ll L = K + b * n;
        ll R = N;
        if (L <= R) d += R - L + 1;

        //printf("%d -> %lld\n", b, d);
        ans += d;
    }

    cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const ll inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n, m; cin >> n >> m;
    ll Q; cin >> Q;
    vector<ll> a(Q); cin >> a; REP(i, Q) a[i]--;
    vector<ll> seq = [&]() {
        set<ll> used;
        vector<ll> res;
        RREP(i, Q) {
            if (used.count(a[i]) == 0) {
                res.pb(a[i]);
                used.insert(a[i]);
            }
        }
        REP(i, m) if ( used.count(i) == 0 ) res.pb(i);
        return res;
    }();

    vector<ll> rseq(m); REP(i, m) rseq[seq[i]] = i;
    vector<ll> cnt(m+1, 0); cnt[0] = n;
    // int skipped = 0;
    RREP(i, Q) {
        ll pos = rseq[a[i]];
        if (cnt[pos] > 0) --cnt[pos], ++cnt[pos+1];
        // else ++skipped;
    }
    ll def = 1;
    RREP(i, m-1) {
        if (seq[i+1] > seq[i]) ++def;
        else break;
    }
    bool ans = true;
    // if (skipped > 0 && cnt[m] == 0 && cnt[m-1] == 0) {
    //     ans = false;
    // }
    // cout << seq << endl;
    // cout << cnt << endl;
    // cout << def << endl;
    REP(i, m) {
        if (cnt[i] > 0 && i+def < m) ans = false;
    }
    if (ans) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 6516
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int,int>;
using Graph = vector<vector<int>>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); ++i)
 
constexpr double PI = acos(-1);
//既に訪れているか(中身は{0,1}しか入れないのでbool的な扱い)
int alre[1000000];
int main() {
    ll n,k;
    cin >> n >> k;
    
    vector<int> g(n+1,0);
    vector<int> log;
    
    int a;
    int nowPos;
    
    rep(i,n) {
        cin >> a;
        g.at(i+1) = a;
    }
    //町1からスタート
    nowPos = 1;
    log.emplace_back(1);
    
    ll s,flag,loop;
    
    s = flag = loop = 0;
    //1～kまで繰り返す
    rep(i,k+1) {
        int ii = i + 1;
        //次の町へテレポート
        nowPos = g.at(nowPos);
        //logを残す
        log.emplace_back(nowPos);
        //訪れるのが2回目だったら最初に訪れた位置との差分でk-sをmodする
        //if文では0でfalse、0以外でtrueとなる(※言語差あり)
        if(flag == 0 && alre[nowPos]) {
            s = alre[nowPos];
            loop=(k-s)%(ii-s);
            flag=true;
            break;
        }
        alre[nowPos]=ii;
    }
    if(!flag) cout << log.at(k) << "\n";
    else{
        nowPos = log.at(s+loop);
        cout << nowPos << "\n";
    }
    return 0;
}

Measured memory_bytes: 5748
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b=0,c=0,d;
  cin>>a;
  for(int i=1;i<=a;i++){
    d=i;
    c=0;
    while(true){
     	if(d<=0) break;
      	d=d/10;
      	c++;
    }
    if(c%2==1) b++;
  }
  cout<<b<<"\n";
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;


int main()
{

    int n; cin>>n;
    int F[50];
    F[0]=F[1]=1;
    for(int i=2;i<=n;i++) F[i]=F[i-1]+F[i-2];
    cout<< F[n] <<endl;
    return 0;
}



Measured memory_bytes: 3100
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#include <queue>
#include <set>
#include <list>
#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;
const ll INF=1e9+7;

int main(void) {
	int a, b;
	cin >> a >> b;
	if (a <= 9 && b <= 9)cout << a * b << endl;
	else cout << "-1" << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  
  if(d2 == 1){
    cout << 1 << endl;
  }else{
    cout << 0 << endl;
  }



  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n,nex[100005],dp2[100005];
long long s[100005],ab[2];
map<vector<int>,int> dp;
int solve(vector<int> v);
int solve2(int i)
{
	if (i==n+1)
	return 0;
	if (dp2[i]!=-1)
	return dp2[i];
	return dp2[i]=(solve2(i+1)+solve({0,i}))%mod;
}
int solve(vector<int> v)
{
	int idx=max(v[0],v[1])+1;
	if (idx==n+1)
	return 1;
	if (dp.count(v))
	return dp[v];
	if (s[idx]-s[idx-1]>=ab[1])
	return dp[v]=(solve({idx,0})+solve({0,idx}))%mod;
	if (s[idx]-s[idx-1]<ab[0])
	{
		bool b=(v[0]==idx-1);
		if (s[idx]-s[v[b]]>=ab[b])
		{
			auto nv=v;
			nv[b]=idx;
			return dp[v]=solve(nv);
		}
		return dp[v]=0;
	}
	vector<int> nv=v;
	nv[0]=nex[idx];
	int ans=solve(nv),st=lower_bound(s,s+n+1,s[v[1]]+ab[1])-s;
	st=max(st,idx);
	if (st<=nex[idx])
	ans=(1LL*ans+solve2(st)-solve2(nex[idx]+1)+mod)%mod;
	return dp[v]=ans;
}
int main()
{
	scanf("%d%lld%lld",&n,&ab[0],&ab[1]);
	if (ab[0]>ab[1])
	swap(ab[0],ab[1]);
	for (int i=1;i<=n;i++)
	scanf("%lld",&s[i]);
	nex[n]=n;
	for (int i=n-1;i>0;i--)
	{
		if (s[i+1]-s[i]>=ab[0] && s[i+1]-s[i]<ab[1])
		nex[i]=nex[i+1];
		else
		nex[i]=i;
	}
	s[0]=-1e18;
	s[n+1]=1e18;
	memset(dp2,-1,sizeof(dp2));
	printf("%d",(solve({1,0})+solve({0,1}))%mod);
}

Measured memory_bytes: 55224
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int mod=1000'000'007;
    vector<int> a(n);
    long long sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum=(sum+a[i])%mod;
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        sum-=a[i];
        if(sum<0)sum+=mod;
        ans=(ans+a[i]*sum)%mod;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4060
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> p(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        p[i] = make_pair(b, a);  //[a. b)に取り除くべき橋
    }

    sort(p.begin(), p.end());

    int ans = 0;
    for (int i = 0; i < m;) {
        auto now = p[i++];
        while (i < m && p[i].second < now.first) { i++; }
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1152
#[allow(unused_imports)] use proconio::{input, marker::{Bytes, Chars, Usize1, Isize1}};
#[allow(unused_imports)] use std::cmp::{min, max};
#[allow(unused_imports)] use superslice::Ext as _;

#[proconio::fastout]
fn main() {
	input! {
		k: usize,
	}

	for _i in 0..k {
		print!("ACL");
	}
	println!("");
}


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

int main(){
	int N;
  	cin >> N;
  	int p[N];
  	for(int i = 0 ; i < N ; i++ )cin >> p[i];
  	
  	sort(p,p+N,greater<int>());
  	
  	int sum = 0;
  	for(int i = 0 ; i < N ; i++ ){
    	if(i == 0) sum += p[i]/2;
      	else sum += p[i];
    }
  	
  	cout << sum << endl;




}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <chrono>
#include <sstream>
#include <iomanip>
using namespace std;
#define MOD 1000000007
#define PI 3.14159265358979
#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v) for (auto i : v)
#define D(x) cout << x << endl
#define d(x) cout << x
#define all(x) (x).begin(), (x).end()
#define pub(x) push_back(x)
#define pob() pop_back()
#define puf(x) push_front(x)
#define pof() pop_front()
#define mp(x, y) make_pair((x), (y))
#define fi first
#define se second
#define setp(x) setprecision(x)
#define mset(m, v) memset(m, v, sizeof(m))
static const int INF = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }

//static const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//#define int ll

int main() { 
        double x, y;
        char s[20], t[20], u[20];

        cin >> s >> t >> u;

        char a, b, c;
        a = toupper(s[0]);
        b = toupper(t[0]);
        c = toupper(u[0]);

        D(a << b << c);

        return 0;
}



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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> m(N);
  for (int i = 0; i < N; i++) {
    cin >> m.at(i);
  }
  
  int m_sum = 0;
  int m_min = 1000;
  for (int i = 0; i < N; i++) {
    m_sum += m.at(i);
    m_min = min(m_min, m.at(i));
  }
  
  cout << N + (X - m_sum)/m_min << endl;
  
}


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

const int Max = 105;
int G[Max][Max], color[Max], d[Max];
int n;

void bfs(int u)
{
    memset(color, -1, sizeof(color));
    memset(d, -1, sizeof(d));
    queue<int> Q;
    int v;
    Q.push(u);
    d[u] = 0;
    color[u] = 0;
    while(!Q.empty())
    {
        u = Q.front(); Q.pop();
        for(int i=0; i<n; i++)
        {
            if(G[u][i] && color[i]==-1)
            {
                color[i] = 0;
                Q.push(i);
                d[i] = d[u]+1;
            }
        }
    }
    for(int i=0; i<n; i++)
    {
        cout << i+1 << " " << d[i] << endl;
    }
}

int main()
{
    int u, k, v;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> u >> k;
        for(int j=0; j<k; j++)
        {
            cin >> v;
            G[u-1][v-1] = 1;
        }
    }
    bfs(0);
    return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
void ABC130(void);
void ABC131(void);
void ABC132(void);
void ABC133(void);
void ABC134(void);
void ABC135(void);
void ABC136(void);
void ABC137(void);
void ABC138(void);
void ABC139(void);

int main(void){
    ABC134();
}

void ABC134(){
    int n,d;
    cin>>n>>d;
    if(n%(2*d+1)==0)cout<<n/(2*d+1)<<endl;
    else cout<<n/(2*d+1)+1<<endl;
}

Measured memory_bytes: 384
n,m,c=map(int,input().split())
b=list(map(int,input().split()))
count=0
for i in range(n):
    a=list(map(int,input().split()))
    p=c
    for j in range(m):
        p+=a[j]*b[j]
    if p>0:
        count+=1
print(count)

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

using namespace std;

int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int s=0;
	for(int i=0;i<k;i++){
		s+=a[i];
	}
	cout<<s<<endl;
}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mod1 1000000007
#define ff first
#define ss second
#define INF 1e9
#define INFLL 1e18
typedef long long int ll;
// #define intLL unsigned long long int//used when x<2^64-1 && x>0
#define int long long//used when x<2^63-1
int fact[200005];
int power(int a, int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
        {
            res*=a;
            res%=mod1;
        }
        a*=a;
        a%=mod1;
        b/=2;
    }
    return res;
}
int add(int a, int b)
{
    return (0LL+a+b)%mod1;
}
int sub(int a, int b)
{
    return add(a, mod1-b);
}
int mul(int a, int b)
{
    return (1LL*a*b)%mod1;
}
int inv(int x)
{
    return power(x, mod1-2);
}
int nCr(int n, int r)
{
    return mul(fact[n], inv(mul(fact[r], fact[n-r])));
}
int cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return (a.ff>b.ff);
}
int32_t main()
{

    IOS;
    int n, m, s;
    cin>>n>>m>>s;
    vector<pair<int, pair<int,int>>> gr[55];//{v, {cost, time}}
    for(int i=0;i<m;i++)
    {
        int u, v, a, b;
        cin>>u>>v>>a>>b;
        u--, v--;
        gr[u].pb({v, {a, b}});
        gr[v].pb({u, {a, b}});
    }
    int c[n+1], d[n+1];
    for(int i=0;i<n;i++)
        cin>>c[i]>>d[i];
    s=min(s, 2500LL);
    int dp[n+1][2501];
    for(int i=0;i<n;i++)
        for(int j=0;j<2501;j++)
            dp[i][j]=INFLL;
    dp[0][s]=0;
    for(int lol=0;lol<n+1;lol++)
    {
        for(int i=0;i<n;i++)
        {
            for(auto it: gr[i])
            {
                for(int j=0;j<=2500;j++)
                {
                    if(j-it.ss.ff>=0)
                    {
                        dp[i][j-it.ss.ff]=min(dp[i][j-it.ss.ff], dp[it.ff][j]+it.ss.ss);
                    }
                }
            }
            for(int j=0;j<=2500;j++)
            {
                if(j-c[i]>=0)
                    dp[i][j]=min(dp[i][j], dp[i][j-c[i]]+d[i]);
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        int ans=INFLL;
        for(int j=0;j<=2500;j++)
            ans=min(ans, dp[i][j]);
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 4560
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		br.readLine();
		
		String[] tmpArray = br.readLine().split(" ");
		int[] sticks = new int[tmpArray.length];
		for(int i = 0; i < tmpArray.length ; i++){
			sticks[i] = Integer.parseInt(tmpArray[i]);
		}
		
		System.out.println(makeRectangle(sticks));
	}
	
	static long makeRectangle(int[] sticks){
		Arrays.sort(sticks);
		int a = 0;
		int b = 0;
		int prev = -1;
		
		for(int i = sticks.length - 1; i >= 0 ; i-- ){
			if(prev == sticks[i]){
				if(a == 0){
					a = sticks[i];
					prev = -1;
					continue;
				}
				else {
					b = sticks[i];
					break;
				}
			}
			
			prev = sticks[i];
		}
		
		return (long)a*b;
	}

}


Measured memory_bytes: 37880
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
num = 1
ans = 0
for i in range(n):
    if a[i] != num:
        ans += 1
    else:
        num += 1

if num == 1:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 31440
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define fi first
#define se second
#define endl "\n"
#define all(v) v.begin(),v.end()
#define fastio ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0)
#define go_t int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; // order_of_key
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf = 0x3f3f3f3f3f3f3f3fll;//4x10e18
const int maxx = 3000000 , mod = 1000000007;
#define PI 3.14159265
int main()
{
    fastio;
    ll a,b,n;
    cin>>a>>b>>n;

    ll ans = ((a*min(n,b-1))/b);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 4*1001001001001001001;
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<int> d(n); REP(i,n) cin >> d[i];
    sort(d.begin(), d.end());

    int mid = n/2;
    int res = d[mid] - d[mid-1];

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



Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map> 
#include <map> 
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
using namespace std;
typedef long long LL;

int main(void) {
	LL a, b, c, i, j, k, n, ans, m;
	cin >> n >> a;
	if (n % 500 <= a) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

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

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

    int n;
    cin >> n;

    vector<int> a(n);
    int a_sum = 0;
    rep(i, n){
        cin >> a[i];
        a_sum += a[i];
    }
    
    int ave = a_sum / n;
    int res = 0;
    rep(i, n) {
        res += (ave - a[i]) * (ave - a[i]);
    }

    int ave1 = ave + 1;
    int res1 = 0;
    rep(i, n){
        res1 += (ave1 - a[i]) * (ave1 - a[i]);
    }

    cout << min(res, res1) << endl;

    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))

BC = []

for i in range(M):
    l, r = map(int, input().split())
    BC.append((r, l))


for a in A:
    BC.append((a, 1))

BC.sort()
BC.reverse()

count = 0
ans = 0


for bc in BC:
    if (bc[1] + count) <= N:
        count += bc[1]
        ans += bc[0] * bc[1]
    else:
        ans += max(0, bc[0] * (N - count))
        break

print(ans)


Measured memory_bytes: 79512
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;

ll k;
ll MOD(int a){
	if(a%k==0) return 0;
	else return a;
}
 
vector<pair<int, ll> > path[100005];
int par[100005];
int dep[100005];
ll cst[100005];
void dfs(int a){
	for(int i=0; i<path[a].size(); i++){
		int d=path[a][i].first;
		ll c=path[a][i].second;
		if(d!=par[a]){
			dep[d]=dep[a]+1;
			par[d]=a;
			cst[d]=c;
			dfs(d);
		}
	}
}
ll add[100005];
 
struct query{
	char t;
	ll a, b;
};
query qry[100005];
 
bool used[100005];
int cnt[100005];
int cntdfs(int a){
	cnt[a]=used[a];
	for(int i=0; i<path[a].size(); i++){
		int d=path[a][i].first;
		if(d!=par[a]) cnt[a]+=cntdfs(d);
	}
	return cnt[a];
}
int ming_par[100005];
ll ming_cst[100005];
int ming_bef[100005];
 
int main(){
	int n;
	cin >> n >> k;
	for(int i=0; i<n-1; i++){
		int a, b;
		ll c;
		cin >> a >> b >> c;
		path[a].push_back(make_pair(b, c));
		path[b].push_back(make_pair(a, c));
	}
	dep[0]=par[0]=cst[0]=0;
	dfs(0);
 
	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		string str;
		ll a, b;
		cin >> str >> a >> b;
		qry[i]={str[0], a, b};
	}
 
	for(int i=0; i<n; i++) add[i]=0;
	 
	int sq=(int)(sqrt(q));
	for(int i=0; i<sq; i++){
		int s=i*sq, t=(i+1)*sq;
		if(i==sq-1) t=q;
		 
		used[0]=true;
		for(int j=1; j<n; j++) used[j]=false;
		for(int j=s; j<t; j++){
			if(qry[j].t=='a') 
				used[qry[j].a]=true;
			else
				used[qry[j].a]=used[qry[j].b]=true;
		}
		cntdfs(0);
		for(int j=1; j<n; j++) 
			if(0<cnt[j] && cnt[j]<cnt[par[j]])
				used[par[j]]=true;
 
		for(int j=1; j<n; j++){
			if(!used[j]) continue;
			ming_cst[j]=0;
			if(used[par[j]]){
				ming_par[j]=par[j];
			}else{
				int p=par[j];
				while(!used[par[p]]){
					ming_cst[j]+=MOD(cst[p]+add[p]+add[par[p]]);
					p=par[p];
				}
				ming_bef[j]=p;
				ming_par[j]=par[p];
			}
		}
		 
		for(int j=s; j<t; j++){
			if(qry[j].t=='a')
				add[qry[j].a]+=qry[j].b;
			else{
				int s=qry[j].a, t=qry[j].b;
				ll ans=0;
				while(s!=t){
					if(dep[s]<dep[t]) swap(s, t);
					int p = ming_par[s];
					if(dep[s]-dep[p]>1){
						int q = ming_bef[s];
						ans+=MOD(add[s]+add[par[s]]+cst[s]);
						ans+=MOD(add[q]+add[par[q]]+cst[q]);
						ans+=ming_cst[s];
					}else{
						ans+=MOD(add[s]+add[p]+cst[s]);
					}
					s=p;
				}
				printf("%lld\n", ans);
			}
		}
	}
}

Measured memory_bytes: 21648