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

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

using namespace std;

void setIO(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

const ld PI = 4*atan((ld)1);
const int INF = 1e9+7;
const int mxn = 107;

int a[mxn];

int main(){
	setIO();
	int n, m, sum=0;
	cin>>n>>m;
	for (int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	double mn = (double)sum/4/m, ct=0;
	for (int i=0;i<n;i++){
		if (a[i] >= mn) ct++;
	}
	if(ct>=m) cout<<"Yes\n";
	else cout<<"No\n";
}

Measured memory_bytes: 3656
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

struct Graph{
    struct Edge{
        int cost, from, dest;
        Edge(int cost, int dest): cost(cost), from(-1), dest(dest){ }
        Edge(int cost, int from, int dest): cost(cost), from(from), dest(dest){ }
        ostream& operator >> (ostream& out){
            return out << '(' << cost << ':' << from << ' ' << dest << ')';
        }
    };
    struct Node{
        vector<Edge> edges;
        ll height = 0;
    };
    vector<Node> nodes;
    Graph(int num): nodes(num){ }
    // vector<Edge> edges;
    // Graph(int nn, int en = 10): nodes(nn){
    //     edges.reserve(en);
    // }
    // void addEdge(int from, int dest, ll cost = 1){
    //     nodes[from].outEdges.emplace_back(edges.size());
    //     edges.emplace_back(from, dest, limit);
    // }
    void addEdge(int from, int dest, int cost = 1){
        nodes[from].edges.emplace_back(cost, dest);
    }
    void addEdge2(int from, int dest, int cost = 1){
        addEdge(from, dest, cost);
        addEdge(dest, from, cost);
    }
    void dfs(int idx, ll height, int from = -1){
        nodes[idx].height = height;
        for(auto& e : nodes[idx].edges){
            if(e.dest == from){ continue; }
            dfs(e.dest, height + e.cost, idx);
        }
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    Graph g(n);
    for(int i = 0; i < n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g.addEdge2(a, b, c);
    }
    int q, k;
    cin >> q >> k;
    k--;
    g.dfs(k, 0);
    for(int i = 0; i < q; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << g.nodes[x].height + g.nodes[y].height << '\n';
    }
}


Measured memory_bytes: 14336
#include <vector>
#include <cstdio>
#define REP(i, a, b) for (int i=(a); i<(b); ++i)
#define rep(i, n) REP(i, 0, n)
using namespace std;
int main()
{
	for (int T=1, n; ~scanf("%d", &n), n; ++T) {
		vector<vector<int> > a(n, vector<int>(n, 0));
		int r = 0, c = 0, k = 1;
		a[r][c++] = k++;
		while (!a[n-1][0]) {
			while (0<=r && r<n && 0<=c && c<n) a[r++][c--] = k++;
			if (c < 0) c = 0;
			while (0<=r && r<n && 0<=c && c<n) a[r--][c++] = k++;
			if (r < 0) r = 0;
		}
		if (n % 2 == 0) {
			r--; c++;
			while (!a[n-1][n-1]) {
				while (0<=r && r<n && 0<=c && c<n) a[r--][c++] = k++;
				r+=2, c--;
				while (0<=r && r<n && 0<=c && c<n) a[r++][c--] = k++;
				r--, c+=2;
			}
		}
		else {
			r++; c--;
			while (!a[n-1][n-1]) {
				while (0<=r && r<n && 0<=c && c<n) a[r++][c--] = k++;
				r--, c+=2;
				while (0<=r && r<n && 0<=c && c<n) a[r--][c++] = k++;
				r+=2, c--;
			}
		}

		printf("Case %d:\n", T);
		rep(i, n) {
			rep(j, n) printf("%3d", a[i][j]);
			puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>

int main()
{
	int N, M;
	std::vector<std::pair<int, std::vector<int>>> bulbs;

	std::cin >> N >> M;
	bulbs.resize(M);
	for (auto& bulb : bulbs) {
		int k;
		std::cin >> k;
		bulb.second.resize(k);
		for (auto& sw : bulb.second) {
			std::cin >> sw;
			--sw;
		}
	}
	for (auto& bulb : bulbs) {
		std::cin >> bulb.first;
	}

	int result = 0;
	for (int i = 0; i < 1 << N; ++i) {
		for (auto& bulb : bulbs) {
			int p = bulb.first;
			int s = 0;
			for (auto& sw : bulb.second) {
				if ((i >> sw) & 1)
					++s;
			}
			if (p != (s & 1))
				goto no_on;
		}
		++result;
	no_on:
		;
	}
	
	std::cout << result << "\n";
}


Measured memory_bytes: 256
/*
 
श्रीगुरु चरन सरोज रज
निजमनु मुकुरु सुधारि
बरनउँ रघुबर बिमल जसु
जो दायकु फल चारि
बुद्धिहीन तनु जानिके, सुमिरौं पवन-कुमार
बल बुधि बिद्या देहु मोहिं, हरहु कलेस बिकार 
 
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD (ll)1000000007

ll dp[1001][1001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s, t;
    cin >> s >> t;
    cout << (s[0] == t[0]) + (s[1] == t[1]) + (s[2] == t[2]);
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define UB upper_bound
#define LB lower_bound
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define be(a) (a).begin(),(a).end()
#define deb(x) cout<< #x <<" "<<endl;
#define deb2(x, y) cout<< #x <<" "<< x <<endl<< #y <<" "<<y<<endl
#define fo(i, n) for(long long i=0; i<n; i++)
#define Fo(i, n, k) for(long long i=k; i<n; i++)
#define mod 1000000007
#define int long long

typedef long long ll;

void fileIO()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
 
typedef vector<pair<int, int>> vll;
typedef unordered_map<int, int> ump;

double dp[3001][1502];

bool sortbysecdesc(const pair<int, int> &a, 
                    const pair<int, int> &b) 
{ 
    return a.second>b.second;
}

// double coins(double p[], double prod[], int n, int k)
// {
//     double ans;
//     if(n == 0 || k == 0)ans = 1.0;    
//     else if(n < k)ans =  0.0;
//     else if(n == k)ans = prod[n-1];
//     else
//     {
//         double one = 1.0;
//         ans =  (p[n-1]*coins(p, prod, n-1, k-1) + (one - p[n-1])*coins(p, prod, n-1, k));
//     }


//      return ans;

    
    
    

// }



int32_t main()
{
    IOS;
    fileIO();
    int T;
    T = 1;
    //cin>>T;

    while(T--)
    {
        int n;
        cin>>n;
        double *p = new double[n];
        for(int i = 0; i<n; i++)cin>>p[i];

        double *prod = new double[n];
        prod[0] = p[0];
        for(int i = 1; i<n; i++) prod[i] = p[i]*prod[i-1];

        int k = (n/2) + 1;

        double one = 1.0;


        cout<<std::fixed;


        for(int i = 0; i<=k; i++) dp[0][i] = 1.0;
        for(int i = 0; i<=n; i++) dp[i][0] = 1.0;

        for(int i = 1; i<=n; i++)
        {
            for(int j = 1; j<=k; j++)
            {
                if(i<j) dp[i][j] = 0;
                else if(i == j)dp[i][j] = prod[i-1];
                else
                {
                    dp[i][j] = p[i-1]*dp[i-1][j-1] + (one - p[i-1])*dp[i-1][j];
                }
            }
        }

        // double res = coins(p, prod, n, k);

        // cout<<res<<"\n";

        cout<<setprecision(10)<<dp[n][k]<<"\n";

    }
    
    return 0;
}



Measured memory_bytes: 39008
#include <bits/stdc++.h>
#define db(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl;
#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define MOD 1000000007
#define FOR(i, n) for(ll i = 0; i < n; i++)
using namespace std;
const long long INF = 3*1e18;

int main() {
    ios::sync_with_stdio(0);    
    cin.tie(0);
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N), B(N);
    for(ll i = 0; i < N; i++) cin >> A[i];
    B[0] = 0;
    for(ll i = 1; i < N; i++){
        ll count = 0, ans = INT_MAX;
        for(ll j = i-1; j >= 0; j--){
            ++count;
            ans = min(ans, abs(A[i] - A[j]) + B[j]);
            if(count >= K) break;
        }
        B[i] = ans;
    }
    cout << B[N-1] << "\n";
}

Measured memory_bytes: 1792
n,k = map(int,input().split())


import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for i in range(1,k+1):
    if n-k+1>=i:
        red = combinations_count(n-k+1,i)
    else:
        red = 0
    
    ls = [int(x) for x in range(1,)]

    
    print((red*combinations_count(k-1,i-1))%(10**9+7))

Measured memory_bytes: 70488
#include <bits/stdc++.h>
using namespace std;
int h, w, n, s1, s2;
bool check(int dr, int dl, int du, int dd) {
	if (dr<0)
		return false;
	if (dl<0)
		return false;
	if (du<0)
		return false;
	if (dd<0)
		return false;
	return true;
}

int main() {
	cin >> h >> w >> n >> s1 >> s2;
	string s, t;
	cin >> s >> t;
	int dr = w-s2, dl =s2-1, du =s1-1 , dd = h-s1;
	for (int i = 0;i < n;i++) {
		if (s[i] == 'L')
			dl--;
		if (s[i] == 'R')
			dr--;
		if (s[i] == 'U')
			du--;
		if (s[i] == 'D')
			dd--;
		if (!check(dr, dl, du, dd)) {
			cout << "NO" << endl;
			return 0;
		}
		if (t[i] == 'L'&&dr<w-1)
			dr++;
		if (t[i] == 'R'&&dl<w-1)
			dl++;
		if (t[i] == 'U'&&dd<h-1)
			dd++;
		if (t[i] == 'D'&&du<h-1)
			du++;
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 776
#include <stdio.h>

int main(){
    int t[101][101], r, c, i, j, sum, total = 0;
    scanf("%d%d", &r, &c);
    for(i=0; i<r; i++) for(j=0; j<c; j++) scanf("%d", &t[i][j]);
    for(i=0; i<r; i++){
        sum = 0;
        for(j=0; j<c; j++){
            sum += t[i][j];
                        total += t[i][j];
        }
        t[i][j] = sum;
    }
        t[r][c] = total;
    for(j=0; j<c; j++){
        sum = 0;
        for(i=0; i<r; i++){
            sum += t[i][j];
        }
        t[i][j] = sum;
    }
    for(i=0; i<=r; i++){
        for(j=0; j<c; j++){
            printf("%d ", t[i][j]);
        }
        printf("%d\n", t[i][j]);
    }
    return 0;
}


Measured memory_bytes: 2100
#include<stdio.h>
int main ()
{
    int A,B,sum,prod,dif;
    scanf("%d %d",&A,&B);
    sum=A+B;
    prod=A*B;
    dif=A-B;
    if(sum>prod&&sum>dif){
        printf("%d",sum);
    }
    else if(prod>sum&&prod>dif){
        printf("%d",prod);
    }
    else{
        printf("%d",dif);
    }
}


Measured memory_bytes: 1692
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    ans = 0

    for i, (a, b) in enumerate(D[:-1]):
        for t in range(T - 1, a - 1, -1):
            if dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b
        if ans < dp[T - 1] + D[i + 1][1]:
            ans = dp[T - 1] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9600
#!/usr/bin/env ruby
# coding: utf-8

g = ARGF.gets.split.map(&:to_i).map do |x|
  (x == 1) ? 300000 : (x == 2) ? 200000 : (x == 3) ? 100000 : 0
end
if g[0] == 300000 && g[1] == 300000
  g[0] += 400000
end
puts g[0] + g[1]


Measured memory_bytes: 1788
# coding: utf-8
import collections

n = int(input().strip())
vs = [int(s) for s in input().strip().split()]

e = [vs[i*2] for i in range(n//2)]
o = [vs[i*2+1] for i in range(n//2)]

e_counter = collections.Counter(e).most_common()
o_counter = collections.Counter(o).most_common()

e1, e1_count = e_counter[0]
try:
    e2, e2_count = e_counter[1]
except IndexError:
    e2_count = 0

o1, o1_count = o_counter[0]
try:
    o2, o2_count = o_counter[1]
except IndexError:
    o2_count = 0

if e1 != o1:
    keep_num_count = e1_count + o1_count
else:
    keep_num_count = e1_count + o2_count
    if keep_num_count < e2_count + o1_count:
        keep_num_count = e2_count + o1_count

print(n - keep_num_count)


Measured memory_bytes: 21084
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <ctype.h>
#include <limits>
#include <numeric>
#include <type_traits>
using namespace std;
int start;
int n;
vector<int> x,d;
int res;

int gcd2(int a, int b){
    int tmp;
    int r;
    if (a < b)
    {
        tmp = a;
        a = b;
        b = tmp;
    }

    r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

int main(void)
{
    cin >> n >> start;
    int tmp;
    //cin >> tmp;
    x.push_back(start);
    for(int i = 1; i <= n; i++)
    {
        cin >> tmp;
        x.push_back(tmp);
    }
    
    if(n == 1){
        cout << abs(x[1] - x[0]);
        return 0;
    }

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

    for (int i = 1; i <= n; i++)
    {
        d.push_back(x[i] - x[i-1]);
    }

    res = gcd2(d[0], d[1]);


    for (int i = 2; i <= n-1; i++)
    {

        res = gcd2(d[i],res);
    }
    
    cout << res;
    return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>
#include <stdlib.h>


int main(void){
	int a,b,c,n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d %d %d",&a,&b,&c);
		a=a*a;
		b=b*b;
		c=c*c;
		if(a==b+c || b==a+c || c==a+b){
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
}

Measured memory_bytes: 1008
//include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring> 
#define db double 
#define LL long long
//#define int LL
#define rep(i,x,y) for (int i=x;i<=y;++i)

using namespace std;
//const int N  =  
int a,b;
//const int mod = ;
void read(int &x)
{
	int f=1;
	x=0;
	char ch=getchar();
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
	return ;
}
signed main()
{
	read(a);read(b);
	if (a+b==15) printf("+");
	else if (a*b==15) printf("*");
	else printf("x");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;

int n;
int parent[100000];
vector<int> child[100000];
int dp[100000] = {};

int depth(int i){
	//if(dp[i] != 0) return dp[i];
	if(parent[i] == -1) return 0;
	return dp[i] = depth(parent[i]) + 1;
}

int main(){
	cin >> n;
	for(int i=0; i<n; i++) parent[i] = -1;
	for(int i=0; i<n; i++){
		int id,k;
		cin >> id >> k;
		for(int j=0; j<k; j++){
			int c;
			cin >> c;
			child[id].push_back(c);
			parent[c] = id;
		}
	}

	for(int i=0; i<n; i++){
		cout << "node " << i << ": ";
		cout << "parent = " << parent[i] << ", ";
		cout << "depth = " << depth(i) << ", ";
		if(parent[i] == -1) cout << "root, ";
		else if(child[i].size() > 0) cout << "internal node, ";
		else cout << "leaf, ";
		cout << "[";
		for(int j=0; j<child[i].size(); j++){
			if(j != 0) cout << ", ";
			cout << child[i][j];
		}
		cout << "]" << endl;
	}
}


Measured memory_bytes: 6932
#include<bits/stdc++.h>
///...................................*****.................................................///
///        Author :  MD. Rakibul Islam ( mmdrakibul2912@gmail.com )                         ///
///                  Department of Computer Science                                         ///
///                  & Engineering,                                                         ///
///                  Comilla University , Bangladesh.                                       ///
///...................................*****.................................................///
using namespace std;
int main()
{
    int n, m, i, j, k, l;
    cin>>n;
    int a[n+2], b[n+2], c[n+2]={0};
    for(i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(i=0; i<n; i++)
    {
        cin>>b[i];
    }
    int tot=0, res=0;
    for(i=0; i<n; i++)
    {
        if(a[i]-b[i]>0)
            {tot+=a[i];
            res+=b[i];}
    }
    /*int mx=0, mx1=0;
    int pos=0, pos1=0;
    for(i=0; i<n; i++)
    {
       if(c[i]>mx)
       {
           mx=c[i];
           pos=i;
       }
    }
    for(i=0; i<n; i++)
    {
       if(c[i]>mx1 && c[i]<mx)
       {
           mx1=c[i];
           pos1=i;
       }
    }*/
    cout<<tot-res<<endl;
    return 0;
}


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

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

  for (int i=1; i<n-1; ++i) {
    ans.at(i) = price_before-abs(a.at(i)-a.at(i-1))-abs(a.at(i+1)-a.at(i))+abs(a.at(i+1)-a.at(i-1));
  }
  ans.at(0) = price_before-abs(a.at(0))-abs(a.at(1)-a.at(0))+abs(a.at(1));
  ans.at(n-1) = price_before-abs(a.at(n-1)-a.at(n-2))-abs(a.at(n-1))+abs(a.at(n-2));
  
  for (int i=0; i<n; ++i) {
    cout << ans.at(i) << endl ;
  }
}

Measured memory_bytes: 2048
#include<iostream>

using namespace std;

int main()
{
	int n, max = 0, sum = 0;
	cin >> n;
	for (int i = 0, j;i < n;i++)
	{
		cin >> j;
		sum += j;
		if (max < j)
			max = j;
	}
	if (max < sum - max)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}

Measured memory_bytes: 3604
//#include "IntMod.h"
//typedef IntMod<1000000007> MInt;

//#include "Union_Find.h"

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>

using namespace std;
#define REP(i,a,n) for(int i = a; i < (int)n; ++i)
#define REPM(i,n,a) for(int i = n - 1; i >= a; --i)
#define EPS 0.0001
#define INF 0x3FFFFFFF
#define INFLL 0x3FFFFFFF3FFFFFFF
#define INFD 1.0e+308
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;

#if 1
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#endif

int H, W;
int N;
int A[10001];

int field[101][101];

void input() {
	cin >> H >> W >> N;
	REP(i, 0, N) {
		cin >> A[i];
	}
	return;
}

void solve() {
	int k = 0;
	REP(i, 0, H) {
		if (i % 2 == 0) {
			REP(j, 0, W) {
				field[i][j] = k;
				A[k]--;
				if (A[k] <= 0) k++;
			}
		}else{
			REPM(j, W, 0) {
				field[i][j] = k;
				A[k]--;
				if (A[k] <= 0) k++;
			}
		}
	}
	return;
}

void output() {
	REP(i, 0, H) {
		REP(j, 0, W) {
			printf("%d%c", field[i][j] + 1, j == W - 1 ? '\n' : ' ');
		}
	}
	return;
}

int main() {
	input();
	solve();
	output();
	return 0;
}

Measured memory_bytes: 384
n,m = map(int, input().split())
import math
import collections
def tds(n):
    prime_count = collections.Counter()
    
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    return prime_count
c=tds(m)
ans=1
def C(n,r):
    res=1
    for i in range(n,n-r,-1):
        res*=i
    return res//math.factorial(r)
for ci in c.values():
    ans*=C(n+ci-1,ci)
    ans%=10**9+7
print(int(ans))

Measured memory_bytes: 3436
s = int(input())

def f(n):
    data = [0, 0, 1, 1, 1]
    if (n == 1) | (n == 2):
        return 0
    elif n == 3:
        return 1
    elif n == 4:
        return 1
    elif n == 5:
        return 1
    elif n > 5:
        for i in range(6, n + 1):
            a = (data[i - 2] + data[i - 4]) % (10**9 + 7)
            data.append(a)
        return data[n - 1]

print(f(s))

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

// macros
#define overload_rep(va_0, va_1, va_2, name, ...) name
#define rep_0(i, n) for(int i = 0; i < (n); ++i)
#define rep_1(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep(...) overload_rep(__VA_ARGS__, rep_1, rep_0)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
void debug_cerr() { cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail) {
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// libraries

// declarations
typedef long long lint;
constexpr int mx = 100000;
constexpr lint inf = 1ll << 60;

int N, memov = -1, memoid = -1;
struct edge{ int to, id; };
vector<edge> graph[mx];
vector<int> cnt[mx];
lint answer[mx - 1];
lint S[mx];

int calc(int v, int p){
    int res = 0;
    for(const edge& e : graph[v]){
        if(e.to == p)cnt[v].push_back(0);
        else {
            int t = calc(e.to, v);
            res += t;
            cnt[v].push_back(t);
        }
    }
    return res + 1;
}

void propagate(int v, int p, int prop){
    int sz = graph[v].size(), sum = 0;
    rep(i, sz){
        if(graph[v][i].to == p){
            cnt[v][i] = prop;
            if(2 * prop != N){
                answer[graph[v][i].id] = (S[v] - S[p]) / (2 * prop - N);
            } else {
                memov = v;
                memoid = graph[v][i].id;
            }
        }
        sum += cnt[v][i];
    }
    rep(i, sz){
        int u = graph[v][i].to;
        if(u != p)propagate(u, v, sum - cnt[v][i] + 1);
    }
}

// solve
int main() {

    cin >> N;
    rep(i, N - 1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back({ b, i });
        graph[b].push_back({ a, i });
    }

    rep(i, N)cin >> S[i];
    calc(0, -1);
    propagate(0, -1, -1);

    if(memov != -1){
        vector<lint> dist(N, inf);
        dist[memov] = 0;
        priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> que;
        que.push(make_pair(0, memov));
        while(!que.empty()){
            int v; lint d;
            tie(d, v) = que.top();
            que.pop();
            if(d > dist[v])continue;
            for(const edge& e : graph[v]){
                if(chmin(dist[e.to], d + answer[e.id])){
                    que.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        answer[memoid] = (S[memov] - accumulate(all(dist), 0ll)) / (N / 2);
    }

    rep(i, N - 1)cout << answer[i] << '\n';
    return 0;

}


Measured memory_bytes: 22912
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

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

signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  
  Int a,b;
  cin>>a>>b;
  Int ans = gcd(a, b);
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3140
function Main(input) {
  lines = input.split("\n")
  S = lines[0].split("")
  a = {}
  for (var i = 0; i < S.length ; i++) {
    if (!a[S[i]]) {
      a[S[i]] = 0
    }      
    a[S[i]] += 1
  }
  cnt = 0
  bool = true
  for (var k in a) {
    if (a[k] != 2) {
        bool = false
    }
    cnt++
  }
  if (cnt != 2) {
      bool = false
  }
  ans = bool ? 'Yes' : 'No'
  console.log(ans)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 300000;
const ll INF = (1LL<<60);
ll f[MAXN + 5], g[MAXN + 5], h[MAXN + 5];
ll S[MAXN + 5], T[MAXN + 5];
ll fk(int i) {return i;}
ll fx(int j) {return 2LL*j;}
ll fc(int i) {return 1LL*i*i + i - 2*S[i];}
ll fy(int j) {return 2*S[j] + f[j] - j + 1LL*j*j;}
double fslope(int p, int q) {return 1.0*(fy(q) - fy(p)) / (fx(q) - fx(p));}
ll gk(int i) {return -i;}
ll gx(int j) {return -2LL*j;}
ll gc(int i) {return 1LL*i*i - i + 2*S[i-1];}
ll gy(int j) {return -2*S[j-1] + g[j] + j + 1LL*j*j;}
double gslope(int p, int q) {return 1.0*(gy(q) - gy(p)) / (gx(q) - gx(p));}
int stk[MAXN + 5], tp;
int N, M;
void get_dp() {
	f[0] = 0; stk[tp = 1] = 0;
	for(int i=1;i<=N;i++) {
		while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) )
			tp--;
		f[i] = max(f[i - 1], fc(i) - fk(i)*fx(stk[tp]) + fy(stk[tp]));
		while( tp > 1 && fslope(i, stk[tp]) >= fslope(stk[tp], stk[tp-1]) )
			tp--;
		stk[++tp] = i;
	}
	g[N + 1] = 0; stk[tp = 1] = N + 1;
	for(int i=N;i>=1;i--) {
		while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) )
			tp--;
		g[i] = max(g[i + 1], gc(i) - gk(i)*gx(stk[tp]) + gy(stk[tp]));
		while( tp > 1 && gslope(i, stk[tp]) >= gslope(stk[tp], stk[tp-1]) )
			tp--;
		stk[++tp] = i;
	}
}
ll tmp[MAXN + 5];
void divide_conquer(int l, int r) {
	if( l == r ) {
		h[l] = f[l + 1] - 2*T[l] + g[r + 1] + 2;
		return ;
	}
	int mid = (l + r) >> 1;
	divide_conquer(l, mid);
	divide_conquer(mid + 1, r);
	stk[tp = 1] = l - 1;
	for(int i=l;i<mid;i++) {
		while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) )
			tp--;
		while( tp > 1 && fslope(i, stk[tp]) >= fslope(stk[tp], stk[tp-1]) )
			tp--;
		stk[++tp] = i;
	}
	for(int i=mid+1;i<=r;i++) {
		while( tp > 1 && fk(i) >= fslope(stk[tp], stk[tp-1]) )
			tp--;
		tmp[i] = fc(i) - fk(i)*fx(stk[tp]) + fy(stk[tp]) + g[i + 1];
	}
	ll p = -INF;
	for(int i=r;i>mid;i--) {
		p = max(p, tmp[i]);
		h[i] = max(h[i], p);
	}
	stk[tp = 1] = r + 1;
	for(int i=r;i>mid+1;i--) {
		while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) )
			tp--;
		while( tp > 1 && gslope(i, stk[tp]) >= gslope(stk[tp], stk[tp-1]) )
			tp--;
		stk[++tp] = i;
	}
	for(int i=mid;i>=l;i--) {
		while( tp > 1 && gk(i) >= gslope(stk[tp], stk[tp-1]) )
			tp--;
		tmp[i] = gc(i) - gk(i)*gx(stk[tp]) + gy(stk[tp]) + f[i - 1];
	}
	p = -INF;
	for(int i=l;i<=mid;i++) {
		p = max(p, tmp[i]);
		h[i] = max(h[i], p);
	}
}
int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++)
		scanf("%lld", &T[i]), S[i] = S[i - 1] + T[i];
	get_dp(), divide_conquer(1, N);
	scanf("%d", &M);
	for(int i=1;i<=M;i++) {
		int P, X; scanf("%d%d", &P, &X);
		printf("%lld\n", max(f[P-1] + g[P+1], h[P] + 2*T[P] - 2*X)/2);
	}
}

