akhauriyash/Code-Regression huggingface dataset:
n = int(input())


sosu = "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997"
ls = list(map(int,sosu.split()))
def solve(n,k,cnt):
    if n%k!=0:
        return cnt
    else:
        return solve(n//k,k,cnt+1)


from collections import defaultdict
d = defaultdict(int)
for i in range(1,n+1):
    for j in ls:
        d[j] += solve(i,j,0)

ans = 1
for i in d.values():
    ans = (ans*(i+1))%(10**9+7)
print(ans%(10**9+7))



Measured memory_bytes: 40432
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int main(){
    long long h, w;
    cin >> h >> w;

    char maze[h][w];
    long long cnt = 0;
    for(long long i = 0; i < h; i++){
        for(long long j = 0; j < w; j++){
            cin >> maze[i][j];
            if(maze[i][j] == '.') cnt++;
        }
    }

    long long sy = 0, sx = 0, gy = h-1, gx = w-1;

    vector<vector<long long> > distance(h, vector<long long> (w, -1));
    queue<pair<long long, long long> > q;

    q.push(make_pair(sy, sx));
    distance[sy][sx] = 0;

    long long dy[] = {1, -1, 0, 0};
    long long dx[] = {0, 0, 1, -1};

    while(!q.empty()){
        pair<long long, long long> top;
        top = q.front();
        q.pop();

        for(long long i = 0; i < 4; i++){
            if(0 <= top.first+dy[i] and top.first+dy[i] < h and 0 <= top.second+dx[i] and top.second+dx[i] < w and distance[top.first+dy[i]][top.second+dx[i]] == -1 and maze[top.first+dy[i]][top.second+dx[i]] == '.'){
                distance[top.first+dy[i]][top.second+dx[i]] = distance[top.first][top.second] + 1;
                q.push(make_pair(top.first+dy[i], top.second+dx[i]));
            }
        }
    }
    long long ans = -1;

    if(distance[gy][gx] != -1){
        ans = cnt - distance[gy][gx] -1;
    }

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

Measured memory_bytes: 3632
from fractions import gcd
N = int(input())
*A, = map(int, input().split())

left = [0] * (N + 1)
right = [0] * (N + 1)

# left[p] := 区間[0, p)までの最大公約数
for i in range(N):
    left[i+1] = gcd(left[i], A[i])

# right[p] := 区間[p, N)までの最大公約数
for i in reversed(range(N)):
    right[i] = gcd(right[i+1], A[i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(left[i], right[i+1]))
print(ans)

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

const double pi = acos(-1);

typedef complex <double> Complex;
struct Point {
    double x, y;
    Point (double x = 0, double y = 0) : x(x), y(y) { }
    Point operator+ (const Point & a) const {
        return { x + a.x, y + a.y };
    }
    Point operator- (const Point & a) const {
        return { x - a.x, y - a.y };
    }
    Point operator* (const double a) const {
        return { x * a, y * a };
    }
    Point operator/ (const double a) const {
        return { x / a, y / a };
    }
    double operator* (const Point & a) const {
        return (x * a.y - y * a.x);
    }
};

double det(Point a, Point b, Point c)
{
    return (a - c) * (b - c);
}

using Poly = vector<Point>;
pair<Poly, Poly> ConvexHull(Poly P) {
  sort(P.begin(), P.end(), [](Point a, Point b) {
    return make_pair(a.x, a.y) < make_pair(b.x, b.y);
  });

  Poly up, dw;
  for (auto p : P) {
    while (up.size() >= 2 &&
           det(up[up.size() - 2], up.back(), p) >= 0) // (1)
      up.pop_back();
    up.push_back(p);

    while (dw.size() >= 2 &&
          det(dw[dw.size() - 2], dw.back(), p) <= 0) // (2)
      dw.pop_back();
    dw.push_back(p);
  }
  return { up, dw };
}

map <pair <int, int>, int> mp;
double rez[1001];

int main()
{
    int n, a, b;
    vector <Point> p;
    cin >> n;

    for (int i(1); i <= n; i++) {
        rez[i] = 0;
        cin >> a >> b;
        mp[{ a, b }] = i;
        p.push_back({ a, b });
    }

    pair <Poly, Poly> q = ConvexHull(p);

    if (q.first.size() + q.second.size() < 4) {
        while (1)
            ;
    }
    Poly ans = q.first;

    if (q.second.back().x == ans.back().x && q.second.back().y == ans.back().y)
        q.second.pop_back();


    reverse(q.second.begin(), q.second.end());

    for (auto i : q.second)
        ans.push_back(i);

    if (ans[0].x == ans.back().x && ans[0].y == ans.back().y)
        ans.push_back(ans[1]);
    else {
        ans.push_back(ans[0]);
        ans.push_back(ans[1]);
    }

    for (int i(1); i < ans.size() - 1; i++) {
        Point act = ans[i];
        Point x = ans[i - 1] - ans[i], y = ans[i + 1] - ans[i];
        swap(a, b);
        double angle = atan2(y.y, y.x) - atan2(x.y, x.x);
        if (angle < 0)
            angle += 2 * pi;
        if (angle > pi)
            angle = 2 * pi - angle;
        int where = mp[{ ans[i].x, ans[i].y }];
        rez[where] = (pi - angle) / (2 * pi);
    }

    cout << setprecision(9) << fixed;
    for (int i(1); i <= n; i++)
        cout << rez[i] << '\n';

    return 0;
}


Measured memory_bytes: 256
import numpy as np
import sys

n=int(sys.stdin.readline())
a=np.array([sys.stdin.readline() for _ in range(n)],dtype='int64')

ma=a.max()
ju=0
for i in range(n):
    if a[i]!=ma or ju==1:
        print(ma)
    else:
        if i==0:
            b=max(a[i+1:])
        elif i==n-1:
            b=max(a[:i])
        else:
            b=max(max(a[:i]),max(a[i+1:]))
        if ju==0:
            if b==ma:
                ju=1
            else:
                ju=-1
        print(b)
            


Measured memory_bytes: 32980
#pragma GCC optimize(3)
#include <iostream>
#include <cmath>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],d1[N],n;
int main()
{
	cin>>n;
    for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int len1=1;
	d1[1]=a[1];
	for(int i=2; i<=n; i++)
	{
	    if(d1[len1]>=a[i])d1[++len1]=a[i];
	    else *upper_bound(d1+1,d1+1+len1,a[i],greater<int>())=a[i];
    }
    printf("%d\n",len1);
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define MOD 1000000007
#define INF 1000000007
#define PI 3.14159265358979323846
using namespace std;
//
int main(){
  int N,A[100],MIN=INF;
  cin>>N;
  FOR(i,0,N){
    cin>>A[i];
  }
  FOR(X,-100,101){
    int cost=0;
    FOR(i,0,N){
      cost+=(X-A[i])*(X-A[i]);
    }
    MIN=min(MIN,cost);
  }
  cout<<MIN<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		int ans = 0;
		for (int i = 1; i < s.length; i++) {
			if(s[i] != s[i-1]) ans++;
		}
		System.out.println(ans);
		sc.close();
	}
}


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


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N, A, B, C, D;
  cin>>N>>A>>B>>C>>D;

  Int ans = 0;
  for(Int i=0;i<N;i++){
    Int a = i; // -D <= d <= -C
    Int b = (N - i - 1); // C <= d <= D
    Int l = -(D * a) + C * b;
    Int r = -(C * a) + D * b;
    ans |= l <= B - A && B - A <= r;
  }

  if(ans) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
  
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
L = []
R = []
for _ in range(M):
    tmp1,tmp2 = map(int,input().split())
    L.append(tmp1)
    R.append(tmp2)

max_L = L[0]
min_R = R[0]
for i in range(1,M):
    max_L = max(max_L, L[i])
    min_R = min(min_R, R[i])

if min_R >= max_L:
    res = min_R - max_L + 1
else:
    res = 0
print(res)

Measured memory_bytes: 10996
N,M = map(int,input().split())
DP = [[10**9]*(2**N)for i in range(M+1)]
DP[0][0] = 0
key = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    rock = 0
    for j in c:
        rock += 2**(j-1)
    key.append([a,rock])
for i in range(M):
    for j in range(2**N):
        DP[i+1][j] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j - (j&key[i][1])])
ans = DP[-1][-1]
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 78296
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n=I()
L=LI()
R=LI()
h=[() for i in range(n)]

p=0

for i in range(n):
    c=L[i]
    if c>p:
        h[i]=(c,c)
    else:
        h[i]=(1,c)
    p=c

p=0
for i in range(n-1,-1,-1):
    c=R[i]
    l,r=h[i]
    if c>p:
        if l==r:
            if l!=c:
                h[i]=(c,c-1)
        elif l<=c<=r:
            h[i]=(c,c)
        else:
            h[i]=(c,c-1)
    else:
        h[i]=(max(l,1),min(r,c))
    p=c

ans=1
for i in range(n):
    l,r=h[i]
    ans*=r-l+1
    ans%=mo

print(ans)


Measured memory_bytes: 79124
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define REPR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m, n) for(int i = m-1; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))
#define FILL2D(A,c) fill(A[0], A[0] +sizeof(A)/sizeof(**A),c)
#define FILL3D(A,c) fill(A[0][0], A[0][0] +sizeof(A)/sizeof(***A),c)
//vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))
//vector<intなど> 変数名(要素数,初期値)
using namespace std;
typedef long long ll;
const int MAX = 510000;
const int INF =2000000000;
const int MOD = 1000000007;
//gcd,lcmセット
ll gcd(ll a, ll b){
   if (a%b == 0) return b;
   else return gcd(b, a%b);
}
ll lcm(ll a, ll b){	
   return a*b/gcd(a, b);
}
int pow_kai(int a, int n){//aのn乗を計算します。
  int x = 1;
  while(n > 0){//全てのbitが捨てられるまで。
    if(n&1){//1番右のbitが1のとき。
      x = x*a;
    }
    a = a*a;
    n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
  }
  return x;
}
// a^n mod を計算する
long long modPow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
// a^{-1} mod を計算する
ll modInv(ll a, ll mod) {
    return modPow(a, mod - 2, mod);
}

