akhauriyash/Code-Regression huggingface dataset:
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

int main()
{
	ios_init();
	int n;
	while(cin >> n) {
		vector<LL> a(n);
		REP(i,n) cin >> a[i];
		vector<P> ns;
		vector<P> tv(n);
		REP(i,n) tv[i]  = {a[i],-i};
		sort(ALL(tv));
		P ma = {-INF,INF};
		RREP(i,n){
			if(ma.S > -tv[i].S){
				ma = {tv[i].F,-tv[i].S};
				ns.push_back(ma);
			}
		}
		dpite(ALL(ns));
		reverse(ALL(ns));
		vector<LL> ans(n);
		vector<LL> imos(SZ(ns)+1);
		RREP(i,n){
			DEBUG(i);
			DEBUG(a[i]);
			auto ite = upper_bound(ALL(ns),P(a[i],0));
			int ind = ite-ns.begin();
			DEBUG(ind);
			if(ind == 0){
				ans[ns[ind].S] += a[i];
			}else{
				DEBUG(a[i]-ns[ind-1].F);
				ans[ns[ind].S] += a[i]-ns[ind-1].F;
				imos[ind] += -1;
				imos[0] += 1;
			}
		}
		dpite(ALL(ans));
		dpite(ALL(imos));
		REP(i,SZ(imos)-1)  imos[i+1] += imos[i];
		dpite(ALL(imos));
		REP(i,SZ(imos)-1){
			LL dis;
			if(i == 0){
				dis = ns[i].F;
			}else{
				dis = ns[i].F-ns[i-1].F;
			}
			ans[ns[i].S] += dis*imos[i];
		}
		REP(i,n){
			cout << ans[i] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 6512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll ret = 0;
string s;

int main(void){
  ll K;
  IN(N);
  IN(K);
  vl arr(N+1, 0);
  ll d;
  ll t;
  REP(i, K) {
    IN(d);
    REP(j, d) {
      IN(t);
      arr[t]++;
    }
  }
  FOR(i, 1, N+1) {
    if (arr[i] == 0) ret++;
  }
  PRINT(ret);

}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
const int maxn=3010;
int n;
double p[maxn],ans;
double dp[maxn][maxn*2];
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
	dp[0][0]=1;
	for (int i=0;i<n;i++)
	for (int j=-i;j<=i;j++) {
		dp[i+1][j+1]+=p[i+1]*dp[i][j];
		dp[i+1][j-1]+=(1.0-p[i+1])*dp[i][j];
	}
	for (int j=1;j<=n;j++) ans+=dp[n][j];
	printf("%.10lf\n",ans);
	return 0;
}

Measured memory_bytes: 139776
#include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <vector>

using namespace std;
using Graph = vector<vector<int>>;

using ll = long long;
typedef pair<ll, ll> P_ll;
typedef pair<int, int> P;

const ll INF_ll = 1e17;
const int INF = 1e8;

int main() {
  int N, X, T;
  cin >> N >> X >> T;
  int times = (N / X);
  if (N % X != 0) {
    times++;
  }
  cout << times * T << endl;

  return 0;
}

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

int main() {
  	int a, b;
  	cin >> a >> b;
    if (a==1) a = 14;
    if (b==1) b = 14;
    if (a>b) cout << "Alice" << endl;
    if (a==b) cout << "Draw" << endl;
    if (a<b) cout << "Bob" << endl;
}


Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            // 標準入力:S,T
            string s = Console.ReadLine();
            string t = Console.ReadLine();

            string t2 = t.Substring(0, s.Length);

            if (s == t2 && t.Length - t2.Length == 1)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 25772
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define double long double
using namespace std;

const ll mod = 1000000007;
ll n, k, pref[200005], suf[200005], sum, top;

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (ll i = 1; i <= n + 1; i ++)
        pref[i] = pref[i - 1] + i - 1;
    for (ll i = n + 1; i >= 1; i --)
        suf[i] = suf[i + 1] + i - 1;
    for (ll i = k; i <= n + 1; i ++)
    {
        top = suf[n + 1 - i + 1] - pref[i] + 1;
        //cout << top << endl;
        sum += top;
        sum %= mod;
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 6736
base=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
s=input()
t=input()

S=[]
T=[]


answer="NO"

for i in s:
    S.append(base.index(i))
for j in t:
    T.append(base.index(j))
S=sorted(S)
T=sorted(T,reverse=True)
#print(S)
#print(T)

for k in range(min(len(S),len(T))):
    if S[k]>T[k]:
        answer="No"
        break
    elif S[k]<T[k]:
        answer="Yes"
        break
if answer=="NO" and len(S)<len(T):
    answer="Yes"
elif answer=="NO" and len(S)>=len(T):
    answer="No"

print(answer)


Measured memory_bytes: 3064
/*
 * a.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 1000;
const int MAX_K = 3;

const int ts[MAX_K] = {1, 10, 100};

/* typedef */

/* global variables */

int ds[MAX_N];
bool used[MAX_N];

/* subroutines */

/* main */

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

  int k = min(MAX_K, n);

  for (int l = 1; l <= k; l++)
    for (int i = 0; i + l <= n; i++) {
      int sum = 0;
      for (int j = 0; j < l; j++) sum += ds[i + j] * ts[l - 1 - j];
      used[sum] = true;
    }

  int mind = 0;
  for (int i = 0; i < MAX_N; i++)
    if (! used[i]) {
      mind = i;
      break;
    }

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

Measured memory_bytes: 1152
//It doesn't matter how slow you go, Unless you don't stop.
#include<iostream>
#include<algorithm>
#include<bitset>
 
#include<cmath>
#include<cstring>
#include<climits>
 
#include<deque>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
 
#include<fstream>
#include<chrono>
using namespace std;
 
typedef long long LL;
typedef pair<LL,LL> p64;
typedef vector<LL> v64;
typedef map<LL,LL> mp64;
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,s,e) for(long long i=s;i<=e;i++)
#define brep(i,s,e) for(long long i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define DANGER std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
void solve()
{
     int a,b,c;
     cin>>a>>b>>c;
     cout<<c<<" "<<a<<" "<<b<<endl;
}
 
int main()
{
    DANGER;
    ofstream out("output.txt");
 
    auto start = chrono::high_resolution_clock::now();
    
    LL t = 1;
    // cin>>t;
    rep(test,1,t)
    {
        solve();
    }
    
    auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start); 
    // cout << "Time taken by function: " << duration.count() << " milliseconds" << endl;
}

Measured memory_bytes: 256
#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;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<double,double> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const double PI = 4*atan(1);
const ll INF = 1e18;
const int MX = 100001;

string S;
int num[300001][3][2][3]; // yes even, yes odd, current parity, current num

void ad(int& x, int y) {
    x = (x+y)%MOD;
}

void solve() {
    num[0][0][0][0] = 1;
    F0R(i,sz(S)) F0R(a,3) F0R(b,2) F0R(c,3) if (num[i][a][b][c]) {
        if (S[i] != '1') ad(num[i+1][a][b][c == 2 ? 1 : c+1],num[i][a][b][c]);
        if (S[i] != '0') {
            if (c == 0) {
                if (b == 0) ad(num[i+1][max(a,1)][b^1][0],num[i][a][b][c]);
                else ad(num[i+1][a>0?2:0][b^1][0],num[i][a][b][c]);
            } else if (c == 1) {
                ad(num[i+1][a][b][0],num[i][a][b][c]);
            } else {
                ad(num[i+1][a][b^1][0],num[i][a][b][c]);
            }
        }
    }
    int ans = 0;
    F0R(a,3) F0R(b,2) F0R(c,3) 
        if (a == 2 || (a == 1 && b == 1 && c == 0)) 
            ad(ans,num[sz(S)][a][b][c]);
            
    cout << ans << "\n";
}

string gen() {
    string t;
    F0R(i,5) {
        int k = rand();
        if (k % 3 == 0) t += '0';
        else if (k % 3 == 1) t += '1';
        else t += '?';
    }
    return t;
}

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

// read the question correctly (is y a vowel?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Measured memory_bytes: 21780
fun main(args: Array<String>) {
    solve(java.util.Scanner(System.`in`))
}

fun <A> List<Comparable<A>>.lowerBoundOf(target: A): Int {
    var l = -1
    var r = this.count()
    while (l + 1 < r) {
        val mid = (l + r) / 2
        if (this[mid] >= target) {
            r = mid
        } else {
            l = mid
        }
    }
    return r
}

fun <A> List<Comparable<A>>.upperBoundOf(target: A): Int {
    var l = -1
    var r = this.count()
    while (l + 1 < r) {
        val mid = (l + r) / 2
        if (this[mid] > target) {
            r = mid
        } else {
            l = mid
        }
    }
    return r
}

fun solve(sc: java.util.Scanner) {
    val N = sc.nextInt()
    val A = Array(N) { sc.nextLong() }.sorted()
    val B = Array(N) { sc.nextLong() }.sorted()
    val C = Array(N) { sc.nextLong() }.sorted()

    val result = B.map { b ->
        A.lowerBoundOf(b) * (N.toLong() - C.upperBoundOf(b))
    }.sum()

    println(result)
}


Measured memory_bytes: 118396
from itertools import product
digits = list(map(int, list(input())))


for x in product('+-', repeat=3):

    result = digits[0]
    output = str(digits[0])

    for pm, digit in zip(x, digits[1:]):

        if pm == '+':
            result += digit
            output += '+'+str(digit)
        else:
            result -= digit
            output += '-{}'.format(digit)
    if result == 7:
        print(output+'=7')
        break


Measured memory_bytes: 3060
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            Console.WriteLine(N % 2 == 0 ? N / 2 : N / 2 + 1);
        }
        private static readonly Func<string> Read = () => Console.ReadLine();
        private static readonly Func<string[]> ReadStringArray = () => Console.ReadLine().Split();
        private static readonly Func<int> ReadInt = () => int.Parse(Console.ReadLine());
        private static readonly Func<long> ReadLong = () => long.Parse(Console.ReadLine());
        private static readonly Func<int[]> ReadIntArray = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
        private static readonly Func<long[]> ReadLongArray = () => Console.ReadLine().Split().Select(long.Parse).ToArray();
        private static readonly Action<string> Cw = str => Console.WriteLine(str);
    }
}

