akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}

	Scanner sc = new Scanner(System.in);

	void run() {

		int dx[] = new int['a'];
		int dy[] = new int['a'];
		dy['N'] = 1;
		dy['S'] = -1;
		dx['E'] = 1;
		dx['W'] = -1;

		for (;;) {

			int n = sc.nextInt();
			if (n == 0) {
				break;
			}

			int x[] = new int[n];
			int y[] = new int[n];

			for (int i = 0; i < n; i++) {
				x[i] = sc.nextInt();
				y[i] = sc.nextInt();
			}

			int m = sc.nextInt();

			int cx = 10;
			int cy = 10;
			
			boolean[] visited = new boolean[n];
			for (int i = 0; i < m; i++) {
				char ch = sc.next().charAt(0);
				int distance = sc.nextInt();

				for (int ii = 0; ii < distance; ii++) {
					cx += dx[ch];
					cy += dy[ch];
					
					for(int j = 0; j < n ; j++){
						if(x[j] == cx && y[j] == cy){
							visited[j] = true;
						}
					}
				}
			}
			
			boolean ans = true;
			for(boolean v: visited){
				ans &= v;
			}
			System.out.println(ans?"Yes":"No");

		}
	}
}



Measured memory_bytes: 41752
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")



#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define Find order_of_key
// #define at find_by_order
#define x first
#define y second
#define ll long long
#define lll __int128
#define ull unsigned long long
#define ulll unsigned __int128
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define gu getchar_unlocked()
#define pu putchar_unlocked()
#define all(x) x.begin(),x.end()
#define endl '\n'

const int mod=998244353;

const static int mx=200010;
ll BIT[mx];

void update(ll pos,ll val)
{
	for(;pos<=mx;pos+=pos&(-pos))BIT[pos]+=val;
}
ll query(ll pos)
{
	ll sum=0;
	for(;pos>0;pos-=pos&(-pos))sum+=BIT[pos];
	return sum;
}

int k;
int L[15],R[15];
int n;
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>L[i]>>R[i];
	}
	update(n,1);
	for(int i=n-1;i>=1;i--){
		int d=n-i;
		ll ans=0;
		for(int j=0;j<k;j++){
			int l=i+L[j];
			int r=min(i+R[j],n);
			if(l<=r){
				ans+=query(r);
				if(l!=1)ans-=query(l-1);
			}
			ans%=mod;
		}
		if(ans<0)ans+=mod;
		update(i,ans);
	}
	cout<<query(1)<<endl;
	return 0;
}

Measured memory_bytes: 5184
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#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 (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
ll A,B;

bool grid[100][100];

int main(){
	cin >> A >> B;
	REP(i,50) {
		REP(j,100) {
			grid[i][j] = true;
		}
	}

	REP(i,A - 1) {
		while(1) {
			ll y = rand() % 49;
			ll x = rand() % 100;
			bool f = grid[y][x];
			REP(j,8) {
				ll yy = y + dy[j],xx = x + dx[j];
				if((0 <= xx && xx < 100 && 0 <= yy && yy < 100) && !grid[yy][xx]){
					f = false;
					break;
				}
			}
			if(f) {
				grid[y][x] = false;
				break;
			}
		}
	}
	
	REP(i,B - 1) {
		while(1) {
			ll y = rand() % 49 + 51;
			ll x = rand() % 100;
			bool f = !grid[y][x];
			REP(j,8) {
				ll yy = y + dy[j],xx = x + dx[j];
				if((0 <= xx && xx < 100 && 0 <= yy && yy < 100) && grid[yy][xx]){
					f = false;
					break;
				}
			}
			if(f) {
				grid[y][x] = true;
				break;
			}
		}
	} 

	cout << 100 << " " << 100 << endl;
	REP(i,100) {
		REP(j,100) {
			if(grid[i][j]) {
				cout << '#';
			}else
				cout << '.';
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
pair<int, int> p[N], a[N];
int visited[N];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].second;
	}
	for (int i = 1; i <= n; i++) {
		cin >> p[i].first;
	}
	sort(p + 1, p + 1 + n);
	for (int i = 1; i <= n; i++) {
		a[i].first = p[i].second;
		a[i].second = i;
	}
	sort(a + 1, a + 1 + n);
	int flag = 1;
	for (int i = 1; i <= n; i++) {
		if (a[i].first > p[i].first) {
			flag = 0;
			break;
		}
	}
	if (flag) {
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				cnt++;
				int j = i;
				do {
					visited[j] = 1;
					j = a[j].second;
				} while (j != i);
			}
		}
		if (cnt >= 2)
			cout << "Yes";
		else {
			flag = 0;
			for (int i = 1; i < n; i++) {
				if (p[i].first >= a[i + 1].first) {
					flag = 1;
					break;
				}
			}
			if (flag)
				cout << "Yes";
			else
				cout << "No";
		}
	} else
		cout << "No";
	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
