akhauriyash/Code-Regression huggingface dataset:
#桁DP
s = input()
n = int(s)
keta = len(s)
# dp[i][j][k][l][smaller][other]
dp = [
    [[[[0] * 2 for _ in range(2)] for _ in range(2)] for _ in range(2)]
    for _ in range(keta + 1)
]
dp[0][0][0][0][0] = 1
kazu = [0, 3, 5, 7]
for i in range(keta):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for smaller in range(2):
                    nd = int(s[i])
                    for d in range(10):
                        ni = i + 1
                        nj = j
                        nk = k
                        nl = l
                        nsmaller = smaller
                        if d not in kazu:
                            continue
                        if d == 3:
                            nj = 1
                        if d == 5:
                            nk = 1
                        if d == 7:
                            nl = 1
                        if smaller == 0:
                            if d > nd:
                                continue
                            if d < nd:
                                nsmaller = 1
                        if d == 0:
                            if nj + nk + nl != 0:
                                continue
                        dp[ni][nj][nk][nl][nsmaller] += dp[i][j][k][l][smaller]
print(dp[keta][1][1][1][0] + dp[keta][1][1][1][1])


Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

vector<bool> eratosthenes_sieve(size_t size) {
  vector<bool> is_prime(size + 1, true);
  for (size_t i = 0; i <= size; i++) {
    if (i < 2) {
      is_prime[i] = false;
    } else if (is_prime[i]) {
      for (size_t j = 2 * i; j <= size; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return is_prime;
}

int main() {
  int n = 1'000'000 - 1;
  auto sieve = eratosthenes_sieve(n);
  vector<int> acc(n + 1, 0);
  rep(i, n) { acc[i + 1] = acc[i] + (sieve[i + 1] ? 1 : 0); }

  int m;
  while (cin >> m) {
    cout << acc[m] << "\n";
  }
  return 0;
}


Measured memory_bytes: 6536
s = input()
f = [True]

if s[0]!="A":
    f[0]=False

slice1 = s[2:-1]
if slice1.count("C")!=1:
    f[0]=False
if (slice1.count("C")==1)and(s[0]=="A"):
    s=s.replace("A","a")
    s=s.replace("C","c")

if s.islower()!=True:
    f[0]=False

if f[0]==True:
    print("AC")
if f[0]==False:
    print("WA")
    

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N, K, L;
  cin >> N >> K >> L;

  map<ll, vl> road;
  map<ll, vl> train;
  ll p, q, r, s;
  rep(i, K){
    cin >> p >> q;
    road[p].push_back(q);
    road[q].push_back(p);
  }
  rep(i, L){
    cin >> r >> s;
    train[r].push_back(s);
    train[s].push_back(r);
  }

  vl ar(N + 1, 0);
  rep(i, N + 1) ar[i] = i;
  vl visited(N + 1, 0);
  queue<ll> que;

  rep2(i, 1, N + 1){
    if(ar[i] != i) continue;
    
    que.push(i);
    visited[i] = 1;

    while(!(que.empty())){
      ll town = que.front();
      ll cnt = road[town].size();

      rep(j, cnt){
        if(visited[road[town][j]] == 1) continue;

        ar[road[town][j]] = i;
        que.push(road[town][j]);
        visited[road[town][j]] = 1;
      }

      que.pop();
    }
  }

  vl br(N + 1, 0);
  rep(i, N + 1){
    br[i] = i;
    visited[i] = 0;
  }

  rep2(i, 1, N + 1){
    if(br[i] != i) continue;
    
    que.push(i);
    visited[i] = 1;

    while(!(que.empty())){
      ll town = que.front();
      ll cnt = train[town].size();

      rep(j, cnt){
        if(visited[train[town][j]] == 1) continue;

        br[train[town][j]] = i;
        que.push(train[town][j]);
        visited[train[town][j]] = 1;
      }

      que.pop();
    }
  }

  map<pll, ll> ab;
  rep2(i, 1, N + 1){
    ab[make_pair(ar[i], br[i])]++;
  }

  rep2(i, 1, N + 1){
    cout << ab[make_pair(ar[i], br[i])] << endl;
  }
  
  return 0;
}

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

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

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

const int maxn=200005;
int n;
int par[maxn];
class Info{
public:
	int cnt0,cnt1,id;
	ll inv;
	Info(int _cnt0=0,int _cnt1=0,int _id=0,ll _inv=0):cnt0(_cnt0),cnt1(_cnt1),id(_id),inv(_inv){}
	bool operator < (const Info &o)const{
		if(1LL*cnt1*o.cnt0!=1LL*o.cnt1*cnt0)return 1LL*cnt1*o.cnt0<1LL*o.cnt1*cnt0;
		return id<o.id;
	}
	Info operator + (const Info &o)const{
		Info res=*this;
		res.cnt0+=o.cnt0;res.cnt1+=o.cnt1;
		res.inv+=o.inv+1LL*cnt1*o.cnt0;
		assert(res.id==id);
		return res;
	} 
}a[maxn];
set<Info>s;
vector<Info>ans;

namespace Dsu{
	int f[maxn];
	void init(){
		REP(i,n)f[i]=i;
	}
	int find(int x){
		return f[x]==x?x:f[x]=find(f[x]);
	}
} 

int main(){
#ifdef FILE
	freopen("FILE.in","r",stdin);
	freopen("FILE.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=2;i<=n;i++)scanf("%d",&par[i]);
	Dsu::init();
	REP(i,n){
		int x;
		scanf("%d",&x);
		if(!x)a[i]=Info(1,0,i,0);
		else a[i]=Info(0,1,i,0);
		s.insert(a[i]);
	}
	while(!s.empty()){
		Info cur=*s.begin();
		s.erase(s.begin());
		int cur2=Dsu::find(par[cur.id]);
		if(!cur2){
			ans.pb(cur);
			Dsu::f[cur.id]=0;
			continue;
		}
		s.erase(s.find(a[cur2]));
		a[cur2]=a[cur2]+a[cur.id];
		Dsu::f[cur.id]=cur2;
		s.insert(a[cur2]);
	}
	Info res;
	rep(i,ans.size())res=res+ans[i];
	printf("%lld\n",res.inv);
#ifdef TIME
	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
#endif
	return 0;
}

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


Measured memory_bytes: 22072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int main(void){
    int n,m;cin>>n>>m;
    vector<vector<int>>V(n+1);
    int x,y;
    rep(i,m){
        cin>>x>>y;
        V[x].push_back(y);
    }
    bool ans=false;
    int s=V[1].size();
    rep(i,s){
        int l=V[1][i];
        int s1=V[l].size();
        rep(j,s1){
            if(V[l][j]==n)ans=true;
        }
    }
    if(ans)cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
}

Measured memory_bytes: 8576
# coding: utf-8
# Your code here!

def selectionSort(A,N):
    cnt=0
    for i in range(N):
        minj=i
        for j in range(i,N):
            if A[j]<A[minj]:
                minj=j
        if i != minj:
            cnt+=1
        A[i],A[minj]=A[minj],A[i]
    return(cnt)
a=int(input())
b=list(map(int,input().split(" ")))
c=selectionSort(b,a)
print(" ".join(list(map(str,b))),c,sep="\n")


Measured memory_bytes: 5608
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
const ll MOD = 1000000007;
const int MAX = 200000;

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

// テーブルを作る前処理
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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// 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;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N; cin >> N;
    int out=0;
    for(int i=1;i<=N;i+=2){
        int cnt=0;
        cerr << i << "\t";
        for(int j=1;j<=N;j++){
            if(i%j==0){cnt++;cerr << j << " ";}
        }
        cerr << "\t" << cnt << "\n";
        if(cnt==8)out++;
    }
    cout << out << endl;
    return 0;
}


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

int main() {
  int N;
  string S;
  cin >> N >> S;
  if (N % 2 != 0) {
    cout << "No";
    return 0;
  }
  int mid = N / 2;
  for (int i = 0; i < mid; ++i) {
    if (S[i] != S[i + mid]) {
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> a(100009),b(200009);
  for(int i=1;i<=200000;i++){b[i]=0;}
  for(int i=0;i<N;i++){cin >> a[i];}
  int count=0;
  for(int i=0;i<N;i++){
    if(a[i]>200000){count++;}
    else{b[a[i]]++;}
  }
  for(int i=1;i<=200000;i++){
    if(b[i]>=i){count+=b[i]-i;}
    else{count+=b[i];}
  }
  cout << count << endl;
}

Measured memory_bytes: 1408
a,b,c=map(int,input().split())

if a<=b<=c:
  print(a,b,c)
elif a<=c<=b:
  print(a,c,b)
elif b<=a<=c:
  print(b,a,c)
elif b<=c<=a:
  print(b,c,a)
elif c<=a<=b:
  print(c,a,b)
elif c<=b<=a:
  print(c,b,a)


Measured memory_bytes: 5596
#! /usr/bin/python3
# キャンディーと2人の子供 / Fighting over Candies

"""
    組み合わせを試す
"""

a, b, c = map(int, input().split())

if a+b == c or b+c == a or c+a == b:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 2940
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner (System.in);
		int N = sc.nextInt ();
		int[] d = new int[N];
		for (int i=0; i<N; i++)
			d[i] = sc.nextInt ();
		Arrays.sort (d);
		System.out.println (d[N/2]-d[N/2-1]);
	}
}

Measured memory_bytes: 49464
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer>[] graph = new ArrayList[n];
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        for (int i = 0; i < m; ++i) {
            int x = scanner.nextInt() - 1;
            int y = scanner.nextInt() - 1;
            if (graph[x] == null)
                graph[x] = new ArrayList<>();
            graph[x].add(y);
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, solve(i, graph, dp));
        }
        System.out.println(res-1);
    }

    private static int solve(int a, ArrayList<Integer>[] graph, int[] dp) {
        if (dp[a] != -1)
            return dp[a];
        int res = 0;
        if(graph[a]!= null) {
            for (int i = 0; i < graph[a].size(); ++i) {
                res = Math.max(res, solve(graph[a].get(i), graph, dp) + 1);
            }
        }else {
            res = 1;
        }
        return dp[a] = res;
    }
}
/*
 *
 */

