akhauriyash/Code-Regression huggingface dataset:
from heapq import heappop
from collections import defaultdict

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, *L = map(int, open(0).read().split())
A, XY = L[:N], L[N:]

uf = UnionFind(N)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)

C = defaultdict(list)
for i, a in enumerate(A):
    C[uf.find(i)].append(a)

if len(C) < 2:
    print(0)
    quit()

D = [sorted(c) for c in C.values()]
s = sum(heappop(d) for d in D)

L = []
for d in D:
    L += d

if len(L) < len(D) - 2:
    print("Impossible")
else:
    print(s + sum(sorted(L)[:len(D) - 2]))


Measured memory_bytes: 41284
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

constexpr int M = (int)1e+6;

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

    int n;
    cin >> n;

    vector<int> a(n), b(M + 1);
    vector<char> c(M + 1, 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[a[i]]++;
    }

    int r = 0;
    for (int j = 1; j <= M; j++) {
        if (!b[j] || !c[j]) continue;
        for (int k = j * 2; k <= M; k += j) {
            c[k] = 0;
        }
        r += b[j] == 1;
    }

    cout << r << endl;

    return 0;
}

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

int main(){
  int N;

  cin>>N;
  vector<int> a(N);

  int i;
  for(i=0;i<N;i++)
  cin>>a.at(i);

  set<int> st;
  int cnt=0;
  bool hand=false;
  i=0;
  while(st.count(i)==0){
    // cout<<"syori"<<endl;
    cnt++;
    st.insert(i);
    i=a.at(i)-1;
    if(i==1){
      hand=true;
      break;
    }
  }
  if(hand)
  cout<<cnt<<endl;
  else
  cout<<-1<<endl;

}


Measured memory_bytes: 5376
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100000+10;
int ans[maxn],d[maxn*2],fa[maxn*2],h[maxn*2],now[maxn*2],go[maxn*6],nxt[maxn*6],sta[maxn*6];
bool bz[maxn*6],czy;
int i,j,k,l,r,s,t,n,m,tot,top,rot1,rot2;
/*int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){

    }
}*/
void add(int x,int y){
    go[++tot]=y;
    nxt[tot]=h[x];
    h[x]=tot;
}
void dfs(int x,int y){
    int t=h[x];
    while (t){
        if (go[t]!=y){
            dfs(go[t],x);
            d[x]^=1;
        }
        t=nxt[t];
    }
    d[x]^=1;
}
void travel(int x){
	int &t=now[x];
    while (t){
        if (!bz[(t+1)/2]){
            bz[(t+1)/2]=1;
            //now[x]=nxt[t];
            travel(go[t]);
        }else t = nxt[t];
    }
    sta[++top]=x;
}
int main(){
    scanf("%d",&n);
    fo(i,1,n){
        scanf("%d",&fa[i]);
        if (fa[i]==-1){
            fa[i]=0;
            rot1=i;
        }
        else{
            add(fa[i],i);
            add(i,fa[i]);
        }
    }
    fo(i,n+1,2*n){
        scanf("%d",&fa[i]);
        if (fa[i]==-1){
            fa[i]=0;
            rot2=i;
        }
        else{
            add(fa[i]+n,i);
            add(i,fa[i]+n);
        }
    }
    dfs(rot1,0);
    dfs(rot2,0);
    czy=1;
    fo(i,1,n)
        if (d[i]^d[i+n]){
            czy=0;
            break;
        }
    if (!czy){
        printf("IMPOSSIBLE\n");
        return 0;
    }
    printf("POSSIBLE\n");
    s=0;
    add(s,rot1);
    add(rot1,s);
    add(s,rot2);
    add(rot2,s);
    fo(i,1,n)
        if (d[i]){
            add(i,i+n);
            add(i+n,i);
        }
    fo(i,s,2*n) now[i]=h[i];
    travel(s);
    fo(i,1,n)
        if (d[i]) ans[i]=-1;
    fo(i,1,top-1)
        if (sta[i]>0&&sta[i]<=n&&sta[i+1]==sta[i]+n) ans[sta[i]]=1;
    fo(i,1,n) printf("%d ",ans[i]);
}

Measured memory_bytes: 20352
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N = int(input())
S = input()

c = Counter(S)

mcount = len(c)

mct = 0
for i in range(N):
    ta = Counter(S[:i])
    tb = Counter(S[i:])
    
    ct = 0
    for st in ta:
        if tb[st]:
           ct += 1
           
    mct = max(mct, ct)
print(mct)


Measured memory_bytes: 10400
#include <iostream>
#include <string>
using namespace std;
int main() {
	string s;
	long long k, c = 0,d = 1;
	cin >> s >> k;
	for (int i = 0; i < s.size();i++) {
		if (s[i] == '1')c++;
		else {
			d = s[i] - '0';
			break;
		}
	}
	if (k <= c) cout << 1 << endl;
	else cout << d << endl;
}


Measured memory_bytes: 256
s = input()
ans1=s[0]

