akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define N 100000
#define T 50000

main()
{

  int i,j;
  int A[N],B[T];
  int n,t,left,right,mid,key=0,count=0;
  
  scanf("%d",&n);
  
  for(i = 0; i < n; i++){
    scanf("%d",&A[i]);
  }

  scanf("%d",&t);
  
  for(j = 0; j < t; j++){
    scanf("%d",&B[j]);
    left = 0;
    right = n;
    
    while(left < right){
      mid = (left + right)/2;
      
      if(B[j] == A[mid]){
	count++;
	break;
      }
      
      if(B[j] > A[mid]){
	left = mid + 1;
      }
      
      else if(B[j] < A[mid]){
	right = mid;
      }
    }
    
    
    
    
  }
  
  
  
  printf("%d\n",count);

  return 0;
  
}

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



int main(){
  vector<int64_t> v={2,1};
  int N;
  cin >> N;
  for (int i=0;i<N-1;i++){
    v.push_back(v.at(v.size()-1)+v.at(v.size()-2));
  }
  cout << v.at(N) << endl;
}
  

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int who[2];

int compar(const int *val1,const int *val2){
	if(*val1<*val2){
		return -1;
	}
	else if(*val1== *val2){
		return 0;
	}
	else{
		return 1;
	}
}

void detect(const int *pnt) {
	int i = 1, j = 0;
	int count = 0;
	while (1) {
		if (i != pnt[j]) {
			who[count] = i;
			count++;
			i++;
			if (count == 2) {
				break;
			}
		}
		else {
			i++;
			j++;
		}
	}
}
int main(void) {
	int stdntID[28];
	int i,j;
	for (i = 0; i<28; i++) {
		scanf("%d", &stdntID[i]);
	}
	qsort(stdntID,28,sizeof(int),compar);
	detect(stdntID);
	printf("%d\n", who[0]);
	printf("%d\n", who[1]);
	return 0;
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    string s;
    cin >> s;
    cout << s[0] - '0' + s[1] - '0' + s[2] - '0' << endl;
    return 0;
}

Measured memory_bytes: 256
#-*- coding: utf-8 -*-
# O(log(n)) + O(n+q) = O(n)
def get_set3(S:list, T:list):
    D:dict = {}
    C = []
    for s in S:
        D[s] = 1
    for t in T:
        if t in D.keys() and D[t] == 1:
            D[t] = 2
            C.append(t)
    return C

def input_array():
    n = int(input())
    S = list(map(int, input().split()))
    return S


if __name__ == '__main__':
    S = input_array()
    T = input_array()
    ret = get_set3(S, T)
    print(len(set(ret)))



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

#define ff              first
#define ss              second
#define int             long long
#define endl            '\n'
#define pb              push_back
#define mp              make_pair
#define pr              pair<int,int>
#define vc              vector<int>
#define ma              map<int,int>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(t)            int t; cin>>t; while(t--)




void fast_bhati()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

}

int sumOfDigits(int n){
    int s = 0;
    while(n!=0){
        s=s+n%10;
        n=n/10;
    }
    return s;
}
void solve(){



}
int32_t main()
{
    fast_bhati();
    int n;
    cin>>n;
    if(n==0){
        cout<<1;
    }
    if(n==1){
        cout<<0;
    }
//    int t;
//    cin>>t;
//    while(t--)
//    {
//        solve();
//        if(t!=0){
//            cout<<endl;
//        }
//    }

    return 0;
}




Measured memory_bytes: 3608
N, K = map(int, input().split())
A = list(map(int, input().split()))

dp = [False] * (10 ** 5 + 10)
for i in range(1, K+1):
    # dp[i-a]の中でどこか一つでもFalseになるdp[i]があればTrueを設定する
    # dp[i-a]がFalseということは、次の手番の相手を負かす取り方が存在するということになるので、この手番でa個取って相手の順番に回してしまえば勝ちが確定する
    # お互いが交互に数字を言っていって、最後に30を言ったほうの負け（最大+3）まで
    # みたいなゲームと同じ構造だと考えていい。上記のゲームで勝つには最後の数から逆算していけば、勝てる数字がわかるのと似ている
    dp[i] = not all(dp[i-a] if i-a >= 0 else True for a in A)

print("First" if dp[K] else "Second")



Measured memory_bytes: 43228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,b,c;
    cin >> a >> b >> c;

    if (b-a==c-b)
    {
      cout << "YES" << endl;
    }
    else
    {
      cout << "NO" << endl;
    }
}


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

struct edge{
    int to,weight;
    edge(int to,int weight):to(to),weight(weight){}
};
using Graph = vector<vector<int>> ;
using GraphEdge = vector<vector<int>> ;

