akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <cstdlib>

const int N = 100000;
int color[N];
std::vector<int> adj_list[N];

void DFS(int node_id, int c)
{
    std::stack<int> S;
    S.push(node_id);
    color[node_id] = c;

    while(!S.empty()) {
        int target = S.top();
        S.pop();
        for (int i = 0; i < adj_list[target].size(); i++) {
            int friend_id = adj_list[target][i];
            if (color[friend_id] == -1) {
                color[friend_id] = c;
                S.push(friend_id);
            }
        }
    }
}

void AssignColor(int n)
{
    int id = 1;
    for (int i = 0; i < n; i++) color[i] = -1;
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) DFS(i, id++);
    }
}

int main(int argc, char *argv[])
{
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);

    // make adj matrix
    for (int i = 0; i < m; i++) {
        int node_id, friend_id;
        scanf("%d", &node_id);
        scanf("%d", &friend_id);
        adj_list[node_id].push_back(friend_id);
        adj_list[friend_id].push_back(node_id);
    }

    AssignColor(n);

    int q_num;
    scanf("%d", &q_num);
    for (int i = 0; i < q_num; i++) {
        int src, dst;
        scanf("%d", &src);
        scanf("%d", &dst);
        if (color[src] == color[dst]) fprintf(stdout, "yes\n");
        else fprintf(stdout, "no\n");
    }

    return 0;
}


Measured memory_bytes: 9064
N,M=map(int,input().split())
sets=[]
if N%2==1:
    for i in range(M):
        sets.append((i+1,i+1+(N-3-2*i)+1))
elif N%2==0:
    count=0
    kukan=[]
    for i in range(N//2-1):
        kukan.append(count)
        count+=2
        if count==N//2 or count==N//2-1:
            count+=1
    kukan.reverse()
    for i in range(M):
        sets.append((i+1,i+1+kukan[i]+1))
for set1 in sets:
    print(set1[0],set1[1])

Measured memory_bytes: 21072
import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        int n=sc.nextInt(),
            m=sc.nextInt();
        char[][] c=new char[n][m];
        for(int i=0;i<n;i++) {
            String s=sc.next();
            for(int j=0;j<m;j++)
                c[i][j]=(char)s.charAt(j);
        }
        int[][] dp=new int[n][m];
        for(int i=0;i<n;i++) {
            if(c[i][0]=='#')
                break;
            dp[i][0]=1;
        }
        for(int i=0;i<m;i++) {
            if(c[0][i]=='#')
                break;
            dp[0][i]=1;
        }
        int mod=1000000007;
        for(int i=1;i<n;i++) {
            for(int j=1;j<m;j++) {
                if(c[i][j]=='#')
                    dp[i][j]=0;
                else
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            }
        }
        pw.print(dp[n-1][m-1]);
        pw.close();
    }
}

Measured memory_bytes: 35240
#include<stdio.h>
#include<string.h>
int main ()
{
    long long int a,i,j,n=0,z;
    scanf("%lld", &a);
    if(a>=500){
        n=(a/500)*1000;
        a=a-500*n/1000;
    }
    if(a<500){
          z=a/5;
          n=n+z*5;
    }
    //if(a==0&&n!=0)printf("0\n");
    printf("%lld",n);
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>

using namespace std;

int main()
{
  int A1, A2, A3;
  cin >> A1 >> A2 >> A3;
  cout << max({A1, A2, A3}) - min({A1, A2, A3}) << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main { 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        while(true){
            int H = sc.nextInt();
            int W = sc.nextInt();
            
            if(H == 0 && W == 0){break;}
            
            for(int i=0 ;i<H;i++){
                for(int j=0 ;j<W;j++){
                    System.out.print("#");
                }
                System.out.println("");
            }
            System.out.println("");
        }
        
    }
}


Measured memory_bytes: 34664
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  map<string, int> mp;
  rep(i, n) {
    string s;
    cin >> s;
    mp[s]++;
  }
  printf("%s x %d\n", "AC", mp["AC"]);
  printf("%s x %d\n", "WA", mp["WA"]);
  printf("%s x %d\n", "TLE", mp["TLE"]);
  printf("%s x %d\n", "RE", mp["RE"]);
  return 0;
}

Measured memory_bytes: 3732
# frozen_string_literal: true