Measured memory_bytes: 17792
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<queue>
#define MM 1000000007
int x[200000],y[200000],z[200000];
using namespace std;
int main(void)
{
	int i,j,mx,mi,n,mx2,mx3;
	scanf("%d",&n);
	for(i=0;i<n;i++)	scanf("%d %d",&x[i],&y[i]);
	mx=-2100000000;	mi=2100000000;
	for(i=0;i<n;i++)	{
		z[i]=x[i]+y[i];
		mx=max(mx,z[i]);
		mi=min(mi,z[i]);
	}
	mx2=mx-mi;
	mx=-2100000000;	mi=2100000000;
	for(i=0;i<n;i++)	{
		z[i]=x[i]-y[i];
		mx=max(mx,z[i]);
		mi=min(mi,z[i]);
	}
	mx3=mx-mi;
	mx=max(mx3,mx2);
	printf("%d\n",mx);
	return 0;
}

Measured memory_bytes: 4068
#include<stdio.h>
int main(){
  int a,b,c,d,tr,bu;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  
  if(a<=b)
    tr=a;
  else tr=b;
  
  if(c<=d)
    bu=c;
  else bu=d;
  
  printf("%d",bu+tr);
}

Measured memory_bytes: 128
#include <iostream>

int main(){
   int a, b;
   std::cin >> a >> b;

   int n = a * 10;
   if(b/10!=0) n *= 10;
   if(b/100!=0) n *= 10;
   n += b;
   for(int i=1; i<317; ++i){
      if(i*i==n) {
	 std::cout << "Yes" << std::endl;
	 return 0;
      }
   }
   std::cout << "No" << std::endl;
   return 0;
}