long long fac[MAX], finv[MAX], inv[MAX];

// combinationのテーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
 
bool isPrime(ll x){
    int i;
    if(x < 2)return false;
    else if(x == 2) return true;
    if(x%2 == 0) return false;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return false;
    return true;
}
//dfsではvector<vector<int>> g(n);で◎
int main() {
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b&&b==c)cout<<"No";
    else if(a==b||a==c||b==c)cout<<"Yes";
    else cout<<"No";
    cout<<endl;
}

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

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

using namespace std;

int main(){
	int h,w,n,a[10000];
	cin>>h>>w>>n;

	vector<int> v;
	rep(c,n){ int a; cin>>a; rep(_,a) v.emplace_back(c); }

	int B[100][100];
	rep(i,h) rep(j,w) B[i][i%2==0?j:w-j-1]=v[i*w+j];
	rep(i,h) rep(j,w) cout<<B[i][j]+1<<(j<w-1?' ':'\n');

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
long long kub[1000002], seq[1000002], nast[1000002], last[1000002];
int tab[1000002];
long long wyn[1000002];
const int mod = 1000000007;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        cin >> tab[i];
    }
    tab[n]=-1;
    long long wyn=1;
    for (int i=n-1; i>=0; i--)
    {
        if (last[tab[i]]==0)
            nast[i]=1000001;
        else
            nast[i]=last[tab[i]];
        last[tab[i]]=i;
        kub[i]=kub[nast[i]];
        if (tab[i+1]!=tab[i])
        {
            kub[i]+=wyn;
            kub[i]%=mod;
        }
        else
            seq[i]=seq[i+1]+1;
        if (i==0 || tab[i-1]!=tab[i])
        {
            wyn+=kub[nast[i+seq[i]]];
            wyn%=mod;
        }
        //cout << nast[i] << " " << seq[i] << " " << kub[i] << "\n";
    }
    cout << wyn;
}


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