Measured memory_bytes: 13140
a, v = list(map(int, input().split()))
b, w = list(map(int, input().split()))
t = int(input())

dif = abs(a-b)
v_dif = abs(v-w)
if v<=w and a!=b:
    print("NO")
elif dif>v_dif*t:
    print('NO')
else:
    print("YES")

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

int main(){
  int n,d;
  cin >> n >> d;
  int ans = 0;
  
  for(int i=0;i<30;i++){
    if((2*d+1)*i>=n){
      ans = i;
      break;
    }
  }
    
    cout << ans << endl;
  }
    

Measured memory_bytes: 3580
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int offset=100000;
const int mod=1e9+7;
const int M=200005;
const int N=100000;
int par[M];
map<int,int>cntx;
map<int,int>cnty;
int fnd(int x)
{
    if(par[x]==x)return x;
    return par[x]=fnd(par[x]);
}
void tie(int x,int y)
{
     x=fnd(x);
     y=fnd(y);
    if(x==y)return ;
    par[y]=x;
}
 main()

{
    fast
    f(i,1,M-1)par[i]=i;
    int n;
    cin>>n;
    f(i,1,n)
    {
        int x,y;
        cin>>x>>y;
        tie(x,y+offset);
    }
    int ses=0;
    f(i,1,N)
    {
        int x=fnd(i);
        cntx[x]++;
        int y=fnd(i+offset);
        cnty[y]++;
    }
    f(i,1,M-1)
    {
        int x=cntx[i];
        int y=cnty[i];
        ses+=(x*y);
    }
    ses=max(0LL,ses-n);
    cout<<ses<<endl;
    return 0;

}





