Measured memory_bytes: 256
import sys
n=int(input())
s=[[int(i) for i in l.split()] for l in sys.stdin]
for cx in range(101):
  for cy in range(101):
    flag=True
    Z=10**18
    for i in range(n):
      x,y,h=s[i]
      if h!=0 and flag:
        H=abs(x-cx)+abs(y-cy)+h
        flag=False
      elif h!=0 and flag==False:
        if H!=abs(x-cx)+abs(y-cy)+h:
          H=10**18+1
          break
      elif h==0:
        Z=min(Z,abs(x-cx)+abs(y-cy)+h)
    if H<=Z:
      print(cx,cy,H)
      exit()


Measured memory_bytes: 3064
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i;
  int a[100],n;
  while(cin>>n&&n){
    for(i=0;i<n;i++){
      int p,q,r,s,t;
      cin>>p>>q>>r>>s>>t;
      a[i]=p+q+r+s+t;
    }
    sort(a,a+n);
    cout<<a[n-1]<<" "<<a[0]<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define __ ios_base::sync_with_stdio(0);cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define forn(i,a,n) for(int i=a; i < n; i++)
typedef long long int lli;
typedef long double Double;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod = 1e9+7;

int main(){__
	int c;
	cin >> c;
	if(c >= 30) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}



Measured memory_bytes: 3604
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] S = new int[m][n];
        int[] P = new int[m];
        int ans = 0;
        for(int i = 0; i < m; i++) {
            int k = sc.nextInt();
            for(int j = 0; j < k; j++) S[i][j] = sc.nextInt();
        }
        for(int i = 0; i < m; i++) P[i] = sc.nextInt();

        for(int i = 0; i < (1 << n); i++) {
            int c1 = 0;
            for(int j = 0; j < m; j++) {
                int c2 = 0;
                for(int sft : S[j]) {
                    if(sft > 0) {
                         c2 += (i >> (n - sft)) & 1;
                    }
                }
                if(c2 % 2 == P[j]) c1++;
            }
            if(c1 == m) ans++;
        }
        System.out.println(ans);
    }
}


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