typedef long long int ld;
typedef unsigned long long int lu;
typedef vector< int > vi;
typedef vector < ld > vd;
typedef set <ld> sd;
typedef vector< vi > vvi;
typedef vector< vd > vvd;
typedef pair< int,int > ii;
typedef pair< ld,ld > id;
#define sz(a) ld((a).size())
#define test(t) ll t;cin>>t;while(t--)
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define Vi vector
#define pr pair
#define mpr make_pair
#define fi first
#define se second
#define isnum(a) (a>=48 && a<=57)
#define isS(a) (a>='a' && a<='z')
#define isU(a) (a>='A' && a<='Z')
#define toS(a) (isU(a)?a+32:a)
#define toU(a) (isS(a)?a-32:a)
#define toC(a) a&15

set <ld> s[100005];
ld d[100005];

vector<char> prime (100000+1, true);
void sieve(ld n)
{	
	//O(nloglogn) time
	prime[0] = prime[1] = false;
	for (ld i=2; i<=n; ++i)
	{
		if (prime[i])
		{
			s[i].insert(i);			
			for (ld j=2*i; j<=n; j+=i)
			{
				prime[j] = false;
				s[j].insert(i);
			}
		}
	}
}
#define forn(i,e) for(int i = 0; i < e; i++)
#define rep(i,a,b) for(i=a;i<b;i++)
#define REP(i,a,b) for(i=a;i<=b;i++)
#define reprev(i,a,b) for(i=a;i>=b;i--)

#define leadzero(a) __builtin_clz(a) //count leading zeros
#define trailzero(a) __builtin_ctz(a) //count trailing zeros
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln cout<<"\n"
#define sp cout<<" "
#define maxe(a) *max_element(a.begin(),a.end())
#define maxi(a) max_element(a.begin(),a.end())-a.begin()
#define mine(a) *min_element(a.begin(),a.end())
#define mini(a) min_element(a.begin(),a.end())-a.begin()
ld gcd(ld a, ld b) { if(b == 0) return a; return gcd(b, a % b); }
ld fastpowMOD(ld a, ld p,ld MOD){ if(p==0) return 1; ld z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }
ld fastpow(ld a, ld p){ if(p==0) return 1; ld z = fastpow(a,p/2); z = (z*z); if(p%2) z = (z*a); return z; }
ld a,b;

ld search1(ld a[], ld f,ld n)
{
	ld left=1;
	ld right=n+1;
	while(right-left>1)
	{
		ld mid = left + (right-left)/2;
		if(a[mid]<f)
		{
			left=mid;
		}
		else right=mid;
	}
	return a[left];
}
ld MOD = 1e9+7;
int main(){
	fastio;
	string k;
	cin >> k;
	ld n = k.length();
	ld d,i,j,t;
	cin >> d;
	ld dp[n][d];
	ld dp2[n][d];
	memset(dp,0,sizeof(dp));
	memset(dp2,0,sizeof(dp2));
	ld num = k[n-1]-'0';
	for(i=0;i<10;i++)
	{
		dp2[n-1][i%d]+=1;
	}
	for(i=0;i<=num;i++)
	{
		dp[n-1][i%d]+=1;
	}
	for(i=n-2;i>=0;i--)
	{
		for(j=0;j<10;j++)
		{
			for(t=0;t<d;t++)
			{
				dp2[i][t]+=dp2[i+1][((t-j)%d+d)%d]%MOD;
			}
		}
		num = k[i]-'0';
		for(j=0;j<num;j++)
		{
			for(t=0;t<d;t++)
			{
				dp[i][t]+=dp2[i+1][((t-j)%d+d)%d]%MOD;
			}
		}
		for(t=0;t<d;t++)
		{
			dp[i][t]+=dp[i+1][((t-num)%d+d)%d]%MOD;
		}
	}
	cout << (dp[0][0]-1+MOD)%MOD << endl;
	return 0;
}

Measured memory_bytes: 20736
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char n[10];
    int s = 0;

    scanf("%s",n);

    int len = strlen(n);
    for (int i = 0; i < len; i++)
    {
        s += n[i] - '0';
    }
    printf(atoi(n) % s == 0 ? "Yes" : "No");
}

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

int main(){
	// sengen
	double l;
	// nyuryoku
	cin >> l;
	// keisan
	double ans = (double)l*l*l/27;
	// syutsuryoku
	cout << setprecision(12) << (double)ans;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val A = Array(N) { sc.next().toInt() }
        if (A.all { it % 2 == 1 || it % 3 == 0 || it % 5 == 0 }) {
            pw.println("APPROVED")
        } else {
            pw.println("DENIED")
        }
    }
}


Measured memory_bytes: 31400
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())
print(sum(x - 1 for x in map(int, input().split())))


Measured memory_bytes: 5716
#include <iostream>

using namespace std;

int main()
{ int a,b;
  cin>>a>>b;
  if(a>b)
  cout<<"a > b"<<endl;
  else if(a==b)
  cout<<"a == b"<<endl;
  else if(a<b)
  cout<<"a < b"<<endl;

  return 0;
}



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

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

  if ( a + b > c + d ) {
    cout << "Left" << endl; 
  }
  else if ( a + b == c + d ){
    cout << "Balanced" << endl;
  } 
  else {
    cout << "Right" << endl;
  }
}
 
  


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int A, B, C;
    cin >> A >> B >> C;
    if (B >= A * C) {
        cout << C << endl;
    } else {
        cout << B / A << endl;
    }
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