Measured memory_bytes: 30168
#include <iostream>
using namespace std;
long long maks,n,i,a,ans;
int main(){
	maks = -1;
	cin >> n;
	for(i=0; i<n; i++){
		cin >> a;
		if(a>maks){
			maks = a;
		}
		if(a<maks){
			ans+= (maks-a);
		}
	}
	cout << ans << endl;
}

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

#define int long long
int tmp, ans;

signed main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'A') tmp++;
        else if(s[i] == 'C') tmp = 0;
        else if(s[i] == 'B' && s[i + 1] != 'C') tmp = 0;
        else{
            ans += tmp;
            i++;
        }
    }
    cout << ans;
}

Measured memory_bytes: 644
from numba import njit
A, B, C, D, E, F = [int(_) for _ in input().split()]


@njit
def main(A, B, C, D, E, F):
    conc = -1
    ans = (1, 2)
    for na in range(F // (100 * A) + 1):
        for nb in range(F // (100 * B) + 1):
            if na == nb == 0:
                continue
            G = F - na * 100 * A - nb * 100 * B
            for nc in range(G // C + 1):
                for nd in range(G // D + 1):
                    W = na * 100 * A + nb * 100 * B + nc * C + nd * D
                    if 0 < W <= F and nc * C + nd * D <= E * (na * A + nb * B):
                        conc2 = 100 * (nc * C + nd * D) / W
                        if conc < conc2 <= 100 * E / (100 + E):
                            ans = (W, nc * C + nd * D)
                            conc = conc2
    return ans


print(*main(A, B, C, D, E, F))


Measured memory_bytes: 111644
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long cnt = 0;
        long cnt2 = 0;
        long ans = 0;
        if(K%2==0) {
            for(int i = 1; i<=N; i++) {
                if(i%K==0) cnt++;
                if(i%K==K/2) cnt2++;
            }
            ans = cnt*cnt*cnt + cnt2*cnt2*cnt2;
        }else {
            for(int i = 1; i<=N; i++) {
                if(i%K==0) cnt++;
            }
            ans = cnt*cnt*cnt;
        }
        System.out.println(ans);

    }
}

Measured memory_bytes: 21716
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
 
int main() {
    int N;
    std::cin >> N;

    std::vector<double> v(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> v[i];
    }

    std::sort(v.begin(), v.end());

    for (int i = 1; i < N; ++i) {
        v[i] = 0.5 * (v[i] + v[i - 1]);
    }

    const auto ret = v.back();

    std::cout << std::setprecision(15);
    std::cout << ret << std::endl;            
}


Measured memory_bytes: 256
const lines=readlines()
input()=shift!(lines)
int(x)=parse(Int,x)
intLine()=map(int,split(input()))
function inE(e)
    u,v=intLine()
    push!(e[u],v)
end
function bfs(e,f,s,t)
    q=Array{Pair{Int,Int}}([s=>1])
    while !isempty(q)
        v,m=shift!(q)
        u=m>2?1:m+1
        for w=e[v]
            if f[w,u]<0
                f[w,u]=f[v,m]+1
                push!(q,w=>u)
            end
        end
    end
end
function main()
    n,m=intLine()
    e=Array{Int,1}[[]for i=1:n]
    for i=1:m;inE(e);end
    s,t=intLine()
    f=ones(Int,(n,3))*-3
    f[s,1]=0
    bfs(e,f,s,t)
    show(f[t,1]÷3)
end
main()

Measured memory_bytes: 224132
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
int main(){
cin.tie(0);
ios::sync_with_stdio(false);

	int a,b;
	cin>>a>>b;
	int ans=0;
	REP(i,b-a){
		ans+=i+1;
	}
	cout<<ans-b<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
    scanf("%d%d",&a,&b);
    if(a<0&&b>0)
    {
    	cout<<"Zero\n";
    	return 0;
	}
	if(a==0||b==0)
	{
		cout<<"Zero\n";
		return 0;
	}
	if(a>0&&b>0)
	{
		cout<<"Positive\n";
		return 0;
	}
	if(a<0&&b<0)
	{
		if((b-a)%2==0)
		{
			cout<<"Negative\n";
			return 0;
		}
		if((b-a)%2==1)
		{
			cout<<"Positive\n";
			return 0;
		}
	}
    return 0;
}

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

using namespace std;

int main(void){
    int n;
    double sum=0;
    int x;
    cin >> n;
    vector<double> a;
    rep(i,n){
        cin >> x;
        a.push_back(x);
    }
    rep(i,n){
         sum +=(1/a[i]);
    }
    sum = 1/sum;
    
    cout << sum <<endl;
    
    
    
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
    int a,b,t=0;
    cin>>a>>b;
    if(a%3==0) t=1;
    if(b%3==0) t=1;
    if((a+b)%3==0) t=1;
    if(t) printf("Possible");
    else printf("Impossible");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int A, B;
  cin >> A >> B;
  if(A <= B){
    cout << A << endl;
  }
  else{
    cout << A - 1 << endl;
  }
}

Measured memory_bytes: 256
//ABC053
#define _USE_MATH_DEFINES

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define LL long long

 
 int main(){
 	int x;
 	cin >> x;
 	if(x>=1200) cout << "ARC" << endl;
 	else cout << "ABC" << endl;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// // for multiset
// // typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
// //              tree_order_statistics_node_update>
// //     new_data_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)
#define lli long long int
#define llu unsigned long long int
#define fr(va, beg, end) for (lli va = beg; va < end; va++)
#define pb push_back
#define rt return 0
#define endln "\n"
#define all(x) x.begin(), x.end()
#define sz(x) (lli)(x.size())
// cout << fixed << setprecision(0) << pi <<endl;

// lli power(lli x, lli y) {
//     // return (x^y) % mod
//     lli ans = 1;
//     x = x % mod;
//     while (y > 0) {
//         if (y & 1) {
//             ans *= x;
//             ans %= mod;
//         }
//         y = y >> 1;
//         x = (x * x) % mod;
//     }
//     return ans;
// }

lli input(lli n, vector<lli> &ve) {
    lli val;
    for (lli i = 0; i < n; i++) {
        cin >> val;
        ve.pb(val);
    }
    return 0;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    lli n, a, t;
    vector<lli> v;
    string st;
    cin >> st;
    if (st.length() % 2 == 1) {
        cout << "No" << endl;
        rt;
    }
    lli flag = 0;
    fr(i, 0, st.length()) {
        if (i % 2 == 0 && st[i] != 'h') {
            flag = 1;
            break;
        }
        if (i % 2 == 1 && st[i] != 'i') {
            flag = 1;
            break;
        }
    }
    if (flag == 1) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    rt;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
void update(ll &po, ll a, ll b){
    if(a == b) po = 0;
    else if(a < b) po = 1;
    else po = -1;
}
int main(){
    ll N;
    cin >> N;
    ll a[N + 1] = {};
    for(ll i = 0; i < N; i++) cin >> a[i];
    ll ans = 0;
    ll po = 0;
    for(ll i = 0; i < N - 1; i++){
        if(!po){
            update(po, a[i], a[i + 1]);
        }else if(po == 1){
            if(a[i] > a[i + 1]){
                ans++;
                update(po, a[i + 1], a[i + 2]);
            }
        }else if(po == -1){
            if(a[i] < a[i + 1]){
                ans++;
                update(po, a[i + 1], a[i + 2]);
            }
        }
    }
    cout << ++ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
#include <limits.h>
//#include <math.h>

#define Min(a, b) (a < b ? a : b)

int main() {
  int n;
  scanf("%d", &n);
  int a, ans=INT_MAX, cnt;
  for (int i=0; i<n; i++) {
    cnt = 0;
    scanf("%d", &a);
    while (a%2 == 0) {
      cnt++;
      a /= 2;
    }
    ans = Min(ans, cnt);
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int toInt(char c) {
  return c-'0';
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s; cin >> s;
  reverse(all(s));
  int n = s.size();
  vector<vector<ll>> dp(n+1, vector<ll>(2, longinf));
  dp[0][0] = 0;
  rep(i, n) {
    if(toInt(s[i]) == 9) {
      dp[i+1][0] = min({dp[i][0]+toInt(s[i])});
      dp[i+1][1] = min({dp[i][0]+10-toInt(s[i]), dp[i][1]+10-(toInt(s[i])+1), dp[i][1]+1});
    } else {
      dp[i+1][0] = min({dp[i][0]+toInt(s[i]), dp[i][1]+toInt(s[i])+1});
      dp[i+1][1] = min({dp[i][0]+10-toInt(s[i]), dp[i][1]+10-(toInt(s[i])+1)});
    }
  }
  cout << min(dp[n][0], dp[n][1]+1) << "\n";
  return 0;
}


Measured memory_bytes: 58908
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,n) for(int (i) = 0;(i) < n;(i)++)
const int INF = 1e9;

int main() {
	int n;
	cin >> n;
	vector<int> t(n);
	rep(i, n) {
		cin >> t[i];
	}
	map<int, map<int, map<int, int>>> dp[51];
	int limit = INF;

	function<int(int, int, int, int)> dfs = [&](int i, int a, int b, int c) {
		if (i == n) {
			return limit = min(limit, max({ a, b, c }));
		}
		int d[3] = { a,b,c };
		sort(d, d + 3);
		a = d[0], b = d[1], c = d[2];
		if (c >= limit)return INF;
		if (dp[i].count(a) && dp[i][a].count(b) && dp[i][a][b].count(c)) {
			return dp[i][a][b][c];
		}

		int ret = dfs(i + 1, a + t[i], b, c);
		ret = min(ret, dfs(i + 1, a, b + t[i], c));
		ret = min(ret, dfs(i + 1, a, b, c + t[i]));
		return dp[i][a][b][c] = ret;
	};

	

	cout << dfs(0, 0, 0, 0) << endl;
}

Measured memory_bytes: 135272
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	string str;cin >> str;
	
	if((str[0] == str[1] && str[1] == str[2])  ||
		(str[1] == str[2] && str[2] == str[3] ))
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
			
		
	
	return 0;
}	

Measured memory_bytes: 256
import java.util.*;

import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int A = Integer.parseInt(tokens[0]);
		int B = Integer.parseInt(tokens[1]);

		if (A < 10 && B < 10) {
			System.out.println(A * B);
		} else {
			System.out.println("-1");
		}
	}
}


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

int main(){
  int n,a;
  cin>>n>>a;
  int memo;
  int ans=0;
  lp(i,n){
    cin>>memo;
    if(memo>a) ans+=memo-a;
  }
  if(ans<=0) cout<<"kusoge"<<endl;
  else cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3088
#include	<stdio.h>

int		main(void)
{
	int rate;

	scanf("%d", &rate);

	if (rate >= 400 && rate <= 599) {
		printf("8\n");
	}
	else if (rate >= 600 && rate <= 799) {
		printf("7\n");
	}
	else if (rate >= 800 && rate <= 999) {
		printf("6\n");
	}
	else if (rate >= 1000 && rate <= 1199) {
		printf("5\n");
	}
	else if (rate >= 1200 && rate <= 1399) {
		printf("4\n");
	}
	else if (rate >= 1400 && rate <= 1599) {
		printf("3\n");
	}
	else if (rate >= 1600 && rate <= 1799) {
		printf("2\n");
	}
	else if (rate >= 1800 && rate <= 1999) {
		printf("1\n");
	}
	else {
	}

	return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define REP(i,e) for (int i = 0; i != int(e); i++)
#define FORIT(i, A) for (auto i : A)
#define ISEQ(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << endl
#define SZ(x) ((int)(x).size())

int main(int argc, char const *argv[])
{
	int a,b,c,d,e,f;
	while(scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) != EOF)
	{
		float ad = (float)d / (float)a;
		float y = ((float)c * ad - (float)f) / ((float)b * ad - (float)e);
		float x = ((float)c - (float)b*y)/(float)a;
		printf("%.3f %.3f\n", x, y);
	}
	return 0;
}

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

bool blocked(char c) {
  return c == '#';
}

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

  string S;
  cin >> S;

  rep(i,A,C-3) {
    if(S.substr(i,2)=="##"){
      cout << "No" << endl;
      return 0;
    }
  }

  for(int i=B; i < D-2; i++) {
    if (S.substr(i,2) == "##") {
      cout << "No" << endl;
      return 0;
    }
  }

  if (C < D) {
    cout << "Yes" << endl;
  } else {
    rep(i,B-2,D-2) {
      if (S.substr(i,3) == "...") {
        cout << "Yes" << endl;
        return 0;
      }
    }
    cout << "No" << endl;
  }

  return 0;
}


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

int main(){
    string str;
    bool ans;
    getline(cin, str);
    while(str != "."){
        stack<int> bra;
        ans = true;
        for(string::iterator it=str.begin();it!=str.end();++it){
            switch(*it){
                case '(':
                    bra.push(1);
                    break;
                case '[':
                    bra.push(0);
                    break;
                case ')':
                    if(bra.empty()) ans = false;
                    else{
                        if(bra.top()!=1) ans = false;
                        bra.pop();
                    }
                    break;
                case ']':
                    if(bra.empty()) ans = false;
                    else{
                        if(bra.top()!=0) ans = false;
                        bra.pop();
                    }
                    break;
            }
            if(!ans) break;
        }
        if(!bra.empty()) ans = false;
        cout << (ans?"yes":"no") << endl;
        getline(cin, str);
    }
}

Measured memory_bytes: 1180
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split())) + [X]
y = list(map(int, input().split())) + [Y]

if X < Y and  max(x) < min(y):
    f = True
else:
    f = False

if f:
    print('No War')
else:
    print('War')



Measured memory_bytes: 3060
N = gets.to_i
As = gets.split.map &:to_i

MOD = 10**9 + 7

sums = []
As.reverse.each do |a|
    sums << ((sums.last || 0) + a) % MOD
end

sums.reverse!

ans = 0
(N-1).times do |i|
    ans += (As[i] * sums[i+1]) % MOD
    ans %= MOD
end

p ans

Measured memory_bytes: 31284
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll N;
    cin >> N;
    ll A[N];
    ll out = 0;
    ll cnt_minus = 0;
    ll cnt_zero = 0;
    ll minimum = 1000000000;
    rep(i,N){
        cin >> A[i];
        out += abs(A[i]);
        if(A[i]==0) cnt_zero++;
        else if(A[i]<0) cnt_minus++;
        minimum = min(minimum,abs(A[i]));
    }
    if(cnt_zero==0&&cnt_minus%2==1) out -= 2*minimum;
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 4328
#include "stdio.h"
#include "math.h"
#include <algorithm>
#include <vector>
using namespace std;

int size = 1;
vector<int> val;
vector<int> lazy;

void lazyPropagate(int p) {
    if (lazy[p] != -1) {
        val[p] = lazy[p];
        if (p < size - 1) {
            lazy[(p * 2) + 1] = lazy[p];
            lazy[(p * 2) + 2] = lazy[p];
        }
        lazy[p] = -1;
    }
}

void update(int l1, int r1, int l2, int r2, int k, int x) {
    if (r1 <= l2 || r2 <= l1) {
        lazyPropagate(k);
        return;
    }
    if (l1 <= l2 && r2 <= r1) {
        lazy[k] = x;
        lazyPropagate(k);
        return;
    }
    int mid = (l2 + r2) / 2;
    lazyPropagate(k);
    update(l1, r1, l2, mid,(k * 2) + 1, x);
    update(l1, r1, mid, r2,(k * 2) + 2, x);
    val[k] = min(val[(k * 2) + 1], val[(k * 2) + 2]);
}

void update(int l, int r, int x) {
    update(l, r, 0, size, 0, x);
}

int getmin(int l1, int r1, int l2, int r2, int k) {
    if (r1 <= l2 || r2 <= l1) {
        return __INT_MAX__;
    }
    if (l1 <= l2 && r2 <= r1) {
        lazyPropagate(k);
        return val[k];
    }
    int mid = (l2 + r2) / 2;
    lazyPropagate(k);
    int ml = getmin(l1, r1, l2, mid,(k * 2) + 1);
    int mr = getmin(l1, r1, mid, r2,(k * 2) + 2);
    return min(ml, mr);
}

int getmin(int l, int r) {
    return getmin(l, r, 0, size, 0);
}

int main(){
    int n,q,command,l,r,value;
    scanf("%d %d",&n,&q);
    for(;size < n;size <<= 1);
    val = vector<int>(size * 2,__INT_MAX__);
    lazy = vector<int>(size * 2, -1);
    
    for(int i = 0;i < q;++i){
        scanf("%d" "%d" "%d",&command,&l,&r);
        // update(s,t,x): as,as+1,...,at をxに変更する。
        if(command == 0){
            scanf("%d",&value);
            update(l,r + 1,value);
        // find(s,t): as,as+1,...,atの最小値を出力する。
        }else{
            printf("%d\n",getmin(l,r + 1));
        }
    }
}



Measured memory_bytes: 5368
#define _USE_MATH_DEFINES

#include <array>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <utility>
#include <tuple>
#include <algorithm>
#include <limits>
#include <fstream>
#include <numeric>
#include <stack>
#include <queue>
#include <list>
#include <cstring>
#include <unordered_set>
#include <cmath>
#include <iomanip>

namespace
{
	template<int N>
	std::array<int, N> GetValue(std::istream& stream)
	{
		std::string buf;
		std::getline(stream, buf);

		std::stringstream sstr(buf);
		std::array<int, N> retval;

		for (int i = 0; i < N; ++i)
		{
			std::getline(sstr, buf, ' ');
			retval[i] = std::stoi(buf);
		}

		return retval;
	}

	std::vector<int> GetValue(std::istream& stream, int num, char delim)
	{
		std::string buf;
		std::getline(stream, buf);
		std::stringstream sstr(buf);

		std::vector<int> retval;
		retval.reserve(num);

		std::string input;;
		for (int i = 0; i < num && std::getline(sstr, input, delim); ++i)
		{
			retval.push_back(std::stoi(input));
		}

		return retval;
	}

	int GetValue(std::istream& stream)
	{
		int in;
		stream >> in;

		return in;
	}

	std::vector<std::string> GetValueString(std::istream& stream, int num, char delim)
	{
		std::string buf;
		std::vector<std::string> retval;
		retval.reserve(num);

		std::getline(stream, buf);
		std::stringstream sstr(buf);

		for (int i = 0; i < num && std::getline(sstr, buf, delim); ++i)
		{
			retval.push_back(std::move(buf));
		}

		return retval;
	}

	template<typename Itr>
	void PrintLine(Itr begin, Itr end)
	{
		bool first = true;

		for (int i = 0; begin != end; ++begin, ++i)
		{
			if (!first)
			{
				std::cout << ' ';
			}

			std::cout << (*begin);

			first = false;
		}
		std::cout << std::endl;
	}

	template<typename T>
	void Print(const std::vector<T>& sequence)
	{
		for (const auto& e : sequence)
		{
			std::cout << e << '\n';
		}

		std::cout << std::flush;
	}

	const int kLen = 1000;
	int c[kLen + 1][kLen + 1] = {};

	int Lcs(std::string x, std::string y)
	{
		int m = x.size();
		int n = y.size();

		int max = 0;

		x = ' ' + x;
		y = ' ' + y;

		for (int i = 1; i <= m; ++i)
		{
			for (int j = 1; j <= n; ++j)
			{
				if (x[i] == y[j])
				{
					c[i][j] = c[i - 1][j - 1] + 1;
				}
				else
				{
					c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);
				}
				max = std::max(max, c[i][j]);
			}
		}

		return max;
	}
}