Measured memory_bytes: 73572
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ENDL '\n'
#define all(a) begin(a),end(a)
#define sz(a) (int)(a.size())
#define deb(a) cout << #a << ": " << a << ENDL
#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli> ii;
typedef vector<lli> vi;


lli MOD = 1e9 + 7;

vector<vector<lli>> ones(int n) {
	vector<vector<lli>> identity(n, vector<lli>(n));
	fore(i, 0, n) identity[i][i] = 1;
	return identity;
}
vector<vector<lli>> operator*(vector<vector<lli>> &u, vector<vector<lli>> &v) {
    int n = sz(u);
	vector<vector<lli>> ans(n, vector<lli>(n));
	fore(i, 0 ,n) fore(j, 0, n) fore(k, 0, n)
        ans[i][j] = (ans[i][j] + (u[i][k] * v[k][j])) % MOD;
	return ans;
}
vector<vector<lli>> pot(vector<vector<lli>> mat, lli exp) {
	vector<vector<lli>> res = ones(sz(mat));
	while(exp) {
        if(exp % 2) res = res * mat;
        mat = mat * mat;
        exp /= 2;
	}
	return res;
}

int main()
{   _
    lli n, k; cin >> n >> k;
    vector<vector<lli>> m(n, vector<lli>(n));
    fore(i, 0, n) fore(j, 0, n) cin >> m[i][j];
    vector<vector<lli>> res = pot(m, k);
    lli ans = 0;
    for(auto itt : res) for(auto it : itt) ans = (ans + it) % MOD;
    cout << ans << ENDL;
    return 0;
}