void solve()
{
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    int ans = 0;
    ll ss = v.front(), mod = 1e9+7;
    for (int i = 1; i < n; ++i) {
        ans = (ans + (v[i] * ss % mod)) % mod;
        ss = (ss + v[i]) % mod;
    }
    cout << ans << '\n';
}

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

Measured memory_bytes: 3984
import sys
import os

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = list(map(int, sys.stdin.buffer.readline().split()))
    even = (N * (N - 1)) // 2
    odd = 0 if M == 1 else (M * (M - 1)) // 2
    print(even + odd)


if __name__ == '__main__':
    main()


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

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

  vector<int> DP(N);
  for (int i = 1; i < N; i++) {
    if (i == 1) {
      DP[1] = abs(H[1] - H[0]);
      continue;
    }
    int step = abs(H[i] - H[i - 1]) + DP[i - 1];
    int skip = abs(H[i] - H[i - 2]) + DP[i - 2];
    if (step < skip) DP[i] = step;
    else DP[i] = skip;
  }

  cout << DP[N - 1] << endl;
}


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

class Program {
    static void Main(string[] args) {
        string s = Cin.Next();

        foreach (var item in s) {
            if(item== '9') {
                Console.WriteLine("Yes");
                return;
            }
        }
        Console.WriteLine("No");
    }
}