def solve(i,tmp,ans):
  global ans1
  if i==3:
    if tmp==7:
      ans1=ans
      return True
    else:
      return False
  
  if solve(i+1,tmp+int(s[i+1]),ans+"+"+s[i+1]): return True
  if solve(i+1,tmp-int(s[i+1]),ans+"-"+s[i+1]): return True

if solve(0,int(s[0]),ans1):
  print(ans1+"=7")

Measured memory_bytes: 9184
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>

using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;


const long long int mod = 1000000007;
const long long int INF = 1e18;

long long int N,Z,W,A[200200]={},memo[100040]={},res=0,cou=0,num,fi=0,se=0;
string S;
int main()
{
    cout << fixed << setprecision(18);
	cin>>N>>Z>>W;
	for(long long int i = 0; i < N; i++){
		cin>>A[i];
		res=max(res,A[i]);
	}
	if(N==1){
		cout<<abs(A[0]-W)<<endl;
	}else{
	cout<<max(abs(A[N-1]-W),abs(A[N-2]-A[N-1]) )<<endl;
	}
	
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    int N, result = 0;
    scanf("%d", &N);

    vector<int> L(N);

    for(int i = 0; i < N; i ++)
        scanf("%d", &L[i]);
    
    sort(L.begin(), L.end());

    auto comp = [](int a, int b, int c){
        if(a < b + c && b < a + c && c < a + b)
            return true;
        return false;
    };

    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            for(int k = j + 1; k < N; k++){
                if(comp(L[i], L[j], L[k]))
                    result++;
                else{
                    break;
                }
            }
        }
    }
    
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <set>
#include <cmath>
#include <math.h>

using namespace std;
        
int main(){
     long long int n;
    cin>>n;
    long long int ans=1;
    while(ans*ans<=n){
        ans++;
    }
    
    ans--;
    cout<<ans*ans<<endl;
    return 0;
}

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

using namespace std;

int main() {
  long int n, a, b, c, d, e;
  cin >> n >> a >> b >> c >> d >> e;
  long int min_passengers = min( {a, b, c, d, e} );
  cout << 4 + ( n + ( min_passengers - 1 ) ) / min_passengers << endl;
  return 0;
}

Measured memory_bytes: 256
from itertools import accumulate
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
lb = 0
ub = 2*10**5+1
while ub - lb > 1:
    m = (lb + ub) // 2
    cnt = 0
    s, t = 0, N-1
    while t >= 0:
        while s < N and A[s] + A[t] >= m:
            s += 1
        cnt += s
        t -= 1

    if cnt >= M:
        lb = m
    else:
        ub = m

accum = list(accumulate([0] + A))
ans = 0
cnt = 0
s, t = 0, N-1
while t >= 0:
    while s < N and A[s] + A[t] >= lb:
        s += 1
    ans += accum[s] + s * A[t]
    cnt += s
    t -= 1
print(ans - (cnt-M) * lb)


Measured memory_bytes: 62172
#include <bits/stdc++.h>
using namespace std;
using  unll = unsigned long long;