Measured memory_bytes: 3752
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}





int main() {

	ll A,B,C;
	cin >> A>>B>>C;
	
	cout <<(A-B+1)*(A-C+1)<< endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

vector<vector<int>> tr;
vector<int> root;
bool rooted = false;
bool visited[100005];

void path(int s, int t){
    if(!rooted){root.push_back(s);}
    visited[s] = true;
    for (auto v1: tr[s]) {
        if(v1==t){
            rooted = true;
            root.push_back(t);
        }
        if(visited[v1] == false && v1 != t){
            path(v1,t);
        }
    }
    if(!rooted){root.pop_back();}
}

void dfs(int s, int t, int* cnt){
    (*cnt)++;
    visited[s] = true;
    for (auto v1: tr[s]) {
        if(visited[v1] == false && v1 != t){
            dfs(v1,t,cnt);
        }
    }
}


int main(){
    int n;
    cin >> n;
    tr.resize(n);
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }
    path(0,n-1);
    int cuta,cutb;
    if(root.size()&1){
        cuta = root[root.size()/2];
        cutb = root[root.size()/2+1];
    }else{
        cuta = root[root.size()/2-1];
        cutb = root[root.size()/2];
    }
    int fennec = 0, snuke = 0;
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }
    dfs(0, cutb, &fennec);
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }
    dfs(n-1, cuta, &snuke);
    if(fennec>snuke){cout << "Fennec" << endl;}
    else{cout << "Snuke" << endl;}



    return 0;

}


Measured memory_bytes: 11000
#include<iostream>
#include<string.h>
#include<cstdlib>


using namespace std;


int main(){
    char str[100];
    string three;
    int min,gap,length;
    min=1000;
    fgets(str,sizeof(str),stdin);
    length=strlen(str);
    //cout<<"length="<<length<<endl;
    int i=0;
    do{ 
        //three="\0";
        //cout<<str[i]<<endl;
        three = str[i];
        three +=str[i+1];
        three += str[i+2];
        //cout<<"three="<<three<<endl;
        auto num=std::atoi(three.c_str());
        gap=abs(753-num);
        if(gap<min){min=gap;}
        i++;
    }while(i+3<=length);
    cout<<min;
    return 0;
}

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

using namespace std;

int main(){

    int r,g,b;
    cin >> r >> g >> b;
    int tmp = 100*r+10*g+b;
    if(tmp%4 == 0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}

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

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<int> as(n), bs(n), cs(m), ds(m);
  for (int i = 0; i < n; i++)
    std::cin >> as[i] >> bs[i];
  for (int i = 0; i < m; i++)
    std::cin >> cs[i] >> ds[i];
  for (int i = 0; i < n; i++) {
    int vis = 0, min_d = 1e9;
    for (int j = 0; j < m; j++) {
      int dist =
        std::abs(as[i] - cs[j]) + std::abs(bs[i] - ds[j]);
      if (min_d > dist) {
        vis = j + 1;
        min_d = dist;
      }
    }
    std::cout << vis << std::endl;
  }
}


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

using namespace std;

int n, k;
vector<int> vec;
int a[100005];

int calc()
{
	//for(int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl;
	
	int ret = 0, sum = 0;
	for(int i = 0; i < vec.size(); i++){
		sum += vec[i];
		if(i % 2) ret = max(ret, sum);
		if(i-2*k >= 0) sum -= vec[i-2*k];
	}
	return ret;
}

int main(void)
{
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		char c;
		cin >> c;
		a[i] = c-'0';
	}
	
	int cnt = 0, pre = 0;
	for(int i = 0; i < n; i++){
		if(a[i] != pre){
			vec.push_back(cnt);
			cnt = 1;
		}
		else cnt++;
		pre = a[i];
	}
	vec.push_back(cnt);
	if(pre == 1) vec.push_back(0);
	
	if(vec.size() == 1){
		cout << vec[0] << endl;
		return 0;
	}
	
	int ans = calc();
	reverse(vec.begin(), vec.end());
	ans = max(ans, calc());
	
	cout << ans << endl;
}

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

    int n,k;
    cin>>n>>k;
    int  a[n];
    for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
      sort(a,a+n);
int ans=0;
    for(int i=0;i<k;i++)
        {
            ans+=a[i];
        }
        cout<<ans;

}


Measured memory_bytes: 3628
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

A,B =inpl()
A -= 1
B -= 1

H,W = 41,100
ans = []