long long modinv(long long a, long long m=MOD) {
    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;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
const int MAXN = 200001;
int A[MAXN];
int main(){
    int N;cin >> N;
    

    rep(i,N){
        cin >>A[i];
    }
    ll ans = 0;
    rep(i,N-1){
        if(A[i]>A[i+1]){
            ans += A[i] - A[i+1];
            A[i+1] = A[i];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4412
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int a;
  	int b[200];
  	int ans = 0;
  	cin >> a;
 	  	while(1){
  			for(int i = 0; i < a; ++i){
      			cin >> b[i];
     			 if(b[i] % 2 != 0){
                   cout << ans << endl;
                   return 0;
                 }
              	else b[i] /= 2;
   			 }
            ans++;
          }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
struct Node{
	int a,b;
}k[100001];
bool cmp(Node x,Node y)
{
	return x.a<y.a;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
    	cin>>k[i].a;
    	k[i].b=i+1;
	}
	sort(k,k+n,cmp);
    for(int i=0;i<n;i++)cout<<k[i].b<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 1536
using System;

namespace TestSpace
{
    class Test
    {
        static void Main(string[] args)
        {
            int S,h,m,s;
            S = int.Parse(Console.ReadLine());
            h = S / 3600;
            s = S % 3600;
            m = s / 60;
            s = s % 60;

            Console.WriteLine("{0}:{1}:{2}", h,m,s);
        }
    }
}



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

int main() {
  int A,N,a;
  cin >> N >> A;
  a=N%500;
  if(a>A)
    cout << "No" << endl;
  else if(a<=A)
    cout << "Yes" << endl;
  // ここにプログラムを追記
}

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

struct crd{
  int x;
  int y;
};
int main(){
  crd p,z {0,0};
  int n;
  cin >> p.x >> p.y >> n;
  
  for(int i=0;i<n;++i){
    int x,y,a;
    cin >> x >> y >> a;
    switch(a){
      case 1:
      if(z.x<x) z.x=x;
      break;
      
      case 2:
      if(p.x>x) p.x=x;
      break;

      case 3:
      if(z.y<y) z.y=y;
      break;
      
      case 4:
      if(p.y>y) p.y=y;
      break;

    }
  }
  auto out=(p.x-z.x)*(p.y-z.y);
  if(p.x<z.x || p.y<z.y) out=0;
  cout << out << endl;

  return 0;
}

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

public class Main {
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    int N = Integer.parseInt(sc.next());
    int M = Integer.parseInt(sc.next());
    
    if (M < N - 1) {
      System.out.println(0);
      return;
    }
    
    int a[] = new int[M];
    int b[] = new int[M];
    for (int i = 0; i < M; i++) {
      a[i] = Integer.parseInt(sc.next());
      b[i] = Integer.parseInt(sc.next());
    }
    boolean ok[][] = new boolean[N][N];
    for (int i = 0; i < M; i++) {
      ok[a[i] - 1][b[i] - 1] = true;
      ok[b[i] - 1][a[i] - 1] = true;
    }
    
    int ans = 0;
    
    Deque<state> stack = new ArrayDeque<state>();
    boolean flag[] = new boolean[N];
    int count = N;
    stack.addLast(new state(0, flag, count));
    while (!stack.isEmpty()) {
      state now = stack.removeLast();
      now.flag[now.num] = true;
      if (--now.left == 0) {
        ans++;
        continue;
      }
      for (int i = 0; i < N; i++) {
        if (ok[now.num][i] && !now.flag[i]) {
          stack.addLast(new state(i, now.flag, now.left));
        }
      }
    }
    System.out.println(ans);
  }
  
  public static class state {
    public int     num;
    public boolean flag[];
    public int     left;
    
    public state(int x, boolean list[], int count) {
      num = x;
      flag = list.clone();
      left = count;
    }
  }
}

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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define PB push_back
#define F first
#define S second

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

const int MOD = 1e9+7;

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

	string s; cin >> s;
	int c = s.back()-'0';
	if(c == 2 || c == 4 || c == 5 || c == 7 || c == 9)
		cout << "hon\n";
	else if(c == 0 || c == 1 || c== 6 || c == 8)
		cout << "pon\n";
	else
		cout << "bon\n";

 	return 0;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int N;
  int sum = 0;

  cin >> N;
  vector<int> d(N);
  for(int i=0; i<N; i++){
    cin >> d[i];
  }
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      sum += d[i] * d[j];
    }
  }
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;

int main() {
    ll n, m;cin >> n >> m;
    ll k;cin >> k;
    ll A[n+1], B[m+1];
    A[0] = 0, B[0] = 0;
    for(int i=0; i<n; i++)cin >> A[i+1];
    for(int i=0; i<m; i++)cin >> B[i+1];

    ll maxA = n;
    for (int i = 1; i <= n; i++)A[i] += A[i-1];
    for (int i = 1; i <= m; i++)B[i] += B[i-1];

    ll cnt_b = m;
    ll ans = 0;
    for (ll cnt_a = 0; cnt_a <= n; cnt_a++)
    {
        if(A[cnt_a] > k)break;
        while(A[cnt_a] + B[cnt_b] > k && cnt_b >= 0)cnt_b--;
        ans = max(ans, cnt_a + cnt_b);
    }
    
    cout << ans << endl;





    // for (int i = 2; i <= m; i++)sumB[i] = sumB[i-1] + B[i];

    // int j = 0;

    // ll ans = maxA;
    // for (int i = maxA; i >= 0; i++)
    // {
    //     while(sumA[i] + sumB[j] <= k && j<m)j++;
    //     if(sumA[i] + sumB[j] > k)j--;
    //     ans = max(ans, (ll)(i+j));
    // }
    
    // cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 6660
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1<<30;
int MOD=10007;
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	string q="JOI";
	int dp[1010][8]={0};
	dp[0][1]=1;
	rep(i,n)loop(j,1,8)if(dp[i][j])loop(k,1,8){//rep(j,3)loop(k,1,8)rep(l,3){
		bool h=true;
//		if((k&1<<j)==0||(k&1<<l)==0)h=false;
		if((j&k)==0)h=false;
		rep(w,3)if(s[i]==q[w]&&(k&1<<w)==0)h=false;
		if(!h)continue;
		dp[i+1][k]=(dp[i+1][k]+dp[i][j])%MOD;
	}
	int out=0;
	rep(i,8)out=(out+dp[n][i])%MOD;
	cout<<out<<endl;
}

Measured memory_bytes: 1252
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    public class Code6
    {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();

            Console.WriteLine(funcMain(s1));
        }

        static public string funcMain(string arg1)
        {
            string[] s = arg1.Split();
            int N, M;
            int ret = 0;

            N = int.Parse(s[0]);
            M = int.Parse(s[1]);

            var OnceTime = (N - M) * 100 + M * 1900;
            var Times = (int)Math.Pow(2,M);
            ret = OnceTime * Times;

            return ret.ToString();
        }
    }
}


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


