akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define inver(a) power(a, mod - 2)
using namespace std;
inline char nc() {
	return getchar();
	static char buf[100000], *l = buf, *r = buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x) {
	x = 0; int f = 1, ch = nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x *= f;
}
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int maxA = 2000 + 10;
int n;
int A[maxn], B[maxn];
int H, W;
int fac[maxA << 2];
int fac_inv[maxA << 2];
int f[maxA << 1][maxA << 1];
inline int add(int x) {
	return x >= mod ? x - mod : x;
}
inline int dec(int x) {
	return x < 0 ? x + mod : x;
}
ll power(ll x, ll y) {
	ll re = 1;
	while(y) {
		if(y & 1) re = re * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return re;
}
inline ll C(int x, int y) {
	return (ll)fac[x] * fac_inv[y] % mod * fac_inv[x - y] % mod;
}
void init(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) {
		fac[i] = (ll)fac[i - 1] * i % mod;
	}
	fac_inv[n] = inver(fac[n]);
	for(int i = n; i >= 1; --i) {
		fac_inv[i - 1] = (ll)fac_inv[i] * i % mod;
	}
}
int solve() {
	init(8000);
	for(int i = 1; i <= n; ++i) {
		++f[W - A[i]][H - B[i]];
	}
	for(int i = 1; i <= (W << 1); ++i) {
		for(int j = 1; j <= (H << 1); ++j) {
			f[i][j] = add(f[i][j] + add(f[i - 1][j] + f[i][j - 1]));
		}
	}
	int an = 0;
	for(int i = 1; i <= n; ++i) {
		an = add(an + f[W + A[i]][H + B[i]]);
		an = dec(an - C((A[i] << 1) + (B[i] << 1), A[i] << 1));
	}
	return (ll)an * fac_inv[2] % mod;
}
int main() {
	read(n);
	for(int i = 1; i <= n; ++i) {
		read(A[i]), read(B[i]);
		W = max(W, A[i] + 1);
		H = max(H, B[i] + 1);
	}
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 65024
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define RREP(i, n) for (ll i = n; i >= 0; i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cerr << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cerr << e << " "; } cerr << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

// DP
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }




// ***************************************

int main() {

    string s, t;
    cin >> s >> t;

    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

    REP(i, s.size()) {
        REP(j, t.size()) {
            if (s[i] == t[j]) chmax(dp.at(i + 1).at(j + 1), dp.at(i).at(j) + 1);
            chmax(dp[i + 1][j + 1], dp[i][j + 1]);
            chmax(dp[i + 1][j + 1], dp[i + 1][j]);
        }
    }

    if (dp[s.size()][t.size()] == 0) {
        cout << endl;
        return 0;
    }


    stack<char> str;
    int i = s.size();
    int j = t.size();
    while (dp[i][j] > 0) {
        while (dp[i][j] == dp[i][j - 1]) j--;
        while (dp[i][j] == dp[i - 1][j]) i--;
        i--; j--;
        str.push(s[i]);
    }

    while (!str.empty()) {
        char c = str.top(); str.pop();
        cout << c;
    }
    cout << endl;

    return 0;
}



Measured memory_bytes: 35584
import std.stdio;
import std.ascii;
import std.conv;
import std.string;
import std.algorithm;
import std.range;
import std.functional;
import std.math;
import core.bitop;

void main()
{
    auto nmq = readln.chomp.split.to!(long[]);
    long N = nmq[0];
    long M = nmq[1];
    long Q = nmq[2];
    long[] L = new long[](M);
    long[] R = new long[](M);
    long[] Qp = new long[](Q);
    long[] Qq = new long[](Q);

    foreach (i; 0 .. M)
    {
        auto lr = readln.split.to!(long[]);
        L[i] = lr[0];
        R[i] = lr[1];
    }
    foreach (i; 0 .. Q)
    {
        auto pq = readln.split.to!(long[]);
        Qp[i] = pq[0];
        Qq[i] = pq[1];
    }

    long[501][501] table;
    foreach (t; zip(L, R))
        table[t[0]][t[1]]++;

    foreach (i; 1 .. N + 1)
        foreach (j; 1 .. N + 1)
        {
            table[i][j] += table[i][j - 1];
            table[i][j - 1] += table[i - 1][j - 1];
        }

    foreach (i; 1 .. N + 1)
        table[i][N] += table[i - 1][N];

    // table.writeln;

    foreach (query; zip(Qp, Qq))
    {
        long result = table[query[1]][query[1]];
        result -= table[query[1]][query[0] - 1];
        result -= table[query[0] - 1][query[1]];
        result += table[query[0] - 1][query[0] - 1];
        result.writeln;
    }
}