for y in range(H//2+1):
	tmp = []
	if y%2==0:
		tmp = ['.']*W
	else:
		for x in range(W):
			if x%2==1 and y%2==1 and B>0:
				tmp.append('#')
				B -= 1
			else:
				tmp.append('.')
	ans.append(tmp)

for y in range(H//2+1,H):
	tmp = []
	if y%2==1:
		tmp = ['#']*W
	else:
		for x in range(W):
			if x%2==1 and y%2==0 and A>0:
				tmp.append('.')
				A -= 1
			else:
				tmp.append('#')
	ans.append(tmp)

print(H,W)
for a in ans:
	print (''.join(a))


Measured memory_bytes: 4332
"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.split(/ |\n/),
    cid = 0;

// number一個取得
// eslint-disable-next-line no-unused-vars
const next = () => +cin[cid++];

// 文字列一個取得
// eslint-disable-next-line no-unused-vars
const nextstr = () => cin[cid++];

// BigInteger一個取得
// eslint-disable-next-line no-unused-vars
const nextbig = () => BigInt(cin[cid++]);

// 長さnの配列として取得。aは文字列フラグ
// eslint-disable-next-line no-unused-vars
const nexts = (n, a) =>
    a ? cin.slice(cid, (cid += n)) : cin.slice(cid, (cid += n)).map((a) => +a);

// w個ずつを組にして長さhの配列。aは文字列フラグ。
// eslint-disable-next-line no-unused-vars
const nextm = (h, w, a) => {
    var r = [],
        i = 0;
    if (a) for (; i < h; i++) r.push(cin.slice(cid, (cid += w)));
    else for (; i < h; i++) r.push(cin.slice(cid, (cid += w)).map((a) => +a));
    return r;
};
// 多次元配列。v,a1,a2,a3 なら、3次元。[[値vで長さa3の配列]をa2個並べた配列]をa1個並べた配列。
// eslint-disable-next-line no-unused-vars
const xArray = (...args) => {
    var a = args,
        l = a.length,
        r = "Array(a[" + --l + "]).fill().map(x=>{return " + a[0] + ";})";
    while (--l) r = "Array(a[" + l + "]).fill().map(x=>" + r + ")";
    return eval(r);
};

console.log(main());

function main() {
    let n = next();
    let a = nexts(n).sort((a, b) => a - b);
    let ans = 0;
    if (n == 1) return 1;
    //let b = Array.from(new Set(a));
    let dp = Array(a[n - 1] + 1).fill(true);
    //let nums = Array(a[n - 1] + 1).fill(0);
    //for (let i = 0; i < n; i++) nums[a[i]]++;
    a.push(0);
    for (let i = 0; i < a.length - 1; i++) {
        let x = a[i];
        if (dp[x]) {
            for (let j = 2; j <= Math.floor(a[n - 1] / x); j++) {
                dp[x * j] = false;
            }
            dp[x] = false;
            if (a[i] != a[i + 1]) ans++;
        }
    }

    return ans;
}


Measured memory_bytes: 58520
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <complex>

using namespace std;
using ll = long long;

int main() {
    ll x, y;
    cin >> x >> y;
    int len = 0;
    auto tmp = x;
    while (tmp <= y) {
        tmp *= 2;
        len++;
    }
    cout << len << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
	int n;
	long long k;
	cin>>n>>k;
	vector<int> a(n);
	rep(i,n)cin>>a[i];
	vector<int> s;
	vector<int> ord(n+1,-1);
	int c=1,l=0;
	{
		int v=1;
		while(ord[v]==-1){
			ord[v]=s.size();
			s.push_back(v);
			v=a[v-1];
		}
		c=s.size()-ord[v];
		l=ord[v];
	}
	if(k<l)cout<<s[k]<<endl;
	else{
		k-=l;
		k%=c;
		cout<<s[l+k]<<endl;
	}
	return 0;
}

Measured memory_bytes: 5808
n=int(input())


#隣接リストtableを作る
table = [[0 for i in range(n)] for j in range(n)]


for _ in range(n):
    
    input_ls=list(map(int,input().split()))
    
    #頂点と辺の整理
    vertex=input_ls[0]
    edges_count=input_ls[1]
    edges=input_ls[2:]
    
    
    for k in edges:
        table[vertex-1][k-1]=1
        
        
        
for i in range(n):
    for j in range(n):
        if j!=n-1:
            print(table[i][j],end=' ')
        else:
            print(table[i][j])


Measured memory_bytes: 6384
#include <cstdio>
#include <iostream>
#include <string>
#define N 1000000007

int main() {
    std::string s;
    std::cin >> s;
    int length = s.length();
    long n[length + 1], a[length + 1], ab[length + 1], abc[length + 1];
    n[0] = 1; a[0] = 0; ab[0] = 0; abc[0] = 0;
    for (int i = 1; i <= length; i++) {
        switch (s[i - 1]) {
        case 'A':
            n[i] = n[i - 1];
            a[i] = (a[i - 1] + n[i - 1]) % N;
            ab[i] = ab[i - 1];
            abc[i] = abc[i - 1];
            break;
        case 'B':
            n[i] = n[i - 1];
            a[i] = a[i - 1];
            ab[i] = (ab[i - 1] + a[i - 1]) % N;
            abc[i] = abc[i - 1];
            break;
        case 'C':
            n[i] = n[i - 1];
            a[i] = a[i - 1];
            ab[i] = ab[i - 1];
            abc[i] = (abc[i - 1] + ab[i - 1]) % N;
            break;
        case '?':
            n[i] = (n[i - 1] * 3) % N;
            a[i] = (a[i - 1] * 3 + n[i - 1]) % N;
            ab[i] = (ab[i - 1] * 3 + a[i - 1]) % N;
            abc[i] = (abc[i - 1] * 3 + ab[i - 1]) % N;
            break;
        default:
            break;
        }
    }
    printf("%ld\n", abc[length]);
    return 0;
}




Measured memory_bytes: 3584
#include<bits/stdc++.h>
char s[100007];
int get[128];
int main(){
    get['b']=0,get['p']=1,get['d']=2,get['q']=3;
    scanf("%s",s+1);
    for(int l=strlen(s+1),i=1;i<=(l>>1)+1;++i){
        if(get[s[i]]^((get[s[l-i+1]]+2)%4))return printf("No\n"),0;
    }
    return printf("Yes\n"),0;
}

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

using namespace std;

int main() {
  size_t N, M;
  cin >> N >> M;

  vector<size_t> L;
  vector<size_t> R;
  for (size_t i = 0; i < M; i++) {
    size_t l, r;
    cin >> l >> r;
    L.emplace_back(l);
    R.emplace_back(r);
  }

  size_t lower = 0;
  size_t upper = 100000;

  for (size_t i = 0; i < M; i++) {
    if (L[i] > lower) {
      lower = L[i];
    }
    if (R[i] < upper) {
      upper = R[i];
    }
  }

  if (upper < lower) {
    cout << 0 << endl;
  } else if (upper == lower) {
    cout << 1 << endl;
  } else {
    cout << upper - lower + 1 << endl;
  }

  return 0;
}

Measured memory_bytes: 2036
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A
# 本よりこっちのほうがぶっちゃけわかりやすい http://www.deqnotes.net/acmicpc/prim/
# 螺旋本ではダイクストラとの違いをあまり解説していないが、違いはダイクストラのところで考えよう
# 記号は本に合わせる。
# 制約条件によりノードはたかだか100なのでオーダーを木にせずにナイーブに実装できる。本ではdを導入することにより計算量を少し削減している

INF = 10**5
# load data
N = int(input())
M = []  # 隣接行列
Color = []  # 訪問状態を記録 0:未訪問, 1:訪問経験あり, 2:訪問済み(用済み) #そうはこいつが2になっているノードはMST
D = []  # 本で言うd #こいつの役割はP299の図を追うとわかりやすい #MSTに隣接しているノードへのコストをノードのところに記録する
P = []  # 本で言うp # MSTにおける親を記録

for _ in range(N):
    Color.append(0)  # ノードはすべて未訪問
    D.append(INF)  # 無限で初期化しておく
    P.append(None)
    M.append([x if x != -1 else INF for x in map(int, input().split())])

# primのアルゴリズムを適応する
# ノード0からMSTを構築していく #まずはノード0をMSTに追加する
D[0] = 0
P[0] = None  # 親が存在しないことをNoneで示す

while True:  # MSTができるまで繰り返す ちなみにループの一周目は0をMSTに追加するところから始まる
    # MSTに隣接するノードへのpathの中で一番小さなコストを見つける、ついでにそのノード番号も
    min_cost = INF
    for i in range(N):
        if Color[i] != 2 and D[i] < min_cost:  # 訪問済みかつ最小値を更新したら
            min_cost = D[i]
            u = i  # uにはコストが一番小さい時のノードが追加される

    if min_cost == INF:
        break  # つながりがもうない

    Color[u] = 2  # つながるのに一番コストの小さい訪問済みに(MSTに追加)する

    for v in range(N):
        if Color[v] != 2 and M[u][v] != INF:  # MSTに追加されていなくてかつ、uとつながっている
            if M[u][v] < D[v]:  # 新たに追加したノードuからvに行くほうがコストが小さいならばそれをメモする
                D[v] = M[u][v]
                P[v] = u  # vの親の候補としてuを代入しておく(だいぶ無駄では？)
                Color[v] = 1  # 一度見たことあるのはgrayにしておくが、ぶっちゃけ意味はない

# これにてPに木構造が入ったのでこれをもとにコストを計算すれば良い
# ぶっちゃけこの操作は上のwhileに組み込み可能なんだけどあえてね
ans = 0
for i, p in enumerate(P[1:], start=1):
    ans += M[i][p]

print(ans)



Measured memory_bytes: 5896
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strAry[] = br.readLine().split(" ");
    
        Integer.parseInt(strAry[0]);
        Integer.parseInt(strAry[1]);
        Integer.parseInt(strAry[2]);
        
        Arrays.sort(strAry);
        
        System.out.println(strAry[0] + " " + strAry[1] + " " + strAry[2]);
    }
}