int o = 0, t = 0;
vector<vector<int>> g;
vector<int> lvl;

void dfs(int u, int p) {
  lvl[u] = 3 - lvl[p];
  if (lvl[u] == 1) o++;
  else t++;

  for (auto v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
}

int main() {

  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  int n;
  cin >> n;

  g.resize(n);
  lvl.resize(n);

  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;

    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  lvl[0] = 1;
  dfs(0, 0);
  int ro = n / 3 + (n%3 >= 1);
  int rt = n / 3 + (n%3 >= 2);

  if (min(o, t) <= n / 3) {
    int x = (o <= n/3) ? 1 : 2;
    int p3 = 3, cnt = n/3 - min(o, t);
    for (int i = 0; i < n; ++i) {
      if (lvl[i] == x) {
        lvl[i] = p3;
        p3 += 3;
      } else lvl[i] = -1;
    }
    for (int i = 0; i < n && cnt > 0; ++i) {
      if (lvl[i] == -1) {
        lvl[i] = p3;
        p3 += 3;
        cnt--;
      }
    }
    int j = 1;
    for (int i = 0; i < n; ++i) {
      if (lvl[i] == -1) {
        lvl[i] = j++;
      }
      if (j % 3 == 0) ++j;
    }
  } else {
   int p1 = 1, p2 = 2, p3 = 3; 
    for (int i = 0; i < n; ++i) {
      if (lvl[i] == 1 && o > ro) {
        lvl[i] = 0;
        o--;
      } else if (lvl[i] == 2 && t > rt) {
        lvl[i] = 0;
        t--;
      }

      if (lvl[i] == 0) {
        lvl[i] = p3;
        p3 += 3;
      } else if (lvl[i] == 1) {
        lvl[i] = p1;
        p1 += 3;
      } else {
        lvl[i] = p2;
        p2 += 3;
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    cout << lvl[i] << " ";
  }
  cout << '\n';

}


Measured memory_bytes: 17280
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    cost = [list(map(int, input().split())) for _ in range(10)]
    grid = [list(map(int, input().split())) for _ in range(H)]

    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    res = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == -1 or grid[h][w] == 1:
                continue
            num = grid[h][w]
            res += cost[num][1]
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9476
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
      n: usize,
      m: usize,
    }
    if n == 1 && m == 1 {
        println!("{}", 1);
    } else if n == 1 || m == 1 {
        println!("{}", n + m - 3);
    } else {
        println!("{}", (n - 2) * (m - 2));
    }
}


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

#define REP(i, n) for(decltype(n) i = 0; i < n; i++)

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

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

    int N;
    std::cin >> N;

    REP(i, 9) {
        int num = (i + 1) * 100 + (i + 1) * 10 + (i + 1);
        if(N <= num) {
            std::cout << num << std::endl;
            break;
        }
    }

    return 0;
}


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

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<long long>; using vvll = vector<vll>;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> istream &operator>>(istream &, vector<T> &);
template <class T> ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U> istream &operator>>(istream &, pair<T, U> &);
template <class T, class U> ostream &operator<<(ostream &, const pair<T, U> &);
template <class T> struct Inf { static constexpr T inf() { return std::numeric_limits<T>::has_infinity ? std::numeric_limits<T>::infinity() : std::numeric_limits<T>::max(); } };
template <> struct Inf<int> { static constexpr int inf() { return 0x3f3f3f3f; } };
template <> struct Inf<long long> { static constexpr long long inf() { return 0x3f3f3f3f3f3f3f3fLL; } };
constexpr int INF = Inf<int>::inf(); constexpr ll BINF = Inf<ll>::inf();
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}
// Preprocessing & "Global" variables {{{
struct Solver {
	Solver() {}
	int solve();
};
// }}}

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