Measured memory_bytes: 10108
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
int main(){
int N, k=2, t=1; cin >> N;
while(k*(k-1)<2*N){ k++; }
if(k*(k-1)>2*N){ cout << "No\n"; return 0; }  
vector< vector<int> > S(k);
REP(i, k-1){ 
  for(int j=i+1; j<k; j++){ 
    S[i].push_back(t); S[j].push_back(t); t++;
  }
}
cout << "Yes\n" << k << "\n";
REP(i, k){ 
  cout << S[i].size() << " ";
  REP(j, S[i].size()){ cout << S[i][j] << " "; }
  cout << "\n";
}
}

Measured memory_bytes: 4416
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
  int n = 0,m = 0,min = 0,max = 0,l = 0,r = 0;
  cin >> n >> m;
  max = n;
  
  for(int i=0;i<m;i++){
    cin >> l >> r;
    if(min < l){min = l;}
    if(max > r){max = r;}
  }
  
  if(max - min >= 0){
    cout << max - min + 1 << endl;
  }else{
    cout << 0 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int k, n, maxi = 0;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[maxi] < a[i]) maxi = i;
    }
    
    cout << max(0, a[maxi] - 1 - (k - a[maxi])) << endl;
    
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
	int left = a+b,right = c+d;
	
	if(left == right){
		cout << "Balanced" << endl;
	}
	else if(left > right){
		cout << "Left" << endl;
	}
	else{
		cout << "Right" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

int main(void) {
    int a,x;
    cin>>x>>a;

    if(x < a) {
        cout<<0<<endl;
    } else {
        cout<<10<<endl;
    }
    return 0;
}




Measured memory_bytes: 256
# Knapsack 1

N, W = map(int, input().split())
knapsack_list = []
for i in range(N):
    knap =  list(map(int, input().split()))
    knapsack_list.append(knap)

cost_list = [0 for i in range(W+1)]
max_cost = 0

# DP loop
for knap in knapsack_list:
    weight = knap[0]
    value = knap[1]
    for i in reversed(range(0, W+1)): # cost update
        loc = i - weight
        if loc<0:
            break
        new_cost = cost_list[loc] + value
        new_cost = max(cost_list[i], new_cost)
        cost_list[i] = new_cost

# max cost process
for cost in cost_list:
    if cost > max_cost:
        max_cost = cost

# print max cost
print(max_cost)


Measured memory_bytes: 45040
#include<iostream>
using std::cin;
using std::cout ;
int main()
{
	int n,i,count=0,flag=1;
	long int a[200];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		if(a[i]%2!=0)
			flag=0;
		a[i]/=2;
	}
	if(0==flag)
		cout<<0;
	else
	{
		count=1;
		while(1)
		{
			for(i=0;i<n;i++)
				{
					if(a[i]%2!=0)
					{
						flag=0;
						break;
					}
					a[i]/=2;
				}
			if(0==flag)
			{
				cout<<count;
				break;
			}
			count+=1;
		}
	}
	return 0;
}	


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


using namespace std;

int main() {

    
    int arr[5] , k;
    for (int i=0;i<5;i++)
        cin >> arr[i];
    cin >> k;
    sort(arr, arr+1);
    if (arr[4] - arr[0] > k) 
        cout << ":(";
    else 
        cout << "Yay!";

    return 0;
}

Measured memory_bytes: 256
import math
N, D = map(int, input().split())
X=[]
for i in range(N):
    X.append([int(j) for j in input().split()])

sum=0
count=0
for x in range(0, N-1):
    for y in range(x+1, N):
        for z in range(D):
            sum +=abs((X[x][z]-X[y][z])*(X[x][z]-X[y][z]))

        sq=math.sqrt(sum)
        if(sq==int(sq)):
            count+=1
        sum=0

print(count)

Measured memory_bytes: 3064
N, K = map(int, input().split())
x = []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, b])

x.sort(key=lambda x: x[0])

c = 0
for a, b in x:
    c += b
    if K <= c:
        print(a)
        exit()


Measured memory_bytes: 25352
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        Set<Point> redSet = new HashSet<>();
        for( int i = 0; i < N; i++ ) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            Point p = new Point(x, y);
            redSet.add( p );
        }
        PriorityQueue<Point> bluePq = new PriorityQueue<>( (a, b) -> a.x - b.x );
        for( int i = 0; i < N; i++ ) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            Point p = new Point(x, y);   
            bluePq.add( p );
        }
        
        int sum = 0;
        while( !bluePq.isEmpty() ) {
            Point blue = bluePq.poll();
            Point fateRed = null;
            for( Point red : redSet ) {
                if( red.x < blue.x && red.y < blue.y ) {
                    if( Objects.isNull(fateRed) ){
                        fateRed = red;  
                    } else {
                        if( fateRed.y < red.y ) {
                            fateRed = red;
                        }
                    }
                }
            }
            
            if( Objects.nonNull(fateRed) ) {
                redSet.remove( fateRed );
                sum++;
            }
        }
        
        System.out.println( sum );

    }
}