Measured memory_bytes: 256
/*
PROG: acf17c
LANG: C++11
    _____
  .'     '.
 /  0   0  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
 */
#include <bits/stdc++.h>

using namespace std;

long long readi()
{
	long long input = 0;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	bool negative = false;
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = 10 * input + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	return input;
}
void printi(long long output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
string reads()
{
	string input = "";
	char c = ' ';
	while (c <= ' ')
	{
		c = getchar();
	}
	while (c > ' ')
	{
		input += c;
		c = getchar();
	}
	return input;
}
int sgn(long long x)
{
	if (x < 0) 
	{
		return -1;
	}
	if (x > 0) 
	{
		return 1;
	}
	return 0;
}
long long randomize(long long x)
{
	return (((1ll << 31) * rand()) + rand()) % x;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 0.000000000000001;

#define SINF 10007
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define CO 1000037
#define 	MAXN 80

long long normalize(long long x)
{
	return (((x % INF) + INF) % INF);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N;
int arr[MAXN];
int cnt[MAXN];
int ans = 0;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	srand(time(0));
	//	cout << fixed << setprecision(12);	
	//	cerr << fixed << setprecision(12);
	if (fopen("acf17c.in", "r"))
	{	
		freopen ("acf17c.in", "r", stdin);
		freopen ("acf17c.out", "w", stdout);
	}
	cin >> N;
	if (N >= 25)
	{
		cout << "0\n";
		return 0;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		if (arr[i] == 0)
		{
			cout << "0\n";
			return 0;
		}
	}
	for (int i = 0; i < (1 << N); i++)
	{
		for (int j = 0; j < 24; j++)
		{
			cnt[j] = 0;
		}
		cnt[0]++;
		for (int j = 0; j < N; j++)
		{
			if (i & (1 << j))
			{
				cnt[24 - arr[j]]++;
			}
			else
			{
				cnt[arr[j]]++;
			}
		}
		int cur = INF;
		for (int j = 0; j < 24; j++)
		{
			if (cnt[j] >= 2)
			{
				cur = 0;
				break;
			}
		}
		if (cur == 0)
		{
			continue;
		}
		for (int j = 0; j < 24; j++)
		{
			for (int k = j + 1; k < 24; k++)
			{
				if (cnt[j] && cnt[k])
				{
					cur = min(cur, min(k - j, 24 - (k - j)));
				}
			}
		}
		ans = max(ans, cur);
	}
	cout << ans << '\n';
	return 0;
}


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

int main() {
    int n,k;
    cin>>n>>k;
    int arr[n],dp[n];
    for(int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(int i=2;i<n;++i)
    {
        int j=min(i,k) , mini = INT_MAX;   
        while(j>0) 
        {
            int a= dp[i-j] + abs(arr[i]-arr[i-j]) ;
            if(a < mini)
            mini=a;
            j--;
        }
        dp[i]=mini;
    }
    cout<<dp[n-1]<<endl;
	return 0;
}


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

int main() {
  string S; cin >> S;

  string flg = "Yes";

  if (S[2] != S[3]) flg = "No";
  if (S[4] != S[5]) flg = "No";

  cout << flg << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF = 100100100100;
int main(){
    long long m, n; cin >> m >> n;
    vector<vector<long long> > dp(n + 1, vector<long long> (m + 1, INF));
    vector<long long> p(m);
    for(int i = 0; i < m; i++) cin >> p[i];
    vector<long long> c(n);
    vector<long long> e(n);
    for(long long i = 0; i < n; i++) cin >> c[i] >> e[i];
    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());

    dp[0][0] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= m; j++){
            if(dp[i][j] != INF){

                //選ぶ
                dp[i + 1][min(m, j + c[i])] = min(dp[i + 1][min(m, j + c[i])], dp[i][j] + e[i]);

                //選ばない
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            }
        }
    }

    for(int i = 1; i < m; i++) p[i] += p[i - 1];

    long long ans = 0;

    for(long long j = 1; j <= m; j++){
        
        ans = max(ans, p[j - 1] - dp[n][j]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 42168
#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;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> A(n);
  rep(i, n) cin >> A[i];
  int M = 1000005;
  vector<bool> done(M);
  vector<int> whichPrime(M);
  for(int i=2; i<M; i++) {
    if(!done[i]) {
      for(int j=0; i*(j+1)<M; j++) {
        whichPrime[i*(j+1)] = i;
        done[i*(j+1)] = true;
      }
    }
  }
  int allGcd = A[0];
  rep(i, n) allGcd = __gcd(allGcd, A[i]);
  if(allGcd != 1) {
    cout << "not coprime" << endk;
    return 0;
  }
  set<int> prime;
  rep(i, n) {
    if(A[i] == 1) continue;
    if(prime.count(whichPrime[A[i]])) {
      cout << "setwise coprime" << endk;
      return 0;
    } else {
      prime.insert(whichPrime[A[i]]);
    }
  }
  cout << "pairwise coprime" << endk;
  return 0;
}


Measured memory_bytes: 11356
using System.Collections.Generic;
using static System.Console;

class Program
{
    static void Main()
    {
        var w = NextString();
        var dic = new Dictionary<char, int>();

        var ans = "Yes";

        foreach (char v in w)
        {
            if (!dic.ContainsKey(v))
                dic[v] = 0;

            dic[v] += 1;
        }

        foreach (int v in dic.Values)
        {
            if (v % 2 != 0)
            {
                ans = "No";
                break;
            }
        }

        WriteLine(ans);
    }

    static string NextString()
    {
        var result = new List<char>();
        while (true)
        {
            int next = Read();
            if (next < 0)
                break;
            var nextChar = (char)next;
            if (!char.IsWhiteSpace(nextChar))
                result.Add(nextChar);
            else if (nextChar != '\r')
                break;
        }
        return string.Join("", result);
    }
}


Measured memory_bytes: 13280
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=524288+3,P=924844033,G=5;
int n,m,o,x,y,invG,f[N],g[N],tr[N],jc[N],cnt[N],inv[N],head[N],size[N],invjc[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int C(Re m,Re n){return (LL)jc[n]*invjc[m]%P*invjc[n-m]%P;}
inline void dfs(Re x,Re fa){
	size[x]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to],++cnt[size[to]];
	if(x!=1)++cnt[n-size[x]];
}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
	
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)f[i+len]*base%P;
				f[i+len]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
			
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=mi(n,P-2);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),m=n-1,invG=mi(G,P-2);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0),jc[0]=jc[1]=inv[1]=invjc[1]=invjc[0]=1;
	for(Re i=2;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P,inv[i]=(LL)inv[P%i]*(P-P/i)%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
	for(Re i=1;i<=n;++i)f[i]=(LL)cnt[i]*jc[i]%P;
	for(Re i=0;i<=n;++i)g[i]=invjc[n-i]%P;
	times(f,n,g,n);
	for(Re j=1;j<=n;++j)printf("%d\n",((LL)n*C(j,n)-(LL)invjc[j]*f[n+j]%P+P)%P);
}