// Template Main {{{
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	Solver solver;
	#ifdef JUDGE_MULTI_CASE
		int t; cin >> t; for (int i = 1; i <= t; i++)
	#endif
	solver.solve();
	// cout << "Case #" << i << ": ", solve();
	return 0;
}

template <class T> istream &operator>>(istream &is, vector<T> &v) {
	for (auto it=v.begin();it!=v.end();++it) is >> *it;
	return is;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	for (auto it=v.begin();it!=v.end();) os << *it, os << " \n"[++it==v.end()];
	return os;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
	return is >> p.first >> p.second;
}

template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << p.first << ' ' << p.second;
}
// }}}

// vim: fdm=marker


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////


#define INF 1e12

ll N, M, A[1010], B[1010], C[1010];
ll bdp[1<<15];
vector<ll> prs;
ll i, j, k,ans;


int main(){
    scanf("%lld%lld", &N, &M);
    fornum(i,0,M){
        scanf("%lld%lld", &A[i], &B[i]);
        fornum(j,0,B[i]){
            ll c;
            scanf("%lld", &c);
            C[i] |= 1 << (c-1);
        }
    }
    fornum(i,0,1<<N){
        bdp[i] = INF;
    }
    bdp[0] = 0;
    fornum(i,0,M){
        fornum(j,0,1<<N){
            ll bj = C[i] | j;
            ll a = A[i] + bdp[j];
            bdp[bj] = min(bdp[bj], a);
        }
    }
    ll ans = bdp[(1 << N) - 1];
    if(ans==INF){
        printf("-1");
    }else{
        printf("%lld", ans);
    }
    
    return 0;
}

Measured memory_bytes: 256
def main():
    a1_lis = list(map(int, input().split()))
    a2_lis = list(map(int, input().split()))
    a3_lis = list(map(int, input().split()))

    n = int(input())
    b_lis = []
    for _ in range(n):
        b_lis.append(int(input()))
    
    if a1_lis[0] in b_lis and a1_lis[1] in b_lis and a1_lis[2] in b_lis:
        print('Yes')
        exit()
    if a2_lis[0] in b_lis and a2_lis[1] in b_lis and a2_lis[2] in b_lis:
        print('Yes')
        exit()
    if a3_lis[0] in b_lis and a3_lis[1] in b_lis and a3_lis[2] in b_lis:
        print('Yes')
        exit()
    if a1_lis[0] in b_lis and a2_lis[0] in b_lis and a3_lis[0] in b_lis:
        print('Yes')
        exit()
    if a1_lis[1] in b_lis and a2_lis[1] in b_lis and a3_lis[1] in b_lis:
        print('Yes')
        exit()
    if a1_lis[2] in b_lis and a2_lis[2] in b_lis and a3_lis[2] in b_lis:
        print('Yes')
        exit()



    if a1_lis[0] in b_lis and a2_lis[1] in b_lis and a3_lis[2] in b_lis:
        print('Yes')
        exit()
    
    if a3_lis[0] in b_lis and a2_lis[1] in b_lis and a1_lis[2] in b_lis:
        print('Yes')
        exit()
    else:
        print("No")
        


    


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
using System;
class Program{
	public static void Main(){
		string str = Console.ReadLine();
		int N = int.Parse(str);
		double sum = 0;
		for (int i = 0 ;i < str.Length ;i++ ){
			sum += Char.GetNumericValue(str[i]);
		}
		if (N % (int)sum == 0)
			Console.WriteLine("Yes");
		else
			Console.WriteLine("No");
	}
}

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

using namespace std;
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define Cor(i,l,r) for (int i = l; i >= r; --i)

int find(int *fa, long long *d, int x) {
	if (fa[x] == 0) return x;
	int res = find(fa, d, fa[x]);
	d[x] += d[fa[x]];
	return fa[x] = res;
}

bool no_sol = false ;

bool uni(int *fa, long long *d, int x, int y, int g) {
	//printf("%d %d %d\n", x, y, g);
	int p = find(fa, d, x), q = find(fa, d, y);	
	if (p == q) {
		if (d[x] - d[y] != g) {
			no_sol = true;
		}
		return false ;
	}
	fa[p] = q; d[p] = g - d[x] + d[y];
}