class Point {
    int x;
    int y;
    
    public Point( int x, int y ) {
        this.x = x;
        this.y = y;
    }
}


Measured memory_bytes: 36696
//スマホコーディング
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
typedef long long ll;
const int inf=1e9;
int main(){
  string s[3];
  rep(i,3)cin>>s[i];
  char c[3];
  rep(i,3)c[i]=s[i][0];
  rep(i,3){
    char a='A'+(c[i]-'a');
    cout<<a;
  }
  cout<<endl;
  return 0;
}


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

using namespace std;

const int maxN = 100010;
const long long oo = 1000000000000ll;

#define foru(i, l, r) for (int i = l; i <= r; ++i)
#define ford(i, r, l) for (int i = r; i >= l; --i)
#define repu(i, r) for (int i = 0; i < r; ++i)
#define ll long long
#define F first
#define S second
#define mp make_pair
#define pint pair < ll, int >

int a[maxN], n;
ll s[maxN], res;

int main() {
    cin >> n;
    foru(i, 1, n) cin >> a[i];
    int now = 0;
    res = 0;
    foru(i, 1, n) {
        s[i] = s[i - 1] + a[i];
        if (!now && s[i] >= 0) {
            res += (s[i] + 1);
            s[i] = -1;
        }
        if (now && s[i] <= 0) {
            res += (1 - s[i]);
            s[i] = 1;
        }
        now = 1 - now;
    }
    ll num = 0;
    now = 1;
    foru(i, 1, n) {
        s[i] = s[i - 1] + a[i];
        if (!now && s[i] >= 0) {
            num += (s[i] + 1);
            s[i] = -1;
        }
        if (now && s[i] <= 0) {
            num += (1 - s[i]);
            s[i] = 1;
        }
        now = 1 - now;
    }
    res = min(res, num);
    cout << res;
}


Measured memory_bytes: 1408
#define ll long long int
#include <bits/stdc++.h>

using namespace std;


int main()
 {
//code
         ll n,i,j,k;
         cin>>n>>k;
         vector<ll> dp(n,INT_MAX);
         vector<ll> a(n);
         for(i=0;i<n;i++)
         {
         	ll temp;
         	cin>>temp;
         	a[i]=temp;
		 }

         dp[0]=0;dp[1]=a[0]>=a[1]?a[0]-a[1]:a[1]-a[0];
         
         for(i=0;i<n;i++)
         {
         	for(j=i+1;j<=i+k&&j<n;j++)
         	{
		
             	
		        ll temp1=a[j]>=a[i]?a[j]-a[i]:a[i]-a[j];
                if(temp1+dp[i]<=dp[j])
                {
                	dp[j]=temp1+dp[i];
				}
           }
        }
          //for(i=0;i<n;i++)
          //cout<<dp[i]<<endl;
        
       
       cout<<dp[n-1];

}

Measured memory_bytes: 1792
N = int(input())
word = [input() for _ in range(N)]
s = set(word)
ok = True
if len(s) != N:
    ok = False
for i in range(1,N):
  if word[i][0] != word[i-1][-1] :
    ok = False
print('Yes' if ok else 'No')


Measured memory_bytes: 3060
// template version 1.15
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

#define divceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define slice(l, r) substr(l, r-l)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
    #include "lib/dump.hpp"
#else
    #define dump(...) 42
    #define dump_1d(...) 42
    #define dump_2d(...) 42
    #define cerrendl 42
#endif
//}}}