Measured memory_bytes: 28800
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
use std::cmp::Ordering;

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}
impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

struct DepthFirstSearch {
    n: usize,
    p: Vec<Vec<i32>>,
    memo: Vec<Vec<i32>>,
}
impl DepthFirstSearch {
    fn rec(&mut self, k: usize, d: usize) -> i32 {

        if k == self.n {
            return 0;
        } else if k == 0 {
            let mut vals: Vec<i32> = Vec::new();
            for i in 0..3 {
                let val = self.rec(k + 1, i) + self.p[k][i];
                vals.push(val);
            }
            vals.sort_by_key(|&x| Rev(x));
            vals[0]

        } else {
            if self.memo[k][d] != -1 {
                return self.memo[k][d];
            }

            let mut vals: Vec<i32> = Vec::new();
            for i in 0..3 {
                if i == d {
                    continue;
                }
                let val = self.rec(k + 1, i) + self.p[k][i];
                vals.push(val);
            }
            vals.sort_by_key(|&x| Rev(x));

            self.memo[k][d] = vals[0];
            vals[0]
        }
    }
}

fn main() {
    input! {
        n: usize,
        p: [[i32; 3]; n],
    }
    let memo = vec![vec![-1; 3]; n];
    let mut dfs = DepthFirstSearch{ n: n, p: p, memo: memo };
    println!("{}", dfs.rec(0, 0))
} 


Measured memory_bytes: 42620
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P u){
  Q[tail] = u;
  tail = (tail+1)%LEN;
}

P dequeue(){
  P u = Q[head];
  head = (head+1)%LEN;
  return u;
}


int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1;
  tail = n+1;
  while(1){
    if(head==tail) break;
    u = dequeue();
    c = (u.t<=q)?u.t:q;
    u.t -= c;
    elaps += c;
    if(u.t>0){
      enqueue(u);
    } 
    else{
      printf("%s %d\n", &u.name,elaps);
    }
  }
  return 0;
}


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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
const long long INF = 1LL << 60;
//const int INF = 1e9+5;


int main(){
  int n;
  cin >> n;
  vector<vector<int>> action(n,vector<int>(3));
  rep(i,n) cin >> action[i][0] >> action[i][1] >>action[i][2];
  vector<vector<ll>> dp(n+3,vector<ll>(3,-1));
  dp[0][0] = action[0][0];dp[0][1] = action[0][1];dp[0][2] = action[0][2];
  for(int i=1;i<n;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if(k == j) continue;
        chmax(dp[i][k],dp[i-1][j]+action[i][k]);
      }
    }
  }
  ll res = 0;
  rep(i,3) chmax(res,dp[n-1][i]); 
  cout << res << endl;
} 

Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
int main()
{long long int x,n,u,v;
 cin>>x>>n;
 if(n==0)
 {cout<<x;
  return 0;}
 vector<long long int>vec;
 for(long long int i=0;i<n;i++)
 {long long int k;
  cin>>k;
  vec.push_back(k);}
 u=v=x;
 while(find(vec.begin(),vec.end(),u)!=vec.end())
 {u=u-1;
 }
 while(find(vec.begin(),vec.end(),v)!=vec.end())
 {v=v+1;}
 if(abs(u-x)<abs(v-x))
   cout<<u;
 else if(abs(v-x)<abs(u-x))
   cout<<v;
 else
   cout<<min(u,v);
           }
 
 