int far[111111], fac[111111], val[111111];
vector<int> vecR[111111], vecC[111111];
long long dr[111111], dc[111111], minval_r[111111], minval_c[111111];
int R, C, n;
pair<int,int> A[111111];
int main() {
	cin >> R >> C >> n;
	For(i,1,n) {
		scanf("%d%d%d", &A[i].first, &A[i].second, &val[i]);
		vecR[A[i].first].push_back(i);
		vecC[A[i].second].push_back(i);
	}
	
	For(i,1,R) if (vecR[i].size() >= 2) {
		for (int j = 1; j < vecR[i].size(); ++j) {
			uni(far, dr, A[vecR[i][j - 1]].second, A[vecR[i][j]].second, val[vecR[i][j - 1]] - val[vecR[i][j]]);
		}
	}
	For(i,1,C) if (vecC[i].size() >= 2) {
		for (int j = 1; j < vecC[i].size(); ++j) {
			uni(fac, dc, A[vecC[i][j - 1]].first, A[vecC[i][j]].first, val[vecC[i][j - 1]] - val[vecC[i][j]]);
		}
	}
	
	For(i,1,C) {
		int t = find(far, dr, i);
		minval_r[t] = min(minval_r[t], dr[i]);
	}
	
	For(i,1,R) {
		int t = find(fac, dc, i);
		minval_c[t] = min(minval_c[t], dc[i]);
	}
	
	For(i,1,n) {
		int r = A[i].first, c = A[i].second;
		if (val[i] < dr[c] - minval_r[find(far, dr, c)] + dc[r] - minval_c[find(fac, dc, r)]) no_sol = true;
	}
	
	if (no_sol) puts("No"); else puts("Yes");
	return 0;
}

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max(0, min(b, d) - max(a, c)) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define pb(a) push_back(a)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main(){
	int t;
	int min=10;
	int res=0;
	REP(i,5){
		cin >>t;
		int one = t-floor(t/10.0)*10;
		if(one<min && one!=0) min = one;
		t = ceil(t/10.0)*10;
		res += t;
	}
	
	cout << res-10+min <<endl;	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point {
public:
	double x, y;
	Point(double x = 0.0, double y = 0.0) :
			x(x), y(y) {
	}

	Point operator +(Point p) {
		return Point(x + p.x, y + p.y);
	}
	Point operator -(Point p) {
		return Point(x - p.x, y - p.y);
	}
	Point operator *(double k) {
		return Point(x * k, y * k);
	}
	Point operator /(double k) {
		return Point(x / k, y / k);
	}

	double norm() {
		return x * x + y * y;
	}
	double abs() {
		return sqrt(norm());
	}

	bool operator <(Point p) {
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator ==(Point p) {
		return equals(x, p.x) && equals(y, p.y);
	}
};
typedef Point Vector;

class Segment {
public:
	Point p1, p2;
	Segment(Point p1 = Point(), Point p2 = Point()) :
			p1(p1), p2(p2) {
	}
};
typedef Segment Line;

double dot(Vector v1, Vector v2) {
	return v1.x * v2.x + v1.y * v2.y;
}
double cross(Vector v1, Vector v2) {
	return v1.x * v2.y - v1.y * v2.x;
}
bool isOrthogonal(Vector v1, Vector v2) {
	return equals(dot(v1, v2), 0.0);
}
bool isOrthogonal(Segment s1, Segment s2) {
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}
bool isOrthogonal(Point l1, Point l2, Point m1, Point m2) {
	return isOrthogonal(l2 - l1, m2 - m1);
}
bool isParallel(Vector v1, Vector v2) {
	return equals(cross(v1, v2), 0.0);
}
bool isParallel(Segment s1, Segment s2) {
	return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}
bool isParallel(Point l1, Point l2, Point m1, Point m2) {
	return isParallel(l1 - l2, m1 - m2);
}

enum PositionSP {
	COUNTER_CLOCKWISE = -1,
	CLOCKWISE = 1,
	ONLINE_BACK = 2,
	ONLINE_FRONT = -2,
	ON_SEGMENT = 0
};
PositionSP ccw(Point p1, Point p2, Point p) {
	Vector a = p2 - p1, b = p - p1;
	if (cross(a, b) > EPS)
		return COUNTER_CLOCKWISE;
	else if (cross(a, b) < -EPS)
		return CLOCKWISE;
	else if (dot(a, b) < -EPS)
		return ONLINE_BACK;
	else if (a.norm() < b.norm())
		return ONLINE_FRONT;
	else
		return ON_SEGMENT;
}
bool intersect(Point p1, Point p2, Point p3, Point p4) {
	return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0
			&& ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}
bool intersect(Segment s1, Segment s2) {
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

double distancePP(Point p1, Point p2) {
	return (p1 - p2).abs();
}
double distanceLP(Line l, Point p) {
	return abs(cross(l.p2 - l.p1, p - l.p1) / distancePP(l.p2, l.p1));
}
double distanceSP(Segment s, Point p) {
	if (dot(s.p2 - s.p1, p - s.p1) < 0.0)
		return distancePP(s.p1, p);
	else if (dot(s.p1 - s.p2, p - s.p2) < 0.0)
		return distancePP(s.p2, p);
	else
		return distanceLP(s, p);
}
double distanceSS(Segment s1, Segment s2) {
	if (intersect(s1, s2))
		return 0.0;
	else {
		return min(min(distanceSP(s1, s2.p1), distanceSP(s1, s2.p2)),
				min(distanceSP(s2, s1.p1), distanceSP(s2, s1.p2)));
	}
}

int main() {
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		Segment s1, s2;
		cin >> s1.p1.x >> s1.p1.y;
		cin >> s1.p2.x >> s1.p2.y;
		cin >> s2.p1.x >> s2.p1.y;
		cin >> s2.p2.x >> s2.p2.y;
		cout << fixed << setprecision(10) << distanceSS(s1, s2) << endl;
	}
	return 0;
}



Measured memory_bytes: 3280
import sys

n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]
time = 0
ab.sort(key=lambda x: x[1])
for i in ab:
  if time + i[0] > i[1]:
    print("No")
    sys.exit()
  else:
    time += i[0]
print("Yes")

Measured memory_bytes: 47084
#include <iostream>
#include<cstring>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
    int n,k,x,y,a;
    cin>>n>>k>>x>>y;
    if(n<=k)
    {
      a=n*x;
    }
    else
        a=k*x+(n-k)*y;
    cout<<a<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

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

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

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

//begin
template <class T>
class SqrtDecompositionRangeAddRangeSum
{
  private:
    int N, K;
    int sqrtN;
    vector<T> data;
    vector<T> bucket_sum;
    vector<T> bucket_add;
  public:
    SqrtDecompositionRangeAddRangeSum(int n) : N(n)
    {
        sqrtN = 320;
        K = (N + sqrtN - 1) / sqrtN;
        data.assign(K * sqrtN, 0);
        bucket_sum.assign(K, 0);
        bucket_add.assign(K, 0);
    }
    // [s, t)
    void add(int s, int t, T x)
    {
        int p = s / sqrtN;
        int q = t / sqrtN;
        for (int k = p; k <= q; ++k)
        {
            int l = k * sqrtN, r = (k + 1) * sqrtN;
            if (r <= s || t <= l)
                continue;
            if (s <= l && r <= t)
            {
                bucket_add[k] += x;
            }
            else
            {
                for (int i = max(s, l); i < min(t, r); ++i)
                {
                    data[i] += x;
                    bucket_sum[k] += x;
                }
            }
        }
    }
    // [s, t)
    T get_sum(int s, int t)
    {
        int p = s / sqrtN;
        int q = t / sqrtN;
        T sum = 0;
        for (int k = p; k <= q; ++k)
        {
            int l = k * sqrtN, r = (k + 1) * sqrtN;
            if (r <= s || t <= l)
                continue;
            if (s <= l && r <= t)
            {
                sum += bucket_sum[k] + bucket_add[k] * sqrtN;
            }
            else
            {
                for (int i = max(s, l); i < min(t, r); ++i)
                {
                    sum += data[i] + bucket_add[k];
                }
            }
        }
        return sum;
    }
    T get_value(int i)
    {
        int k = i / sqrtN;
        return data[i] + bucket_add[k];
    }
};
//end
signed main()
{
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    SqrtDecompositionRangeAddRangeSum<ll> decomp(N);
    while (Q--)
    {
        int c;
        cin >> c;
        if (c == 0)
        {
            int s, t, x;
            cin >> s >> t >> x;
            decomp.add(s, t + 1, (long long)x);
        }
        else
        {
            int s, t;
            cin >> s >> t;
            cout << decomp.get_sum(s, t + 1) << endl;
        }
    }
}

Measured memory_bytes: 3588
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
	      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        while(true) {
	            String[] line = br.readLine().split(" ");
	            int a = Integer.parseInt(line[0]);
	            int b = Integer.parseInt(line[2]);
	             
	            if(line[1].equals("+")) System.out.println(a + b);
	            else if(line[1].equals("-")) System.out.println(a - b);
	            else if(line[1].equals("*")) System.out.println(a * b);
	            else if(line[1].equals("/")) System.out.println(a / b);
	            else break;
	        }
	         
	    }
}