vi divisor(int n){  // 約数全列挙{{{
    vi p,q;
    for(int i=1; i*i<=n; i++){
        if (n%i==0){
            p.pb(i);
            if (i*i!=n) q.pb(n/i);
        }
    }
    reverse(all(q));
    p.insert(p.end(), all(q));
    return p;
}//}}}

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

    auto ds = divisor(n-1);
    dump(ds);

    int ans = sz(ds) - 1;

    ds = divisor(n);
    each(d, ds){
        if (d==1) continue;
        dump(d);

        int nn = n;
        while(nn%d==0){
            nn /= d;
        }
        if ((nn-1)%d==0) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

long GCD(long a, long b){
  long dividend, divisor;
  if (a >= b) {
    dividend = a;
    divisor = b;
  } else {
    dividend = b;
    divisor = a;
  }
  long remainder;
  while (1) {
    if (divisor == 1) {
      return 1;
    }
    remainder = dividend % divisor;
    if (remainder == 0) {
      break;
    } else {
      dividend = divisor;
      divisor = remainder;
    }
  }
  return divisor;
}

int main(void){

  long n;
  scanf("%ld", &n);
  long a[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld", &a[i]);
  }
  long Lgcd[n];
  Lgcd[0] = a[0];
  for (long i = 1; i < n; i++) {
    Lgcd[i] = GCD(Lgcd[i-1],a[i]);
  }
  long Rgcd[n];
  Rgcd[n-1] = a[n-1];
  for (long i = n-2; i >= 0; i--) {
    Rgcd[i] = GCD(Rgcd[i+1],a[i]);
  }
  long max = Rgcd[1];
  for (long i = 1; i < n-1; i++) {
    if (GCD(Lgcd[i-1],Rgcd[i+1]) > max) {
      max = GCD(Lgcd[i-1],Rgcd[i+1]);
    }
  }
  if (Lgcd[n-2] > max) {
    max = Lgcd[n-2];
  }
  printf("%ld\n", max);

  return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <tuple>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <functional>
using namespace std;


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

  string  s;
  cin >> s;

  if (s == "ABC") {
    cout << "ARC" << endl;
  } else {
    cout << "ABC" << endl;
  }
  


}
  

Measured memory_bytes: 3556
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <cinttypes>

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define abs(a) (((a) < 0) ? -(a) : (a))

#define FOR(var, to)          for (register int var = 0; var < to; var++)
#define FROMTO(var, from, to) for (register int var = from; var <= to; var++)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

static inline int ri() {
	int a;
	scanf("%d", &a);
	return a;
}

static inline s64 rs64() {
	s64 a;
	scanf("%" SCNd64, &a);
	return a;
}

static inline void wi(int a) {
	printf("%d", a);
}

static inline void wu64(u64 a) {
	printf("%" PRIu64, a);
}

int main() {
	int a = ri();
	int b = ri();
	if (a+b == 15) printf("+");
	else if (a*b == 15) printf("*");
	else printf("x");
	
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <bits/stdc++.h>
//#include "D:\C++\test_lib_projects\testlib.h"
using namespace std;
#define ll long long
#define pii pair<int,int>

bool debug=true;
/*
   Write In New Computer
    By XiaoGeNintendo
	     gwq2017
	Type:
*/
template<typename T1,typename T2>ostream& operator<<(ostream& os,pair<T1,T2> ptt){
	os<<ptt.first<<","<<ptt.second;
	return os;
}
template<typename T>ostream& operator<<(ostream& os,vector<T> vt){
	os<<"{";
	for(int i=0;i<vt.size();i++){
		os<<vt[i]<<" ";
	}
	os<<"}";
	return os;
}

ll n,m,d;
int main(int argc,char* argv[]){
	cin>>n>>m>>d;

	if(n==1){
		if(d==1){
			cout<<0<<endl;
		}else{
			cout<<m-1<<endl;
		}
		
		return 0;
	}
	
	
	if(d==0){
		double dd=(m-1)/(double)n;
		printf("%.10f",dd);
		return 0;
	}
	
	
	ll a=(n-1)*2; 
	
	ll b=(m-1)*a;
	
	ll c=b/(n-1);
	ll e=b-c*(d-1);
	
	double ans=e/(double)(n*n);
	printf("%.10f",ans);
	
	//cout<<a<<" "<<b<<" "<<c<<" "<<e<<endl;
	//cout<<((n-d)*(m-1)*2)/(double)(n*n);
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s;
  cin >> s;
  map<char, int> mp;
  mp['N'] = 0;
  mp['E'] = 1;
  mp['S'] = 2;
  mp['W'] = 3;
  vector<int> cnt(4);
  for (char c : s)
    ++cnt[mp[c]];
  if (max(cnt[0], cnt[2]) > 0 && min(cnt[0], cnt[2]) == 0 ||
      max(cnt[1], cnt[3]) > 0 && min(cnt[1], cnt[3]) == 0)
    cout << "No";
  else
    cout << "Yes";

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 256
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
abcd = []
for _ in range(q):
    abcd.append(list(map(int, input().split())))

res = 0
for arr in combinations_with_replacement(range(1, m+1), n):
    score = 0
    for a, b, c, d in abcd:
        if arr[b-1] - arr[a-1] == c:
            score += d
    if score > res:
        res = score

print(res)


Measured memory_bytes: 9092
#include<iostream>
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);
    
    int n, m, k;
    cin >> n >> m >> k;

    bool ok = false;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int b = i * (m - j) + j * (n - i);
            if (b == k) ok = true;
        }
    }

    cout << (ok ? "Yes" : "No") << endl;

}

Measured memory_bytes: 3064
N = int(input())
A = []
xy = []
for i in range(N):
    A_ = int(input())
    A.append(A_)
    xy_ = []
    xy.append(xy_)
    for j in range(A_):
        xy_.append(list(map(int, input().split())))
answer = 0
for i in range(2 ** N):
    peoples = format(i, "0{0}b".format(N))
    num = peoples.count('1')
    if num <= answer:
        continue
    for j in range(len(peoples)):
        people = peoples[j]
        if people == '0':
            continue
        for x, y in xy[j]:
            if peoples[x - 1] != str(y):
                break
        else:
            continue
        break
    else:
        answer = num