Measured memory_bytes: 3592
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

# Written by NoKnowledgeGG @YlePhan

#import math
mod = 10**9+7



def main():
  n = int(input())
  ans = 1
  for _ in range(2,n+1):
    ans *= _
    ans %= mod
  print(ans%mod)
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 2940
import numpy as np 


dim = list(map(int, input().split()))
N = dim[0]
D = dim[1]

x = []
for i in range(N):
	x_i = list(map(int, input().split()))
	x.append(x_i)

x = np.array(x)
count = 0
for i in range(N):
	for j in range(N-i-1):
		if(np.linalg.norm(x[i]-x[i+j+1]).is_integer()==True):
			count += 1

print(count)


Measured memory_bytes: 12504
#pragma GCC optimize("Ofast")
#include <iostream>
#include <map>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <iomanip>
#include <bitset>
#include <random>
#include <complex>
#include <random>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define pb push_back
#define ll long long
#define mp make_pair
#define fdeg firdeg
#define snd second
#define ins insert
#define ld long double
#define mt make_tuple
#define fst first
const double PI = acos(-1);
// = 5e5 + 17;
ll MOD = 1e9 + 7;
const int INF = 1e9;
const int MaXN = 105;
const int N = 5e5;
const int maxlog = 18;
ld ecr = 1e-8;
random_device rd;
mt19937 rnd(rd());
uniform_int_distribution<ll> nextRand(0,(ll)1e9);
template<class A, class B>
void sum(A &a, B b)
{
    a += b;
    if (a < 0LL) a += MOD;
    if (a >= MOD) a -= MOD;
}
ll add(ll a, ll b)
{
    a += b;
    if (a < 0) a += MOD;
    if (a >= MOD) a -= MOD;
    return a;
    
}
int to_i(char c)
{
    return c - 'a';
}
ll mult(ll a, ll b)
{
    ll val = a * b - (ll) ((ld) a * b / MOD) * MOD;
    if (val < 0)
    {
        val += MOD;
    }
    if (val >= MOD)
    {
        val -= MOD;
    }
    return val;
}