Measured memory_bytes: 24248
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
#define dame { printf("No\n"); return 0;}
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)


signed main(){
    int n,k;
    cin >> n;
    cin >> k;
    int A[n];
    REP(i,n) scanf("%lld",&A[i]);
    int asum = 0;
    REP(i,n) asum += max(llong(0),A[i]);

    int pos = 0,neg = 0;
    REP(i,k){
        if(A[i] > 0) pos += A[i];
        else neg -= A[i];
    }
    int tmp = min(pos,neg);
  
    FOR(i,k,n){
        if(A[i] > 0) pos += A[i];
        else neg -= A[i];

        if(A[i-k] > 0) pos -= A[i-k];
        else neg += A[i-k];
        int tmpp = min(pos,neg);
        tmp = min(tmp,tmpp);

    }

    cout << asum - tmp << endl;

}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int         long long
#define mod         1000000007
#define FAST        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define f(i,n)      for(int i=0;i<n;i++)
#define fp(i,k,n)   for(int i=k;i<=n;i++)
#define fr(i,k,n)   for(int i=k;i>=n;i--)
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define dbg(x)      cout << (#x) << " is " << (x) << '\n' 
#define F           first
#define S           second
#define sz(x)       (int)(x).size()
#define lb          lower_bound
#define ub          upper_bound
#define mems(x)     memset(x,0,sizeof(x))
#define all(a)      a.begin(),a.end()
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
/*---------------------------------------------------------------------------------------------------*/

void solve()
{
  int l,r,d,cnt=0;
  cin >> l >> r >> d;
  fp(i,l,r)
  {
      if(i%d==0)
        cnt++;
  }
  cout << cnt << '\n';
  return;
} 

signed main()
{
  FAST
  int T=1;
//   cin >> T;
  while(T--)
  {
    solve();
  }
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pi 3.141592653589793238462643383
bool  vis[300005];
int main() {
     ios::sync_with_stdio(false);
  cin.tie(0);
double a,b,h,m;
cin>>a>>b>>h>>m;

	double r1=(6*m)*(pi/180.0);
	double r2=(30*h+0.5*m)*(pi/180.0);
double rad=abs(r2-r1);

	double ans=sqrt((a*a)+(b*b)-(2*a*b*cos(rad)));
	cout<<fixed<<setprecision(20)<<ans<<endl;
}
	
	



Measured memory_bytes: 4140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(obj) (obj).begin, (obj).end()

int main() {
  ll N, K;
  cin >> N >> K;
  vector<ll> A(N);

  ll minA = N+1;

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

  while(K>0){
    minA = N+1;

    vector<ll> B(N,0);
    for (int j=0; j<N; j++){
      if (j-A[j] < 0){
        B[0]+=1;
      }else{
        B[j-A[j]] += 1;
      }

      if (j+A[j]< N-1){
        B[j+A[j]+1] -= 1;
      }
    }

    A[0] = B[0];
    minA = min(minA, A[0]);
    for (int j=1; j<N; j++){
      A[j] = A[j-1] + B[j];
      minA = min(minA, A[j]);
    }
    if (minA == N){
      for (int j=0; j<N; j++){
        cout << N << " ";
      }
      return 0;
    }
  
  K-=1;
  }



  for (int j=0; j<N; j++){
    cout << A[j] << " ";
  }
}


Measured memory_bytes: 6424
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1010][1010];
int main(){string a,b;cin>>a>>b;
int A=a.size(),B=b.size();
for(int i=0;i<=A;i++)dp[i][0]=i;
for(int i=0;i<=B;i++)dp[0][i]=i;
for(int i=1;i<=A;i++){
for(int j=1;j<=B;j++){
int q=1;if(a[i-1]==b[j-1])q = 0;
dp[i][j]=min(min(dp[i-1][j-1]+q,dp[i][j-1]+1),dp[i-1][j]+1);}}
cout<<dp[A][B]<<endl;return 0;}

Measured memory_bytes: 7120
#include <iostream>
#include <iomanip>

typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for(ll i=init;i<(n);i++)

ll gcd(ll a, ll b) {
    if (b > a)swap(a, b);
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll cd = gcd(c, d);
    cout << b - (a - 1)
            - b / c + (a - 1) / c
            - b / d + (a - 1) / d
            + b / (c * d / cd)
            - (a - 1) / (c * d / cd) << endl;
    return 0;
}


Measured memory_bytes: 3588
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using PLL = pair<LL,LL>;
using VPI = vector<PII>;
using VPL = vector<PLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define RREP(i,m,n) for(int i=(m);i>=(n);i--)
#define all(v) v.begin(), v.end()

int main(){
  int n,m;
  cin >> n >> m;
  VI a(m),b(m);
  REP(i,0,m){
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
  }
  dsu d(n);
  REP(i,0,m){
    d.merge(a[i],b[i]);
  }
  
  cout << (d.groups().size())-1 << endl;
  
  return 0;
}


Measured memory_bytes: 11752
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int d = sc.nextInt();
    int x[][] = new int[n][d];
    int dist2 =0;
    int answer =0;
    for(int i=0;i<n;i++){
      for(int j=0;j<d;j++){
        x[i][j]=sc.nextInt();
      }
    }
    
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        dist2=0;
        for(int k=0;k<d;k++){
          dist2 = dist2+(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
        }
        if(isSq(dist2)){
          answer = answer+1;
        }
      }
    }
        
    System.out.println(answer);
       
  }
  
  public static boolean isSq(int N){
    for(int i=0;i<=N;i++){
      if(i*i==N){
        return true;
      }
    }
    return false;
  }
  

  
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll INF=1e18;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
    //a^tを求める
    //例：d[i] = mint(k/i).pow(n);
    //mint(2).pow(n); 2^n
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[2005][2005];
mint S[2005][2005];

