akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1000000007;
int fpow(int x,int y)
{
	if(y==0)
		return 1;
	int ret=fpow(x,y>>1);
	ret=(long long)ret*ret%mod;
	if(y&1)
		ret=(long long)ret*x%mod;
	return ret;
}
int inv(int x)
{
	return fpow(x,mod-2);
}
int cnt[202020];
int h[202020];
int a[202020];
int la[202020];
int sum[202020];
int n;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int v)
{
	for(int i=x;i<=n;i+=lowbit(i))
		(sum[i]+=v)%=mod;
}
int query(int x)
{
	int ret=0;
	for(int i=x;i;i-=lowbit(i))
		(ret+=sum[i])%=mod;
	return ret;
}
int main()
{
	int pn=1;
	int ans1=0,ans2=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	for(int i=n-1;i>=1;i--)
		cnt[i]+=cnt[i+1];
	for(int i=1;i<=n;i++)
		cnt[i]-=(n-i);
	for(int i=1;i<=n;i++)
		if(cnt[i]>0)
			pn=(long long)pn*cnt[i]%mod;
		else
			pn=0;
	if(pn==0)
	{
		printf("0");
		return 0;
	}
	la[0]=1;
	h[0]=1;
	for(int i=1;i<=n;i++)
		if(cnt[i]>1)
		{
			h[i]=(long long)(cnt[i]-1)*inv(cnt[i])%mod;
			la[i]=la[i-1];
		}
		else
		{
			h[i]=1;
			la[i]=i;
		}
	for(int i=2;i<=n;i++)
		h[i]=(long long)h[i]*h[i-1]%mod;
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++)
	{
		ans1=((long long)(query(a[i])-query(la[a[i]]-1)+mod)*h[a[i]]+ans1)%mod;
		add(a[i],inv(h[a[i]]));
	}
	ans1=(long long)ans1*inv(2)%mod;
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++)
	{
		(ans1+=i-1-query(a[i]))%=mod;
		add(a[i],1);
	}
	memset(sum,0,sizeof(sum));
	for(int i=n;i>=1;i--)
	{
		ans2=((long long)(query(a[i]-1)-query(la[a[i]]-1)+mod)*h[a[i]]+ans2)%mod;
		add(a[i],inv(h[a[i]]));
	}
	ans2=(long long)ans2*inv(2)%mod;
	ans1=(ans1-ans2+mod)%mod;
	printf("%lld",(long long)ans1*pn%mod);
	return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}

template <class T>
void read(T &x) {
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        ;
    for (x = 0; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + (c & 15);
}
#define ll long long 
#define lll __int128_t
#define pb push_back
#define mp make_pair
typedef pair < int,int> ii;
typedef vector<ii> vii;
typedef vector<ll>vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll i, j, k, l, n, m;
    cin >> n;
    vector<ll> data;
    for (i = 1; i <= n;i++){
        ll u, v;
        cin >> u >> v;
        data.pb(u - v);
    }
    for (i = 0; i < n-2;i++){
        if(data[i]==data[i+1]&&data[i+1]==data[i+2]&&data[i]==0){
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}

Measured memory_bytes: 3636
N,D = map(int,input().split())
X = []
for i in range(N):
    X.append(list(map(int,input().split())))
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        dis = 0
        for k in range(D):
            dis += (X[i][k] - X[j][k])**2
        dis **=(0.5)
        if dis == int(dis):
            ans += 1
print(ans)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
#import math

def main():
	N, K = map(int, input().split(" "))
	A = input().split(" ")
	A = [int(s) for s in A]
	
	DP = [100000000000000000000000000000000 for _ in range(N)]
	DP[0] = 0
	
	for i, val in enumerate(A):
		if i == 0:
			continue
		tmp = 100000000000000000000000000000000
		
		for j in range(K):
			index = j+1
			if i >= index:
				tmp1 = DP[i-index] + abs(A[i-index] - val)
				tmp = min(tmp, tmp1)
			else:
				break
		DP[i] = min(DP[i], tmp)
		
	#print(DP)
	print(DP[N-1])
	
	
if __name__ == "__main__":
	main()


Measured memory_bytes: 58336
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll a;
    cin >> a;
    string s;
    cin >> s;

    if(a >= 3200) cout << s << endl;
    else cout << "red" << endl;
    return 0;
}

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

public class Main {
	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		int N = Integer.parseInt(line);
		line = br.readLine();
		String text[] = line.split(" ");
		int a[] = new int[N];
		
		int max = 0, min = 0;
		
		for(int i = 0; i < text.length;i++){
			a[i] = Integer.parseInt(text[i]);
//			
//			if(max < a[i]){
//				max = a[i];
//			}
//			if(min > a[i]){
//				min = a[i];
//			}
//			System.out.println(a[i]);
		}
		//最小コスト
		int res = 1000000000;
		
		for(int i = -100; i <= 100; i++){
			int cost = 0;
			for(int k = 0; k < a.length; k++){
				cost += Math.pow(i -a[k] , 2);
			}
			if(cost < res)res = cost;
		}
		System.out.println(res);
	}
}