ll gcd (ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
}
ll gcd_eu (ll a, ll b, ll & x, ll & y)
{
    if (a == 0)
    {
        x = 0LL; y = 1LL;
        return b;
    }
    ll x1, y1;
    ll d = gcd_eu (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
long long poww(long long a, long long b)
{
    long long val = 1;
    a %= MOD;
    while (b > 0)
    {
        if (b % 2) val = mult(a, val);
        a = mult(a, a);
        b >>= 1;
    }
    return val % MOD;
}
ll inv(ll a)
{
    return poww(a , MOD - 2);
}
vector<int> g[N];
bool used[N];
pair <int, int> diam(int u)
{
    used[u] = 1;
    auto x = mp(0 , u);
    for (auto v : g[u])
    {
        if(!used[v])
        {
            auto nw = diam(v);
            nw = mp(nw.fst + 1 , nw.snd);
            x = max(x, nw);
        }
    }
    return x;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin  >> n;
    for(int i = 0; i < n - 1; i++)
    {
        int u , v;
        cin >> u >> v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    auto x = diam(0);
    for(int i = 0; i < N; i++)
    {
        used[i] = 0;
    }
    if((diam(x.second).first % 3 - 1) != 0)
    {
        cout << "First\n";
        return 0;
    }
    cout << "Second\n";
    return 0;
}


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

int main(){
int N;
string S;
cin >> N >> S;
int count = 0;
  for(int i = 0; i < N - 2;i++){
   if(S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C'){
     count++;
     }

  }
     cout << count << endl;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
c=[0]*(N+1)
w=[0]*(N+1)
AC=0
WA=0
for i in range(M):
    p,s=input().split()
    p=int(p)
    if(c[p]==0 and s=="AC"):
        c[p]+=1
        AC+=1
        WA+=w[p]
    elif(c[p]==0 and s=="WA"):
        w[p]+=1
print(AC,WA)

Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
int main(void){

    int N, D;
    cin >> N >> D;
    
    int index = 0;
    int result = 0;
    while(1) {
        index += D*2+1;
        result++;
        if(index>=N) break;
    }

    cout << result << endl;

    return 0;
    
}


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

int main()
{
	int n; cin >> n;
	int x[n], y[n];	for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; }

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

	double tmpDist = 0;
	int cnt = 0;
	do {
		double tmpSum = 0;
		for (int i = 0; i < n - 1; i++) {

			int next = vec.at(i + 1);
			int prev = vec.at(i);

			tmpSum += sqrt((x[next] - x[prev]) * (x[next] - x[prev]) + (y[next] - y[prev]) * (y[next] - y[prev]));
		}

		tmpDist += tmpSum;
		cnt++;
				
	} while (next_permutation(vec.begin(), vec.end()));

	cout << fixed << setprecision(11) << tmpDist / cnt << endl;

	return 0;
}

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

int main() {
    int n;
    int cnt = 0;
    int ans = 0;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];

    rep(i,n-1) {
        if (h[i] >= h[i+1]) {
            cnt += 1;
        } else {
            ans = max(ans, cnt);
            cnt = 0;
        }
        ans = max(ans, cnt);
    }

    cout << ans << endl;
    return 0;
}

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

using namespace std;

int L;
char s[32];
int fst[128];

vector<string> v;

void decrypt(char *s, int p)
{
	if (p == L){
		v.push_back((string)s);
		return;
	}

	if (s[p] == 'z' && fst[s[p]] == -1) return;

	if (s[p] == 'a' || ~fst[s[p]]) decrypt(s, p + 1);

	if (s[p] == 'z' || ~fst[s[p] + 1]) return;
	s[p]++;
	fst[s[p]] = p;
	decrypt(s, p + 1);
	fst[s[p]] = -1;
	s[p]--;
}

int main()
{
	while (scanf("%s", s) && s[0] != '#'){
		v.clear();
		memset(fst, -1, sizeof(fst));

		L = strlen(s);

		decrypt(s, 0);

		printf("%d\n", v.size());
		if (v.size() <= 10)
			for (int i = 0; i < v.size(); i++) printf("%s\n", v[i].c_str());
		else {
			for (int i = 0; i < 5; i++) printf("%s\n", v[i].c_str());
			for (int i = 4; i >= 0; i--) printf("%s\n", v[v.size() - i - 1].c_str());
		}
	}

	return (0);
}

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

#define int long long
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define COUT(x) cout << x << endl;
#define PB(x) push_back(x)
#define MP make_pair
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int INF = 1e9;
const int MOD = 1e9+7;

signed main(){
    int k,a,b; cin >> k >> a >> b;
    for(int i=a; i<=b; i++){
        if(i%k==0) {
            cout<<"OK"<<endl;
            return 0;
        }
         
    }
    cout<<"NG"<<endl;
}

Measured memory_bytes: 3588
#pragma GCC optimize("Ofast")
#include<stdio.h>
int main(void)
{
  char buf1[200001];
  char buf2[200001];
  gets(buf1);
  gets(buf2);
  int ans = 0;
  int i = 0;
  do if(buf1[i] != buf2[i]) ++ans; while(buf1[++i]);
  printf("%d", ans);
}


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

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

using namespace std;

int main(){
/*
	a < b < c として, 最大 - 最小は
	c - a
	->
	(b+c)/2 - (a+b)/2 = (c-a)/2
	->
	(a+b+2c)/4 - (2a+b+c)/4 = (c-a)/4
*/
	int a,b,c; scanf("%d%d%d",&a,&b,&c);

	set<tuple<int,int,int>> S;
	while(S.count(make_tuple(a,b,c))==0){
		if(a%2==1 || b%2==1 || c%2==1) return printf("%lu\n",S.size()),0;
		S.emplace(a,b,c);
		tie(a,b,c)=make_tuple((b+c)/2,(a+c)/2,(a+b)/2);
	}
	puts("-1");

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define int long long
const int mod = 1e9 + 7;

int32_t main(){
	fastio;
	
	int n; cin >> n;
	vector<char> ans;
	while(n){
		n--;
		ans.push_back(n%26+'a');
		n /= 26;
	}
	
	for(int i=ans.size()-1; i>=0; i--){
		cout << ans[i];
	}
	cout << endl;
	return 0;
}
		


Measured memory_bytes: 3652
h, w = map(int, input().split())
mas = [list(input()) for i in range(h)]

for i in range(h):
    for j in range(w):
        if mas[i][j] == '.':
            # 爆弾検索
            count = 0
            for k in range(i-1, i+2):
                for l in range(j-1, j+2):
                    if ((0 <= k < h and 0 <= l < w)
                        and mas[k][l] == '#'):
                        count += 1
            mas[i][j] = str(count)

[print("".join(mas[i])) for i in range(h)]


Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define Graph vector<vector<int>>;
#define iterG(next_v, G, v) for(auto next_v : G[v]
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, y, z;
    cin >> x >> y >> z;
    cout << z << " " << x << " " << y << endl;
    
    return 0;
}



Measured memory_bytes: 256
def main():
    L, R = (int(i) for i in input().split())
    if R - L >= 2018:
        return print(0)
    MOD = 2019
    ans = 2019
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(ans, (i*j) % MOD)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38896
/* --- author: dxm --- */
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

void qread(int &x){
	int neg=1;x=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
	while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
	x*=neg;
}

const int maxn=100005;
int n,tot;
string s;
char c[maxn];
vector<pii>ans;

int main(){
#ifdef FILE
	freopen("FILE.in","r",stdin);
	freopen("FILE.out","w",stdout);
#endif
	scanf("%s",c+1);c[0]='#';
	s=c;n=s.size()-1;
	REP(i,n-1)if(s[i]!=s[n-i]){
		puts("-1");
		return 0;
	}
	if(s[1]=='0'||s[n]=='1'){
		puts("-1");
		return 0;
	}
	s[n]='1';
	int last=1,id=1;
	tot=1;
	for(int i=2;i<=n;i++){
		if(s[i]=='1'){
			tot++;
			ans.pb(mp(id,tot));
			id=tot;
			for(int j=1;j<=i-last-1;j++)ans.pb(mp(tot,tot+j));
			tot+=i-last-1;
			last=i;
		}
	}
	rep(i,ans.size())printf("%d %d\n",ans[i].fst,ans[i].snd);
#ifdef TIME
	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
#endif
	return 0;
}

/*
Input:
-----------------
Output:
*/


Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define X first
#define Y second
#define pb push_back
#define CL(x) (x << 1)
#define CR(x) ((x << 1) + 1)
#define sqr(x) ((x) * (x))
#define Task ""

typedef long long cc;
typedef long double ld;
typedef pair <int, int> pii;
multiset <int> mst;
multiset <int> :: iterator it;
int main() {
    std :: ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    //-------------------------------------------------------------------------------------------------------
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        mst.insert(x);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        it = mst.find(x);
        if (it != mst.end()) {
            //cout << x << " df a\n";
            mst.erase(it);
        } else {
            cout << "NO\n";
        //cout </< x  << " fuck\n";
            return 0;
        }
    }
    cout << "YES\n";
    //-------------------------------------------------------------------------------------------------------
    return 0;
}


Measured memory_bytes: 9728
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define int ll
//#define endl '\n'
#define all(C) (C).begin(), (C).end()
#define rall(C) (C).rbegin(), (C).rend()
#define mp make_pair 
#define pb emplace_back
#define dbg(x) cerr << #x << " : " << x << endl
#define PI 3.141592653589

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
using pld = pair <ld, ld>;

template <class T>
istream& operator>> (istream &in, vector <T> &a)
{
    for (auto &i : a)
        in >> i;
    return in;
}

template <class T> 
ostream& operator<< (ostream &out, vector <T> a)
{
    for (auto &i : a)
        out << i << ' ';
    return out;
}

template <class T, class U>
istream& operator>> (istream &in, pair <T, U> &p)
{
    in >> p.first >> p.second;
    return in;
}

template <class T, class U>
ostream& operator<< (ostream &out, pair <T, U> p)
{
    out << p.first << " " << p.second << " ";
    return out;
}

inline void Start()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
}