int main() {
  ll n,m;
  cin >> n>>m;
  vector<ll> s(n);
  vector<ll> t(m);

  rep(i,n)cin>>s[i];
  rep(i,m)cin>>t[i];
  rep(i,2005)rep(j,2005)dp[i][j]=0;
  rep(i,2005)rep(j,2005)S[i][j]=0;
/*
  rep(i,2005){
    dp[0][i]=1;
    dp[i][0]=1;
    S[i][0]=1;
  S[0][i]=1;
  }
*/
  rep(i,n)rep(j,m){
  //  cout<<"i"<<i<<"j"<<j<<endl;
    if(s[i]==t[j]){
      dp[i+1][j+1]=S[i][j]+1;
    }
    S[i+1][j+1]=S[i+1][j]+S[i][j+1]-S[i][j]+dp[i+1][j+1];
  //  cout<<S[i+1][j]<<" "<<S[i][j+1]<<" "<<S[i][j]<<" "<<dp[i+1][j+1]<<" "<<S[i+1][j+1]<<endl;
  }

cout<<(S[n][m]+1);
}


Measured memory_bytes: 66468
#include<bits/stdc++.h>
using namespace std;
int main(){
int i,j,k,l,m,n,x=0,y=0;
cin>>n;
int a[n];
for(i=0;i<n;i++){
	cin>>a[i];
}
int dp[n];
if(n>2){
dp[0]=0;
dp[1]=abs(a[0]-a[1]);
for(i=2;i<n;i++){
	l=abs(a[i]-a[i-1]);
	m=abs(a[i]-a[i-2]);
dp[i]=min((l+dp[i-1]),(m+dp[i-2]));
}
cout<<dp[n-1]<<"\n";
}
else{

	k=abs(a[1]-a[0]);
	cout<<k<<"\n";
}
}