# https://github.com/universato/ac-library-rb/blob/master/src/scc.rb
class SCCGraph
  # initialize graph with n vertices
  def initialize(n = 0)
    @n, @edges = n, []
  end

  # add directed edge
  def add_edge(from, to)
    raise "invalid params" unless (0...@n).include? from and (0...@n).include? to

    @edges << [from, to]
  end

  # returns list of strongly connected components
  # the components are sorted in topological order
  # O(@n + @edges.size)
  def scc
    group_num, ids = scc_ids
    counts = [0] * group_num
    ids.each { |x| counts[x] += 1 }
    groups = Array.new(group_num) { [] }
    ids.each_with_index { |x, i| groups[x] << i }
    groups
  end

  private

  def scc_ids
    start, elist = csr
    now_ord = group_num = 0
    visited, low, ord, ids = [], [], [-1] * @n, []
    dfs = ->(v) {
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited << v
      (start[v]...start[v + 1]).each do |i|
        to = elist[i]
        low[v] = if ord[to] == -1
                   dfs.(to)
                   [low[v], low[to]].min
                 else
                   [low[v], ord[to]].min
                 end
      end
      if low[v] == ord[v]
        loop do
          u = visited.pop
          ord[u] = @n
          ids[u] = group_num
          break if u == v
        end
        group_num += 1
      end
    }
    @n.times { |i| dfs.(i) if ord[i] == -1 }
    ids = ids.map { |x| group_num - 1 - x }
    [group_num, ids]
  end

  def csr
    start, elist = [0] * (@n + 1), [nil] * @edges.size
    @edges.each { |(i, _)| start[i + 1] += 1 }
    @n.times { |i| start[i + 1] += start[i] }
    counter = start.dup
    @edges.each do |(i, j)|
      elist[counter[i]] = j
      counter[i] += 1
    end
    [start, elist]
  end
end

# TwoSat
# Reference: https://github.com/atcoder/ac-library/blob/master/atcoder/twosat.hpp
class TwoSat
  def initialize(n = 0)
    @n = n
    @answer = Array.new(n)
    @scc = SCCGraph.new(2 * n)
  end

  attr_reader :answer

  def add_clause(i, f, j, g)
    raise RangeError unless (0...@n).cover?(i) && (0...@n).cover?(j)

    @scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0))
    @scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0))
    nil
  end

  def satisfiable
    id = @scc.send(:scc_ids)[1]
    @n.times do |i|
      return false if id[2 * i] == id[2 * i + 1]

      @answer[i] = id[2 * i] < id[2 * i + 1]
    end
    true
  end
end


n, d = gets.split.map(&:to_i)
x, y = n.times.map { gets.split.map(&:to_i) }.transpose
ts = TwoSat.new(n)

n.times do |i|
  (i + 1...n).each do |j|
    ts.add_clause(i, false, j, false) if (x[i] - x[j]).abs < d
    ts.add_clause(i, false, j, true) if (x[i] - y[j]).abs < d
    ts.add_clause(i, true, j, false) if (y[i] - x[j]).abs < d
    ts.add_clause(i, true, j, true) if (y[i] - y[j]).abs < d
  end
end

if ts.satisfiable
  puts 'Yes'
  ts.answer.each_with_index do |ans, i|
    puts ans ? x[i] : y[i]
  end
else
  puts 'No'
end


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

using ll = long long;