int n;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	bool val = true;
	for(int i = 0; i < n; i++){
		int a;
		cin >> a;
		if(a % 2 == 0 && (a % 3 && a % 5)) val = false;
	}
	cout << (val ? "APPROVED\n" : "DENIED\n");
	return 0;
}

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

#define N_SUM(X) (((X)*((X)+1))/2)

using namespace std;

int main(void)
{
    unsigned long long  N; 
    cin >> N;
    cout << N_SUM(N) - (3*N_SUM(N/3)) - (5*N_SUM(N/5)) + (15*N_SUM(N/15)) << endl;
    return 0;
}


Measured memory_bytes: 3624
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt();
        int w = scanner.nextInt();
        List<String> list = new ArrayList<>();
        long[] dp = new long[w];
        for(int i = 0; i < h; i++){
            list.add(scanner.next());
        }
        int k = h;
        for(int i = 0; i < h; i++){
            if(list.get(i).charAt(0) == '#'){
                k = i;
                break;
            }
        }
        for(int i = 0; i < w; i++){
            if(list.get(0).charAt(i) == '#')
                break;
            dp[i] = 1;
        }
        for(int i = 1; i < h; i++){
            for(int j = 0; j < w; j++){
                if(list.get(i).charAt(j) == '#'){
                    dp[j] = 0;
                }else{
                    if(j == 0){
                        if(i < k){
                            dp[j] = 1;
                        }else{
                            dp[j] = 0;
                        }
                    }else{
                        dp[j] += dp[j-1];
                    }
                    dp[j] %= 1000000007;
                }
            }
        }
        System.out.println(dp[w-1]);
    }
}


Measured memory_bytes: 31336
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include<cmath>
#include<vector>
#include<map>
#include<algorithm>

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

using namespace std;
typedef long long ll;



int main(void){
	string s;
	int k;
	vector<char> vec;

	cin >> k >> s;
	if (k < s.size()) {
		for (int i = 0; i < k;i++) {
			vec.push_back(s[i]);
		}
		for(int i=0; i<k;i++) {
			cout << vec[i];
		}
		cout << "...";
	}
	else
		cout << s;
	

	cout << endl;
}