Measured memory_bytes: 1024
//organize and stay in moment
//Abhinav - IIITA
//I love you Disha
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ld long double
int prime[100005] ,arr[100005],pre[100005];
void seive(){
	prime[0]=prime[1]=1;
	for(int i=2;i<100005;++i){
		if(prime[i]==0)
		for(int j=2*i;j<100005;j+=i)
			prime[j]=1;
	}
}
int32_t main(){
	int n; cin>>n;
	int a,b,c; cin>>a>>b>>c;
	for(int i=0;i<n-1;++i){
		int x,y,z; cin>>x>>y>>z;
		x+=max(b,c); y+=max(a,c); z+=max(a,b);
		a=x; b=y; c=z;
	}
	cout<<max(a,max(b,c));
	return 0;
}

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

int x[10];
int y[10];
int p[10];

double d(int i, int j) {
  return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

int main() {
  int n;
  cin >> n;
  for (int i=0; i<n; i++){
    cin >> x[i] >> y[i];
    p[i] = i;
  }
  
  double sum = 0;
  int  cnt = 0;
  
  do {
    for (int i=0; i<n-1; i++){
      sum += d(p[i], p[i+1]);
    }
    cnt++;
  }while(next_permutation(p,p+n));
 
  printf("%.8f\n", sum/cnt);
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int ans = 0;
    set<int> s;
    rep(i, n) {
        if ((i * i) == n) continue;
        s.insert(i);
        s.insert(n - i);
    }
    cout << (sz(s) / 2 - 1) << endl;
    return 0;
}

Measured memory_bytes: 47104
parseint(x) = parse(Int, x)
readint() = readline() |> parseint
readints() = map(parseint, readline() |> split)

function main()
    n = readint()
    p = readints()
    cnt = 0
    for i = 2:n-1
        (sort(p[i-1:i+1])[2] == p[i]) && (cnt += 1)
    end
    println(cnt)
end

main()

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  int N, M; cin >> N >> M;
  if (N%2==1) {
    rep(i,M) cout << i+1 << " " << N - (i+1) << endl;
  }
  else {
    if (N%4==2) {
      if (M<N/4) rep(i,M) cout << i+1 << " " << N - (i+2) << endl;
      else {
        rep(i,N/4) cout << i+1 << " " << N - (i+1) << endl;
        repr(i,N/4,M) cout << i+1 << " " << N - (i+2) << endl;
      }
    }
    else {
      if (M<N/4-1) rep(i,M) cout << i+1 << " " << N - (i+2) << endl;
      else {
        rep(i,N/4-1) cout << i+1 << " " << N - (i+1) << endl;
        repr(i,N/4-1,M) cout << i+1 << " " << N - (i+2) << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3644
import sys
sys.setrecursionlimit(10 ** 6)
N, K = map(int, input().split())

lis = [[] for i in range(N + 1)]

for n in range(N - 1):
    a, b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)

MOD = 10 ** 9 + 7

def dfs(pos, from_, K, lis):
    if from_ == -1:
        to_multi = K - 1
    else:
        to_multi = K - 2
    if len(lis[pos]) > K:
        return 0

    ans = 1
    for item in lis[pos]:
        if item != from_:
            ans *= to_multi
            to_multi -= 1
            ans %= MOD
    for item in lis[pos]:
        if item != from_:
            ans *= dfs(item, pos, K, lis)
            ans %= MOD
    
    return ans

print(K * dfs(1, from_=-1, K=K, lis=lis) % MOD)

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

int main(){
    string S;
    ll K;
    cin >> S >> K;
    string ans;
    if (K <= 100){
        rep(i,100){
            if (S[i] != '1'){
                ans = S.substr(i,1);
                break;
            }
            else if (i == K - 1){
                ans = S.substr(i,1);
                break;
            }
        }
    }
    else{
        rep(i,100){
            if (S[i] != '1'){
                ans = S.substr(i,1);
                break;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 1

typedef long long ll;

const double PI = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

int main(){
    string s;
    cin >> s;
    string temp = s;
    reverse(s.begin(),s.end());
    if(s == temp) cout << "Yes" << endl;
    else cout << "No" << endl; 
    return 0;
}


Measured memory_bytes: 256