public class Cin {
    private static string[] s = new string[0];
    private static int i = 0;

    private static char[] cs = new char[] { ' ' };

    public static string Next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return Next();
    }

    public static int Ni() {
        return int.Parse(Next());
    }

    public static long NextLong() {
        return long.Parse(Next());
    }

    public static double NextDouble() {
        return double.Parse(Next());
    }

}


Measured memory_bytes: 11092
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}
}
mod math {

use std;
use std::cmp;
use std::ops;

pub fn gcd<T>(a: T, b: T) -> T
where
    T: ops::Add<Output = T> + ops::Rem<Output = T> + ops::Div<Output = T> + cmp::PartialEq + Copy,
{
    if b + b == b {
        return a;
    }
    gcd(b, a % b)
}

}

use input::*;
use math::*;

fn main() {
    let n: usize;
    input!(n);
    let v = input_vector::<usize>();
    let mut ans = v[0];
    for z in v {
        ans = gcd(ans, z);
    }
    p(ans);
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
  int N;
  cin>>N;
  std::vector<int> v(N);
  for(int i=0;i<N;i++)cin>>v[i];
  int out=0;
  if(v[N-1]>2)out++;
  int mi=2;
  int ma=2;
  int kmin,kmax;
  for(int i=N-1;i>=0;i--){
    if(ma<v[i])out++;
    kmin=((mi-1)/v[i]+1)*v[i];
    kmax=ma/v[i]*v[i]+v[i]-1;
    if(kmin>kmax)out++;
    mi=kmin;ma=kmax;
    //cout<<mi<<" "<<ma<<endl;
  }
  if(out)cout<<-1<<endl;
  else cout<<mi<<" "<<ma<<endl;
}