Measured memory_bytes: 7892
// Problem : F - LIS on Tree
// Contest : AtCoder - AtCoder Beginner Contest 165
// URL : https://atcoder.jp/contests/abc165/tasks/abc165_f
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,a,b;
	cin>>n>>a>>b;
	int is_possible = 0;
	for(int j = a; j <= b; j++)
	{
		if(j % n == 0)
		{
			is_possible = 1;
		}
	}
	if(is_possible == 1)
	{
		cout<<"OK";
	}
	else
	{
		cout<<"NG";
	}
	return 0;
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,N-1,0)
#define RREPS(i,n) RFOR(i,N,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;
const int MAX=1000001;
int fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

int COM(int n,int k){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int powMOD(int n,int r){
    if(r==0)return 1;
    if(r%2==0)return powMOD(n,r/2)*powMOD(n,r/2)%MOD;
    if(r%2==1)return powMOD(n,r-1)*n%MOD;
}
map<int,int>lar;
void bunkai(int x){
    map<int,int>memo;
    for(int i=2;i<=sqrt(x);i++){
        while(x%i==0){
            x/=i;
            memo[i]++;
        }
        lar[i]=max(memo[i],lar[i]);
    }
    if(x!=0)memo[x]++;
    lar[x]=max(lar[x],memo[x]);
}

signed main(){
    COMinit();
    int N;cin>>N;
    int A[N];
    REP(i,N){
        cin>>A[i];
        bunkai(A[i]);
    }
    int z=1;
    for(auto v:lar){
        z*=powMOD(v.first,v.second);
        z%=MOD;
    }
    int ans=0;
    REP(i,N){
        ans+=z*inv[A[i]];
        ans%=MOD;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 24448
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        bubbleSort(a, n);
        sc.close();
    }

    private static void bubbleSort(int[] a, int n) {
        int exchange = 0;
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = n - 1; i > 0; i--) {
                if (a[i] < a[i - 1]) {
                    int ai = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = ai;
                    exchange++;
                    flag = true;
                }
            }
        }
        print(a, n, exchange);
    }

    private static void print(int[] a, int n, int exchange) {
        String[] aStr = new String[n];
        for (int i = 0; i < n; i++) {
            aStr[i] = String.valueOf(a[i]);
        }
        System.out.println(String.join(" ", aStr));
        System.out.println(exchange);
    }
}


Measured memory_bytes: 26208
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void Say(bool say, string a = "Yes", string b = "No"){cout << (say ? a : b) << endl;};

const ll MOD = 1000000007;

int main(){

    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    ll dp[2][13] = {};
    dp[0][0] = 1;
    ll tmp = 1;
    for(ll i = 0; i < s.size(); i++){
        for(ll j = 0; j < 13; j++){
            for(ll k = 0; k < 10; k++){
                if(s[i] != '?' && s[i] != ('0' + k))continue;
                ll t = (k * tmp) % 13;
                ll nxt = (j + t) % 13;
                dp[1][nxt] = (dp[1][nxt] + dp[0][j]) % MOD;
            }
        }
        for(ll j = 0; j < 13; j++){
            dp[0][j] = dp[1][j];
            dp[1][j] = 0;
        }
        tmp = (tmp * 10) % 13;
    }
    cout << dp[0][5] << endl;

    return 0;
}

Measured memory_bytes: 512
def distance(L1, L2):
    return ((L1[0] - L2[0]) ** 2 + (L1[1] - L2[1]) ** 2) ** 0.5

N = int(input())
mat = [list(map(int, input().split())) for i in range(N)]

dis_sum = 0
for i in range(N):
    for j in range(i+1,N):
        dis_sum += distance(mat[i], mat[j])
dis_sum = dis_sum / (N * (N - 1) / 2) * (N - 1)
print(dis_sum)

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

int main()
{
    int x[10000];
    int i;

    i = 0;
    do
    {
        i++;
        cin >> x[i];
    } while (x[i]);

    i = 1;
    while (x[i])
    {
        cout << "Case " << i << ": " << x[i] << endl;
        i++;
    }

    return 0;
}



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

int main()
{
    char card[201];
    char shuffle[200];

    int m;
    int h;

    for (;;) {
        scanf("%s", card);
        if (card[0] == '-') {
            break;
        } else {
            scanf("%d", &m);
            int i;
            for (i = 0; i < m; i++) {
                scanf("%d", &h);
                strncpy(shuffle, card, h);
                shuffle[h] = '\0';
                strcpy(card, &(card[h]));
                strcat(card, shuffle);
            }
            printf("%s\n", card);
        }
    }

    return 0;
}



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

int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9') f|=c=='-',c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return f?-x:x;
}

#define LL long long
#define MAXN 50
int A[MAXN+5];