int main(void){
  int n,m; cin >> n >> m;
  vector<int> a(m);
  rep(i,m) cin >> a[i];
  for(int i=0;i<m-1;i++){
    if(a[i+1]-a[i]==1){
      cout << "0" << endl;
      return 0;
    }
  }
  
  ll div = 1000000007;
  
  vector<ll> count(n+1,-10);
  rep(i,m) count[a[i]]=0;

  count[n]=1;
  for(int i=n-1;i>=0;i--){
    if(count[i]!=-10) continue;
    if(i!=n-1)count[i] = count[i+2]+count[i+1];
    else count[i] = 1;
    count[i] %= div;
  }

  cout << count[0] << endl;
  
  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll dp[100005][2];
const ll mod=1e9+7;
vector<int>vec[100005];
void dfs(int pre,int pst)
{
	dp[pre][0]=1;
	dp[pre][1]=1;
	for(int i=0;i<vec[pre].size();i++)
	{
		int to=vec[pre][i];
		if(to!=pst)
		{
			dfs(to,pre);
			dp[pre][0]*=dp[to][0]+dp[to][1];
			dp[pre][0]%=mod;
			dp[pre][1]*=dp[to][0];
			dp[pre][1]%=mod;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dfs(1,-1);
	cout<<(dp[1][0]+dp[1][1])%mod;
	return 0;
} 

Measured memory_bytes: 17556
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::string;

int main()
{
  char values[] = {'A', 'T', 'C', 'G'};
  string s;
  cin >> s;
  std::replace(s.begin(), s.end(), 'T', 'A');
  std::replace(s.begin(), s.end(), 'C', 'A');
  std::replace(s.begin(), s.end(), 'G', 'A');

  int max_count = 0;
  int count = 0;
  for (size_t i = 0; i < s.size(); ++i)
  {
    if (s[i] == 'A')
    {
      count++;
    }
    else
    {
      max_count = std::max(max_count, count);
      count = 0;
    }
  }

  max_count = std::max(max_count, count);

  cout << max_count << "\n";

  return 0;
}


Measured memory_bytes: 256
const lines: string[] = [];
const reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
reader.on("line", function (line: string) {
  lines.push(line);
});

reader.on("close", function () {
  const input = (lines[0] as string).split(" ");
  const A = [Number(input[0]), Number(input[1])];
  const B = [Number(input[2]), Number(input[3])];

  while (true) {
    B[0] -= A[1];
    if (B[0] <= 0) {
      console.log("Yes");
      break;
    }
    A[0] -= B[1];
    if (A[0] <= 0) {
      console.log("No");
      break;
    }
  }
});


Measured memory_bytes: 30076
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC119B
{
    static class MainClass
    {

        static int[] s;
        //static int[] n;

        public static void Main(string[] args)
        {

            s = Array.ConvertAll(Console.ReadLine().Split().ToArray(), int.Parse);

           // var xulst = new List<string[]>();
            double ans = 0;
            for(int i = 0; i < s[0]; i++)
            {
                string[] xu = Console.ReadLine().Split().ToArray();
                if (xu[1] == "BTC")
                {
                    ans += double.Parse(xu[0]) * 380000;
                }
                else
                {
                    ans += double.Parse(xu[0]);
                }
            }
            Console.WriteLine(ans);
            return;
        }
    }
}


Measured memory_bytes: 13268
#include<stdio.h>
#define MOD 1000000007

long int com(int n, int k);
long int C[2000][2000]={};

int main(void){
  int N,K;
  scanf("%d %d",&N,&K);
  for(int i=1;i<=K;i++){
  printf("%ld\n",(com(K-1,i-1)*com(N-K+1,i))%MOD);
  }
}


long int com(int n,int k){
 if(n < k)return 0;
 if(C[n][k] >0) return C[n][k];
 if(k == 0 || n == k || n==0) return C[n][k]=1;
 if(n>k){
   C[n][k]=(com(n-1,k-1) + com(n-1,k))%MOD; 
   return C[n][k];
 }
}

Measured memory_bytes: 30080
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[101000], L[101000];
int C[101000], n, par[101000], M = 1e9, x;
long long s = 0;
void DFS(int a, int pp){
    C[a] = 1;
    par[a] = pp;
    int i;
    for(i=0;i<E[a].size();i++){
        if(E[a][i]==pp)continue;
        DFS(E[a][i], a);
        C[a] += C[E[a][i]];
    }
    if(C[a]*2>=n){
        if(M>C[a])M=C[a], x=a;
    }
}
void Do(int a, int pp, long long d){
    s += d*2;
    int i;
    for(i=0;i<E[a].size();i++){
        if(E[a][i]!=pp) Do(E[a][i], a, d+L[a][i]);
    }
}
int main(){
    int i, a, b, c;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        E[a].push_back(b);
        L[a].push_back(c);
        E[b].push_back(a);
        L[b].push_back(c);
    }
    DFS(1,0);
    Do(x,0,0);
    if(M*2==n){
        for(i=0;i<E[x].size();i++)if(E[x][i]==par[x]) s -= L[x][i];
    }
    else{
        M = 1e9;
        for(i=0;i<E[x].size();i++) M = min(M, L[x][i]);
        s -= M;
    }
    printf("%lld\n",s);
}

Measured memory_bytes: 17280
#include <stdio.h>

int main(void) {
	int a, b, c, d, n, ans;
	while(scanf("%d", &n) != EOF) {
		ans = 0;
		for(a = 0; a < 10; a++)
			for(b = 0; b < 10; b++)
				for(c = 0; c < 10; c++)
					for(d = 0; d < 10; d++)
						if(a+b+c+d==n) ans++;
		printf("%d\n", ans);
	}
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;


int main(){
  int n, a, b;
  cin >> n >> a >> b;
  int ans = 0;
  repd(i, 1, n+1){
    int tmp = i;
    int res = 0;
    while(tmp != 0){
      res += tmp % 10;
      tmp /= 10;
    }
    if(a <= res && res <= b){
      // cout << res << " " << i << endl;
      ans += i;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

string itos(int num){
	int cnt=0;
	while(num/(int)pow(10,cnt)){
		cnt++;
	}
	string ans="";
	for(int i=cnt-1;i>=0;i--){
		ans+=(char)(num/(int)pow(10,i)+48);
		num-=(num/(int)pow(10,i))*pow(10,i);
	}
	return ans;
}

int main(){
	int n;
	while(1){
		cin>>n;
		if(!n)break;
		string s;
		cin>>s;
		int size=s.size();
		int count=0;
		string ans="";
		rep(i,n){
			count=0;
			while(count<size){
				char check=s[count];
				int cnt=0;
				while(s[++count]==check){
					cnt++;
				}
				cnt++;
				ans+=itos(cnt);
				ans+=check;
			}
			s=ans;
			size=s.size();
			ans="";
		}
		cout<<s<<endl;
	}
	return 0;
}

Measured memory_bytes: 1364
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

__int128_t calc(__int128_t H, __int128_t W, __int128_t h, __int128_t w) {
    return (H - h) * (W - w);
}

int H, W, h, w;

int main(int argc, char **argv) {
    std::cin >> H >> W;
    std::cin >> h >> w;

    long long ret = calc(H, W, h, w);
    std::cout << ret << std::endl;
}

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

using namespace std;

int main(){
  int n;
  string s;
  map<string, int> mp;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s;
    mp[s]++;
  }
  for(auto p: {"AC", "WA", "TLE", "RE"}){
    cout << p << " x " << mp[p] << endl;
  }
}



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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define LL long long
#define ULL unsigned long long

// n개중에서 k 를 고르는 Combination table을 미리 세팅한다.
// C[n][k] -> nCk
ULL Comb[51][51];
void combination_table(int n)
{
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= i; ++j)
        {
            if(j == 0 || j == i)
                Comb[i][j] = 1ll;
            else
                Comb[i][j] = Comb[i - 1][j - 1] + Comb[i - 1][j];
        }
}

LL cache[51][51];
LL bino2(int n, int r)
{
    if(r > n) return 0;
    if(r == 0 || n == r) return 1;

    LL& ret = cache[n][r];
    if(ret != -1)
        return ret;
    return ret = (bino2(n - 1, r - 1) + bino2(n - 1, r));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
    int N, A, B;
    cin >> N >> A >> B;

    VL items(N, 0);
    REP(i, 0, N) cin >> items[i];

    combination_table(N);
    sort(items.begin(), items.end(), greater<LL>());

    double max_avg = (double)accumulate(items.begin(), items.begin() + A, 0ll) / A;
    
    int num = 0, pos = 0;
    REP(i, 0, N){
        if(items[i] == items[A - 1])
        {
            ++num;
            if(i < A)
                ++pos;   
        }
    }

    CLEAR(cache, -1);
    LL cnt = 0ll;
    if(pos == A)
    {
        for(int i = A; i <= B; ++i)
            cnt += bino2(num, i);
    }
    else
        cnt += bino2(num, pos);

    cout.precision(10);
    cout << fixed << max_avg << endl << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]

use std::cmp;

#[allow(dead_code)]
pub struct Scanner<'a> {
    _buf: &'a str,
    iter: ::std::str::SplitWhitespace<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    pub fn new(buf: &'a str) -> Self {
        Scanner {
            _buf: buf,
            iter: buf.split_whitespace(),
        }
    }

    pub fn array<T>(&mut self, n: usize) -> Vec<T>
        where T: ::std::str::FromStr,
              T::Err: ::std::fmt::Debug,
    {
        let mut res = Vec::with_capacity(n);
        for _ in 0..n {
            res.push(self.value());
        }
        res
    }

    pub fn value<T>(&mut self) -> T
        where T: ::std::str::FromStr,
              T::Err: ::std::fmt::Debug,
    {
        self.next().parse().unwrap()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.next().chars().collect()
    }

    fn next(&mut self) -> &str {
        self.iter.next().unwrap()
    }
}

#[allow(dead_code)]
const INF: i64 = 1_010_000_000_000_000_000;

#[allow(dead_code)]
const MOD: i64 = 1_000_000_007;

struct Solver {
    M: Vec<Vec<char>>,
    memo: Vec<Vec<Option<i64>>>,
}

impl Solver {
    fn new(H: i64, W: i64, M: Vec<Vec<char>>) -> Self {
        Solver {
            M: M,
            memo: vec![vec![None; H as usize]; W as usize],
        }
    }

    fn f(&mut self, x: i64, y: i64) -> i64 {
        if x == 0 && y == 0 { return 1; }

        if self.memo[x as usize][y as usize].is_none() {
            let mut res = 0;
            if x > 0 && self.M[y as usize][(x-1) as usize] != '#' {
                res += self.f(x-1,y);
                res %= MOD;
            }
            if y > 0 && self.M[(y-1) as usize][x as usize] != '#' {
                res += self.f(x,y-1);
                res %= MOD;
            }
            self.memo[x as usize][y as usize] = Some(res);
        }
        self.memo[x as usize][y as usize].unwrap()
    }
}

fn main() {
    let mut _input = String::new();
    {
        use ::std::io::Read;
        ::std::io::stdin().read_to_string(&mut _input).unwrap();
    }
    let mut sc = Scanner::new(&_input);

    let H = sc.value::<i64>();
    let W = sc.value::<i64>();
    let mut M = Vec::with_capacity(H as usize);
    for _ in 0..H {
        M.push(sc.chars());
    }

    let mut sol = Solver::new(H, W, M);
    let ans = sol.f(W-1,H-1);

    println!("{}", ans);
}


Measured memory_bytes: 29052
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
const int mod = 1000000007;
const int MAXV =  3010;

int dp[MAXV][MAXV];

int main() {
  int n, t;
  cin >> n >> t;
  vector<pair<int, int>> p(n);
  rep(i, n) cin >> p[i].first >> p[i].second;
  sort(p.begin(), p.end());
  int ans = 0;
  rep(i, n) {
    rep(j, t) {
      chmax(dp[i + 1][j], dp[i][j]);
      int nj = p[i].first + j;
      if (nj < t) chmax(dp[i + 1][nj], dp[i][j] + p[i].second);
    }
    chmax(ans, dp[i][t - 1] + p[i].second);

  }
  cout << ans << endl;
}

Measured memory_bytes: 35584
N = int(input())
h = list(map(int,input().split()))
dp = [0]
dp.append(abs(h[1]-h[0]))
for i in range(2,N):
    mindp = []
    mindp.append(abs(h[i] - h[i-1])+dp[i-1])
    mindp.append(abs(h[i] - h[i-2])+dp[i-2])
    mindp.sort()
    dp.append(mindp[0])
print(dp[-1])

Measured memory_bytes: 13980
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int64_t ans = 1;
  vector<int64_t> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    if (A.at(i) == 0) {
      ans = 0;
      break;
    }
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  
  for (int i = 0; i < N; i++) {
    if (ans == 0) {
      break;
    }
    int64_t dummy = ans;
    double judge = log10(ans) + log10(A.at(i));
    if (judge > 18 ) {
      ans = -1;
      break;
   }
    ans *= A.at(i);
    if (ans > 1000000000000000000 || ans < dummy ) {
      ans = -1;
      break;
    }
  }
  
  cout << ans << endl;
}

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

 
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 (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

 
int N;
vector<long long> a;
vector< vector<long long> > dp;

//dp[l][r]:[l, r)の範囲における二人が最適な行動をした時のX-Yの値
//dp[l][r] = max(dp[l][r-1]+a[r-1], dp[l+1][r]+a[l]) (大郎)
//dp[l][r] = min(dp[l][r-1]-a[r-1], dp[l+1][r]-a[l]) (次郎)

long long rec(int l, int r) {
    if (dp[l][r] != -1) return dp[l][r];
    if (r-l == 0) return 0; //数字が残っていない時
    else {
        if ((r-l) % 2 == N % 2) { //大郎のturn
            dp[l][r] = max(rec(l+1, r)+a[l], rec(l, r-1)+a[r-1]);
        }
        else { //次郎のturn
            dp[l][r] = min(rec(l+1, r)-a[l], rec(l, r-1)-a[r-1]);
        }
    }
    return dp[l][r];
}

int main() {
    cin >> N;
    a.resize(N);
    dp.resize(N+2, vector<long long> (N+2, -1));
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    long long ret = rec(0, N);
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 71040
#include <stdio.h>
#define N 200000

int main(void) {
	int n,R[N];
	int i,j,temp,max,min;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&R[i]);
	max=R[n-1]-R[n-2];
	min=R[n-1];
	for(i=n-2;i>=0;i--){
		if(max<min-R[i]) max=min-R[i];
		if(min<R[i]) min=R[i];
	}
	printf("%d\n",max);

	return 0;
}


Measured memory_bytes: 2544
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N = ni()
V = na()
C = na()
#print(V,C)
def Solve(x,cnt,c,v,res):
    if(cnt>=0 and x):
        #print("cnt",cnt,"  C",C[cnt],"  v",V[cnt])
        c+=C[cnt]
        v+=V[cnt]
    if(cnt==N-1):
        res = max(v-c,res)
        #print(v-c,res)
    else:
        res = Solve(True,cnt+1,c,v,res)
        #print("ll")
        res = Solve(False,cnt+1,c,v,res)
    #print("aa",res)
    return res
ans = Solve(True,-1,0,0,0)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}

ll solve(){
  ll N; cin>>N;
  ll ans = 1;
  REP(i,N){
    ll t; cin>>t;
    ans = lcm(t,ans);
  }
  return ans;
}

int main(){
  cout << solve()<<"\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(a) int((a).size())


int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
    ll x;
    cin>>x;
    if(x>=30) cout<<"Yes\n";
    else cout<<"No\n";
    
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

using namespace std;

int main(){

	int n;
	scanf("%d",&n);

	int table[n][n];

	int*** memo = new int**[n];
	for(int i = 0; i < n; i++){
		memo[i] = new int*[n];
		for(int k = 0; k < n; k++){
			memo[i][k] = new int[n+1];
		}
	}

	for(int i = 0; i < n; i++){
		for(int k = 0; k < n; k++)scanf("%d",&table[i][k]);
	}

	int maximum = -2000000000,tmp,pre,pre_row;

	for(int H = 1; H <= n; H++){ //??????????????????
		for(int W = 1; W <= n; W++){ //???????????????
			for(int row = 0; row <= n-H;row++){
				for(int col = 0; col <= n-W; col++){
					if(W == 1){ //W == 1??????????????¢???
						if(col == 0){ //?????????
							if(row == 0){
								tmp = 0;
								for(int i = 0; i < H; i++){
									for(int k = 0; k < W; k++)tmp += table[i][k];
								}
								memo[row][col][1] = tmp; //????§????[row][col],??????H,???W?????????????¨???????
								maximum = max(maximum,tmp);
								pre = tmp;
								pre_row = tmp;
							}else{
								for(int i = 0; i < W; i++)pre_row -= table[row-1][i]; //?????????1????????????
								for(int i = 0; i < W; i++)pre_row += table[row+H-1][i]; //????????????????????????
								memo[row][col][1] = pre_row; //????§????[row][col],??????H,???W?????????????¨???????
								maximum = max(maximum,pre_row);
								pre = pre_row;
							}
						}else{
							for(int i = 0; i < H; i++)pre -= table[row+i][col-1]; //?????????1????????????
							for(int i = 0; i < H; i++)pre += table[row+i][col+W-1]; //???????????????
							memo[row][col][1] = pre; //????§????[row][col],??????H,???W?????????????¨???????
							maximum = max(maximum,pre);
						}

					}else{ //W > 1??????????????¢????´???¨??????
						if(col == 0){ //?????????
							if(row == 0){
								tmp = memo[row][col][W-1];
								for(int i = 0; i < H; i++){
									tmp += table[i][W-1];
								}
								memo[row][col][W] = tmp; //????§????[row][col],??????H,???W?????????????¨???????
								maximum = max(maximum,tmp);
							}else{
								tmp = memo[row][col][W-1];
								for(int i = 0; i < H; i++){
									tmp += table[row+i][W-1];
								}
								memo[row][col][W] = tmp;
								maximum = max(maximum,tmp);
							}
						}else{
							tmp = memo[row][col][W-1];
							for(int i = 0; i < H; i++){
								tmp += table[row+i][col+W-1];
							}
							memo[row][col][W] = tmp;
							maximum = max(maximum,tmp);
						}
					}
				}
			}
		}
	}

	printf("%d\n",maximum);

	return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n;
	int64_t d;
	cin >> n >> d;
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
	    int64_t x, y;
	    cin >> x >> y;
	    int64_t dist = (x * x) + (y * y);
	    
	    if (dist <= d * d) {
	        ans++;
	    }
	}
	cout << ans << "\n";
	return 0;
}

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

int main() {
	
	int n; cin >> n;
	ll ans = 0;
	for (int a = 1; a < n; a++) {
		ans += (n - 1) / a;
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3668
n, u, v = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
d1 = [-1] * n
d1[u - 1] = 0
s = [u - 1]
while s:
    d = s.pop()
    for node in g[d]:
        if d1[node] == -1:
            s.append(node)
            d1[node] = d1[d] + 1
d2 = [-1] * n
d2[v - 1] = 0
s = [v - 1]
while s:
    d = s.pop()
    for node in g[d]:
        if d2[node] == -1:
            s.append(node)
            d2[node] = d2[d] + 1
m = 0
mi = 0
for i in range(n):
    if d1[i] < d2[i]:
        if m < d2[i]:
            m = d2[i]
            mi = i
print(m - 1)


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

char C;

int main() {
    cin >> C;
    if (C == 'z') {
        cout << 'a' << endl;
    } else {
        cout << (char)(C + 1) << endl;
    }
}

Measured memory_bytes: 256
// AOJ 1241: Lagrange's Four-Square Theorem
// 2017.10.12 bal4u@uu

#include <stdio.h>
#include <math.h>

#define MAX 32768	// 2^15
int a[185];
char f1[34000];
char f2[34000], c2[34000][9], w2[34000];

int main()
{
	int n, i, j, k, s, sq, ans;

	sq = 1+(int)sqrt(MAX);
	for (i = 1; i <= sq; i++) a[i] = i*i, f1[a[i]] = 1;
	for (i = 1; i < sq; i++) for (j = i; j <= sq; j++) {
		if ((s = a[i]+a[j]) <= MAX) f2[s]++, c2[s][w2[s]++] = i;
	}

	while (scanf("%d", &n) && n > 0) {
		ans = f1[n] + f2[n]; sq = (int)sqrt(n);
		for (i = 1; i <= sq; i++) {
			s = n-a[i];
			if (f2[s]) for (k = 0; k < w2[s]; k++) if (c2[s][k] >= i) ans++;
			for (j = i; j <= sq; j++) {
				if ((s = n-a[i]-a[j]) <= 0) continue;
				if (f2[s]) for (k = 0; k < w2[s]; k++) if (c2[s][k] >= j) ans++;
			}
		}
		printf("%d\n", ans);	
	}
	return 0;
}

Measured memory_bytes: 2140
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr int inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
int main() {
    int n,a;cin >> n >> a;
    if(n%500>a)cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3476
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)

const LL MOD = 1000000007;
LL dp[100005];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	REP(i, m) {
		int a;
		scanf("%d", &a);
		dp[a] = -1;
	}
	dp[0] = 1;
	REP(i, n) {
		if (dp[i] == -1)continue;
		if (dp[i + 1] != -1)dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
		if (dp[i + 2] != -1)dp[i + 2] = (dp[i + 2] + dp[i]) % MOD;
	}
	printf("%lld\n", dp[n]);
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
class Main {
    public void kami() {
        		Scanner sc = new Scanner(System.in);
		double r = sc.nextDouble();
		double p = 3.141592653589;
		
		double r1 = r * r * p;
		double r2 = r * 2 * p;
		
		System.out.printf("%8.6f %8.6f \n", r1 , r2);

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

}

Measured memory_bytes: 19000
n,a,b = map(int,input().split())

def f(c,d):
  i = 1
  while d > 0:
    if d % 2 == 1:
      i *= c
      i = i % (10**9+7)  
    c *= c
    c = c % (10**9+7)
    d >>= 1
  return i

def p(c,d):
  i = 1
  for j in range(c,c-d,-1):
    i *= j
    i = i % (10**9+7)
  return i

A = p(n,a)*f(p(a,a),10**9+5) % (10**9+7)
B = p(n,b)*f(p(b,b),10**9+5) % (10**9+7)

print((f(2,n)-1-A-B) % (10**9+7))

Measured memory_bytes: 3064
import numpy as np

n, t = map(int, input().split())
a = []
b = []
for _ in range(n):
  a_tmp, b_tmp = map(int, input().split())
  a.append(a_tmp)
  b.append(b_tmp)
arg = np.argsort(a)
a = np.array(a)[arg]
b = np.array(b)[arg]
dp = np.zeros((n, t), dtype=np.int)
for i in range(n - 1):
  dp[i+1, :a[i]] = dp[i, :a[i]]
  dp[i+1, a[i]:] = np.maximum(dp[i, a[i]:], dp[i, :-a[i]] + b[i])
  
print(np.max(dp[:, -1] + b))

Measured memory_bytes: 82764
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from collections import deque
n,m = inm()
chi = [{} for i in range(n+1)]
par = [{} for i in range(n+1)]
for i in range(n-1+m):
    a,b = inm()
    chi[a][b] = 1
    par[b][a] = 1
dep = [0]*(n+1)
rpar = [0]*(n+1)
for i in range(1,n+1):
    if len(par[i])==0:
        root = i
        break
ddprint("chi")
ddprint(chi)
ddprint("par")
ddprint(par)
ddprint(root)
q = deque([root])
while len(q)>0:
    p = q.popleft()
    d = dep[p]
    for z in chi[p]:
        del par[z][p]
        #if dep[z]<d+1 and len(par[z])==0:
        if len(par[z])==0:
            dep[z] = d+1
            rpar[z] = p
            q.append(z)
for i in range(1,n+1):
    print(rpar[i])


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

int main() {
	int n;
	cin>>n;
	int x;
	vector<int>v(n);
	for(int i=0;i<n;i++){
		cin>>x;
		v[i] = x;
	}
	
	sort(v.begin(),v.end());
	int mid = (n-1)/2;
	int ans = v[mid+1] - v[mid];
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}

// oooooooooo
// xoxoxoxoxo


int main(){
  ll N,M; cin>>N>>M;
  string s,t; cin>>s>>t;
  ll L = lcm(N,M);
  bool ok = true;
  if(gcd(N,M)>1){
    ll nol = L/N;
    ll mol = L/M;
    for(ll i=0;i<L;++i){
      if(i%nol==0 && i%mol==0){
        ll idx_s = i/nol;
        ll idx_t = i/mol;
        if(s[idx_s]!=t[idx_t]){ ok = false; break;}
      }
    }
  }else{
    if(s[0]!=t[0]){ok=false;}
  }
  if(ok){ cout << L <<"\n";}
  else{ cout << "-1\n"; }
}

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

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

Measured memory_bytes: 4820
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;



int main(){

    ll n;
    cin >> n;
    ll res=0;
    for(int i=1; i<=n; i++){
        if(i%3!= 0 && i%5!= 0){
            res += i;
        }
    }
    cout << res << endl;
   

}

Measured memory_bytes: 3532
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ii pair<int, int>
#define iii tuple<int, int, int>
#define iiii tuple<int, int, int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define fi first
#define se second
#define eb emplace_back

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int M = 1 << 20, N = 51;
int n, m;
vi edge_bit(N), in(N);
vector<ii> edge_info(N);
vector<ll> dp(M);
vvi g(N);
map<ii, int> edge_pos;

int edge_set(int u, int e, int j) {
    if (u == e) return 1;
    if (in[u]) return 0;
    in[u] = 1;
    for (auto v : g[u]) {
        if (edge_set(v, e, j)) {
            if (u > v) swap(u, v);
            edge_bit[edge_pos[{u, v}]] |= (1 << j);
            return 1;
        }
    }
    return 0;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        g[u].eb(v);
        g[v].eb(u);
        edge_info[i] = {u, v};
        edge_pos[{u, v}] = i;
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        in.assign(N, 0);
        edge_set(u, v, i);
    }
    dp[0] = 1;
    for (int i = 1; i < n; ++i)
        for (int msk = (1 << m) - 1; msk >= 0; --msk)
            dp[msk | edge_bit[i]] += dp[msk];

    cout << dp[(1 << m) - 1] << '\n';
    // for (int i = 1; i < n; ++i)
    //     cout << edge_info[i].fi << ' ' << edge_info[i].se << ' ' <<
    //     edge_bit[i]
    //          << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // freopen("in", "r", stdin);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

Measured memory_bytes: 8448
n=int(input())
s=input()
num=[]
for i in range(1000):
    p=str(i)
    while len(p)<3:
        p="".join(["0",p])
    num.append(p)
ans=0
for k in range(len(num)):
    q=0
    for i in range(len(s)):
        if q==3:
            break
        elif num[k][q]==s[i]:
            q+=1
    if q==3:
        ans+=1
print(ans)


Measured memory_bytes: 41052
/// meowa 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7;
const int INF = 1e9 + 1e2;
  
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

void ma1n() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = max({b*d, a*d, b*c, a*c});
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    return 0;
}

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

def Selection_Sort(A,n):
    count = 0
    for i in range(n):
        mini = i
        for j in range(i,n): #i以上の要素において最小のAをminiに格納
            if A[j] < A[mini]:
                mini = j
        if A[i] != A[mini]:
            A[i], A[mini] = A[mini], A[i]
            count += 1
    return A, count

n = int(input())
numbers = list(map(int, input().split(" ")))

ans_list, count = Selection_Sort(numbers, n)
ans_list = map(str, ans_list)

print(" ".join(ans_list))
print(count)

Measured memory_bytes: 7740
/*
 KUNAL RAUT (ZUKONIT14)  :- "DO WHAT YOU LIKE!"
 -PICT,PUNE! :)
 */
#include<bits/stdc++.h>
using namespace std;
#define ll          unsigned long long
#define int         long long
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define fi          first
#define se          second
#define mod         1000000007
#define mod9        1000000009
#define pi          3.1415926535
#define MAXN        1000005
#define N           1000001
#define MAX2N       1*1000 + 10
#define all(v)      v.begin(), v.end()
#define allr(v)     v.rbegin(), v.rend()
#define ms(s, n)    memset(s, n, sizeof(s))
#define prec(n)     fixed<<setprecision(n)
#define forci(p,n)  for(ll i=p;i<(ll)n;i++)
#define forcj(p,n)  for(ll j=p;j<(ll)n;j++)
#define bolt        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a)     __builtin_popcount(a)
#define test        ll t;cin>>t;for(ll testi=1;testi<=t;testi++)
#define djokovic    freopen("input00.txt", "r", stdin);freopen("output00.txt", "w", stdout);

ll gcd(ll a, ll b)  {    if (b == 0) return a;    return gcd(b, a % b);}
ll lcm(ll a, ll b)  {    return (a / gcd(a, b) * b);}
ll expo(ll x, ll y) {
    ll res = 1; x = x % mod; while (y > 0) {
        if (y & 1)res = (1ll * res * x) % mod;
        y = y >> 1; x = (1ll * x * x) % mod;
    } return res;
}
ll ncr(ll n, ll r)  { ll res = 1; if (r > n - r)r = n - r; for (ll i = 0; i < r; i++) {  res *= n - i;  res /= i + 1; } return res;}
ll max(ll a, ll b)  {return (a > b) ? a : b;}
bool prime(ll n)    {ll i; for (i = 2; i <= sqrt(n); i++) {if (n % i == 0)return false;} return true;}
bool sortbysec(const pair<ll, ll> &a, const pair<ll, ll> &b)
{   if (a.second == b.second)
        return a.first < b.first;
    return (a.second < b.second);
}
//https://www.youtube.com/watch?v=WTJSt4wP2ME

// ll rr[] = {0, 1, 1, 1, 0, -1, -1, -1};
// ll cc[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll n, k, m, q, ans, a[MAXN], ans1[MAXN]; vector<ll>v;
void solve()
{
    string s;cin>>s;
    if(s[1]=='B')cout<<"ARC\n";
    else    cout<<"ABC\n";
}
signed main()
{
    bolt;
	solve();
}




Measured memory_bytes: 3632
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int a;
    int b;
    cin >> a >> b;
    for(int i = 0; i < 1010; i++){
        double result1 = i * 0.08;
        double result2 = i * 0.1;
        if(floor(result1) == a && floor(result2) == b){
            cout << i << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
}

Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		Map<String, Deque<String>> deq = new HashMap<>();
		String[] participants = new String[] {"a", "b", "c"};
		for (int i = 0; i < 3; i++) {
			String s = sc.next();
			deq.put(participants[i], new ArrayDeque<>());
			for (int j = 0; j < s.length(); j++) {
				deq.get(participants[i]).addLast(s.charAt(j) + "");
			}
		}
		String prev = participants[0];
		while (true) {
			if (deq.get(prev).size() == 0) {
				System.out.println(prev.toUpperCase());
				return;
			}
			prev = deq.get(prev).pollFirst();
		}
	}
}

Measured memory_bytes: 21844
N = int(raw_input())
H = []
 
for _ in xrange(N):
    a, b, c = map(int, raw_input().split())
    H.append([a, b, c])
 
dp = [[0]*3 for __ in xrange(N)]
 
for i in xrange(0, N):
    for j in xrange(3):
        if i==0:
            dp[i][j] = H[0][j]
        else:
            dp[i][j] = max(dp[i-1][j-1]+H[i][j], dp[i-1][j-2]+H[i][j])
 
print max(dp[N-1])

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

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

using namespace std;

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 S;

int main() {
    cin >> S;
    int h = S / (60 * 60);
    int m = S / 60 % 60;
    int s = S % 60;
    printf("%d:%d:%d\n", h, m, s);
}



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

int main()
{
    string o,e;
    cin>>o>>e;
    for(int i=0;i<o.size();i++){
        if(o.size()>e.size() && i==o.size()-1) cout<<o[i];
        else cout<<o[i]<<e[i];
        
    }
}

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

int main()
{
	int n;

	while (1) {
		cin >> n;
		
		if (n == 0)
			break;

		int s[n] = {0};
		double m = 0.0;
		int sum_s = 0;

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

		m = sum_s/double(n);

		
		double a = 0;
		double a2 = 0.0;

		for (int i=0; i<n; i++) {
			a += (s[i]-m) * (s[i]-m);
		}

		a2 = sqrt(a/double(n));

		cout << fixed << setprecision(8) << a2 << '\n';
	}


	return 0;
}


Measured memory_bytes: 3256