vector <vector <int>> complete(vector <vector <int>> g)
{
    int n = g.size();
    vector <vector <int>> a(n, vector <int> (n)), b(n, vector <int> (n));
    for (int i = 0; i < n; ++i)
        for (auto &j : g[i])
            a[i][j] = a[j][i] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i][j] == 0)
                b[i][j] = b[j][i] = 1;
    vector <vector <int>> gr(n);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (b[i][j])
                gr[i].pb(j);
    return gr;
}

signed main()
{
    Start();
    int n;
    cin >> n;
    vector <vector <int>> g(n);
    for (int i = 0; i < n / 2; ++i)
        g[i].pb(n - i - (n & 1) - 1);
    auto gr = complete(g);
    int sum = 0;
    for (int i = 0; i < n; ++i)
        sum += gr[i].size();
    cout << sum << endl;
    for (int i = 0; i < n; ++i)
        for (auto &to : gr[i])
            cout << i + 1 << " " << to + 1 << endl;
    return 0;
}



Measured memory_bytes: 512
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=1e5+5;
const int mod=1e9+7;

signed main(){
    FastIO;
    int n;
    cin>>n;
    ll a[N];
    rep(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    if(!a[1]) return cout<<0,0;
    ll prod=1;
    const ll M=1e18;
    rep(i,1,n){
        if(a[i]>M/prod) return cout<<-1,0;
        prod=prod*a[i];
    }
    cout<<prod;
    return 0;
}


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

int main(){
  int N, M;
  
  cin >> N >> M;
  
  vector<int> cnt(N);
  for(int i = 0;i < M;i++){
    int a, b;
    cin >> a >> b;
    cnt.at(--a)++;
    cnt.at(--b)++;
  }
  
  for(int i = 0;i < N;i++) cout << cnt.at(i) << endl;
  
  return 0;
}

Measured memory_bytes: 3588
#include<stdio.h>
int main()
{
  int N,i;
  scanf("%d",&N);
  double A[N],inA[N],sum=0;
  for(i=0;i<N;i++)
  {
    scanf("%lf",&A[i]);
    inA[i]=1/A[i];
    sum=sum+inA[i];
  }
  printf("%lf",1/sum);
}

Measured memory_bytes: 128
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

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

typedef unsigned long long int ull;
typedef long long ll;
#define pb push_back

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //your code starts here

    int x;
    cin >> x;
    if (x >= 30)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int n, sum=0;

	cin>>n;

	vi s(n);

	rep(i, n){
		cin>>s[i];
		sum+=s[i];
	}

	int j=0;
	if(sum%10==0){
		int temp=sum;
		rep(i, n){
			if(s[i]%10!=0&&temp>s[i]){
				temp=s[i];
			}
		}
		sum-=temp;
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
def main():    
    import numpy as np
    N, W = map(int, input().split())
    ndp = np.zeros(W+1, dtype= np.int64)
    for _ in range(N):
        w, v = map(int,input().split())
        np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
    print(ndp[-1])
main()

Measured memory_bytes: 14580
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e6 + 5;
int main() {
	char s[110];
	int n,k;
	cin >> n >> k;
	cin >> s+1;
	for (int i = 1; i <= n; i++) {
		if (i == k)
			s[i] += 32;
	}
	cout << s + 1 << endl;
	//system("pause");
}


Measured memory_bytes: 256
n = int(input())
max_num = 0
word_dict = {}
for i in range(n):
    w = input()
    temp = word_dict.get(w, 0) + 1
    word_dict[w] = temp
    if temp > max_num:
        max_num = temp

ans_list = []
for w in word_dict:
    if word_dict[w] == max_num:
        ans_list.append(w)

ans_list.sort()

for w in ans_list:
    print(w)


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

#define x first
#define y second

using namespace std;

typedef unsigned long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const int mod=1000000000+7;

int addm(int& a,int b) {return (a+=b)<mod?a:a-=mod;}

template<class T,class U> bool smin(T& a,U b) {return a>b?(a=b,1):0;}
template<class T,class U> bool smax(T& a,U b) {return a<b?(a=b,1):0;}

struct BigInt {
	ll b=1000000000;
	vector<ll> a;

	BigInt () {}
	BigInt (const string& s): a(s.size()/9+100) {
		for (int i=0;i<a.size();i++) for (int j=0,p=1;j<9;j++,p*=10) {
			int k=i*9+j;
			if (k<s.size()) a[i]+=p*(s[s.size()-1-k]-'0');
		}
	}

	void times9() {
		ll carry=0;
		for (int i=0;i<a.size();i++) {
			a[i]=a[i]*9+carry;
			carry=a[i]/b;
			a[i]%=b;
		}
	}

	void add(int n) {
		ll carry=n;
		for (int i=0;i<a.size();i++) {
			a[i]+=carry;
			carry=a[i]/b;
			a[i]%=b;
		}
	}

	int pc(int n) {
		int r=0;
		for (;n;n/=10) r+=n%10;
		return r;
	}

	int pc() {
		int r=0;
		for (int i=0;i<a.size();i++) r+=pc(a[i]);
		return r;
	}
};

string s;
BigInt n,ne;

bool nd(int num) {
	ne=n;
	ne.add(num);
	int pc=ne.pc();
	return pc>num;
}

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

	cin >> s;
	n=BigInt(s);
	n.times9();

	int ans=0;
	for (int i=30;i>=0;i--) if (nd(ans+(1<<i))) ans+=1<<i;
	cout << ans/9+1 << endl;
}

Measured memory_bytes: 1692
#include<stdio.h>
#include<string.h>
using namespace std;
int a[300005];
int b[300005];
int c[300005];
char s[300005];
int main(){
    int n;
    scanf("%d",&n);
    getchar();
    scanf("%s",s);
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=0,j;i<n;i++){
        j=n-1-i;
        if(i==0)a[i]=0;
        else a[i]=a[i-1];
        if(j==n-1)b[j]=0;
        else b[j]=b[j+1];
        c[i]+=a[i];
        c[j]+=b[j];

        if(s[i]=='W')a[i]++;
        if(s[j]=='E')b[j]++;
    }
    int Min=99999999999;
    int p;
    for(int i=0;i<n;i++){
        if(Min>c[i]){
            Min=c[i];
        }
    }
    printf("%d\n",Min);
    return 0;
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define M 1101
#define MOD 1000000007
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define all(v) v.begin(),v.end()
#define repl(i,l,r) for(long long i=l;i<=r;++i)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define ins insert
#define inf INT_MAX
#define vp vector< pair<int,int> >
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;cin>>n>>k;
    int x=min(k-1,n);
    double sum=0.0;
   for(int i=1;i<=n;i++)
   {
       double p1=(double)1/n;
       int j=i;
       int c=0;
       while(j<k)
       {
           c++;
           j=j*2;
       }
       double p2=pow(0.5,c);
       double p=p1*p2;
       sum+=p;

   }



    cout.precision(12);
    cout<<fixed<<sum<<"\n";

    return 0;
}



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

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

    if(A == 1) A += 13;
    if(B == 1) B += 13;

    if(A > B)
        cout << "Alice" << endl;
    else if(A < B)
        cout << "Bob" << endl;
    else
        cout << "Draw" << endl;
}

Measured memory_bytes: 256