print(answer)


Measured memory_bytes: 3064
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int x = Integer.parseInt(sc.nextLine());

		sc.close();

		System.out.println(multiply(x, 3));
	}

	private static int multiply(int a, int b) {
		int result = 1;
		for (int i = 0; i < b; i++) {
			result *= a;
		}
		return result;
	}

}



Measured memory_bytes: 26080
#define yuki(x, y) for(int i = x; i < (y); ++i)
#define yukj(x, y) for(int j = x; j < (y); ++j)
#define yukii(x, y) for(int i = x; i <= (y); ++i)
#define yukji(x, y) for(int j = x; j <= (y); ++j)
#define yuk(x, y, z) for(int x = y; x < (z); ++x)
#define yui(x, y, z) for(int x = y; x >= (z); --x)
#define sclr(x) memset(x, 0, sizeof(x))
#define sclr1(x) memset(x, -1, sizeof(x))
#define scl(x, y) memset(x, y, sizeof(x))
#define ft first
#define sc second
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long lol;
int x, y;
int snow(int x) {return x < 0 ? -x : x;}
int main(int argc, char **argv)
{
	scanf("%d%d", &x, &y);
	if(x <= y)
    {
        if((lol)x*y >= 0) printf("%d\n", y-x);
        else printf("%d\n", snow(snow(y)-snow(x))+1);
    }
	else
    {
        if((lol)x*y > 0) printf("%d\n", x-y+2);
        else printf("%d\n", snow(snow(y)-snow(x))+1);
    }
	return 0;
}


Measured memory_bytes: 128
import bisect
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))
    
    cnt = 0
    for b in B:
        i = bisect.bisect_left(A, b)
        k = bisect.bisect_right(C, b)
        cnt += i * (N-k)
    print(cnt)

if '__main__' == __name__:
    resolve()

Measured memory_bytes: 107108
import math

a,b,h,m = input().split()
h=int(h)
m=int(m)

a_detect = 360 * h / 12 + 360 / 12 * m / 60

b_detect = 360 * m/60

diff = a_detect - b_detect
if diff < 0 :
  diff = -diff
diff -=180
if diff < 0 :
  diff = -diff

nagasa = int(a)**2 + int(b)**2 + 2* int(a)*int(b)*math.cos(math.radians(diff))
nagasa = math.sqrt(nagasa)


print(nagasa)

Measured memory_bytes: 9524
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

ll n,d,a;
vpii v;

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> d >> a;
    rep(i,0,n){
        ll x,h;
        cin >> x >> h;
        v.push_back({x,h});
    }
    sort(all(v));
    ll j=0;
    ll ans=0;
    ll c[n+1]={0};
    for(ll i=0; i<n; i++){
        ll need=max((v[i].S-c[i]*a+(a-1))/a,0LL);
        while(j<n && v[j].F-v[i].F<=2*d) j++;
        ans+=need;
        c[i]+=need;
        c[j]-=need;
        c[i+1]+=c[i];
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 6512
import unittest


class TestA(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think('3776'), 'Bad')

    def test_2(self):
        self.assertEqual(think('8080'), 'Good')

    def test_3(self):
        self.assertEqual(think('1333'), 'Bad')

    def test_4(self):
        self.assertEqual(think('0024'), 'Bad')


def solve():
    s = read()
    result = think(s)
    write(result)


def read():
    length_of_string = 4
    return read_line(n=length_of_string)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(data):
    for i in range(len(data) - 1):
        if data[i] == data[i + 1]:
            return 'Bad'
    return 'Good'


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Measured memory_bytes: 5692
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<LL, pii> plpii;
typedef pair<LD, LD> pdd;
typedef pair<LD, int> pdi;
typedef pair<LD, LL> pdl;
typedef pair<int, LD> pid;
typedef pair<LL, LD> pld;
const int mod = 1e9 + 7;
const int hf = 999983;
const int N = 1e6;
int a[105];
int n, k;
int dp[2][100005];
int dfs(int t, int k){
    if(dp[t][k] != -1) return dp[t][k];

    int ans = 1-t;
    for(int i=1;i<=n;i++){
        if(k-a[i] < 0) continue;
        int res = dfs(1-t, k-a[i]);
        if(res == t) ans = t;
    }
    return dp[t][k] = ans;
}
int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    int ans = dfs(0, k);
    if(ans == 0) printf("First\n");
    else printf("Second\n");
}

Measured memory_bytes: 7296
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[305][305][305],k;
char a[305];
inline int dfs(int l,int r,int x) {
	if(l>r) return 0;if(l==r) return 1;if(~dp[l][r][x]) return dp[l][r][x];
	int rt=max(dfs(l,r-1,x),dfs(l+1,r,x));
	if(a[l]==a[r]) rt=max(rt,2+dfs(l+1,r-1,x));
	if(x) rt=max(rt,2+dfs(l+1,r-1,x-1));
	dp[l][r][x]=rt;
	return rt;
}
int main()
{
	scanf("%s%d",a+1,&k);memset(dp,-1,sizeof(dp));
	printf("%d",dfs(1,strlen(a+1),k));
	return 0;
}