Measured memory_bytes: 1024
# -*- coding: utf-8 -*-

a,b = input().split()

if a == "H" and b == "H":
    print("H")
elif a == "H" and b == "D":
    print("D")
elif a == "D" and b == "H":
    print("D")
elif a == "D" and b == "D":
    print("H")


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long ll;



int main() {
	int n; cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	vector<ll> v(n);
	for (int i = 0; i < n; i++) v[i] = (i&1) ? -2 : 2;
	v[0] /= 2; v[n - 1] /= 2;
	sort(v.begin(), v.end());
	ll s = 0, t = 0;
	for (int i = 0; i < n; i++) {
		s += a[i] * v[i];
	}
	sort(v.rbegin(), v.rend());
	for (int i = 0; i < n; i++) {
		t += a[i] * -v[i];
	}
	cout << max(s, t) << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <list>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <map>

using namespace std;

int main(){
	int n;
	char str[10], com[13];
	map<string, bool> m;
	cin >> n;
	for( int i = 0; i < n; i++) {
		scanf("%s%s", com, str);
		if( com[0] == 'i') m[string(str)] = true;
		else {
			if( m[string(str)]) cout << "yes";
			else cout << "no";
			cout <<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 45504
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            int N = sc.nextInt();
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int i = 0; i < N; i++) {
                int x = sc.nextInt();
                int c = 1;
                if (cnt.containsKey(x)) {
                    c = cnt.get(x) + 1;
                }
                cnt.put(x, c);
            }
            int ans = 0;
            for (int x : cnt.keySet()) {
                int c = cnt.get(x);
                if (c < x) {
                    ans += c;
                } else if (c > x) {
                    ans += c - x;
                }
            }
            System.out.println(ans);
        }
    }
}