Measured memory_bytes: 3628
import Control.Monad

main :: IO ()
main = do
  wh <- getLine
  
  let wh' :: [Int]
      wh' = map read (words wh)
  ss <- replicateM (head wh') getLine
  let ans = fix (solve ss)
  mapM putStrLn ans
  return ()

solve :: [String] -> [[Int]]
solve [] = []
solve (xs:xss) = (change xs):(solve xss)
  where
    change :: String -> [Int]
    change ss = change' ss (-1000)
      where
        change' :: String -> Int -> [Int]
        change' [] count = []
        change' ('c':xs) count = (0:(change' xs 1))
        change' ('.':xs) count
          | count < 0 = (-1:(change' xs count))
          | otherwise = (count:(change' xs (count+1)))
fix :: [[Int]] -> [String]
fix [] = []
fix (x:xs) = (fix' x):(fix xs)
  where
    fix' :: [Int] -> String
    fix' [] = ""
    fix' (x:[]) = (show x)
    fix' (x:xs) = ((show x) ++ " ") ++ (fix' xs)

Measured memory_bytes: 4464
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <cstring>
#include <sstream>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i,l,r) for(int i=(l);i<(r);i++)
#define forb(i,r,l) for(int i=(r);i>(l);i--)
#define sqr(x) (x)*(x)
#define log2i(x) 32 - __builtin_clz((x)) - 1
#define log2l(x) 64 - __builtin_clzll((x)) - 1
#define inf1 int(1e9+7)
#define inf2 0x3f3f3f3f
#define infll ll(1e18+7)
#define Pi acos(-1.0)
#define mu(x,y) trunc(exp(log((x))*(y)))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

int n,ans=0;
int a[100005];

int main() {
    fastIO;
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);

    cin >> n;
    forw(i,0,n) cin >> a[i];
    sort(a,a+n);
    cout << a[n/2]-a[n/2-1];
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main() {
	while (1) {
		int a, b, result;
		char op;
		scanf("%d %c %d\n", &a, &op, &b);

		if (op == '?') break;

		switch (op) {
			case '+':
				result = a + b;
				break;

			case '-':
				result = a - b;
				break;

			case '*':
				result = a * b;
				break;

			case '/':
				result = a / b;
				break;
		}

		printf("%d\n", result);
	}


	return 0;
}


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

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

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

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

  cout << min(a, min(b,c)) << " " << max(a, max(b,c)) << endl;
  return 0;
}



Measured memory_bytes: 3088
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

//snuke
struct Sieve {
  ll n;
  vector<ll> f, primes;
  Sieve(ll n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    //エラトステネスの篩
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        //最小素因数がかかれるようにしている
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(ll x) { return f[x] == x;}
  //素因数列挙
  vector<ll> factorList(ll x) {
    vector<ll> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  //頻度を集計したもの
  vector<P> factor(ll x) {
    vector<ll> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (ll p : fl) {
      //小さい順に出てくるので前回と同じなら足す作業でmapが作れる
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
};

int main(){
  Sieve sieve(1e7 + 10);
  ll N; cin >> N;
  ll ans = 0;
  repn(i,N){
    vector<P> a = sieve.factor(i);
    ll tmp = 1;
    rep(j , a.size()){
      tmp *= a[j].sc + 1;
    }
    ans += tmp * i;
  }
  cout << ans << endl;
}


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

int f(int n){
    if(n == 1)return 1;
    if(n == 2)return 2;
    if(n == 3)return 4;
    return f(n-1) + f(n-2) +f(n-3);
}

int main(void){
    while(true){
        int n;
        cin >> n;
        if(n==0)break;
        cout << (f(n) / 3650)+1 << endl;
    }
}


Measured memory_bytes: 2984
#include <algorithm>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

using P = pair<ll, ll>;

struct Item {
  int v;
  ll w, m;
};

vector<P> ps;
ll best;

pair<ll, bool> upper_bound(int i, ll W) {
  ll res = 0;
  bool integer = true;
  for (; i < ps.size() && W > 0; i++) {
    if (ps[i].snd > W) {
      res += __int128(ps[i].fst) * W / ps[i].snd;
      integer = false;
    } else {
      res += ps[i].fst;
    }
    W -= ps[i].snd;
  }
  return make_pair(res, integer);
}

void dfs(int i, ll V, ll W) {
  if (W < 0) return;
  if (i >= ps.size()) {
    if (V > best) best = V;
    return;
  }
  auto ub = upper_bound(i, W);
  if (V + ub.fst <= best) return;
  if (ub.snd) {
    best = V + ub.fst;
    return;
  }
  dfs(i + 1, V + ps[i].fst, W - ps[i].snd);
  dfs(i + 1, V, W);
}

ll solveKnapsackBB(ll W, const vector<Item>& items) {
  ps.clear();
  for (auto& item : items) {
    ll num = item.m;
    for (ll k = 1; num > 0; k <<= 1) {
      ll mul = min(num, k);
      if (mul * item.w > W) break;
      ps.emplace_back(mul * item.v, mul * item.w);
      num -= mul;
    }
  }
  sort(ps.begin(), ps.end(), [&](const P& a, const P& b) {
    auto x = __int128(a.fst) * b.snd;
    auto y = __int128(b.fst) * a.snd;
    if (x != y) return x > y;
    return a.fst > b.fst;
  });
  best = 0;
  dfs(0, 0, W);
  return best;
}

int main() {
  int N;
  ll X, D;
  while (cin >> N >> X >> D) {
    vector<ll> m(N);
    cin >> m[0];
    vec<int, 2> G(N);
    for (int i = 1; i < N; i++) {
      int p;
      cin >> m[i] >> p;
      --p;
      G[p].push_back(i);
    }
    vector<int> sz(N);
    vector<ll> msum(N);
    function<void(int)> dfs = [&](int v) {
      sz[v] = 1;
      msum[v] = m[v];
      for (int u : G[v]) {
        dfs(u);
        sz[v] += sz[u];
        msum[v] += msum[u];
      }
    };
    dfs(0);
    vector<Item> items;
    for (int i = 0; i < N; i++) {
      ll lim = D;
      if (i == 0) lim = X / msum[0];
      items.push_back({sz[i], msum[i], lim});
    }
    cout << solveKnapsackBB(X, items) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
int  main(){
  int n;
  cin >>n;
  string s;
  cin >> s;
  int ans = 0;
  for(int i=0;i<n;i++){
    int che =0;
    for(char z ='a';z<='z';z++){
      bool l=false,r=false;
      for(int j=0;j<i;j++){
        if(z==s.at(j))l=true;
      }
      for(int j=i;j<n;j++){
        if(z==s.at(j))r=true;
      }
      if(l&&r)che++;
    }
    ans = max(ans,che);
  }
  cout << ans << endl;
}







Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define minimize(a,b) (a>(b)?a=(b),1:0)
#define maximize(a,b) (a<(b)?a=(b),1:0)
#define ceil(a,b) (((a)+(b)-1)/(b))
#define yn(i) ((i)?"Yes":"No")
#define chmin(a,b) (a>(b)?a=(b),1:0)
#define abs(n) max((n),-(n))
#define dist(a,b) max((a)-(b),(b)-(a))
#define chmax(a,b) (a<(b)?a=(b),1:0)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define MOD 1000000000
#define rep(i,n) for(int i=0;i<(n);i++)

#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << " ";
    cout << *(itr++);
  }
  return os;
}




string key="keyence";

void add(char m,string s,set<string> st){
  int n=s.size();
  rep(i,n){
    if(s[i]!=m) continue;
    string t;
    repa(j,i,n){
      t.push_back(s[j]);
      st.insert(t);
    }
  }
}

int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}

int main(){
  int n,x,t; cin >>n >>x >>t;
  print(ceil(n,x)*t);
}





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

int main()
{
  int n; cin >> n;
  int h[n];
  for(int i=0 ; i<n ; i++)
    cin >> h[i];
  int cost[n] = {0};
  cost[1] = abs(h[0] - h[1]);
  cost[2] = min(abs(h[0] - h[2]) , cost[1] + abs(h[1] - h[2]));
  for(int i=3 ; i<n ; i++)
    cost[i] = min(cost[i-1] + abs(h[i-1] - h[i]) , cost[i-2] + abs(h[i-2] - h[i]));
  cout << cost[n-1];
}

Measured memory_bytes: 1024
use std::thread;

/// ローカル環境なら _in.txt から入力を受ける
fn read_input() -> String {
    use std::fs::File;
    use std::io::Read;
    let mut s = String::new();
    match option_env!("LOCAL") {
        Some(_) => File::open("src/_in.txt")
            .expect("File not found")
            .read_to_string(&mut s)
            .unwrap(),
        None => std::io::stdin().read_to_string(&mut s).unwrap(),
    };
    s
}

fn main() {
    thread::Builder::new()
        .stack_size(32 * 1024 * 1024) // 32MB
        .spawn(run)
        .unwrap()
        .join()
        .unwrap();
}

fn run() {
    let input = read_input();
    let mut input = input.split_whitespace();
    let in_s: &str = input.next().unwrap();
    println!("{} {}", &in_s[..4], &in_s[4..]);
}


Measured memory_bytes: 8572
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n, m;
// 素集合データ構造
struct UnionFind
{
  // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
  vector<int> par;
  // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
  vector<int> sizes;

  UnionFind(int n) : par(n), sizes(n, 1) {
    // 最初は全てのデータiがグループiに存在するものとして初期化
    rep(i,n) par[i] = i;
  }

  // データxが属する木の根を得る
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
  }

  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // データの根ノードを得る
    x = find(x);
    y = find(y);

    // 既に同じ木に属しているならマージしない
    if (x == y) return;

    // xの木がyの木より大きくなるようにする
    if (sizes[x] < sizes[y]) swap(x, y);

    // xがyの親になるように連結する
    par[y] = x;
    sizes[x] += sizes[y];
    // sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
  }

  // 2つのデータx, yが属する木が同じならtrueを返す
  bool same(int x, int y) {
    return find(x) == find(y);
  }

  // データxが含まれる木の大きさを返す
  int size(int x) {
    return sizes[find(x)];
  }
};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>m;
    vector<vector<int> > a(n), b(m);
    UnionFind uf(n+m);
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        for(int j=0;j<temp;j++){
        int temp1;
        cin>>temp1;
        temp1--;
        //a[i].push_back(temp1);//人が話せる言語
        uf.unite(i,n+temp1);
        }
    }
    for(int i=0;i<n-1;i++){
        //cout<<uf.find(i)<<" "<<uf.find(i+1)<<"\n";
        if(!uf.same(i,i+1)) return cout<<"NO"<<"\n",0;
    }
    cout<<"YES"<<"\n";
}



Measured memory_bytes: 6528
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define pb push_back
#define vect(x) vector<x>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
using namespace __gnu_pbds; 
using namespace std;


ll valueOfIndex(ordered_set&s , ll i){ return *(s.find_by_order(i)); }
ll indexOfValue(ordered_set&s , ll x){ return s.order_of_key(x); }

ll add(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a+b + p)%p;}
ll mul(ll a, ll b,ll p=MOD) { a%=p; b%=p; return ((__int128)a*b + p)%p;}

ll power(ll x,ll n,ll p=MOD){ if(x==0) return 0; if(n==0 || x==1) return 1LL;
    ll r = (power(x,n/2,p))%p; if(n&1) return mul(mul(r,r,p) , x,p); else return mul(r,r,p);
}




void solve()
{
    string a,b;
    cin >> a >> b;
    ll na=a.size() , nb = b.size();
    ll dp[na+2][nb+2];
    memset(dp,0,sizeof(dp));
    for(ll i=1;i<=na;i++)
    {
        for(ll j=1;j<=nb;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j] = 1 + dp[i-1][j-1];
            }
            else
            {
                dp[i][j] = max( dp[i-1][j] , dp[i][j-1] );
            }
        }
    }
    string s="";
    ll i=na , j=nb;
    while(i>0 && j>0)
    {
        if(a[i-1]==b[j-1])
        {
            s+= b[j-1];
            i--;
            j--;
        }
        else
        {
            if(dp[i-1][j] > dp[i][j-1])
            {
                i = i-1;
                
            }
            else j=j-1;
        }
    }
    reverse(all(s));
    cout << s;
    
}