Measured memory_bytes: 110976
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rep2(i,k,n) for(int i=k;i>=n;i--)
#define pa pair<int,int>
#define fr first
#define se second
#define mk make_pair
using namespace std;
typedef long long ll;
ll ans;int n,p;
int main(){
	scanf("%d%d",&n,&p);int cnt=0,x;
	rep(i,1,n)scanf("%d",&x),cnt+=(x&1);
	if(p==1 && !cnt)puts("0");
	else{
		ans=1ll<<(n-(cnt>0));
		printf("%lld\n",ans);
	}
}

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

int main() {
  int N;
  cin>>N;
  vector<string>A(N);
  for (int i = 0; i < N; i++){
    cin>>A.at(i);
  }
  map<string,int>p;
  vector<string>B={};
  for (int i = 0; i < N; i++){
    if(p.count(A.at(i))){
      p.at(A.at(i))++;
    }else{
      p[A.at(i)]=1;
      B.push_back(A.at(i));
    }
       }
       int M=0;
       vector<string>Z={};
       for(int i=0;i<B.size();i++){
         if(M==p.at(B.at(i))){
           Z.push_back(B.at(i));
         }
         else if(M<p.at(B.at(i))){
           Z={B.at(i)};
           M=p.at(B.at(i));
         }
       }
       sort(Z.begin(), Z.end());
       for(int i=0;i<Z.size();i++){
         cout<<Z.at(i)<<endl;
       }
       
}

Measured memory_bytes: 30064
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[0 for i in range(n)]
B=[0 for i in range(m)]
A[0]=a[0]
B[0]=b[0]
for i in range(n-1):
    A[i+1]=a[i+1]+A[i]

for i in range(m-1):
    B[i+1]=b[i+1]+B[i]

ans=0
A.insert(0,0)
B.insert(0,0)

for i in range(n+1):
    x=0
    y=m
    j=(x+y)//2
    if A[i]+B[m]<=k:
        ans=max(ans,i+m)
    elif not A[i]+B[0]>k:
        
        
        while y-x>1:
            if A[i]+B[j]<=k:
                x=j
            else:
                y=j
            j=(x+y)//2
        ans=max(ans,i+x)
    
print(ans)
    
    


Measured memory_bytes: 47512
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,k,tmp;
bool u[11];
bool check(int t)
{
    while(t)
    {
        if (u[t%10]) return 0;
        t/=10;
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&tmp);
        u[tmp]=1;
    }
    int cur=n;
    while(!check(cur)) cur++;
    printf("%d",cur);
}


Measured memory_bytes: 256
def prepare(n):
    global nodes,diff_weight
    # ノードは-1で初期化, Nは頂点数
    nodes = [-1]*n
    # 差分重みは0で初期化, Nは頂点数
    diff_weight = [0]*n

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    # xの重みを知りたいので経路圧縮
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# x,yの根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xの木の高さを返す
def rank(x):
    return -nodes[x]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 再帰的に根を調べる
        root_x = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        # xを根に直接繋ぎ直す
        nodes[x] = root_x
        return root_x

def unite(x,y,w):
    # 以下x,yの根について考えるので,重みを補正
    w += weight(x); w -= weight(y)
    x = root(x); y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if x == y:
        return
    rank_x = rank(x); rank_y = rank(y)
    # xの方が木が高いことを想定しているのでx,yをスワップ,wを-wに
    if rank_x < rank_y:
        x,y = y,x; w = -w
    # 木の高さが同じ場合は繋いだ後の高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[x] -= 1
    # 低い木の根を高い木の根に繋ぎ直す
    nodes[y] = x
    # 低い木の根の差分重みを設定
    diff_weight[y] = w

N,M = map(int,input().split())
prepare(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
print(ans)

Measured memory_bytes: 8804
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
//           dx[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
int main() {
  int n; cin >> n;
  cout << n / 3 << '\n';
  return 0;
}


Measured memory_bytes: 256
use proconio::{fastout, input};

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

    let mut ans: f64 = 0.0;
    for mut i in 1..=n {
        let mut count = 1;
        while i < k {
            i *= 2;
            count *= 2;
        }
        ans += 1f64 / count as f64;
    }

    println!("{:.12}", ans / n as f64);
}


Measured memory_bytes: 2220
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

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(), greater<ll>());

    ll e[2] = {};
    int index = 0;
    for (int i = 0; index < 2 && i < n - 1; ++i) {
        if (a[i] == a[i + 1]) {
            e[index] = a[i];
            ++i;
            ++index;
        }
    }
    cout << e[0] * e[1] << endl;
    return 0;
}

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

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