Measured memory_bytes: 64540
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  string s;map<string,int>mp;
  for(auto i=0;i<n;i++)
  {
    cin>>s;
    mp[s]++;
  }
  vector<pair<string,int>>v;int m=-1;
  for(auto i:mp)
  {
      m=max(m,i.second);
    v.push_back({i.first,i.second});
  }
  sort(v.begin(),v.end());
  //reverse(v.begin(),v.end());
  for(auto i=0;i<mp.size();i++)
  {
    if(v[i].second==m)
    {
      cout<<v[i].first<<endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 29684
# from itertools import combinations
N, P = list(map(int,input().split()))
A = list(map(int,input().split()))
count = 0
# for i in range(N+1):
# 	for a in combinations(A, i):
# 		if sum(a) % 2 == P:
# 			count += 1
for a in A:
	if a % 2 == 0:
		count+=1
# print(count, N-count)
evenans = 1
oddans = 0
for i in range(1,count+1):
	c = 1
	m = 1
	# print(i+1, end=':')
	for j in range(i):
		c*=(count-j)
		m*=(j+1)
	evenans += c/m
	# print(evenans)
if P == 0:
	oddans += 1
	for i in range(2, N-count+1,2):
		c = 1
		m = 1
		# print(i, end=':')
		for j in range(i):
			c*=(N-count-j)
			m*=(j+1)
		oddans += c/m
		# print(oddans)
else:
	for i in range(1, N-count+1,2):
		c = 1
		m = 1
		# print(i, end=':')

		for j in range(i):
			c*=(N-count-j)
			m*=(j+1)
		oddans += c/m
		# print(oddans)
print(int(evenans*oddans))

Measured memory_bytes: 3064
def resolve():
    INF = float("-inf")
    N = int(input())
    A = list(map(int, input().split()))

    # 取る 取らない 取る 取らない ... を貪欲にやっていくと 1 + n % 2 個余って、
    # 1 + n % 2 回飛ばせることがわかる
    skip = 1 + N % 2;

    # dp[i][j] := a[0, i) を j 要素無視して1つ飛びに取ったときの最大値
    dp = [[INF] * (skip + 1) for _ in range(N + 2)]
    dp[0][0] = 0
    for i in range(N + 1):
        for j in range(skip + 1):
            if j < skip:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            if i < N:
                dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + A[i])
    # 1個選んだら1個選ばないのもセット
    # なので floor(n / 2) * 2 + skip == n + 1 に答えが入る
    print(dp[N + 1][skip])


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 53756
#include <iostream>

using namespace std;

int main()
{
	int D, N;
	cin >> D >> N;

	int answer = N;
	if (N != 100){
		for (int i = 0 ; i < D ; i++)	answer *= 100;
	}else{
		answer = 101;
		for (int i = 0 ; i < D; i++)	answer *= 100;
	}
	cout << answer << '\n';

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
#define mod 1000000007
#define PI 3.1415926535
using namespace std;
ll power(ll x, ll y)
{
	if (y == 0)
		return 1;
	else if (y % 2 == 0)
		return power(x, y / 2) * power(x, y / 2);
	else
		return x * power(x, y / 2) * power(x, y / 2);
}
ll modExpo(ll x,ll n)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return modExpo((x*x)%mod,n/2);
    else                            
        return (x*modExpo((x*x)%mod,(n-1)/2))%mod;
}
ll sum(ll n)
{
	ll s=0;
	while(n)
	{
		s+=n%10;
		n/=10;
	}
	return s;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	ll n;
	cin>>n;
	ll a[n+1];
	memset(a,0,sizeof(a));
	for(ll i=3;i<=n;i++)
	{
		a[i]=1;
		for(ll j=0;j<=i-3;j++)
			a[i]=(a[i]%mod + a[j]%mod)%mod;
	}
	cout<<a[n]<<endl;
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

const int M = 100000;
int n, m;

vector<pair<int, LL>> v[M];
bool f[M];
LL x[M];

bool dfs(int no, LL val) {
	if(f[no]) { return (val == x[no]); }
	
	f[no] = true;
	x[no] = val;
	
	bool ans = true;
	inc(i, v[no].size()) {
		ans &= dfs(v[no][i].FI, val + v[no][i].SE);
	}
	
	return ans;
}

int main() {
	cin >> n >> m;
	inc(i, m) {
		LL l, r, d;
		cin >> l >> r >> d;
		l--; r--;
		v[l].EB(r,  d);
		v[r].EB(l, -d);
	}
	
	bool ans = true;
	inc(i, n) {
		if(! f[i]) { ans &= dfs(i, 0); }
	}
	
	cout << (ans ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 16512
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))


n=input()

t=int(n[-1])
hon=[2,4,5,7,9]

if t==3:
    print("bon")
    exit()

if t in hon:
    print("hon")
    exit()

print("pon")

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

#define ll long long

using namespace std;


int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   
   int A,B,C; cin >> A >> B >> C;

   swap(A, B);
   swap(A, C);

   printf("%d %d %d", A, B, C);

   return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int count = 0;
		while(!(n == 0 && x == 0)){
			for(int i = 1; i <= n; i++){
				for(int j = i + 1; j <= n; j++){
					for(int k = j + 1; k <= n; k++){
						if(i + j + k == x){
							count++;
						}
					}
				}
			}
			System.out.println(count);
			count = 0;
			n = sc.nextInt();
			x = sc.nextInt();
		}

	}
}