int main(int argc, char* argv[])
{
	auto file = (argc == 1) ? std::ifstream() : std::ifstream(argv[1]);
	std::istream& stream = (argc == 1) ? std::cin : file;
	if (argc == 1)
	{
		std::cin.tie(0);
		std::ios::sync_with_stdio(false);
	}

	int num;
	stream >> num;
	std::string x, y;

	for (int i = 0; i < num; ++i)
	{
		stream >> x >> y;
		std::cout << Lcs(x, y) << std::endl;
	}
}



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

int main() {
  int N, C = 36;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    int A, D = 0;
    cin >> A;
    while(A % 2 == 0) {
      A /= 2;
      D++;
    }
    if (D < C)
      C = D;
  }
  cout << C;
}

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    int count = 0;
    int total = 0;
    vector<int> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
        total += v[i];
    }

    double threshold = (double) total / (4 * M);
    int res_count = 0;
    for (auto i: v) {
        if (i >= threshold)
            res_count++;
    }

    if (res_count >= M)
        cout << "Yes" << "\n";
    else
        cout << "No" << "\n";
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(a>b){
if(b>c){
printf("%d %d %d\n",c,b,a);
}
else if(b<c){
	if(c<a)
printf("%d %d %d\n",b,c,a);
	else
		printf("%d %d %d\n",b,a,c);
}
else
	printf("%d %d %d\n",b,c,a);
}else if(a<b){
if(b<c){
printf("%d %d %d\n",a,b,c);
}
else if(b>c){
	if(c<a)
printf("%d %d %d\n",c,a,b);
	else
		printf("%d %d %d\n",a,c,b);
}
else
	printf("%d %d %d\n",a,b,c);
}
else{
	if(a>c)
		printf("%d %d %d\n",c,a,b);
	else if(a<c)
		printf("%d %d %d\n",a,b,c);
	else
	printf("%d %d %d\n",b,c,a);
}
}

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