int main() {
  int n;
  string s;
  cin >> n >> s;
  bool flag = false;
  if( n%2 != 0 ){
    cout << "No" << endl;
    return 0;
  }
  if( s.substr(0,n/2) == s.substr(n/2) ){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)	
#define REP(i,b) FOR(i,0,b)
int read(){
	int i;
	scanf("%lld",&i);
	return i;
}
using vi=vector<int>;
#define PB push_back
#define ALL(x) x.begin(),x.end()

void chmin(int&a,int b){
	a=a<b?a:b;
}

signed main(){
	int n=read(),m=read();
	
	vector<queue<int>> q(n);
	REP(i,n)REP(j,m)q[i].push(read()-1);
	
	vi avail(m,1);
	int ans=n;
	
	REP(_,m){
		vi cnt(m,0);
		
		REP(i,n){
			while(!avail[q[i].front()])
				q[i].pop();
			cnt[q[i].front()]++;
		}
		
		int i=max_element(ALL(cnt))-cnt.begin();
		chmin(ans,cnt[i]);
		avail[i]=0;
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n,k,r,temp,x1,x2;
    cin>>n>>k;
    if(n>=k){
        r=n%k;
        if(r==0)
        cout<<r<<endl;
        else{
                temp=abs(r-k);
        cout<<min(temp,r)<<endl;
        }
    }
    else{
        x1=abs(k-n);
        if(x1<n)
            cout<<x1<<endl;
        else
        cout<<n<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mod 1000000007
int main()
{
    fast;
    int n;
    cin>>n;
    int a[n+2][3];
    for(int i=0;i<n;i++)
    {
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    int dp[n+2][3];
    dp[0][0]=a[0][0];dp[0][1]=a[0][1];dp[0][2]=a[0][2];
    int max_=max_ = max(dp[0][0],max(dp[0][1],dp[0][2]));
    for(int i=1;i<n;i++)
    {
        dp[i][0]=a[i][0];dp[i][1]=a[i][1];dp[i][2]=a[i][2];
        if(i>1)
        {
            for(int j=0;j<3;j++)
                dp[i][j]=max(dp[i-2][j] , max(dp[i][j]+dp[i-1][(j+1)%3] , dp[i][j]+dp[i-1][(j+2)%3]));
        }
        else
        {
             for(int j=0;j<3;j++)
                dp[i][j]=dp[i][j]+max(dp[i-1][0] , max(dp[i-1][1] , dp[i-1][2]));
        }
        max_ = max(max_,max(dp[i][0],max(dp[i][1],dp[i][2])));
    }
    cout<<max_;
return 0;
}

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

using namespace std;

long long inf=1000000007;

int main(){
	int n,k,r,s,p;
	string t;
	cin>>n>>k>>r>>s>>p>>t;
	map<char,long long> point;
	point['r']=p;
	point['s']=r;
	point['p']=s;

	long long ans=0;

	for(int i=0;i<k;i++){
		int cnt=0;
		char now=t.at(i);
		for(int j=i;j<n;j+=k){
			if(t.at(j)==now) cnt++;
			else{
				ans+=ceil((double)cnt/2)*point.at(now);
				now=t.at(j);
				cnt=1;
			}
		}
		ans+=ceil((double)cnt/2)*point.at(now);
	}

	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define FOREACH(i,Itr) for(auto (i)=(Itr).begin();(i)!=(Itr).end();(i)++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))
#define EPS 1.0e-8
#define MOD 1000000007
typedef long long ll;


int main(){
    
    int n; cin>>n;
    int cnt=0;
    REP(i,n){
        int t; cin>>t;
        if(t%2==1)cnt++;
    }
    
    if(cnt%2==0)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

#define FILL(a, n, x) memset((a), (x), sizeof ((a)[0]) * (n))
#define FILLA(a, x) memset((a), (x), sizeof (a))
#define COPY(a, n, b) memcpy((b), (a), sizeof ((a)[0]) * (n))
#define COPYA(a, b) memcpy((b), (a), sizeof (a))

typedef unsigned long long lu;
typedef vector<int> Poly;

const int mod = 1e9 + 7;

inline int Add(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline int Sub(int x) { return x < 0 ? x + mod : x; }
inline void Sub(int &x, int y) { x = Sub(x - y); }
inline int Mul(int x, int y) { return (int)((lu)x * y % mod); }
inline int Mul(int x, int y, int z) { return (int)((lu)x * y % mod * z % mod); }

int Pow(int x, int y) {
  int z = 1;
  for (; y; y >>= 1) {
    if (y & 1) z = Mul(z, x);
    x = Mul(x, x);
  }
  return z;
}

int Inv(int x) { return Pow(x, mod - 2); }

// ----------------------------------------

const int maxn = 16;

int n, m;
int a[maxn];
int dp[1 << maxn], dp2[1 << maxn];
int fact[1 << maxn | 1], ifact[1 << maxn | 1];

void InitFact(int n) {
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = Mul(fact[i - 1], i);
  ifact[n] = Inv(fact[n]);
  for (int i = n; i >= 1; --i) ifact[i - 1] = Mul(ifact[i], i);
}

int Binom(int i, int j) {
  return Mul(fact[i], ifact[j], ifact[i - j]);
}

int Sgn(int i) {
  return i & 1 ? mod - 1 : 1;
}

int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d", a + i);
    --a[i];
  }
  InitFact(1 << n);

  FILLA(dp, 0);
  dp[0] = 1;
  for (int i = m - 1; i >= 0; --i) {
    FILLA(dp2, 0);
    for (int s = 0; s < 1 << n; ++s) {
      int val = dp[s];
      if (!val) continue;

      // do nothing
      Add(dp2[s], val);

      // join
      for (int j = 0; j < n; ++j) {
        if ((~s >> j & 1) && (((1 << n) - a[i] - s) >= (1 << j))) {
          Add(dp2[s | 1 << j], Mul(val, Binom((1 << n) - a[i] - s - 1,
                                              (1 << j) - 1),
                                   fact[1 << j]));
        }
      }
    }
    COPYA(dp2, dp);
  }

  int ans = 0;
  for (int s = 0; s < 1 << n; ++s) {
    int res = Mul(dp[s], Sgn(__builtin_popcount(s)));
    res = Mul(res, fact[(1 << n) - 1 - s]);
    Add(ans, res);
  }
  ans = Mul(ans, 1 << n);
  // for (int i = 1; i < n; ++i) {
  //   ans = Mul(ans, fact[1 << i]);
  // }
  printf("%d\n", ans);
  return 0;
}


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

struct Node {
    int index = -1;
    int depth = -1;
    int parent = -1;
    int *child;
    int ccnt = 0;
    int type = 0;
};

void depth(Node *node, int x, int d) {
    node[x].depth = d;
    for (int i = 0; i < node[x].ccnt; ++i) {
        depth(node, node[x].child[i], d+1);
    }
}

int Root(Node *node, int x) {
    if (node[x].parent > -1) {
        Root(node, node[x].parent);
    } else {
        return x;
    }
}

int main() {
    int n, x, root;
    string type[] = {"leaf", "internal node", "root"};
    cin >> n;
    Node a[n];
    for (int i = 0; i < n; ++i) {
        cin >> x;
        cin >> a[x].ccnt;
        a[x].index = x;
        a[x].child = new int[a[x].ccnt];
        for (int j = 0; j < a[x].ccnt; ++j) {
            a[x].type = 1;
            cin >> a[x].child[j];
            a[a[x].child[j]].parent = x;
        }
    }
    
    root = Root(a, 0);
    a[root].type = 2;
    depth(a, root, 0);
    
    for (auto& i : a) {
        cout << "node " << i.index << ": ";
        cout << "parent = " << i.parent << ", ";
        cout << "depth = " << i.depth << ", ";
        cout << type[i.type] << ", ";
        cout << "[";
        for (int j = 0; j < i.ccnt-1; ++j) {
            cout << i.child[j] << ", ";
        }
        if (i.ccnt) { 
            cout << i.child[i.ccnt-1] << "]" << endl;
        } else {
            cout << "]" << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 9680
def get_ints():
    return list(map(int, input().split()))

n = int(input())
a,b = [],[]
for i in range(n):
    x, y = get_ints()
    a.append(x+y)
    b.append(x-y)

a.sort()
b.sort()
ans = max(a[-1]-a[0], b[-1]-b[0])
print(ans)

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	n%=10;
	string ans;
	if(n==3)ans="bon"s;
	else if(n==0||n==1||n==6||n==8)ans="pon"s;
	else ans="hon"s;
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 3640
/*                    ___          |\    /|           ____   ____   ____  ____
   |     |    /\    /    \ |     | | \  / |    /\    |    \ |    \ |     |    \
   |_____|   /__\   \____  |_____| |  \/  |   /__\   |____/ |____/ |__   |____/
   |     |  /    \       \ |     | |      |  /    \  |      |      |     |   \
   |     | /      \ \____/ |     | |      | /      \ |      |      |____ |    \
*/
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pl, null_type, less<pl>, rb_tree_tag, tree_order_statistics_node_update>
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define ll long long
#define pi pair<int, int>
#define pl pair<long long, long long>
#define pld pair<long double, long double>
#define endl '\n'
#define loop(i, n) for (ll i = 0; i < n; i++)
#define rep(i, begin, end) for (__typeof(begin) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define mod ((ll)(1e9 + 7))
#define all(x) x.begin(), x.end()
#define vl vector<ll>
#define ml map<ll, ll>
#define vpl vector<pair<ll, ll>>

template <typename T, typename TT>
ostream &operator<<(ostream &os, const pair<T, TT> &t) {
    return os << t.first << " " << t.second;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &t) {
    for (auto &i : t)
        os << i << " ";
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &t : v)
        is >> t;
    return is;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, vector<pair<T1, T2>> &v) {
    for (pair<T1, T2> &t : v)
        is >> t.first >> t.second;
    return is;
}

const ll md = 998244353;
ll inv[int(2e5+5)];
ll fact[int(2e5 + 5)];

ll modpow(ll n, ll p)
{
    ll ans = 1;
    while(p) {
        if(p&1)
            (ans *= n) %= md;
        (n *= n) %= md, p /= 2;
    }
    return ans;
}

ll ncr(ll n, ll k) {
    if(!k)
        return 1;
    ll res = (fact[n] * inv[k]) % md;
    return (res * inv[n - k]) % md;
}

int main() {
    fast;
    fact[0] = 1, inv[0] = 1;
    rep(i, 1, 2e5 + 5)
    {
        fact[i] = (fact[i - 1] * i)%md;
        inv[i] = modpow(fact[i], md - 2);
    }
    ll n, m, k;
    cin >> n >> m >> k;
    ll ans = 0;
    loop(i, k + 1) {
        (ans += ncr(n-1,i) *  modpow(m - 1, n - i - 1)) %= md;
    }
    cout << (ans*m)%md << endl;

#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif

    return 0;
}

Measured memory_bytes: 6728
n,c1 = map(int, input().split())
g = []
c = [0]
d = [0]
a = 0
ans=[]
m1=0
m2=0
for i in range(n):
  x,v = map(int, input().split())
  g.append([x,v])
  a+=v
  m1= max(a-x,m1)
  m2= max(a-2*x,m2)
  c.append(m1)
  d.append(m2)
b = 0
e = [0]
f = [0]
for i,j in reversed(g):
  b+=j
  e.append(b-(c1-i))
  f.append(b-2*(c1-i))
for i in range(n+1):
  ans.append(c[i]+f[-i-1])
  ans.append(d[i]+e[-i-1])
print(max(ans))

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

int main() {
	long long a, b, c, d, ans;
	cin>>a>>b>>c>>d;
	ans=a*c;
	ans=max(ans, a*d);
	ans=max(ans, b*c);
	ans=max(ans, b*d);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i >= n; --i)
typedef long long ll;
#define mod 1000000007
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; }

bool solve() {
  int N; cin >> N;
  vector<string> S(N);
  rep(i, 0, N) cin >> S[i];
  map<string, int> mp;
  rep(i, 0, N) {
    if(mp[S[i]]) return false;
    mp[S[i]]++;
  }
  rep(i, 1, N) {
    if(S[i-1].back() != S[i].front()) return false;
  }
  return true;
}

int main() {
  cout << (solve() ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
def check(i, j, k, K):
    if (i + j + 2) % K == 0 and (i + k + 2) % K == 0 and (k + j + 2) % K == 0:
        return 1
    else:
        return 0


def get_num(i, j, k):
    if i != j and i != k and j != k:
        return 6
    elif i == j == k:
        return 1
    else:
        return 3

def main():
    a, b = map(int, input().split())
    print(a - b + 1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
n = int(input())
w = []
for _ in range(n):
    w.append(input())
a = ''
for i in range(n):
    for j in range(i):
        if w[i] == w[j]:
            print('No')
            exit()
for j in w:
    b = [i for i in j]
    if j != w[0] and a != b[0]:
        print('No')
        exit()
    a = b[-1]
print('Yes')

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

  
int main() {
  int N;
	string S;
  cin >> N >>S;
  int ans =0;
  for(int i=0;i<N-2;i++){
	if(S[i]== 'A' && S[i+1] == 'B' && S[i+2] == 'C'){
     ans++; 
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n,k,q,a,i;
  cin>>n>>k>>q;
  vector<int> b(n);
  for(i=0;i<q;i++){
    cin>>a;
    b.at(a-1)++;
  }
  for(i=0;i<n;i++){
    if(k-q+b.at(i)>0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(v) v.begin(), v.end()
#define revall(v) v.rbegin(), v.rend()
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){ if(y<h && y>=0 && x<w && x>=0) return true; return false; }
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; }






int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n + 1), b(n);
	rep(i,n + 1) cin >> a.at(i);
	rep(i,n) cin >> b.at(i);
	ll ans = 0;
	rep(i,n){
		int t = min(a.at(i), b.at(i));
		ans += t;
		b.at(i) -= t;
		t = min(a.at(i + 1), b.at(i));
		ans += t;
		a.at(i + 1) -= t;
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

const ll MOD = 1e9+7;

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  ll ans;
  bool vertical;
  int i;
  if((vertical = s[0] == t[0])) {
    ans = 3;
    i = 1;
  } else {
    ans = 6;
    i = 2;
  }
  for(; i<n; i++) {
    if(s[i] == t[i]) {
      if(vertical) {
        ans = ans * 2 % MOD;
      }
      vertical = true;
    } else {
      if(vertical) {
        ans = ans * 2 % MOD;
      } else {
        ans = ans * 3 % MOD;
      }
      i++;
      vertical = false;
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
N=int(input())
l=[]
l_value=[]
i=0
stack=-1
for i in range(N):
    if i < N:
        l.append(input())
list_simple=[]
for i in l:
    if stack != i:
        list_simple.append(i)
    stack = i
dp_dict=[0]*200001
dp=1
for i in list_simple:
    i=int(i)
    dp = dp_dict[i] +dp
    dp_dict[i] = dp
print(dp%(10**9+7))

Measured memory_bytes: 34988
def gcd(a, b):
    while(True):
        if a==0:return b
        b%=a
        if b==0:return a
        a%=b

def lcm(a, b):
    return a*b//gcd(a,b)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for x in a:l = lcm(l, x)
    ans = 0
    for x in a:
        ans+=l//x

    print(ans%1000000007)
main()


Measured memory_bytes: 4084
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>

typedef long long ll;
typedef unsigned short int unsi;
typedef unsigned int uni;
typedef unsigned long int unli;

using namespace std;

int main(){
	int N;
	cin >> N;
	if (N % 2 == 0) {
		cout << 0.5000000000 << endl;
	} else {
		double M = (N - 1)*0.5 + 1;
		cout << M / (double)N << endl;
	}
}

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

int main(){
  int a ,c,sum,ans;
  int b[9] ={};
  sum =0;
while(1){
  cin >> a;

if(a == 0)break;

  for(int i=0;i<9;i++){
    cin >> b[i];
  }


  for(int i=0;i<9;i++){
    sum += b[i];
  }

  ans = a -sum;

  cout << ans << endl;

sum = 0;

}

}


Measured memory_bytes: 3072
#include <iostream>

using namespace std;
int main(){
    int n;cin >> n;
    int count=1,min;cin >> min;
    for(int i=1; i<n; i++) {
        int num;cin >> num;
        if(min > num) {
            min = num;
            count++;
        }
        if(min == 1) break;
    }
    cout << count << endl;
}

Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0179
{
    public class Program

    {
        public static HashSet<char> colors = new HashSet<char>() { 'r', 'g', 'b' };

        public static void Main(string[] args)
        {
            while (true)
            {
                string line = RSt();
                if (line == "0") break;

                Console.WriteLine(GetSameSteps(line));
            }

        }

        private static string GetSameSteps(string line)
        {

            Dictionary<string, int> dic = new Dictionary<string, int>();
            Queue<string> q = new Queue<string>();

            dic.Add(line, 0);
            q.Enqueue(line);

            while (q.Count() > 0)
            {
                string cur = q.Dequeue();

                if (isAllSame(cur))
                {
                    return dic[cur].ToString();
                }

                for (int i = 0 ; i < cur.Length - 1 ; i++)
                {
                    if (cur[i] != cur[i + 1])
                    {
                        char[] tmp = cur.ToCharArray();
                        tmp[i] = colors.Except(new char[] { cur[i], cur[i + 1] }).First();
                        tmp[i + 1] = tmp[i];

                        string next = string.Join("", tmp);
                        if (!dic.ContainsKey(next))
                        {
                            dic.Add(next, dic[cur] + 1);
                            q.Enqueue(next);
                        }
                    }
                }
            }

            return "NA";
        }

        private static bool isAllSame(string cur)
        {
            foreach (var color in colors) if (cur.All(x => x == color)) return true;
            return false;
        }

        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RStAr(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }

}



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

using namespace std;

int main()
{
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  for(int i=0;;i++){
    if(a<=0){cout<<"No"<<endl;return 0;}
    if(c<=0){cout<<"Yes"<<endl;return 0;}
    if(i&1){
        a-=d;
    }
    else{
        c-=b;
    }
  }
}


Measured memory_bytes: 3632
#include <cstdio>
int main(){
    int a,b,c,d;
    std::scanf("%d %d %d %d",&a,&b,&c,&d);
    if(a+b>c+d)std::puts("Left");
    else if(a+b==c+d)std::puts("Balanced");
    else std::puts("Right");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
using namespace std;

const ll N = 7005;
const ll MOD = 1e9+7;
int main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ll n;
	cin>>n;
	cout<<(n+1)/2<<endl;

	return 0;	
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  ll a, b, n;
  cin >> a >> b >> n;
  if(n < b - 1){
    cout << floor(a * n / b) - a * floor(n / b) << endl;
  }else{
    cout << floor(a * (b - 1) / b) - a * floor((b - 1) / b) << endl;
  }
  return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;
const ll MINF = LLONG_MIN;
using Tree = vector<pair<int, int>>;

int main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    unordered_map<string, ll> mp;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
        mp[s[i]]++;
        ans += mp[s[i]] - 1;
    }
    cout << ans << endl;
}

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

int main() {
	int a, b, k; cin >> a >> b >> k;

	for (int i = min(a,b); i >= 1; i--) {
		if (a % i == 0 && b % i == 0)k--;
		if (k == 0) {
			cout << i << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 3552
import java.util.Scanner;

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

		int h = sc.nextInt();
		int w = sc.nextInt();

		int cnt = 0;
		for (int i = 0; i < h; i++) {
			char[] c = sc.next().toCharArray();
			for (int j = 0; j < c.length; j++)
				if (c[j] == '#')
					cnt++;
		}

		String ans = cnt == h + w - 1 ? "Possible" : "Impossible";
		System.out.println(ans);
		sc.close();
	}

}


Measured memory_bytes: 21588
from collections import Counter
n, *a = map(int, open(0).read().split())
a = Counter(a)

if n%2==0:
        i = cant = 0
        for v, c in sorted(a.items()):
                if 2*i+1!=v or c!=2: cant = True
                i += 1
else:
        i = cant = 0
        for v, c in sorted(a.items()):
                if i==0: cant = (c!=1)
                elif 2*i!=v or c!=2:  cant = True
                i += 1

if cant: print(0)
else: print(pow(2, n//2, 1000000007))

Measured memory_bytes: 15048
#define ll long long int
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector <int> a(n);
	ll sum = 0;
	map<int, int> m;
	for (int i = 0; i < n; i++) { cin >> a[i]; m[a[i]]++; sum += a[i]; }
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int b, c;
		cin >> b >> c;
		sum += (c - b) * m[b];
		m[c] += m[b];
		m[b] = 0;
		cout << sum << endl;
	}
}

Measured memory_bytes: 8056
gets
d = gets.chomp.split(" ").map(&:to_i)
gets
t = gets.chomp.split(" ").map(&:to_i)

h = Hash.new
d.each do |di|
	h[di] ? h[di] += 1 : h[di] = 1
end

t.each do |ti|
	if h[ti] == nil or h[ti] == 0
		puts "NO"
		exit
	end
	h[ti] -= 1
end
puts "YES"

Measured memory_bytes: 45868
// --------------
// Tejas Pandey  |
// 19 - 06 - 20  |
// Atcoder BC 171|
// --------------

#include <bits/stdc++.h>
using namespace std;
     
#define mod 1000000007
#define vi vector<int>
typedef long long int ll;

ll cnt[100007];
     
int main (void){
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  ll a[n];
  ll sum = 0;
  for(int i = 0;i < n;i++) cin >> a[i],sum += a[i],cnt[a[i]]++;
  int q;
  cin >> q;
  while(q--){
	ll b,c;
	cin >> b >> c;
	sum -= cnt[b]*b;
	sum += cnt[b]*c;
	cnt[c] += cnt[b];
	cnt[b] = 0;
	cout << sum << "\n";
  }
  return 0;
}


Measured memory_bytes: 5168
'use strict'

function main(s) {
  s = s.split('\n');

  const n = Number(s[0]);
  const a = s[1].split(' ');

  const absArr = [];
  for (let i = 0; i < n; i++) {
    absArr[i] = a[i] - (i + 1);
  }

  absArr.sort((a, b) => a - b);

  const med = n / 2;
  let b = 0;
  let ans = 0;

  if (n === 1) {
    b = absArr[0];
  } else {
    if (n % 2 === 0) {
      b = (absArr[med] + absArr[med - 1]) / 2;
    } else {
      b = (absArr[Math.floor(med)]);
    }
  }

  ans = absArr.reduce((acc, val) => acc + Math.abs(val - b), 0);
  console.log(ans);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 36992
package main

import "fmt"

const div = 1000000000 + 7

func main() {
	var H, W int
	fmt.Scan(&H, &W)
	m := make([][]bool, H+1)
	dp := make([][]int, H+1)
	for i := 0; i <= H; i++ {
		m[i] = make([]bool, W+1)
		dp[i] = make([]int, W+1)
	}
	var line string
	for y := 1; y <= H; y++ {
		fmt.Scan(&line)
		for i, r := range line {
			x := i + 1
			if r == '#' {
				m[y][x] = true
			}
		}
	}
	dp[1][1] = 1
	for y := 1; y <= H; y++ {
		for x := 1; x <= W; x++ {
			if m[y][x] {
				dp[y][x] = 0
			} else {
				dp[y][x] += dp[y-1][x] + dp[y][x-1]
				dp[y][x] %= div
			}
		}
	}
	fmt.Println(dp[H][W])
}

Measured memory_bytes: 11136
#include<stdio.h>

int m[10][10],c,x,y,N=10;

int main(){
  for(x=0;x<10;x++){
    for(y=0;y<10;y++){
      m[x][y]=x?m[x-1][y+1]+1:y?m[x][y-1]+y:1;
    }
  }
  for(;scanf("%d",&N),N;){
    printf("Case %d:\n",++c);
    for(x=0;x<N;x++){
      for(y=0;y<N;y++){
        if(x+y<N){
            printf("%3d",(x+y)%2?m[x][y]:m[y][x]);
        }
        else{
            printf("%3d",N*N+1-((x+y)%2?m[N-1-x][N-1-y]:m[N-1-y][N-1-x]));
        }
      }
      printf("\n");
    }
  }
}

Measured memory_bytes: 616
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define Rep(i,a,b) for(ll i=a;i<b;i++)
#define pb emplace_back
#define allv v.begin(),v.end()
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
#define FASTio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define deb(x) cout<<(#x)<<" "<<x<<endl
ll mod=1e9+7;
template<typename t>
ll Max(ll a,ll b)
{
    return (a>b)?a:b;
    
}
ll Min(ll a,ll b)
{
    return (a>b)?b:a;
}
ll Power(ll a,ll b)
{
    ll p=1;
    a=a;
    b=b;
    while(b)
    {
        if(b&1)
        {
            p=((p)*(a));
        }
        a=((a)*(a));
        b=(b/2);
    }
    return p;
}
ll power(ll a,ll b)
{
    if(b==0)
    return 1;
    ll p=power(a,b/2)%mod;
    p=(p*p)%mod;
    if(b&1)
    p=(p*a)%mod;
    return p;
}
ll gcd(ll a,ll b)
{
    if(a==0)
    return b;
    return gcd(b%a,a);
}
/*void dfs(ll i)
{
    visited[i]=true;
   // provinces.pb(i);
    for(auto it:adj[i])
    {
        if(!visited[it] && choices[it])
        dfs(it);
    }
}*/
ll prod(ll a,ll b)
{
    return ((a%mod)*(b%mod))%mod;
}
ll add(ll a,ll b)
{
    return ((a%mod)+(b%mod))%mod;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<ll> x,y;
    ll n;
    cin>>n;
    ll a,b;
    rep(i,n)
    {
        cin>>a>>b;
        x.push_back(a+b);
        y.push_back(a-b);
    }
    ll r=*max_element(x.begin(),x.end());
    ll s=*min_element(x.begin(),x.end());
    ll u=*max_element(y.begin(),y.end());
    ll v=*min_element(y.begin(),y.end());
    cout<<max(r-s,u-v)<<endl;
    return 0;
}


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

using namespace std;

int main(){
  int a, b, c, d, e, k;
  
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  cin >> e;
  cin >> k;
  if(e-a<=k) cout << "Yay!" << endl;
  else cout << ":(" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int pwmd(int a, int n)
{
	if (!n)
		return 1;
	int pt = pwmd(a, n / 2);
	pt *= pt, pt %= mod;
	if (n & 1)
		pt *= a, pt %= mod;
	return pt;
}
int pow(int a,int b)
{
	int ans=1;
	while(b>0)
	{
		if(b&1)
			ans*=a;
		a*=a;
		b=b>>1;
	}
	return ans;
}
int n,ans;
vector<pair<int,int>> vec;
bool compare(pair<int,int> v1,pair<int,int> v2)
{
	return v1.ss<v2.ss;
}
int32_t main()
{       
    FIO;
    int r;
    cin>>r;

    double ans=2*3.1415*r;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3804
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		
		while (true) {
			c -= b;
//			System.out.println("c=" + c);
			if (c <= 0) {
				System.out.println("Yes");
				return;
			}
			
			a -= d;
//			System.out.println("a=" + a);
			if (a <= 0) {
				System.out.println("No");
				return;
			}
			
		}
	}
}


Measured memory_bytes: 27068
N, M = list(map(int, input().split()))

if N == 1 and M == 1:
	print(1)
elif N == 1 or M == 1:
	if N == 1:
		print(M - 2)
	else:
		print(N - 2)

else:
	print((N - 2) * (M - 2))

Measured memory_bytes: 3060
def solve(n,m):
    ans=[-1]*n
    for _ in range(m):
        s,c=input().split()
        s=int(s)-1
        if ans[s]==c:
            continue
        elif ans[s]==-1:
            ans[s]=c
        else:
            return -1
    if ans[0]=='0':
        if n==1:
            return '0'
        else:
            return -1
    elif ans[0]==-1:
        if n==1:
            return '0'
        else:
            ans[0]='1'
    for i in range(1, n):
        if ans[i]==-1:
            ans[i]='0'
    return ''.join(ans)

n,m=map(int,input().split())
print(solve(n,m))


Measured memory_bytes: 3064
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    ans = 0
    w = n+2
    grid = np.ones((w,w),np.int32)
    dis = np.zeros((w,w),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    grid = grid.ravel()
    dis = dis.ravel()
    stack = np.empty_like(grid)
    for pos in p:
        pos -= 1
        x = pos % n + 1
        y = pos // n + 1
        v = y*w+x
        ans += dis[v]
        grid[v] = 0
        k = min(dis[v-1],dis[v+1],dis[v+w],dis[v-w])
        cur = 0
        stack[0] = v
        while cur >= 0:
            v = stack[cur]
            cur -= 1
            for dx in (-1,1,w,-w):
                next_v = v + dx
                k = dis[v]+grid[v]
                if dis[next_v] > k:
                    dis[next_v] = k
                    cur += 1
                    stack[cur] = next_v
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))

Measured memory_bytes: 122868
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define gcd __gcd
#define F first
#define B begin()
#define E end()
#define ln length()
#define sz size()
#define S second
#define em empty()
#define mp make_pair
#define pb push_back
#define pq priority_queue
#define um unordered_map
#define us unordered_set
#define lb lower_bound
#define ub upper_bound
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sbits(a) __builtin_popcount(a)
#define lcm(a, b) ((a * b) / gcd(a, b))
#define nani(x) cerr << #x << " is " << x << endl;
#define adde(g, u, v) g[u].pb(v), g[v].pb(u);
#define addew(g, u, v, w) g[u].pb({ v, w }), g[v].pb({ u, w });
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inf 10000000000
#define mod 1000000007

typedef long long ll;

const int N = 1e5 + 5;

int A[N];

int main()
{
    fast;

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, k;
    cin >> n >> k;

    int ans = 0;

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

    cout << ans;
    return 0;
}


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

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 1) {
        cout << 1 << endl;
        return 0;
    } else {
        int ans = 1;
        int start = 1;
        ll sign = a[1] - a[0];
        while (sign == 0) {
            sign = a[start + 1] - a[start];
            ++start;
        }
        for (int i = start; i < n - 1; ++i) {
            if ((a[i + 1] - a[i]) * sign < 0) {
                ++ans;
                for (int j = i + 1; j < n - 1; ++j) {
                    if (a[j + 1] != a[j]) {
                        sign = a[j + 1] - a[j];
                        i = j;
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
while 1:
    try:
        a = list(map(int,input().split()))
        b = list(map(int,input().split()))
        hit = 0
        blow = 0
        for i in range(4):
            if a[i] == b[i]:
                hit += 1
            elif b[i] in a:
                blow += 1
        print(hit,blow) 
    except:
        break


Measured memory_bytes: 5592
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

// 入力
int N;
vector<double> p;

// DP テーブル
double dp[3100][3100];

int main() {
    cin >> N;
    p.resize(N);
    for (int i = 0; i < N; ++i) cin >> p[i];

    // 初期条件
    dp[0][0] = 1.0;

    // DP ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            dp[i+1][j+1] += dp[i][j] * p[i];
            dp[i+1][j] += dp[i][j] * (1.0 - p[i]);
        }
    }

    // 答え
    double res = 0.0;
    for (int j = N/2 + 1; j <= N; ++j) res += dp[N][j];
    cout << fixed << setprecision(10) << res << endl;
}

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

int main()
{
	int n, a[100];

	cin >> n;

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

	for (int j = n - 1; j >= 0; j--) {
		if (j == 0) cout << a[j] ;
		else cout << a[j] << " ";
	}

	cout << endl;

	return 0;
}

Measured memory_bytes: 1160