Measured memory_bytes: 26476
#include<stdio.h>
#include<string.h>
#define M 1030000
#define L 14

char H[M][L];
int getChar(char ch){
  if(ch=='A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
  else return 0;
}
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}
int h1(int key){ return key%M; }
int h2(int key){ return 1+key%(M-1); }

int find(char str[]){
  long long i,key,j;
  key=getKey(str);
  for(i=0;;i++){
    j=(h1(key)+(i*h2(key)))%M;
    if(strcmp(H[j],str)==0) return 1;
    else if(strlen(H[j])==0 || i>=M) return 0;
  }
}

int insert(char str[]){
  long long i,key,j;
  key=getKey(str);
  for(i=0;;i++){
    j=(h1(key)+(i*h2(key)))%M;
    if(strcmp(H[j],str)==0) return 1;
    else if(strlen(H[j])==0){
      strcpy(H[j],str);
      return 0;
    }
  }
  return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
        scanf("%s %s", com, str);
        
        if ( com[0] == 'i' ){
            insert(str);
        } else {
            if (find(str)){
                printf("yes\n");
            } else {
                printf("no\n");
            }
        }
    }

    return 0;
}



Measured memory_bytes: 15816
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void) {
  int N, K;
  scanf("%d %d", &N, &K);
  if (N == K) printf("%d\n", 1);
  else {
    printf("%d\n", (int)ceil((double)(N-1) / (K-1)));
  }

  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define OUT(a) cout << (a) << "\n"
#define ll long long
ll MOD = 10e9 + 7;

int main() {
    int n,k;
    cin >> n >> k;
    int tmp = n - k;
    if (tmp > 0 && k != 1) printf("%d\n",tmp);
    else printf("0\n");
    return 0;
}

Measured memory_bytes: 384