#define ll long long
#define ff first
#define ss second
#define pb push_back

using namespace std;

const int N  = 1e6 + 69, INF = 1e9, mod = 1e9 + 7;

const ll INFLL = 1e18;

int n, K;
ll dp[105][100005], A[N], sum[105][100005];

ll go(ll x){
        x += mod;
        x %= mod;
        return x;
}

int main(){

        cin >> n >> K;

        for(int i = 1; i <= n; i++){
                cin >> A[i];
        }



        dp[0][0] = 1;
        sum[0][0] = 1;
        for(int i = 1; i <= K; i++) sum[0][i] = 1;
        for(int i = 1; i <= n; i++){
                for(int k = 0; k <= K; k++){
                        if(k - A[i] - 1 < 0){
                                dp[i][k] = sum[i-1][k];
                                dp[i][k] = go(dp[i][k]);
                                sum[i][k] = (k == 0) ? dp[i][k] : (sum[i][k-1] + dp[i][k]);
                                sum[i][k] = go(sum[i][k]);
                        } else {
                                dp[i][k] = sum[i-1][k] - sum[i-1][k - A[i] - 1];
                                dp[i][k] = go(dp[i][k]);
                                sum[i][k] = (k == 0) ? dp[i][k] : (sum[i][k-1] + dp[i][k]);
                                sum[i][k] = go(sum[i][k]);
                        }
                        //cout << dp[i][k] << " ";
                }
                //cout << endl;
        }



        cout << dp[n][K] << endl;
}