int main(){
    int N=read();
    for(int i=1;i<=N;i++)
        A[i]=read();
    int Ans=0;
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
            Ans+=A[i]*A[j];
    printf("%d",Ans);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

// 最小全域木 O(ElogV)?
// verify : https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_A
template<typename T>
struct Prim {
private:
    struct Edge {
        T cost;
        int to;
        bool operator>(const Edge e)const {
            return this->cost > e.cost;
        }
        bool operator<(const Edge e)const {
            return this->cost < e.cost;
        }
    };
    int V; // 頂点数
    vector<vector<Edge>> G;
public:
    Prim(int V) : V(V) {
        G.resize(V);
    }

    void add_edge(int from, int to, T weight) {
        G[from].push_back({weight,to});
        G[to].push_back({weight,from});
    }

    T build() {
        T res = 0;
        vector<bool> used(V, false);
        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
        for (const Edge &e : G[0]) {
            pq.push(e);
        }
        used[0] = true;
        while (!pq.empty()) {
            Edge e = pq.top(); pq.pop();
            if (used[e.to]) continue;
            used[e.to] = true;
            res += e.cost;
            for (const Edge &u : G[e.to]) {
                if (used[u.to]) continue;
                pq.push(u);
            }
        }
        return res;
    }
};

int main() {
    while (true) {
        int n, m; cin >> n;
        if (n == 0) break;
        cin >> m;
        Prim<ll> G(n);
        REP(i, m) {
            int a, b; ll c;
            char p;
            scanf("%d%c%d%c%lld", &a, &p, &b, &p, &c);
            G.add_edge(a, b, c / 100);
        }
        cout << G.build() - (n - 1) << endl;
    }
    return 0;
}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10; //1e-9?
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n; cin >> n;

    auto dp = vec<ll>(n + 1, 4, 4, 4);
    dp[0][0][0][0] = 1;
    FOR(i, 0, n)FOR(a, 0, 4)FOR(b, 0, 4)FOR(c, 0, 4) {
        (dp[i + 1][b][c][0] += dp[i][a][b][c]) %= mod;
        (dp[i + 1][b][c][1] += dp[i][a][b][c]) %= mod;
        if (!(b == 1 && c == 2) && !(a == 1 && c == 2) && !(a == 1 && b == 2) && !(b == 2 && c == 1)) {
            (dp[i + 1][b][c][3] += dp[i][a][b][c]) %= mod;
        }
        if (!(b == 1 && c == 3)) {
            (dp[i + 1][b][c][2] += dp[i][a][b][c]) %= mod;
        }
    }

    ll ans = 0;
    FOR(a, 0, 4)FOR(b, 0, 4)FOR(c, 0, 4) {
        (ans += dp[n][a][b][c]) %= mod;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using o_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define M 1000010

int main(){
	IOS;
	ll a,b;cin>>a>>b;
	if(a>=6 and a<=12)cout<<b/2;
	else if(a<=5)cout<<0;
	else cout<<b;
	return 0;
}



Measured memory_bytes: 384
S = input()
N = len(S)
K = int(input())
T = []
for i in range(N):
    s = ord(S[i]) - 97
    a = (26-s) % 26
    if a <= K:
        K -= a
        T.append("a")
    else:
        T.append(S[i])
T[-1] = chr((ord(T[-1]) - 97 + K) % 26 + 97)
print("".join(T))

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

const long long INF = 1LL << 60;

int main() {
  int n,k;
  cin >> n >> k;
  
  int x=k;
  REP(i,31){
    if(n/x!=0){
      x*=k;
    }
    else{
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

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

    vector<int> s,o(n+1,-1);
    int t=1,l=0,v=1;
    while(o[v]==-1){
        o[v]=s.size();
        s.push_back(v);
        v=a[v-1];
    }
    t=s.size()-o[v];
    l=o[v];

    if(k<l) cout<<s[k]<<endl;
    else{
        k-=l;
        k%=t;
        cout<<s[l+k]<<endl;
    }
}

Measured memory_bytes: 5864
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
using namespace std;

#define rep(i, n) for(int i = 0; i< n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1 << 29;
const double EPS = 1e-10;

int deg[1<<20];
int c[20];
int need[20];

int bitscount(int n){
  int res = 0;
  while(n){
    res++;
    n -= (n & -n);
  }
  return res;
}

int main(){
  int n, U, k,r;
  while(cin >> n >> U && (n || U)){
    memset(deg, -1, sizeof(deg));
    memset(need, 0, sizeof(need));
    int res = INF;
    rep(i, n){
      cin >> c[i] >> k;
      rep(j, k){
	cin >> r;
	need[i] |= (1 << r);
      }
    }
    deg[0] = 0;
    rep(i, (1 << n)){
      if(deg[i] == -1) continue;
      if(deg[i] >= U){
	res = min(res, bitscount(i));
	continue;
      }
      rep(j, n){
	if(!(i & (1 << j)) && ((i & need[j]) == need[j])){
	  deg[i|(1<<j)] = c[j] + deg[i];
	}
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
 
int main() {
    
    int i;
    int h, n, a, all = 0;
 
    scanf("%d%d", &h, &n);
    for(i = 0; i < n; i++) {
        scanf("%d", &a);
        all += a;
    }
 
    if(h <= all) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    
    return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python
# -*- coding: utf-8 -*-
n = int(raw_input())
for i in range(n):
    xa, ya, xb, yb, xc, yc, xd, yd = map(float, raw_input().split(" "))
    if abs((ya - yb)*(xc - xd) - (yc - yd)*(xa - xb)) < 1e-12:print "YES"
    else:print "NO"

Measured memory_bytes: 6352
//#include"pch.h"
//#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int main() {

	int A, B, C, D;
	cin >> A >> B >> C >> D;
	if (abs(B - A) <= D && abs(C - B) <= D || abs(C - A) <= D)puts("Yes");
	else puts("No");





	return(0);
}

Measured memory_bytes: 256
H, W = map(int, input().split())
s = [["."] * (W + 2)]
for _ in range(H):
    s.append(["."] + list(input()) + ["."])
s.append(["."] * (W + 2))


def judge(s):
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if s[i][j] == "#":
                if s[i + 1][j] == "."and s[i][j + 1] == "."and s[i - 1][j] == "."and s[i][j - 1] == ".":
                    return "No"
    return "Yes"


print(judge(s))


Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

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

  ll r,d,x2000; cin >> r >> d >> x2000;
  ll x = x2000;
  for (ll i = 0; i < 10; ++i) {
    x = r*x - d;
    cout << x << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main()
{
    int N;
    std::cin >> N;

    int A[N];
    for(int i=0; i<N; i++)
        std::cin >> A[i]; // A_iを代入

    int cnt=0;  // これは答え
    int cnt_i=0;
    while(true) // Aの全要素が2で割り切れる限り繰り返す
    {
        cnt_i=0; // この while ループの中で，A の全要素が2で割り切れるか判定する．0 なら割り切れる．
        for(int i=0; i<N; i++) // 各要素が2で割り切れるか検証する．
        {
            if(A[i]%2 != 0) // 割り切れないときは
                cnt_i++; // cnt_i を 0 以外にする
            else
                A[i]/=2; // 次のループのために2で割る
        }

        if(cnt_i == 0) // 全要素が2で割り切れるとき
            cnt++; // 答えの cnt に1加える
        else
            break; // 2 で割り切れない要素があれば抜ける．
    }

    std::cout << cnt << std::endl;
    
}

Measured memory_bytes: 3508
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>



#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))

using namespace std;
int n,t;
int c[2000];
int ti[2000];

int main(){
  cin >> n >> t;
  REP(i,n) cin >> c[i] >> ti[i];
  int ans = 10000;
  REP(i,n){
    if(ti[i]<=t&&c[i]<ans) ans = c[i];
  }
  if(ans == 10000) cout <<"TLE"<< endl;
  else cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    N = int(input())

    ans = [0]*N
    for i in range(1, 101):
        for j in range(1, 101):
            for k in range(1, 101):
                res = i**2 + j ** 2 + k**2 + i*j + j*k + k*i
                if res > N:
                    continue
                else:
                    ans[res-1] += 1

    for i in range(N):
        print(ans[i])


main()


Measured memory_bytes: 68476
#include<stdio.h>
void swap(int * , int * );

main()
{
  int i,j,A[100];
  int N,count=0;
  scanf("%d",&N);
  for(i=0 ; i<N ; i++){
    scanf("%d",&A[i]);
  }
  for(i=0; i<N ; i++){
    for(j=N-1; j>0 ; j--){
      if(A[j] < A[j-1]){
	swap(&A[j],&A[j-1]);
	count++;
      }
    }
  }
  
  for(i=0 ; i<N ; i++){
    if(i == N-1){
      printf("%d\n",A[i]);
      break;
    }
    printf("%d ",A[i]);
  }
  printf("%d\n",count);
  return 0;
}

void swap(int *a , int *b){

  int change;
  change = *a;
  *a = *b;
  *b = change;
}

Measured memory_bytes: 600
# 0028
array = []
while True:
    try:
        a = input()
        array.append(int(a))
    except EOFError:
        break
s = set(array)
mx = array.count(max(s, key = array.count))
for a in sorted(s):
    if array.count(a) == mx:
        print(a)

Measured memory_bytes: 7540
N = int(input())

L = [0 for i in range(87)]
L[0] = 2
L[1] = 1

if N == 1:
    print(1)
else:
    for i in range(2, N + 1):
        L[i] = L[i-1] + L[i-2]
    print(L[N])


Measured memory_bytes: 2940
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}
vector<int> r,g;
set_t b;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    rep(i,n){
        if(s[i]=='R'){
            r.push_back(i);
        }else if(s[i]=='G'){
            g.push_back(i);
        }else{
            b.insert(i);
        }
    }
    int rs=r.size();
    int gs=g.size();
    int bs=b.size();
    ll ans=0;
    rep(i,rs){
        rep(j,gs){
            int temp=bs;
            if(b.count(2*g[j]-r[i])){
                temp--;
            }
            if(b.count(2*r[i]-g[j])){
                temp--;
            }
            
            if((r[i]+g[j])%2==0){
                if(b.count((r[i]+g[j])/2)){
                    temp--;
                }
            }
            ans+=temp;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3644
//
//  roudupthemean.cpp
//
//
//  Created by 田中諒 on 2019/10/22.
//

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    
    int x;
    x = (a + b);
    if (x % 2 == 0){
        x = x / 2;
    }else {
        x = x / 2 + 1;
    }
    
    cout << x << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cmath>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
const ll MOD = 1000000007;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++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; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};
#define print(x) cout << (x) << endl;
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
 
template<typename T>
T gcd(T a,T b){return b?gcd(b,a%b):a;}

const int INF = 1e9;
const ll LLINF = 1e16;
 
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
 
template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

// 割り算の切り上げ処理
template<typename T>
T round_up(T a, T b) {
  return (a + b - 1) / b;
}


using pint = pair<int, int>;
using pll = pair<ll, ll>;

ll dp[10100][10100];
int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    string s,t;
    cin >> s >> t;
    int a,b;
    cin >> a >> b;
    string u;
    cin >> u;
    if(u == s){
      print(a - 1);
      print(b);
    }else if(u == t){
      print(a);
      print(b-1);
    }else{
      print(a);
      print(b);
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int memo[700000];
int c[6] = {1, 5, 10, 50, 100, 500}, cnt;
vector<int> v(6), m;

bool can(int x) {
	int res = x;
	cnt = 0;

	rep(i, 6) {
		int t = res / c[5-i];
		t = min(t, v[5-i]);

		res -= c[5-i] * t;
		cnt += t;
	}

	if(res == 0) return true;
	else return false;
}

int func(int x) {
	int res = x,ret = 0;
	rep(i, 6) {
		ret += res / c[5-i];
		res -= c[5-i] * (res / c[5-i]);
	}

	memo[x] = ret;
	return ret;
}

int main() {
	int p;
	rep(i, 700000) memo[i] = -1;

	while(cin >> p >> v[0] >> v[1] >> v[2] >> v[3] >> v[4] >> v[5]) {
		if(p == 0 && v[0] == 0 && v[1] == 0 && v[2] == 0 && v[3] == 0 && v[4] == 0 && v[5] == 0) {
			break;
		}

		int ans = INF;
		int sum = 0;
		rep(i, 6) {
			sum += c[i] * v[i];
		}

		REP(i, p, sum+1) {
			if(!can(i)) continue;
			if(memo[i-p] == -1) {
				ans = min(ans, cnt + func(i-p));
			}
			else {
				ans = min(ans, cnt + memo[i-p]);
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 3924
import numpy as np


def main():
    N, K = [int(x) for x in input().split()]
    A = np.array(input().split(), np.int64)
    A = np.sort(A)
    minus = A[A<0]
    zero = A[A==0]
    plus = A[A>0]


    def f(x):
        """number of products <=x
        """
        res = 0
        if x >= 0:
            res += len(zero) * N
        # positive
        res += np.searchsorted(A, x // plus, side="right").sum()

        # negative
        res += (N - np.searchsorted(A, (-x-1) // (-minus), side="right")).sum()

        # remove dup
        res -= np.count_nonzero(A*A <= x)
        res //= 2

        return res

    l = -10**18
    r = 10**18

    while l+1 < r:
        mid = (l+r)//2
        if f(mid) >= K:
            r = mid
        else:
            l = mid
    print(r)


if __name__ == '__main__':
    main()

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

int N, M;
vector<int> A;


int main(){
    cin >> N >> M;
    A.resize(M);
    int out =0;
    for(auto& a: A){
        cin >> a;
        out += a;
    }
    cout << (out > N ? -1 : N-out);
    
    return 0;
}

Measured memory_bytes: 3676
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int r, g, b, n;
    cin >> r >> g >> b >> n;
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            int k = n-r*i-g*j;
            if(k%b == 0 && k >= 0){
                ans++;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct UnionFind
{
    vector<int> data;

    UnionFind(int sz)
    {
        data.assign(sz,-1);
    }

    bool unite(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y) return(false);
        if(data[x] > data[y]) swap(x,y);
        data[x] += data[y];
        data[y] = x;
        return(true);
    }

    int find(int k)
    {
        if(data[k] < 0) return(k);
        return(data[k] = find(data[k]));
    }

    int size(int k)
    {
        return(-data[find(k)]);
    }
};

int main(){
    int n,m;
    cin >> n >> m;
    int p[n];
    for(int i=0; i<n; i++){
        cin >> p[i];
        p[i]--;
    }
    UnionFind tree(n);
    for(int i=0; i<m; i++){
        int x,y;
        cin >> x >> y;
        x--; y--;
        tree.unite(p[x],p[y]);
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        if(tree.find(i) == tree.find(p[i])) ans++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define M (1<<22)
#define bp(x) __builtin_popcount(x)

ll n, a[50][50], dp[M];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    dp[0] = 1;
    for (int mask = 0; mask < (1<<n); mask++){
        for (int i = 0; i < n; i++){
            if (bp(mask) != i) continue;
            for (int j = 0; j < n; j++){
                if (mask&(1<<j)) continue;
                if (a[i][j] == 0) continue;
                dp[mask + (1<<j)] += dp[mask];
                dp[mask + (1<<j)] %= MOD;
            }
        }
    }
    cout << dp[(1<<n) - 1];
}

Measured memory_bytes: 18688
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define sort(vec) sort(vec.begin(),vec.end())
#define reverse(vec) reverse(vec.begin(),vec.end())
int gcd(int x,int y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
string s;
int ans;
signed main(){
    cin>>s;
    int le=s.size();
    rep(i,le){
        int l=s.size();
        string n="";
        rep(i,l-1){
            n+=s[i];
        }
        s=n;
        l--;
        if(l%2||i==0)continue;
        int x=l/2;
        string a=s.substr(0,x);
        string b=s.substr(x);
        if(a==b){
            ans=l;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        k = bisect.bisect_left(L, a + b)
        ans += k - j - 1
print(ans)


Measured memory_bytes: 43740
#include<bits/stdc++.h> 
using namespace std;
#define ll long long
#define MOD 1000000007

ll n,k;
int t;
ll m, M;

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

	cin>> k;
	string str ;
	cin>> str;

	if( str.size() <= k ) {
		cout<< str<<endl;
	} else {
		str = str.substr(0,k);
		str += "...";
		cout<<str<<endl;
	}

	return 0;

}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int p = 1e9 + 7;

using ll = long long int;

ll fac(int n) {
	ll ans = 1;
	for (ll i = 1; i <= n; i++) {
		ans = ans * i % p;
	}
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	if (abs(n - m) > 1) {
		cout << 0 << endl;
	}else if (n == m) {
		ll nd = fac(n);
		cout << (2 * (nd % p)* (nd % p)) % p << endl;
		return 0;
	} else {
		cout << fac(n) * fac(m) % p << endl;
	}
}

Measured memory_bytes: 256
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
AA = [list(map(int, input().split())) for _ in range(N)]

count = 0
for A in AA:
    if sum(a * b for a, b in zip(A, B)) + C > 0:
        count += 1
print(count)


Measured memory_bytes: 3060
#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>
using namespace std;

int main(){
 
    string s,f;
    
    cin >> s >> f;
    
    if(s[0] == f[2] && s[1] == f[1] && s[2] == f[0]){
    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 ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main()
{
  int N; cin >> N;
  cout << (N%2==0 ? 1./2 : (N/2+1.)/N) << endl;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

/* エラトステネスの篩 */
const int SIZE = 2000000;
vector<ll> primes;
bool isPrime[SIZE];

void make_primes() {
  if (primes.size() > 0) return;
  memset(isPrime, true, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i * i < SIZE; i++)
    if (isPrime[i])
      for (int j = i * i; j < SIZE; j += i)
        isPrime[j] = false;
  REP(i, SIZE) if (isPrime[i]) primes.push_back(i);
}

map<ll, ll> factorize(ll n) {
  map<ll, ll> ps;
  for (int i = 0; primes[i] * primes[i] <= n; i++) {
    while (n % primes[i] == 0) {
      ps[ primes[i] ]++;
      n /= primes[i];
    }
  }
  if (n > 1) ps[n]++;
  return ps;
}


int main2() {
  ll N; cin >> N;
  auto ps = factorize(N);
  ll ans = 0;
  // pv(ALL(ps));
  for (auto p : ps) {
    int m = p.second;
    int k = 1;
    while (k <= m) {
      ans++;
      m -= k;
      k++;
    }
  }
  cout << ans << endl;
  return 0;
}

int main() {
  make_primes();
#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 7124
////In the name of God:)
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ll long long int
#define fast  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MAXN = 1e5 + 10;
# define PI 3.14159265358979323846
int main(){
    double n;
    cin>>n;
    double ans = n * 2 * PI;
    cout<<fixed<<setprecision(20)<<ans<<endl;
}


Measured memory_bytes: 3788
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a=n/1000;
    int b=n/100%10;
    int c=n/10%10;
    int d=n%10;
    //cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
    
    string s;
    if(a+b+c+d==7){
        s="+++";
    }else if(a+b+c-d==7){
        s="++-";
    }else if(a+b-c+d==7){
        s="+-+";
    }else if(a-b+c+d==7){
        s="-++";
    }else if(a+b-c-d==7){
        s="+--";
    }else if(a-b+c-d==7){
        s="-+-";
    }else if(a-b-c+d==7){
        s="--+";
    }else if(a-b-c-d==7){
        s="---";
    }
    
    cout<<a<<s[0]<<b<<s[1]<<c<<s[2]<<d<<"=7"<<endl;
    return 0;
}


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

struct mp{
	int to,dis;
};

void trip(int nw,int f,int64_t dist,vector<vector<mp>>&v,vector<int64_t>&d){
	d.at(nw)=dist;
	for(auto&i:v.at(nw)){
		if(i.to!=f)trip(i.to,nw,dist+i.dis,v,d);
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<vector<mp>>v(n+1);
	for(int i=1;i<n;++i){
		int a,b,c; cin>>a>>b>>c;
		v.at(a).push_back({b,c});
		v.at(b).push_back({a,c});
	}
	int q,k; cin>>q>>k;
	vector<int64_t>d(n+1);
	trip(k,-1,0,v,d);
	for(int i=0;i<q;++i){
		int x,y; cin>>x>>y;
		cout<<d.at(x)+d.at(y)<<"\n"s;
	}
}

Measured memory_bytes: 15872
n, m, x, y = list(map(int, input().split()))
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))

max_x = sorted(xs)[-1]
min_y = sorted(ys)[0]

if max_x < min_y and x < min_y and max_x < y:
    print('No War')
else:
    print('War')


Measured memory_bytes: 3060
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split()))for i in range(m)]
p =[]
d = []
a.sort()
for i in range(m):
    b = bc[i][0]
    c = bc[i][1]
    p.append([c,b])
p.sort(reverse = True)
look = 0
for i in range(n):
    if look > m-1:break
    if p[look][1] >0:
        d.append(p[look][0])
        p[look][1]-=1
    
    else:
        if look ==m-1:break
        look+=1
        d.append(p[look][0])
        p[look][1]-=1
sm = sum(a)
updatefrom = 0
updateto = 0
ans = sm
for x in range(n):
    if x >= len(d):break
    updatefrom +=a[x]
    updateto +=d[x]
    ans = max(ans,sm-updatefrom +updateto)
print(ans)
    

    
    

Measured memory_bytes: 39288
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
lint N, l, r;
vector<lint> a;
vector<vector<lint> > memo;

lint rec(lint l, lint r){
	if(l > r) return 0;
	if(memo[l][r] != -1) return memo[l][r];
	if((N - (r - l + 1)) % 2 == 0) {
		if(rec(l + 1, r) + a[l] >= rec(l, r - 1) + a[r]){
			return memo[l][r] = rec(l + 1, r) + a[l]; l++;
		}
		else return memo[l][r] = rec(l, r - 1) + a[r]; r--;
	}
	else{
		if(rec(l + 1, r) - a[l] <= rec(l, r - 1) - a[r]){
			return memo[l][r] = rec(l + 1, r) - a[l]; l++;
		}
		else return memo[l][r] = rec(l, r - 1) - a[r]; r--;
	}
}

signed main(){
	cin >> N;
	a.resize(N);
	for(lint i = 0; i < N; i++) cin >> a[i];
	memo.resize(N, vector<lint> (N, -1));
	l = 0, r = N - 1;
	cout << rec(l, r) << endl;
}

Measured memory_bytes: 70912
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
#define loop(n) for(int i=0; i<n; i++)
#define rep(i,start,n) for(int i=start; i<n; i++)
bool check(string s,int n){
	int mid = n/2;
	int st = 0;
	while(st!=n/2){
		if(s[st]!=s[mid])return 0;
		st++;
		mid++;
	}
	return 1;
}
void solve(){
	string s;cin >> s;
	int n = s.length();

	if(n%2!=0)n--;

	while( n>2 ){
		n-=2;
		// cout<<n<<endl;		
		if(check(s,n)){
			cout<<n;
			return;
		}
	}	
	cout<<n<<endl;
}	
signed main(){
    fast;    
    // int t;cin>>t;while(t--)
    solve();    
    return 0;
}


Measured memory_bytes: 3664
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

class Team {
public:
	int id;
	int time = 0;
	vector<int> AC;
	vector<int> WA;
	Team(int P) {
		AC.resize(P, 0);
		WA.resize(P, 0);
	}
	bool operator<(const Team &t) {
		int cntAC1 = count(AC.begin(), AC.end(), 1);
		int cntAC2 = count(t.AC.begin(), t.AC.end(), 1);
		if (cntAC1 == cntAC2) {
			int t1 = time, t2 = t.time;
			rep(i, 0, AC.size())
				if (AC[i]) t1 += WA[i] * 20;
			rep(i, 0, t.AC.size())
				if (t.AC[i]) t2 += t.WA[i] * 20;
			if (t1 == t2)return id < t.id;
			else return t1 > t2;
		}
		else return cntAC1 < cntAC2;
	}
	bool operator==(const Team &t) {
		int cntAC1 = count(AC.begin(), AC.end(), 1);
		int cntAC2 = count(t.AC.begin(), t.AC.end(), 1);
		if (cntAC1 == cntAC2) {
			int t1 = time, t2 = t.time;
			rep(i, 0, AC.size())
				if (AC[i]) t1 += WA[i] * 20;
			rep(i, 0, t.AC.size())
				if (t.AC[i]) t2 += t.WA[i] * 20;
			return t1 == t2;
		}
		else return false;
	}
};

signed main() {
	for (int M, T, P, R; cin >> M >> T >> P >> R && (M || T || P || R);) {
		vector<Team> Teams(T, Team(P));
		rep(i, 0, T) { Teams[i].id = i + 1; }
		rep(i, 0, R) {
			int m, t, p, j; cin >> m >> t >> p >> j;
			t--;
			p--;
			if (j == 0) {
				Teams[t].AC[p] = 1;
				Teams[t].time += m;
			}
			else {
				Teams[t].WA[p]++;
			}
		}
		sort(Teams.begin(), Teams.end());
		reverse(Teams.begin(), Teams.end());
		cout << Teams[0].id;
		rep(i, 1, T) {
			cout << ",="[Teams[i] == Teams[i - 1]] << Teams[i].id;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3080
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <math.h>
using namespace std;

int main() {
	double a, b, c;
	double S, L ,h;
	cin >> a >> b >> c;
	S = a * b * sin(c * M_PI / 180) / 2;
	L = a + b + sqrt(a*a + b*b - 2*a*b*cos(c * M_PI / 180));
	h = b * sin(c * M_PI /180);
	printf("%.6lf\n",S);
	printf("%.6lf\n",L);
	printf("%.6lf\n",h);
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define rep(i,l,r) for(int (i)=(l);(i)<(r);(i)++)
#define ll long long
using namespace std;
int main(){
    ll n,p;
    cin>>n>>p;
    if(n==1){
      cout<<p<<endl;
      return 0;
    }
    ll ans=1;
    for(ll a=2;p>=a*a;a++){ 
        int buf=0;
        while(p%a==0){
            buf++;
            p/=a;
        }
        buf/=n;
        while(buf--)ans*=a;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


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

	ll mod = 1e9 + 7;
	ll dp[101][10] = {};
	dp[0][1] = 1;

	ll zentai = 1;
	ll yoko[10] = {};

	rep1(i, W - 1) {
		for (int ii = i + 2; ii < W; ii++) {
			for (int iii = ii + 2; iii < W; iii++) {
				for (int iiii = iii + 2; iiii < W; iiii++) {
					yoko[i]++;
					yoko[ii]++;
					yoko[iii]++;
					yoko[iiii]++;
					zentai++;
				}
				yoko[i]++;
				yoko[ii]++;
				yoko[iii]++;
				zentai++;
			}
			yoko[i]++;
			yoko[ii]++;
			zentai++;
		}
		yoko[i]++;
		zentai++;
	}

	rep(i, H) {
		rep1(ii, W) {
			dp[i + 1][ii] += (dp[i][ii - 1] * yoko[ii - 1]) % mod;
			dp[i + 1][ii] += (dp[i][ii + 1] * yoko[ii]) % mod;
			dp[i + 1][ii] += (dp[i][ii] * (zentai - yoko[ii - 1] - yoko[ii])) % mod;
			dp[i + 1][ii] %= mod;
		}
	}
	co(dp[H][K]);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

int main(){
    vector<vector<int> > vec(3,vector<int>(3,0));
    for(auto &line:vec){
        for(auto &x:line){
            cin >> x;
        }
    }
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        int b;
        cin >> b;
        for(auto &line:vec){
            for(auto &x:line){
                if(x==b){
                    x=0;
                }
            }
        }
    }
    for(int i=0; i<3; i++){
        if(vec[i][0]+vec[i][1]+vec[i][2]==0){
            cout << "Yes" << endl;
            return 0;
        }
        if(vec[0][i]+vec[1][i]+vec[2][i]==0){
            cout << "Yes" << endl;
            return 0;
        }
        if(vec[0][0]+vec[1][1]+vec[2][2]==0){
            cout << "Yes" << endl;
            return 0;
        }
        if(vec[0][2]+vec[1][1]+vec[2][0]==0){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

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

int main() {

	ll n; cin >> n;
	vector<ll> a(n), num(n + 1, 0);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
		num[a[i]]++;
	}
	ll sum = 0;
	for (ll i = 0; i <= n; i++) {
		sum += num[i] * (num[i] - 1) / 2;
	}
	for (ll i = 0; i < n; i++) {
		ll tmp = 0;
		tmp += sum;
		tmp -= num[a[i]] * (num[a[i]] - 1) / 2;
		tmp += (num[a[i]] - 1) * (num[a[i]] - 2) / 2;
		cout << tmp << endl;
	}
	return 0;
}

Measured memory_bytes: 6416