int main()
{
    
    fastio
    
    ll tc=1;
   // read(tc);
    while(tc--)
    {
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 70656
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
using ll = long long;
const ll INF=1e15;
#define F first
#define S second
#define I XH[i]


ll N,D,A,now=0,res=0;
pair<ll,ll>XH[200005];
queue<pair<ll,ll> >P;
int main() {
	
	cin>>N>>D>>A;
	for(ll i=0;i<N;i++){
		cin>>I.F>>I.S;
	}
	sort(XH,XH+N);
	for(ll i=0;i<N;i++){
		while(!P.empty()&&P.front().F<I.F){
			now-=P.front().S;
			P.pop();
		}

		I.S-=now;
		
		if(I.S>0){
			res+=(I.S+A-1)/A;
			P.push({I.F+2*D,((I.S+A-1)/A)*A});
			now+=((I.S+A-1)/A)*A;
		}
	}
	cout<<res;
} 


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

#define ln '\n'
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    VP a(n);
    REP(i, n) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(ALL(a), greater<P>());

    REP(i, n) {
        if (i == a[0].second)
            cout << a[1].first << ln;
        else
            cout << a[0].first << ln;
    }

    return 0;
}


Measured memory_bytes: 3200
#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str;
	int n;
	int E=0,out=0,score=0,base=0;
	
	cin >> n ;
	for(;;)
	{
		if(E==n)
			break;
		cin >> str ;
		if(str=="OUT")
		{
			out++;
		}
		else if(str=="HIT")
		{
			base++;
			if(base==4)
			{
				score++;
				base--;
			}
		}
		else
		{
			score+=base+1;
			base=0;
		}
		
		if(out==3)
		{
			cout << score << endl;
			out=base=score=0;
			E++;
		}
	}
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(){
  int a,b;
  char map[300][300];
  while(1){
    cin>>a>>b;
    if(a==0&&b==0){
      break;
    }
    for(int i=0;i<a;i++){
      for(int j=0;j<b;j++){
	if(j==0||i==0||j==b-1||i==a-1){
	map[j][i]='#';
	}else if(j!=0||i!=0){
	  map[j][i]='.';
	}
	cout<<map[j][i];
      }
      cout<<endl;
    }
    cout<<endl;
  }
  return(0);
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)

map<ll,ll> dp;

ll Lucas(ll num)
{
    if(dp.count(num)){
        return dp.at(num);
    }
    else if (num == 0)
    {
        dp[num] = 2;
        return 2;
    }
    else if (num == 1)
    {
        dp[num] = 1;
        return 1;
    }
    else
    {
        dp[num] = Lucas(num - 1) + Lucas(num - 2);
        return dp.at(num);
    }
}

int main()
{
    ll N;
    cin >> N;
    cout << Lucas(N) << endl;
    return 0;
}

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

n = int(input())
s = [input() for i in range(n)]

m = int(input())
t = [input() for i in range(m)]

sset = list(set(s))

ans = 0
for i in range(len(sset)):
    a = sset[i]
    ans = max(ans, s.count(a) - t.count(a))

print(ans)

Measured memory_bytes: 3064
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    d = [inf]*N
    d[K] = 0
    que = []
    heappush(que, K)

    while que:
        v = heappop(que)
        for b, c in adj[v]:
            if d[b] > d[v] + c:
                d[b] = d[v] + c
                heappush(que, b)

    for i in range(Q):
        x, y = MAP()
        print(d[x-1]+d[y-1])

if __name__ == '__main__':
    solve()

Measured memory_bytes: 51520
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1L<<32;
ll fac[MAX], finv[MAX], inv[MAX];
//ワーシャルフロイド法、o(v^3)
int main(){
  ll v,e,r,ans=MOD;cin>>v>>e>>r;
  vll rr(r);
  rep(i,0,r){cin>>rr[i];rr[i]--;}
  vvll g(v,vll(v,MOD));
  rep(i,0,e){
    ll s,t,d;cin>>s>>t>>d;
    s--;t--;
    g[s][t]=d;
    g[t][s]=d;
  }
  rep(i,0,v){g[i][i]=0;}
  
  rep(k,0,v){
    rep(i,0,v){
      rep(j,0,v){
        g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
      }
    }
  }
  sort(rr.begin(),rr.end());
  do{
    ll tmp=0;
    rep(i,0,r-1){
      tmp+=g[rr[i]][rr[i+1]];
    }
    ans=min(ans,tmp);
  }while(next_permutation(rr.begin(),rr.end()));
  
  out(ans);
}




Measured memory_bytes: 512
def main():
	import sys
	input = sys.stdin.readline
	n = int(input())
	p = list(map(int, input().split()))
	count = 0
	for i in range(n-2):
		if ((p[i] <= p[i+1]) & (p[i+1] <= p[i+2])) | ((p[i] >= p[i+1]) & (p[i+1] >= p[i+2])):
			count += 1
	print(count)

if __name__ == '__main__':
    main()

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

using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const int inf = 1e9+7;
const int mod = 1e9+7;

int main(){
    int x,y;
    cin>>x>>y;

    rep2(i,0,50){
        if(i*2+(x-i)*4==y){
            cout<<"Yes"<<endl;
            return 0;
        }
    }

    cout<<"No"<<endl;

}


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

int main(){
  int m1, m2, d1, d2;
  cin >> m1 >> d1;
  cin >> m2 >> d2;
  if(m1 != m2 && d1 > d2) cout << 1 << endl;
  else cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;

main(){
	long long a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	if(a%2==0||b%2==0||c%2==0)puts("0");
	else printf("%lld\n",min(a*b,min(a*c,b*c)));
}

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

#define int long long
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) otp(v[i]) cte
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n;
vector<int> v;

main() {
    cin >> n;
    rep(i,7) v.pb(pow(2,i))
    auto it = upper_bound(all(v),n);
    ct(v[it-v.begin()-1])
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

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

    int A, B;
    cin >> A >> B;
    char c;
    bool ans = true;
    for(int i=0; cin >> c; i++){
        if(i < A){
            if(!(0 <= c - '0' && c - '0' <= 9)){
                ans = false;
                break;
            }
        }else if(i == A){
            if(c != '-'){
                ans = false;
                break;
            }
        }else if(i < A+B+1){
            if(!(0 <= c - '0' && c - '0' <= 9)){
                ans = false;
                break;
            }
        }else{
            ans = false;
            break;
        }
    }
    cout << (ans ? "Yes" : "No") << "\n";
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

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

	ll N, A, res = 1;
	cin >> N;
	const ll m = 1e18;
	while(N --> 0) {
		cin >> A;
		// cerr << A << " " << res << " " << res/m
		if(res == 0 || A == 0) res = 0;
		else if(res < 0 || A > m/res) res = -1;
		else res *= A;
	}
	cout << res << "\n";

	return 0;
}

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

int main(){
    int n, m;
    cin >> n;
    m = (int)pow(2, n);
    rep(i, m){
        bitset<20> x(i);
        cout << i << ":";
        rep(j, n){
            if(x.test(j)){
                cout << " " << j;
            }
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3272
#include<bits/stdc++.h>
using namespace std;
int a[3];
void read(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
namespace NB {
	
	int main(){
		read(a[0]);
		read(a[1]);
		read(a[2]);
		sort(a,a+3);
		cout<<a[0]+a[1]<<"\n";
		return 0;
	}
	
}
int main(){
	return NB::main();
}

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

int main(){
  int N,K;
  cin >>N>>K;
  set<int> S;
  vector<int> vec1(N);
  vector<int> vec2(N);
  for (int i = 0; i < N; i++) {
    cin >> vec1.at(i);
    for (int j=0;j<vec1.at(i);j++) {
      cin >> vec2.at(j); 
  S.insert(vec2.at(j));
    }
  }
    cout<<N - S.size()<<endl;
}

Measured memory_bytes: 3604
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	N      int
	s      string
	answer int
	w, r   []int
)

const red = 'R'
const white = 'W'

func main() {
	readVariables()
	answer = N
	for i := 0; i <= N; i++ {
		cand := MaxInt(w[i], r[i])
		answer = MinInt(cand, answer)
	}
	fmt.Println(answer)
}

func readVariables() {
	N = nextInt()
	s = nextStr()
	w, r = make([]int, N+1), make([]int, N+1)
	for i := 1; i <= N; i++ {
		w[i] = w[i-1]
		if i-1 < N && s[i-1] == white {
			w[i]++
		}
	}
	for i := N; i >= 0; i-- {
		if i+1 < N+1 {
			r[i] = r[i+1]
		}
		if i < N && s[i] == red {
			r[i]++
		}
	}
}

/* Template */

var scanner *bufio.Scanner

func init() {
	Max := 1001001
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 0, Max), Max)
	scanner.Split(bufio.ScanWords)
}

//nextInt converts next token from stdin and returns integer value.
//nextInt panics when conversion into an integer fails.
func nextInt() int {
	if !scanner.Scan() {
		panic("No more token.")
	}
	num, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic("nextInt(): cannot convert to int: " + scanner.Text())
	}
	return num
}

func nextStr() string {
	if !scanner.Scan() {
		panic("No more token.")
	}
	return scanner.Text()
}

// MinInt returns minimum argument
func MinInt(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}

//MaxInt returns maximum argument
func MaxInt(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

//AbsInt returns |x| for x
func AbsInt(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

//ModPow calculates integer power with modulo operation
//if modulo <= 1, it powers w/o module operation
//if base < 0, return value might be negative too.
func ModPow(base, exponent, modulo int) (result int) {
	result = 1
	for exponent > 0 {
		if exponent%2 == 1 {
			result *= base
			if modulo > 1 {
				result %= modulo
			}
		}
		base *= base
		if modulo > 1 {
			base %= modulo
		}
		exponent /= 2
	}
	return
}

//Gcd
func Gcd(vals ...int) (result int) {
	if len(vals) == 0 {
		return
	}
	result = vals[0]
	for i := 1; i < len(vals); i++ {
		result = gcd(result, vals[i])
	}
	return
}

func gcd(x, y int) int {
	x, y = AbsInt(x), AbsInt(y)
	for y > 0 {
		x, y = y, x%y
	}
	return x
}

//Lcm
func Lcm(vals ...int) (result int) {
	if len(vals) == 0 {
		return
	}
	result = vals[0]
	for i := 1; i < len(vals); i++ {
		result = lcm(result, vals[i])
	}
	return
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}


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

long long v[100002], n, g, w, p;

int main()
{
  cin >> n >> g;
  for (int i = 1; i <= 100000; i++)
    v[i] = (1ll << 50);
  v[0] = 0;
  for(int i = 1; i <= n; i++){
    cin >> w >> p;
    for(int j = 100000; j >= p; j--) v[j] = min(v[j - p] + w, v[j]);
  }
  for (int i = 100000; i>= 0;i--)
  if (v[i] <= g) {
    cout << i;
    return 0;
  }
  return 0;
}


Measured memory_bytes: 1024