Measured memory_bytes: 164224
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define MAXN 5010
using namespace std;
const int MOD = 1e9 + 7;
long long dp[MAXN][MAXN],f[MAXN],t[MAXN];
int siz[MAXN];
vector<int> a[MAXN];
void dfs(int x,int fa){
    siz[x] = 1;
    dp[x][1] = 1;
    for(int i = 0;i < a[x].size();i++){
        int u = a[x][i];
        if(u == fa)
            continue;
        dfs(u,x);
        for(int j = 0;j <= siz[x]; ++j){
            t[j] = dp[x][j];
            dp[x][j] = 0;
        }
        for(int j = 0;j <= siz[x]; ++j)
            for(int k = 0;k <= siz[u]; ++k)
                (dp[x][j + k] += t[j] * dp[u][k] % MOD) %= MOD;
        siz[x] += siz[u];
    }
    for(int i = 0;i <= siz[x]; i += 2)
        dp[x][0] = (dp[x][0] - dp[x][i] * f[i] % MOD + MOD) % MOD;
}
int n,u,v;
int main(){
    scanf("%d",&n);
    for(int i = 1;i < n; ++i){
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    f[0] = 1;
    for(int i = 2;i <= n;i += 2)
        f[i] = f[i - 2] * (i - 1) % MOD;
    dfs(1,0);
    printf("%lld",MOD - dp[1][0]);
}


Measured memory_bytes: 195200
N,Q = map(int, input().split())
s = ' ' + input() + '  '

ts,ds = [None]*Q, [None]*Q
for i in range(Q):
    ts[i], ds[i] = input().split()

def getFinalPos(pos):
    for t, d in zip(ts, ds):
        if s[pos]==t:
            if d=='L':
                pos -= 1
            else:
                pos += 1
    return pos


def b_search(l, nr, t):
    if abs(nr - l) <= 1:
        return l
    mid = (nr + l) // 2
    if getFinalPos(mid) == t:
        return b_search(mid, nr, t)
    else:
        return b_search(l, mid, t)

l = b_search(0, N+2, 0)
nr = b_search(N+1, 0, N+1)

print(nr - 1 - l)


Measured memory_bytes: 6588
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  char S;
  int flag = 0;
  for (int i = 0; i < N; i++) {
    cin >> S;
    if (S == 'Y') {
      flag = 1;
      break;
    }
  }
  if (flag == 0) cout << "Three" << endl;
  else cout << "Four" << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n = int(input())
connect_list = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = [ int(v)-1 for v in input().split() ]
    c += 1
    connect_list[a].append((b,c))
    connect_list[b].append((a,c))


q, k = [ int(v) for v in input().split() ]
k -= 1

shortest_list = [-1 for i in range(n)]
shortest_list[k] = 0

searching_list = [k]

while searching_list != []:

    new_search_list = []
    for i in searching_list:
        for j in connect_list[i]:
            x, y = j
            if shortest_list[x] == -1:
                shortest_list[x] = y + shortest_list[i]
                new_search_list.append(x)
    searching_list = new_search_list


for i in range(q):
    a, b = [ int(v)-1 for v in input().split() ]
    print(shortest_list[a] + shortest_list[b])


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

int main() {
    double n;
    cin >> n;
    double a = n / 3;
    double ans = a * a * a;
    printf("%.10lf\n", ans);
}

Measured memory_bytes: 256
import bisect
n = int(input())
S = input()
r = []
g = []
b = []
for i, s in enumerate(S):
    if s == "R":
        r.append(i)
    elif s == "G":
        g.append(i)
    else:
        b.append(i)

# print(s, r, g, b)
ans = len(r) * len(g) * len(b)
i = 0
j = 1
while i + 2 * j < n:
    while i + 2 * j < n:
        if S[i] != S[i + j] != S[i + 2 * j] != S[i]:
            ans -= 1
        i += 1
    j += 1
    i = 0

print(ans)

Measured memory_bytes: 68044
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
parity = [-1 for _ in range(n)]
valid = True

def dfs(x):
	global valid
	p = parity[x]
	for v in adj[x]:
		if parity[v] < 0:
			parity[v] = 1^p
			dfs(v)
		elif parity[v] == p:
			valid = False
			return
	return

for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

parity[0] = 0
dfs(0)
if not valid:
	print((n*(n-1)//2) - m)
else:
	o = sum(parity)
	print((n*(n-1)//2) - m - (o*(o-1)//2) - ((n-o)*(n-o-1)//2))

Measured memory_bytes: 40240
al=[*?a..?z]
h=Hash.new 0
s=gets.chomp
s.length.times do |i|
  h[s[i]] += 1
end
c = s.length * (s.length - 1) / 2
h.each do |e,v|
  c -= v*(v-1)/2
end
p c+1


Measured memory_bytes: 2172
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M = lr()
    t = [False for _ in range(N)]
    u = ['e' for _ in range(N)]
    for i in range(M):
        s, c = lr()
        if t[s-1] == False or u[s-1] == str(c):
            u[s-1] = str(c)
            t[s-1] = True
        else:
            print(-1)
            return
    ans = ''
    if N == 1 and u[0] == 'e':
        print(0)
        return
    elif N == 2 and u[0] == 'e':
        if u[1] == 'e':
            print(10)
            return
        else:
            print('1'+u[1])
            return
    elif N == 2 and u[0] == '0':
        print(-1)
        return
    elif N == 3 and u[0] == 'e':
        if u[1] == 'e':
            if u[2] == 'e':
                print('100')
                return
            else:
                print('10'+u[2])
                return
        elif u[1] == '0':
            if u[2] == 'e':
                print('100')
            else:
                print('10'+u[2])
        else:
            if u[2] == 'e':
                print('1'+u[1]+'0')
                return
            else:
                print('1'+u[1]+u[2])
                return
    elif N == 3 and u[0] == '0':
        print(-1)
        return
    for i in range(N):
        if u[i] == 'e':
            u[i] = '0'
        ans += u[i]
    print(ans)
resolve()

Measured memory_bytes: 3188
#include <iostream>

using namespace std;

int main()
{
    string S, T; cin >> S >> T;
    bool ans = false;
    for (int i = 0; i < S.size(); ++i) {
        if (S == T) { ans = true; break; }
        S = S.back() + S.substr(0, S.size()-1);
    }
    if(ans) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

typedef struct {
	double x,y,z;
	int seen;
} star_t;

int star_num;
star_t stars[500];

int main(void) {
	int boenkyo_num;
	double bx,by,bz,br;
	double cosine;
	int i,j;
	int count;
	while(1) {
		scanf("%d",&star_num);
		if(star_num==0)break;
		for(i=0;i<star_num;i++) {
			scanf("%lf%lf%lf",&stars[i].x,&stars[i].y,&stars[i].z);
			stars[i].seen=0;
		}
		scanf("%d",&boenkyo_num);
		count=0;
		for(i=0;i<boenkyo_num;i++) {
			scanf("%lf%lf%lf%lf",&bx,&by,&bz,&br);
			for(j=0;j<star_num;j++) {
				if(stars[j].seen)continue;
				cosine=(stars[j].x*bx+stars[j].y*by+stars[j].z*bz)/
					sqrt(stars[j].x*stars[j].x+stars[j].y*stars[j].y
						+stars[j].z*stars[j].z)/
					sqrt(bx*bx+by*by+bz*bz);
				if(cosine>=cos(br)) {
					stars[j].seen=1;
					count++;
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 0