long long dp[1000005];

const long long MOD = 1e9+7;

int main(){
    int N, H, D;
    scanf("%d%d%d", &N, &H, &D);

    long long retainWays = 0;
    long long fact = 1;
    for(int i = 1; i <= N; i ++){
        fact = fact*i%MOD;
        retainWays += fact;
    }
    retainWays %= MOD;

    //printf("retainWays=%lld\n", retainWays);

    dp[0] = fact;
    long long slidingWindowSum = dp[0];
    for(int i = 1; i <= H; i ++){
        dp[i] = slidingWindowSum;

        if(i == H){break;}

        dp[i] = dp[i]*retainWays%MOD;
        slidingWindowSum += dp[i];
        if(i >= D){slidingWindowSum -= dp[i-D];}

        if(slidingWindowSum >= MOD){slidingWindowSum -= MOD;}
        else if(slidingWindowSum < 0){slidingWindowSum += MOD;}

        //printf("dp[%d]=%lld\n", i, dp[i]);
    }

    printf("%lld", dp[H]);
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define ri register int
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void gi (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = (x << 1) + (x << 3) + (c & 15); x *= f;
	}
	// input a letter
	template <class I>
	inline void get (I &x) {
		for (c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		x = c;
	}
	// input a string
	inline void read (char *s){
		for(c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		for(; c >= 'A' && c <= 'Z'; c = gc()) *++s = c;
		*++s = '\0';
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: get;
using io :: read;
using io :: putc;
using io :: print;
const int N=105;
int tot,head[N],nxt[N<<1],adj[N<<1],dis,p,s,t,st[N],top,mx[N],mxd;
inline void addedge(ri x,ri y){
	nxt[++tot]=head[x];
	adj[head[x]=tot]=y;
}
inline void dfs(ri x,ri fa,ri now){
	if(now>dis) dis=now,p=x;
	for(ri y,i=head[x];i;i=nxt[i])
		if((y=adj[i])!=fa)
			dfs(y,x,now+1);
}
inline bool dfs(ri x,ri fa){
	st[++top]=x;
	if(x==t) return true;
	for(ri y,i=head[x];i;i=nxt[i])
		if((y=adj[i])!=fa&&dfs(y,x))
			return true;
	--top;
	return false;
}
inline void dp(ri x,ri fa,ri dep){
	ri i,y,deg=0;
	for(i=head[x];i;i=nxt[i])
		if((y=adj[i])!=fa)
			dp(y,x,dep+1),
			++deg;
	mx[dep]=max(mx[dep],deg);
	mxd=max(mxd,dep);
}
int main(){
	ri n,i,x,y,o;
	gi(n);
	for(i=1;i^n;++i) gi(x),gi(y),addedge(x,y),addedge(y,x);
	dis=-1;
	dfs(1,0,0);
	s=p;
	dis=-1;
	dfs(s,0,0);
	t=p;
	dfs(s,0);
	register long long ans,res;
	ans=9e18;
	for(x=1;x<=n;++x){
		dp(x,0,1);
		if(mxd==top+1>>1){
			res=1;
			for(i=1;i^mxd;++i) res*=mx[i];
			ans=min(ans,res);
		//	printf("dp %d %lld\n",x,res);
		}
		for(i=1;i^mxd;++i) mx[i]=0;
		mxd=0;
	}
	for(x=1;x<=n;++x)
		for(o=head[x];o;o=nxt[o]){
			y=adj[o];
			dp(x,y,1);
			dp(y,x,1);
			if(mxd==top+1>>1){
				res=2;
				for(i=1;i^mxd;++i) res*=mx[i];
				ans=min(ans,res);
			//	printf("dp %d %d %lld\n",x,y,res);
			}
			for(i=1;i^mxd;++i) mx[i]=0;
			mxd=0;
		}
	printf("%d %lld\n",top+1>>1,ans);
	return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
const int MAX_V = 200000;
struct edge
{
    ll to;
    ll cost;
};
vector<vector<edge>> G(MAX_V);
vector<ll> dijkstra(ll s, ll N)
{
    vector<ll> value(N, INF);
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
    value[s] = 0;
    while (!que.empty())
    {
        P p = que.top();
        que.pop();
        ll v = p.second;
        if (value[v] < p.first)
        {
            continue;
        }
        rep(i, G[v].size())
        {
            edge e = G[v][i];
            if (value[e.to] > value[v] + e.cost)
            {
                value[e.to] = value[v] + e.cost;
                que.push(P(value[e.to], e.to));
            }
        }
    }

    return value;
}

int main()
{
    int N;
    cin >> N;
    rep(i, N - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    
    int Q, K;
    cin >> Q >> K;
    K--;

    vector<ll> res = dijkstra(K, N);
    rep(i, Q) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << res[x] + res[y] << endl;
    }
    
    return 0;
}

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

#define ff first
#define ss second
#define ll long long
#define pq priority_queue
#define mii map<int,int>

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef set<int> si;
typedef vector<vi> vii;
typedef vector<ii> vpi;
typedef vector<ll> vll;
int oo = (1e9) + 7;

string s, t;
int tb[3005][3005];
ii aux[3005][3005];

int dp(int i, int j) {
    if(i == (int)s.size() or j == (int)t.size()) return 0;
    if(tb[i][j] != -1) return tb[i][j];

    int tmp1 = dp(i+1, j);
    int tmp2 = dp(i, j+1);
    aux[i][j] = tmp1 > tmp2 ? ii(i+1, j) : ii(i, j+1);
    int ans = max(tmp1, tmp2);
    if(s[i] == t[j]) {
        int tmp = dp(i+1, j+1)+1;
        if(tmp > ans) aux[i][j] = ii(i+1, j+1), ans = tmp;
    }

    tb[i][j] = ans;
    return ans;
}

void build(int i, int j) {
    if(i == (int)s.size() or j == (int)t.size()) return;

    if(aux[i][j] != ii(0,0)) {
        if(aux[i][j].ff == i+1 and aux[i][j].ss == j+1) printf("%c", s[i]);
        // else if(aux[i][j].ff == i+1) printf("%c ", s[i]);
        // else printf("%c ", t[j]);
    }
    build(aux[i][j].ff, aux[i][j].ss);
}

int main() {
    cin >> s >> t;

    memset(tb, -1, sizeof tb);
    dp(0, 0);
    build(0, 0);


    return 0;
}

Measured memory_bytes: 106496
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())



class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
	n,m=map(int,input().split())
	uf=WeightedUnionFind(n)
	
	for i in range(m):
		l,r,d=map(int,input().split())
		if uf.same(l,r):
			if d!=uf.diff(l,r):
				print("No")
				exit(0)
		else:
			uf.union(l,r,d)
	print("Yes")
	
if __name__ == '__main__':
	main()

Measured memory_bytes: 96560
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	int n;
	int m;
	ArrayList<Pair> pairList;
	
	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		n = fs.nextInt();
		m = fs.nextInt();
		int q = fs.nextInt();
		
		pairList = new ArrayList<>();
		for(int i = 0; i < q ; i++) {
			int a = fs.nextInt()-1;
			int b = fs.nextInt()-1;
			int c = fs.nextInt();
			int d = fs.nextInt();
			pairList.add(new Pair(a,b,c,d));
		}
		
		int[] mArr = new int[n];
		mArr[0] = 1;
		System.out.println(dfs(1, mArr));
		
		
	}
	
	
	int dfs(int depth, int[] mArr){
		
		if(depth == n) {
			int score = 0;
			for(Pair pair : pairList) {
				if(mArr[pair.b] - mArr[pair.a] == pair.c) {
					score += pair.d;
				}
			}
			return score;
		}
		
		int beforeVal = mArr[depth-1];
		int max = 0;
		
		for(int i = beforeVal; i <= m; i++) {
			mArr[depth] = i;
			max = Math.max(max, dfs(depth+1,mArr));
		}
		
		return max;
	}
	
	class Pair{
		int a;
		int b;
		int c;
		int d;
		
		Pair(int a, int b, int c, int d) {
			this.a = a;
			this.b = b;
			this.c = c;
			this.d = d;
		}
		
		int getB() {
			return b;
		}
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}


}


Measured memory_bytes: 36044
def bit_set(num:int,n:int):
  if num & (1<<n):
    return True
  return False

n,m,x = map(int,input().split())
ca_list = [list(map(int,input().split())) 
           for nesya in range(n)]
c = -1
for i in range(2**n):
  skill = [0]*m
  cost = 0
  for k in range(n):
    if bit_set(i,k) == True:
      ca =  ca_list[k]
      cost += ca[0]
      a = ca[1:]
      skill = [j+l for (j,l) in zip(skill, a)]
  if all((hoge >= x) for hoge in skill):
    if c == -1:
      c = cost
    else:
      c = min(c,cost)
print(c)

Measured memory_bytes: 9212
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

#define rep(p,q) for(int i = p;i < q;i++)

using namespace std;

//A
int main(void) {
	long long alp[26];
	rep(0, 26)alp[i] = 0;
	int n;
	char c;
	cin >> n;
	rep(0, n) {
		cin >> c;
		alp[(int)(c - 'a')]++;
	}
	long long div = 1000000000 + 7;
	long long ans = 1;
	rep(0, 26) {
		if (alp[i] == 0) continue;
		ans = ans * (alp[i] + 1) % div;
	}
	ans--;
	if (ans < 0)ans = div - 1;
	cout << ans << endl;
}

Measured memory_bytes: 256