Measured memory_bytes: 24232
from collections import defaultdict as dd
from collections import Counter
from pprint import pprint as pp

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
d = ['ABC','ABD']
print(d[N//1000])

Measured memory_bytes: 3564
n, m, l = gets.split(" ").map(&:to_i)

a = []
b = []
c = Array.new(n).map{Array.new(l, 0)}

n.times { |d|
  a[d] = gets.split.map(&:to_i)
}

m.times { |e|
  b[e] = gets.split.map(&:to_i)
}

for i in 0..n-1
  for j in 0..l-1
    for k in 0..m-1
      c[i][j] += a[i][k] * b[k][j]
    end
  end
end

n.times { |l|
  puts c[l].join(" ")
} 

Measured memory_bytes: 9308
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

ll dp[110][4][4][4];

int main(){
    int N; cin >> N;
    dp[0][3][3][3] = 1;
    rep(i,N){
        rep(j,4){
            rep(k,4){
                rep(l,4){
                    if(dp[i][j][k][l] == 0) continue;
                    rep(a,4){
                        if(a == 2 && j == 1 && k == 0) continue;
                        if(a == 2 && j == 0 && k == 1) continue;
                        if(a == 1 && j == 2 && k == 0) continue;
                        if(a == 2 && j == 1 && l == 0) continue;
                        if(a == 2 && k == 1 && l == 0) continue;
                        dp[i+1][a][j][k] += dp[i][j][k][l];
                        dp[i+1][a][j][k] %= MOD;
                    }
                }
            }
        }
    }
    ll ans = 0;
    rep(i,4)rep(j,4)rep(k,4){
        ans = (ans + dp[N][i][j][k]) % MOD;
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define watch(x) cout<<(#x)<<" is "<<x<<endl;
#define ll long long int
#define pb push_back
#define in insert
#define mp make_pair
#define F first
#define S second
#define N 1000000
#define mod 1000000007
#define PI acos(-1)
int main()
{
	IOS
    int n;
    cin>>n;
    int i;
    map<string,int> mp;
    string s;
    for(i=0;i<n;i++)
    {
    	cin>>s;
    	mp[s]++;
	}
	cout<<"AC"<<" x "<<mp["AC"]<<"\n";
	cout<<"WA"<<" x "<<mp["WA"]<<"\n";
	cout<<"TLE"<<" x "<<mp["TLE"]<<"\n";
	cout<<"RE"<<" x "<<mp["RE"]<<"\n";
}

Measured memory_bytes: 3668
import collections

N, K, Q = map(int, input().split())
m = Q - K + 1
A = [input() for _ in range(Q)]
C = collections.Counter(A)
Ans = []
for i in range(N):
    if m <= 0:
        Ans.append("Yes")
    elif C[str(i+1)] < m:
        Ans.append("No")
    else:
        Ans.append("Yes")

for i in range(N):
    print(Ans[i])

Measured memory_bytes: 14332
//Volume0-0078
import java.util.Scanner;

class P {
	public int x;
	public int y;
}

public class Main {

	//declare
	private static int     n;
	private static int[][] square;

	public static void main(String[] args) {

		int max;
		P   p;

        //input
        Scanner sc = new Scanner(System.in);
        while((n = sc.nextInt()) != 0){

        	//calculate
        	square = new int[n][n];
        	max = (int)Math.pow(n, 2);
        	p = start_p(n);
        	for(int i=1;i<=max;i++){
        		square[p.y][p.x] = i;
        		p = next_p(p);
        	}

        	//output
        	print();
        }
	}

	private static P start_p(int n){
		P ret = new P();
		ret.x = (n - 1) / 2;
		ret.y = ret.x + 1;
		return ret;
	}

	private static P next_p(P p){
		p.x = (p.x + 1) % n;
		p.y = (p.y + 1) % n;
		if(square[p.y][p.x] != 0){
			p.x = (p.x - 1 + n) % n;
			p.y = (p.y + 1) % n;
		}
		return p;
	}

	private static void print(){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				System.out.printf("%4d",square[i][j]);
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 18280
import java.io.*;

public class Main {

  static final long MOD = 1000000007;
  static long n, k, ans;

  static long fastPowMOD(long base, long expo){
    long ret = 1;
    base %= MOD;
    while(expo > 0){
      if(expo % 2 == 1){
        ret *= base;
      }
      expo >>= 1;
      base *= base;
      base %= MOD;
      ret %= MOD;
    }
    return ret;
}

  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] in = br.readLine().split(" ");
    n = Long.parseLong(in[0]);
    k = Long.parseLong(in[1]);

    br.close();

    ans = fastPowMOD(k, n);
    long[] occupied = new long[(int)(k + 1)];

    for(long i = k; i >= 2; i--){
      long num = k / i;
      long pat = (fastPowMOD(num, n) - occupied[(int)i]) % MOD;
      if(pat < 0) pat += MOD;
      ans += (pat * (i - 1)) % MOD;
      ans %= MOD;

      long tmp = i;
      for(long j = 2; j * j <= tmp; j++){
        if(tmp % j == 0){
          occupied[(int)j] += pat;
          occupied[(int)j] %= MOD;
          if(tmp / j != j){
            occupied[(int)(tmp / j)] += pat;
            occupied[(int)(tmp / j)] %= MOD;
          }
        }
      }
    }

    System.out.println(ans);

  }
}

Measured memory_bytes: 33900
#include <iostream>

using namespace std;

char x;
struct
{
    int val_R;
    int val_G;
    int val_B;
} v[4010];
long long s[4010], dif_poz_1, dif_poz_2, prod, nr, n;
int main()
{

    cin>>n;
    cin.get();
    for(int i=1; i<=n; i++)
    {
        cin>>x;
        if(x=='R')
        {
            s[i]=-1;
            continue;
        }
        if(x=='G')
        {
            s[i]=2;
            continue;
        }
        if(x=='B')
        {
            s[i]=3;
            continue;
        }
    }
    for(int i=n; i>=1; i--)
    {
        v[i]=v[i+1];

        if(s[i]==-1)
        {
            v[i].val_R++;
            continue;
        }
        if(s[i]==2)
        {

            v[i].val_G++;
            continue;
        }
        if(s[i]==3)
        {
            v[i].val_B++;
            continue;
        }
    }
    for(int i=1; i<n-1; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            prod=s[i]*s[j];
            dif_poz_1=j-i;
            if(prod==-2)
            {
                nr+=v[j+1].val_B;
                dif_poz_2=j+dif_poz_1;
                if(dif_poz_2<=n)
                    nr=nr-(v[dif_poz_2].val_B-v[dif_poz_2+1].val_B);
                continue;
            }

            if(prod==-3)
            {
                nr+=v[j+1].val_G;
                dif_poz_2=j+dif_poz_1;
                if(dif_poz_2<=n)
                    nr=nr-(v[dif_poz_2].val_G-v[dif_poz_2+1].val_G);
                continue;
            }

            if(prod==6)
            {
                nr+=v[j+1].val_R;
                dif_poz_2=j+dif_poz_1;
                if(dif_poz_2<=n)
                    nr=nr-(v[dif_poz_2].val_R-v[dif_poz_2+1].val_R);
                continue;
            }
        }
    }
    cout<<nr;
    return 0;
}


Measured memory_bytes: 3712
import java.io.*;

class Main {
    static int n;
    static double[][] kochCurve;
    static int i = 0;

    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        kochCurve = new double[(int) Math.pow(4, n) + 1][2];

        drawKoch(0, 0, 100, 0, 1);

        kochCurve[kochCurve.length - 1] = new double[] {100, 0};

        StringBuilder sb = new StringBuilder("");
        for (int j = 0; j < kochCurve.length; j++) {
            sb.append(kochCurve[j][0]).append(" ").append(kochCurve[j][1]).append("\n");
        }
        System.out.print(sb.toString());
    }

    public static void drawKoch(double p1x, double p1y, double p2x, double p2y, int count) {
        if (count == n + 1) {
            kochCurve[i++] = new double[] {p1x, p1y};
            return;
        }

        double sx = (p2x - p1x) / 3 + p1x;
        double sy = (p2y - p1y) / 3 + p1y;
        double tx = p2x - (p2x - p1x) / 3;
        double ty = p2y - (p2y - p1y) / 3;

        double ux = ((tx - sx) - Math.sqrt(3) * (ty - sy)) / 2 + sx;
        double uy = ((ty - sy) + Math.sqrt(3) * (tx - sx)) / 2 + sy;

        count++;
        drawKoch(p1x, p1y, sx, sy, count);
        drawKoch(sx, sy, ux, uy, count);
        drawKoch(ux, uy, tx, ty, count);
        drawKoch(tx, ty, p2x, p2y, count);
    }
}

Measured memory_bytes: 29536
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> flag(N + 1);
    vector<ll> Ai(N + 1);
    vector<ll> table(N + 1);
    REP(x, N + 1)
    {
        table.at(x) = (x * (x - 1)) / 2;
    }

    REP(i, N)
    {
        cin >> Ai.at(i);
        flag.at(Ai.at(i))++;
    }

    ll ans = 0;
    REP(j, N + 1)
    {
        ans += table.at(flag.at(j));
    }

    REP(k, N)
    {
        ll tmp = ans - flag.at(Ai.at(k)) + 1;
        cout << tmp << "\n";
    }
}

Measured memory_bytes: 7296
#include<stdio.h>
#include<string.h>

int main(){
  int n, i, taro = 0, hana = 0;
  char s1[101], s2[101];

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
	  scanf("%s %s", s1, s2);
      if ( strcmp(s1, s2) == 0 ) {taro++; hana++;}
      else if ( strcmp(s1, s2) > 0 ) taro += 3;
      else if ( strcmp(s1, s2) < 0 ) hana += 3;
  }
  printf("%d %d\n", taro, hana);
  return 0;
}


Measured memory_bytes: 2076
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

string s;
int n;

ll f(int i, ll last){
	if(i+1==s.size()){
		// cout<<last*10+(s[i]-'0')<<endl;
		return last*10+(s[i]-'0');
	}
	// cout<<last*10+(s[i]-'0')<<endl;
	return (last*10 + (s[i]-'0'))*(1LL<<(n-i-2)) + f(i+1,0) + f(i+1,last*10 + (s[i]-'0'));
}

void solve(){
	cin>>s;
	n = s.size();
	if(n==1){
		cout<<s<<endl;
		return;
	}
	cout<<f(0,0)<<endl;
}

int main(){
	fastread;
	int t = 1;
	// cin>>t;
	for(int i=1;i<=t;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
// AOJ GRL_1_A: Shortest Path - Single Source Shortest Path
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

using namespace std;

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define Get(t, i) get<(i)>((t))
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto a : b)

const int inf = 1 << 25;
const ll INF = 1LL << 55;

// Bellman-Ford algorithm: Single-source shoretest paths
struct edge {
  int from, to, weight;
  edge(){}
  edge(int from, int to, int weight):from(from), to(to), weight(weight){}
};

struct BellmanFord
{
  vector<edge> edges;
  vector<int> distance;
  BellmanFord(int V):distance(V, inf){}
  void add_edge(int from, int to, int weight)
  {
    edges.push_back(edge(from, to, weight));
  }
  bool shortest_path(int source)
  {
    distance[source] = 0;

    // if this graph doesn't have negative cycle,
    // the shortest path is found in |V|-1 times.
    for(int i = 0; i < (int)distance.size()-1; i++) {
      for(edge e : edges) {
	if(distance[e.from] != inf &&
	   distance[e.from] + e.weight < distance[e.to]) {
	  distance[e.to] = distance[e.from] + e.weight;
	}
      }
    }

    // check for negative-weight cycles
    for(edge e : edges) {
      if(distance[e.from] != inf &&
	 distance[e.from] + e.weight < distance[e.to]) {
	return true;
      }
    }
    return false;
  }
};

int main()
{
  int V, E, r; cin >> V >> E >> r;
  BellmanFord sssp(V);
  while(E--) {
    int s, t, d; cin >> s >> t >> d;
    sssp.add_edge(s, t, d);
  }
  if(sssp.shortest_path(r)) {
    cout << "NEGATIVE CYCLE" << endl;
    return 0;
  }
  for(int i = 0; i < V; i++) {
    if(sssp.distance[i] == inf) puts("INF");
    else cout << sssp.distance[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3120
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    A,B=map(int,input().split())
    B+=1
    ans=0
    N=max(len(bin(A)),len(bin(B)))-2
    for i in range(N):
        a=A//(2**(i+1))*(2**i)+max(A%(2**(i+1))-2**i,0)
        b=B//(2**(i+1))*(2**i)+max(B%(2**(i+1))-2**i,0)
        if (b-a)%2:
            ans|=(1<<i)
    print(ans)
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 38488
<?php
$n = int();
for($i = 0; $i < $n; $i++){
  $aArray[] = int();
}
$max = 0;
for($i = 0; $i < $n; $i++){
  $max = max($aArray[$i], $max); 
  $b[$i] = $max;
}
$max = 0;
for($i = $n - 1; $i >= 0; $i--){
  $max = max($aArray[$i], $max); 
  $c[$i] = $max;
}
for($i = 0; $i < $n; $i++){
  echo max($b[$i-1] ?? 0, $c[$i+1] ?? 0),"\n";
}

function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}

Measured memory_bytes: 33776
myinput = list(map(int,input().split()))

firstarg = myinput[0:2]
secondarg = myinput[2:4]

#print(firstarg,secondarg)

resultlist = [0]*4

for i in range(2):
    for j in range(2):
        resultlist[2*i+j]=firstarg[i]*secondarg[j]

#print(resultlist)
print(max(resultlist))

Measured memory_bytes: 61728
function main(input) {
	const arg = input.split(' ');
	const a = parseInt(arg[0], 10);
	const b = parseInt(arg[1], 10);

	if ((a * b) % 2 == 0)
		console.log('Even');
	else
		console.log('Odd');
}

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

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

int main()
{
    ll n;
    string s,t;
    cin>>s>>t;
    ll ans=0;
    for(ll i=0;i<ll(s.size());i++)
    {
        if(s[i]==t[i]&&(s[i]=='S'||s[i]=='C'||s[i]=='R'))
            ans++;
    }
    cout<<ans<<endl;
}


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

int main() {
  int n,k;
  cin>>n>>k;
  int ans=0;
  for(int i=0;i<n;i++){
    int h;
    cin>>h;
    if(h>=k){
      ans++;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
Scanf.scanf "%d" (fun n ->
    let digit_sum d =
        let rec loop r acc =
            if r = 0 then acc else loop (r / 10) (acc + r mod 10)
        in
        loop d 0
    in
    print_endline @@ if n mod digit_sum n = 0 then "Yes" else "No"
)

Measured memory_bytes: 3672
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
int n, k, d[9];

bool solve(int n) {
	string s;
	stringstream ss;
	ss << n;
	ss >> s;
	for (int i = 0; i < k; i++) {
		if (s.find((char)(d[i] + '0')) != string::npos) return false;
	}
	return true;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < k; i++) cin >> d[i];
	while (n < 100000) {
		if (solve(n)) break;
		n++;
	}
	cout << n << endl;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
x = -1

for i in A:
    ans += B[i-1]
    if x+1 == i:
        ans += C[x-1]
    x = i

print(ans)



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

int main() {
	int h, w;
	cin >> h >> w;
	vector<string> a(h);
	rep(i, h) cin >> a[i];
	vector<string> ans(h);
	int r = 0, c = 0;
	rep(i, h) {
		bool ok = true;
		rep(j, w) {
			if(a[i][j] == '#') ok = false;
		}
		if(!ok) {
			ans[r] = a[i];
			r++;
		}
	}
	vector<int> pri;
	rep(j, w) {
		bool ok = true;
		rep(i, h) {
			if(a[i][j] == '#') ok = false;
		}
		if(!ok) {
			pri.push_back(j);
		}
	}
	rep(i, r) {
		for(int j: pri) {
			cout << ans[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
def selectionSort(A, N):
	global cnt

	for i in range(N):
		minj = i
		for j in range(i, N):
			if A[j] < A[minj]:
				minj = j
		if i != minj:
			tmp = A[i]
			A[i] = A[minj]
			A[minj] = tmp
			cnt = cnt + 1 #

	return A

if __name__ == '__main__':
	n = int(input())
	R = list(map(int, input().split()))
	cnt = 0
	R = selectionSort(R, n)
	print(" ".join(map(str, R)))
	print(cnt)

Measured memory_bytes: 7756
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const int M = 2e5+5;
ld a[M];
ll val[M];
ll ct[62][62];
int main()
{
	ll n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		int c = 0;
		bool f=0;
		for(int j=0;j<sz(s);j++)
		{
			if(s[j]=='.')
			{
				f=1;
				continue;
			}
			if(f)
				c++;
		}
		for(int j=c;j<9;j++)
		{
			s.pb('0');
		}
		for(int j=0;j<sz(s);j++)
		{
			if(s[j]=='.')
				continue;
			ll z = (s[j]-'0');
			val[i] = val[i]*(ll)10 + z;
		}
	}

	for(ll i=1;i<=n;i++)
	{
		ll x=0;
		while(val[i]%2==0)
		{
			val[i]/=2;
			x++;
		}
		ll y=0;
		while(val[i]%5==0)
		{
			val[i]/=5;
			y++;
		}
		ct[x][y]++;
	}
	ll ans = 0;
	for(ll i=0;i<=60;i++)
	{
		for(ll j=0;j<=60;j++)
		{
			for(ll k=0;k<=60;k++)
			{
				for(ll m=0;m<=60;m++)
				{
					ll p = min(i+k,j+m);
					if(p<18)
						continue;
					if(i==k && j==m)
					{
						ans += (ct[i][j]*(ct[i][j]-1));
					}
					else
					{
						ans += ct[i][j]*ct[k][m];
					}
				}
			}
		}
	}
	ans/=2;
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 5208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}
int dp[1010][1010];
int main() {
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; ++i) {
        cin >> s[i];
    }
    dp[0][0] = 1;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if(i+1 < h && s[i+1][j] == '.'){
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= mod;
            }
            if(j+1 < w && s[i][j+1] == '.'){
                dp[i][j+1] += dp[i][j];
                dp[i][j+1] %= mod;
            }
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}


Measured memory_bytes: 5248