akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int TOT = 1 << 15, N = 100010;
int dp[TOT],n,val[N],cnt[16],ans,sta,res[TOT];
int main() {
  int a,b,c,tmp;
  scanf("%d",&n);
  for (int i = 1 ; i < n ; ++ i) {
    scanf("%d%d%d",&a,&b,&c);
    a++, b++;
    val[a] ^= c;
    val[b] ^= c;
  }
  for (int i = 1 ; i <= n ; ++ i)
    ++ cnt[val[i]];
  ans = n;
  ans -= cnt[0];
  for (int i = 1 ; i <= 15 ; ++ i)
    ans -= cnt[i]/2, sta |= (cnt[i]&1) << i >> 1;
  for (int i = 0 ; i < TOT ; ++ i) {
    tmp = 0;
    for (int j = 1 ; j <= 15 ; ++ j)
      if ((i >> j-1)&1) tmp ^= j;
    res[i] = tmp;
  }
  for (int i = 1 ; i < TOT ; ++ i) {
    for (int j = i ; j ; j = (j-1) & i)
      if (!res[j]) dp[i] = max(dp[i],dp[i^j] + 1);
  }
  ans -= dp[sta];
  printf("%d\n",ans);
  return 0;
}

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

int main() {
  string S;
  cin >> S;
  
  int N=S.size();
  
  string ans;
  
  for (int i = 0; i < (N-1)/2; i++) {
    if(S.at(N-(i+1))==S.at(i)){
      ans = "Yes";
    }
    else{
      ans ="No";
      break;
    }
  }
  
  if (ans=="Yes"){  
  for (int j = 0; j < (N-1)/2/2; j++) {
    if(S.at((N-1)/2-(j+1))==S.at(j)){
      ans = "Yes";
    }
    else{
      ans = "No";
      break;
    }

  }
  }
   else{
     ans="No";
   }
     
    
      
  
    cout << ans << endl;
}


Measured memory_bytes: 256
# include <iostream>

//https://atcoder.jp/contests/abc083/tasks/abc083_a

using namespace std;

int main(){
    int A,B,C,D;

    cin >> A >> B >> C >> D;
    
    int L = A + B;
    int R = C + D;

    if( L > R) {
        cout << "Left" << endl;
    }
    else if(L == R){
        cout << "Balanced" << endl;
    }
    else if( L < R ){
        cout << "Right" << endl;
    }
    return 0;

}

Measured memory_bytes: 256
S = input()

st = 0
en = len(S) - 1
ans = 0
while st < en:
    if S[st] == S[en]:
        st += 1
        en -= 1
    elif S[st] == 'x':
        ans += 1
        st += 1
    elif S[en] == 'x':
        ans += 1
        en -= 1
    else:
        ans = -1
        break

print(ans)


Measured memory_bytes: 3316
#include <iostream>
using namespace std;
typedef long long int LLI;
int solve(int arr[], int n)
{
	int start = 1, ans = 1, tmp;
	for(int i = 1; i <= n; i++)
	{
		tmp = arr[start];
		if( tmp == 2 or tmp == 0 ){
			return ans;
		}
		ans++;
		start = tmp;
	}
	return -1;
}
int main()
{
	int n;
	cin >> n;
	int arr[n+1]{};
    for(int i = 1; i <= n; i++)
    	cin >> arr[i];
    	
	cout << solve(arr,n);
}

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

namespace ABC140B
{
    class Program
    {
        public static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine()
                    .Split(' ').Select(x => int.Parse(x))
                    .ToArray();
            var b = Console.ReadLine()
                    .Split(' ').Select(x => int.Parse(x));
            var c = Console.ReadLine()
                    .Split(' ').Select(x => int.Parse(x))
                    .ToArray();

            var ans = b.Sum();
            for (int i = 0; i < n-1; i++) {
                if (a[i]+1 == a[i+1] ) {
                    ans += c[a[i]-1];
                }
            }
            Console.WriteLine(ans);
         }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
typedef pair<ll, ll> P;
const ll INF = 1LL << 60;
//const int MOD = 1000000007;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

ll kazu[100010];
const long long mod = 998244353;
long long modpow(long long a, long long n) {
  long long atai = 1;
  while (n > 0) {
    if (n % 2) {
      atai *= a;
	  atai%=mod;
      n-=1;
    } 
    a *= a;
    a%=mod;
    n /= 2;
  }
  return atai;
}
int main(){
  int n;
  cin>>n;
  vector<ll>d(n);
  ll saidai=0;
  rep(i,n){
    cin>>d[i];
    if(i!=0)kazu[d[i]]++;
    if(i!=0&&d[i]==0||d[0]!=0){
      cout<<0<<endl;
      return 0;
    }
    chmax(saidai,d[i]);
  }
  ll ans=1;
  for(int i=2;i<=saidai;i++){
      ans*=modpow(kazu[i-1],kazu[i]);
      ans%=mod;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4848
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000007;
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int a[105];
  int cnt;
  int ans = 0;

  cin >> n;

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

  cnt = 1;
  for(int i = 1;i <= n;i++){
    if(a[i - 1] == a[i]){
      cnt ++;
    }else{
      ans += cnt / 2;
      cnt = 1;
    }
  }

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



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <complex>
#include <numeric>
using namespace std;

typedef long long LL; typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define OUT(a) cout<<(a)<<endl;

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

    LL n,l,a[100010];
    int last=-1;

    cin >> n >> l;
    cin >>a[1];
    FOR(i,2,n+1){
        cin >> a[i];
        if((a[i]+a[i-1]>=l)){
            last=i-1;
        }
    }
    if(last==-1){
        cout << "Impossible" << endl;
        return 0;
    }else{
        cout << "Possible" <<endl;
        FOR(i,1,last){
            cout << i <<endl;
        }
        for(int i=n-1;i>=last ;--i){
            cout << i << endl;
        }
    }

    return 0;
}


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

using namespace std;

int main()
{
    int N;
    string S;
    cin >> N >> S;

    bool flag = true;
    if ((N&1) == 1) flag = false;
    else if (S.substr(0, N/2) != S.substr(N/2, N/2)) flag = false;

    cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()

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

left = -1
right = n + 1

for _ in range(m):
    l, r = map(int, input().split())
    if r < left or l > right:
        print(0)
        sys.exit()
    left = max(left, l)
    right = min(right, r)

print(right - left + 1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define endl '\n'
typedef pair<int, int> P;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    vector<ll> bucket(100100);
    ll res = 0;
    rep(i, n)
    {
        ll a;
        cin >> a;
        res += a;
        bucket[a]++;
    }
    ll q;
    cin >> q;
    rep(i, q)
    {
        ll b, c;
        cin >> b >> c;
        res -= b * bucket[b];
        res += c * bucket[b];
        bucket[c] += bucket[b];
        bucket[b] = 0;
        cout << res << endl;
    }
}

Measured memory_bytes: 3988
while 1:
    n,p = map(int,input().split())
    if n==0: break
    a = [0 for _ in range(n)]
    while 1:
        for i in range(n):
            #print(i, a, p)
            if p != 0:
                a[i] += 1
                p -= 1
                if p == 0 and sum(a[:i])+sum(a[i+1:]) == 0:
                    print(i)
                    break
            else:
                p = a[i]
                a[i] = 0
        else:
            continue
        break


Measured memory_bytes: 5600
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <cmath>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
typedef long long ll;

int main()
{
	int n,m,r;
	cin >> n >> m >> r;

	vector<int> R(r);
	rep(i,r){cin >> R[i],R[i]--;};

	vector<vector<ll>> dist(n,vector<ll>(n));
	rep(i,n)
		rep(j,n)
		{
			dist[i][j]=INT_MAX;
		}

	rep(i,n)dist[i][i]=0;
	
	rep(i,m)
	{
		int foo, fooo,foooo;
		cin >> foo >> fooo >> foooo;
		if(dist[foo-1][fooo-1]>foooo)
		dist[foo-1][fooo-1] = dist[fooo-1][foo-1] = foooo;
	}

	rep(k,n)
		rep(i,n)
			rep(j,n)
			{
				dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
			}

	sort(R.begin(),R.end());
	
	ll ans=LLONG_MAX;
	do{
		ll ddd=0;
		rep(i,r-1)ddd+=dist[R[i]][R[i+1]];
		ans=min(ddd,ans);
	}
	while(next_permutation(R.begin(),R.end()));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 512
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    static final int INF = 1000000000;     
    
    public static void main(String[] args) throws Exception {                
        Scanner input = new Scanner(System.in);
        int n, q;
        n = input.nextInt();
        ArrayList<Integer> s = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            int x = input.nextInt();
            if (s.size() > 0 && x == s.get(s.size() - 1)) continue;
            s.add(x);
        }
        q = input.nextInt();
        ArrayList<Integer> t = new ArrayList<Integer>();
        for (int i = 0; i < q; ++i) {
            int x = input.nextInt();
            t.add(x);
        }
        s.retainAll(t);
        System.out.println(s.size());
    }                
}

Measured memory_bytes: 66724
sss = input()
while not sss == '-1 -1 -1':
	m,f,r = map(int, sss.split(' '))
	if m == -1 or f == -1:
		print('F')
	elif m+f >= 80:
		print('A')
	elif m+f >= 65 and m+f < 80:
		print('B')
	elif m+f >= 50 and m+f < 65:
		print('C')
	elif m+f >= 30 and m+f < 50:
		if r >= 50: print('C')
		else: print('D')
	elif m+f < 30:
		print('F')
	sss = input()


Measured memory_bytes: 7676
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define MOD 998244353

using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	n %= 10;
	if (n == 3) cout << "bon";
	else if (n == 0 || n == 1 || n == 6 || n == 8) cout << "pon";
	else cout << "hon";
	cout << endl;
	return 0;
}


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

int main() {
  int N;
  cin>>N;
  
  if(N<10) cout<<N<<endl;
  else if(N<100) cout<<"9"<<endl;
  else if(N<1000) cout<<N-90<<endl;
  else if(N<10000) cout<<"909"<<endl;
  else if(N<100000) cout<<N-9090<<endl;
  else cout<<"90909"<<endl;
}


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


int main(){
	int N,M;
	cin>>N>>M;
	for(int i=N;i<=M;i++){
		if(M%i==0){
			cout<<M/i<<endl;
			return 0;
		}
		if(M/i==20){
			break;
		}
	}
	for(int i=20;i>=0;i--){
		if(M%i==0){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int ans;
int N, M;
vector<int> g[10]; 
bool used[10];

void dfs(int u) {
    bool ok = true;
    for (int i=1; i<=N; i++) {
        if (!used[i]) ok = false;
    }
    if(ok) {
        ans++;
        return;
    }

    for(int i=0; i<(int)g[u].size(); i++) {
        int v = g[u][i];
        if (!used[v]) {
            used[v] = true;
            dfs(v);
            used[v] = false;
        }
    }
} 

int main(void) {
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        g[a].pb(b);
        g[b].pb(a);
    }
    used[1] = true;
    dfs(1);
   

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

	return 0;
}


Measured memory_bytes: 256
s = require("fs").readFileSync("/dev/stdin","utf8").split('\n')
a = 1000000000
n = s[0].split(' ')[0] | 0
k = s[0].split(' ')[1] | 0
s.shift()
s = s.map(n => n | 0).sort((a, b) => b - a);
[...Array(n - k + 1)].forEach((_, i) => {
	t = s[i] - s[i + k - 1]
	if (t < a) a = t
})
console.log(a)

Measured memory_bytes: 29368
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int res[100000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    FOR(i,1,100)
        FOR(j,1,100)
            FOR(k,1,100) {
                int n = i * i + j * j + k * k + i * j + j * k + k * i;
                res[n]++;
            }
    int n;
    cin >> n;
    FOR(i,1,n) cout << res[i] << "\n";
    return 0;
}


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

vector<ll> a, limit;

bool feasible(ll n) {
    ll able = 1;
    rep(i, n+1) {
        limit[i] = able;
        able = (able-a[i])*2;
        if (able>1e13) able=1e13;
        //cout << able << "," << a[i] << endl;
        if (able < 0) return false;
    }
    return true;
}

ll comb(ll n) {
    ll ans = 0;
    ll current = 0;
    rep(i,n+1) {
        current += a[n-i];
        current = min(current, limit[n-i]);
        ans += current;
        //cout << n-i << ":" << a[n-i] << "," << current << "," << ans << endl;
    }
    return ans;
}


int main() {
    ll n;
    cin >> n;

    a = vector<ll>(n+1);
    limit = vector<ll>(n+1);
    rep(i, n+1) { cin >> a[i]; }

    if (feasible(n)) {
        cout << comb(n) << endl;
    } else {
        cout << -1 << endl;
    }
}


Measured memory_bytes: 4768
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
#include <queue>

using namespace std;
typedef long long ll;
using namespace std;
int c[100000];

ll gcd(ll a, ll b){
    if(b < a) return gcd(b, a);
    else if(a == 0) return b;
    else return gcd(b%a, a);
}
int main(){
    ll A, B;
    cin >> A >> B;
    ll ans = 1;
    ll g = gcd(A, B);
    A /= g;
    B /= g;
    ans *= g*A*B;
    cout << ans << endl;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b; cin>>a>>b;
    cout<<setp(12);
    cout<<a/b<<" "<<a%b<<" "<<(double)a/b<<endl;
    return 0;
}



Measured memory_bytes: 3256
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {
    a:usize,b:usize,
     }
    if a >= 13 {
        println!("{}", b);
    } else if a >= 6 {
        println!("{}", b / 2);
    } else {
        println!("{}", 0);
    }
}


Measured memory_bytes: 2128
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
    read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
    match n {
        0 => a,
        _ => {
            a.push(read::<T>());
            read_n_logic(n - 1, a)
        }
    }
}

use std::cmp::{max, min};

fn main() {
    let a: i64 = read();
    println!("{}", a.pow(2))
}


Measured memory_bytes: 4352
#include <iostream>
#include <cmath>
#include <iomanip>

int main(void)
{
	using namespace std;
	double x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << fixed << setprecision(12) << sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) << endl;
	return 0;
}


Measured memory_bytes: 3292
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int m = scan.nextInt();

		System.out.println(n*(n-1)/2 + m*(m-1)/2);

		scan.close();

	}

}


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

int main() {
  int n;
  long long ans = 0,x;
  cin >> n;
  vector<long long> num(n);
  for(int i = 0;i < n;i++){
    cin >> num[i];
  }
  ans = num[0];
  for(int i = 1;i < n;i++){
    ans = ans^num[i];
  }
  for(int i = 0;i < n;i++){
    x = ans^num[i];
    cout << x << endl;
  }
}


Measured memory_bytes: 4832
#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 - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

ll mod = 1e9 + 7;

int main(){
    ll n;
    string s;
    cin >> n >> s;
    vll used(26, 0);

    REP(i, n){
        used[ll(s[i] - 'a')]++;
    }
    ll ans = 1;
    REP(i, 26){
        ans = (ans * (used[i] + 1)) % mod;
    }
    cout << ans - 1 << endl;
}

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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

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

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%lld",x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int inf=LLONG_MAX/3;

signed main(){
	int h=read(),w=read(),k=read();
	vector<string> board(h);
	REP(i,h)board[i]=readString();
	int sx,sy;
	REP(i,h)REP(j,w)if(board[i][j]=='S'){
		board[i][j]='.';
		sx=j,sy=i;
	}
	vector<vi> dist(h,vi(w,inf));
	dist[sy][sx]=0;
	queue<pi> q;
	q.push(pi(sx,sy));
	int dxy[]{0,-1,0,1,0};
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();
		int d=dist[y][x];
		if(d==k)break;
		REP(c,4){
			int nx=x+dxy[c],ny=y+dxy[c+1];
			if(0<=nx&&nx<w&&0<=ny&&ny<h&&board[ny][nx]=='.'&&dist[ny][nx]==inf){
				dist[ny][nx]=d+1;
				q.push(pi(nx,ny));
			}
		}
	}
	q=queue<pi>();
	REP(i,h)REP(j,w)if(dist[i][j]<inf)dist[i][j]=k,q.push(pi(j,i));
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();
		int d=dist[y][x];
		REP(c,4){
			int nx=x+dxy[c],ny=y+dxy[c+1];
			if(0<=nx&&nx<w&&0<=ny&&ny<h&&dist[ny][nx]==inf){
				dist[ny][nx]=d+1;
				q.push(pi(nx,ny));
			}
		}
	}
	int ans=inf;
	REP(i,h)chmin(ans,dist[i][0]/k+!!(dist[i][0]%k));
	REP(i,h)chmin(ans,dist[i][w-1]/k+!!(dist[i][w-1]%k));
	REP(j,w)chmin(ans,dist[0][j]/k+!!(dist[0][j]%k));
	REP(j,w)chmin(ans,dist[h-1][j]/k+!!(dist[h-1][j]%k));
	cout<<ans<<endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }

  for (int i = 1; i < n; i++) {
    int a = vec.at(i);
    int j = i;

    for (int k = 0; k < n-1; k++) {
      cout << vec.at(k) << " ";
    }
    cout << vec.at(n-1) << endl;

    while (j > 0 && vec.at(j) < vec.at(j-1)) {
      vec.at(j) = vec.at(j-1);
      vec.at(j-1) = a;
      j--;
    }
  }
  for (int k = 0; k < n-1; k++) {
    cout << vec.at(k) << " ";
  }
  cout << vec.at(n-1) << endl;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

struct Node
{
    int to[26];
    char c;
    bool final;
};

const int maxN = 1e6 + 47;
Node nodes[maxN];
int cnt[maxN][26];
int nodes_cnt = 1;

void insert(const string& s)
{
    int cur = 0;
    FOR(i, 0, SZ(s))
    {
        int& nxt = nodes[cur].to[s[i] - 'a'];
        if (nxt == 0)
        {
            nxt = nodes_cnt++;
            nodes[nxt].c = s[i];
        }
        cur = nxt;
    }
    nodes[cur].final = true;
}

LL ans = 0;

int dfs(int cur)
{
    int res = 0;
    FOR(c, 0, 26)
    {
        int nxt = nodes[cur].to[c];
        if (nxt)
        {
            int val = dfs(nxt);
            res += val;
            FOR(t, 0, 26)
            {
                if (nodes[nxt].c - 'a' != t)
                    cnt[cur][t] += cnt[nxt][t];
                else
                    cnt[cur][t] += val;
            }
        }
    }
    FOR(c, 0, 26)
    {
        int nxt = nodes[cur].to[c];
        assert(cnt[cur][c] <= res);
        if (nxt && nodes[nxt].final)
        {
            ans += cnt[cur][c] - 1;
        }
    }
    if (nodes[cur].final)
    {
        cnt[cur][nodes[cur].c - 'a']++;
        res++;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    FOR(i, 0, n)
    {
        string s;
        cin >> s;
        reverse(ALL(s));
        insert(s);
    }
    dfs(0);
    cout << ans << "\n";
    return 0;
}

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

int main()
{
	int N, M;
	cin >> N >> M;
	if (N == M)
	{
		cout << "Yes" << endl;
		return 0;
	}
	else
	{
		cout << "No" << endl;
		return 0;
	}
}

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

int main() {
	int N,M;
	cin >> N >> M;
	int a,b,rest=M;
	unsigned long money=0;
	vector<pair<unsigned long, unsigned long> > AB(N);
	for(int i=0;i<N;i++){
		cin >> a >> b;
		AB.push_back(make_pair(a,b));
		a=0;
		b=0;
	}
	sort(AB.begin(),AB.end());
	int j=0;
	while(rest!=0){
		if(rest>=AB.at(j).second){
			money+=AB.at(j).first*AB.at(j).second;
			rest-=AB.at(j).second;
		}else{
			money+=AB.at(j).first*rest;
			rest=0;
		}
		j++;
	}

	cout << money << endl;

	return 0;
}


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

#define Bye return 0
#define ll long long
const ll MAX = 1e2;

void solve(){
    int a, b, c; cin>>a>>b>>c;
    if(!(c<a) and !(c>b)) printf("Yes\n");
    else printf("No\n");
}

int main(){
    solve();
    Bye;
}

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

int main() {
	long long h,w,c[10][10],jwb=0;
	cin >> h >> w;
	for (int i=0;i<10;++i) {
		for (int j=0;j<10;++j) {
			cin >> c[i][j];
		}
	}
	for (int k=0;k<10;++k) {
		for (int i=0;i<10;++i) {
			for (int j=0;j<10;++j) {
				c[i][j] = min(c[i][j], c[i][k]+c[k][j]);
			}
		}
	}
	int x;
	for (int i=0;i<h;++i) {
		for (int j=0;j<w;++j) {
			cin >> x;
			if (x>=0) jwb += c[x][1];
		}
	}
	cout << jwb << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){

int n, i, k[100001], g[100001], h, p, q;
for(i=0; i<100001; i+=2){
 k[i]=g[i]=0;
 k[i+1]=g[i+1]=0;
}

scanf("%d", &n);
for(i=0; i<n/2; i++){
scanf("%d %d", &p, &q);
 k[p]++;
 g[q]++;
}

int meg1, meg2, mek1, mek2,mg1, mk1, mg2, mk2;
mg1=mk1=mg2=mk2=meg1=meg2=mek1=mek2=0;
for(i=0; i<100001; i++){
 if(mk1<k[i]){
  mk2=mk1;
  mek2=mek1;
  mk1=k[i];
  mek1=i;
 }
 else if(mk2<k[i]){
  mk2=k[i];
  mek2=i;
 }

 if(mg1<g[i]){
  mg2=mg1;
  meg2=meg1;
  mg1=g[i];
  meg1=i;
 }
 else if(mg2<g[i]){
 mg2=g[i];
 meg2=i;
 }
}


h=0;
if(mek1!=meg1)
 h=n-mk1-mg1;
else if(mk1+mg2>mk2+mg1)
 h=n-mk1-mg2;
else
 h=n-mk2-mg1;


printf("%d\n", h);
return 0;
}


Measured memory_bytes: 896
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/
auto cmn=[](auto&x,auto y){if(x>y){x=y;return true;}return false;};
int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    std::string s;
    std::cin >> s;
    usize n = s.length();
    vec<vec<i64>> a(2, vec<i64>(n));
    std::transform(ALL(s), a.at(0).begin(), [](char c){ return c-'0'; });
    std::transform(ALL(a.at(0)), a.at(1).begin(), [](i64 x){ return 9 - x; });

    i64 inf = numr<i64>::max();

    vec<i64> dp(2);
    dp.at(0) = a.at(0).front();
    dp.at(1) = 1 + a.at(1).front();
    for (usize i=1; i<n; i++) {
        vec<i64> swp(2, inf);
        for (usize j=0; j<2; j++) for (usize k=0; k<2; k++) {
            cmn(swp.at(k), dp.at(j) + a.at(k).at(i) + (j!=k));
        }
        swp.swap(dp);
    }
    std::cout << std::min(dp.at(0), dp.at(1) + 1) << '\n';
}


Measured memory_bytes: 24860
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mpr make_pair
#define mt make_tuple
 
using namespace std;
 
const ll N = 100010;
const ll mod = 1e9 + 7;
ll power(ll x, ll   y, ll p){ ll res = 1; x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p; y = y>>1; x = (x*x) % p;} return res; }
ll n,u,v;
ll dp[N][2];
vector<ll> graph[N];

ll dfs(ll ind, ll parent, ll flag){
    ll temp;
    if(dp[ind][flag] != -1) return dp[ind][flag];
    dp[ind][flag] = 1;
    for(int i=0;i<graph[ind].size();i++){
        if(graph[ind][i] != parent){
            temp = dfs(graph[ind][i], ind, 0);
            if(!flag)   temp += dfs(graph[ind][i], ind, 1);
            dp[ind][flag] *= temp;
            dp[ind][flag] = dp[ind][flag]%mod;
        }
    }
    return dp[ind][flag];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    memset(dp, -1, sizeof(dp));
    for(int i=1;i<n;i++){
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    cout<<(dfs(1,0,0) + dfs(1,0,1))%mod<<endl;
    return 0;
}

Measured memory_bytes: 15616
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;

    string mat[2*n];
    rep(i, n){
        cin >> mat[i];
    }
    reps(i, n, 2*n){
        mat[i] = mat[i-n];
    }

    ll ans = 0;
    bool flagGood = true;
    rep(k, n){
        flagGood = true;
        rep(i, n){
            reps(j, i+1, n){
                if(mat[i+k][j] != mat[j+k][i]){
                    flagGood = false;
                    break;
                }
            }
            if(!flagGood) break;
        }
        if(flagGood){
            ans += n;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define FOR(i, a, b) for (int i=(a); i<(b); ++i)
#define ROF(i, b, a) for (int i=(b); i>(a); --i)
#define CASET int _T; cin >> _T; FOR(caset, 0, _T)
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vi>
#define vvb vector<vb>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define mii map<int,int>
#define vpii vector<pii>
#define vt3i vector<t3i>
#define sq(x) (x)*(x)
#define inv(x) powa(x, MOD-2)
 
long long INF = 1LL<<60;
long long MOD = 1e9+7;

template <typename A, typename B> istream &operator>>(istream &is, pair<A, B> &pr) {is >> pr.first >> pr.second; return is;}
template <typename A> istream &operator>>(istream &is, vector<A> &v) {for (auto &x : v) is >> x; return is;}
ostream &operator<<(ostream &os, char &c) {os << (char)c; return os;}
ostream &operator<<(ostream &os, const char s[]) {os << (string)s; return os;}
ostream &operator<<(ostream &os, string &s) {for (char &c : s) os << (char)c; return os;}
template <typename A, typename B> ostream &operator<<(ostream &os, pair<A, B> &pr) {os << '(' << pr.first << ", " << pr.second << ')'; return os;}
ostream &operator<<(ostream &os, vb &v) {
    bool first = true;
    os << '[';
    for (const bool &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
template <class C> ostream &operator<<(ostream &os, C &v) {
    bool first = true;
    os << '[';
    for (auto &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}
bool mini(int &a, int b) { return b < a ? a = b, 1 : 0; }
bool maxi(int &a, int b) { return b > a ? a = b, 1 : 0; }

main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    int n;
    cin >> n;
    vi a(n);
    cin >> a;

    int BIG = 1e6+5;
    vi sieve(BIG);
    for (int p=2; p*p<BIG; ++p) if (!sieve[p]) for (int u=p*p; u<BIG; u+=p) sieve[u] = p;

    vi lcm(BIG);
    vi cur(BIG);
    FOR(i, 0, n) {
        int x = a[i];
        vi facts;
        while (sieve[x]) {
            facts.push_back(sieve[x]);
            ++cur[sieve[x]];
            x /= sieve[x];
        }
        facts.push_back(x);
        ++cur[x];
        for (int i : facts) {
            maxi(lcm[i], cur[i]);
            cur[i] = 0;
        }
    }

    int lcmval = 1;
    FOR(i, 2, BIG) if (lcm[i]) lcmval = lcmval * powa(i, lcm[i]) % MOD;
    
    int res = 0;
    FOR(i, 0, n) res = (res + lcmval*inv(a[i]) % MOD) % MOD;
    cout << res;
}

Measured memory_bytes: 23808
import java.util.*;
public class Main {

	private static Scanner sc;

	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int w = sc.nextInt();
		int h = sc.nextInt();
		int n = sc.nextInt();
		int Xmax=w,Ymax=h,Xmin=0,Ymin=0;
		for(int i= 0;i<n;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			int a=sc.nextInt();
			if(a==1) Xmin=Math.max(Xmin,x);
			if(a==2) Xmax=Math.min(Xmax,x);
			if(a==3) Ymin=Math.max(Ymin,y);
			if(a==4) Ymax=Math.min(Ymax,y);
				
		}
		System.out.println(Math.max(0,Xmax-Xmin) * Math.max(0,Ymax-Ymin));
		

	}

}


Measured memory_bytes: 22100
S = str(input())
s = list(map(str, S))
N = len(s)
t = 0
for i in range(int((N-1)/2)):
    if s[i] != s[N-i-1]:
        t += 1
        break
for i in range(int((N-1)/4)):
    if s[i] != s[int((N-1)/2) - i - 1]:
        t += 1
        break

if t == 0:
    print('Yes')
else:
    print('No')

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

using namespace std;
typedef long long ll;

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

    /*Solve*/

int main(){
    string S;
    cin >> S;
    ll s0=0;
    ll s1=0;
    rep(i,S.size()){
        if(S[i]=='0')
            s0++;
        else
            s1++;
    }
    
    cout << 2*min(s0,s1);
}

Measured memory_bytes: 512
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import heapq

import logging
logging.basicConfig(level=logging.DEBUG)

import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

MOD = 10**9+7
INF = float('inf')

"""
## test data 
# input
5 5
10 2
1 3
15 2
2 4
5 2
3 5
20 1
5
20 4
1 2 3 4

# output
25
"""

def main():
    N,M=[int(x) for x in input().split()]
    dp = [INF] * 2**N
    dp[0]=0
    for i in range(M):
        a,b=[int(x) for x in input().split()]
        c=sum([1 << (p-1) for p in list(map(int, input().split()))])
        for j in range(2**N):
            dp[j|c]=min(dp[j|c], dp[j]+a)
    print(dp[-1] if dp[-1]!=INF else -1)

main()

Measured memory_bytes: 73688
input()
s = input()
ans = ''
cnt_l = 0
cnt_r = 0
cur = 0
for c in s:
    if c == '(':
        if cur < 0:
            cnt_l += abs(cur)
            cur = 0
        cur += 1
    else:
        cur -= 1
if cur > 0:
    cnt_r += cur
else:
    cnt_l += abs(cur)
print(cnt_l*'(' + s + cnt_r*')')

Measured memory_bytes: 38256
#include<stdio.h>
int main(){
  int  n;
  int a[n];
  int k=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(int i=0;i<n;i++){
    if(a[i]!=i+1){
      k=k+1;
    }
  }
  //printf("%d\n",k);
  if(k==0||k==2){
    printf("YES\n");
  }
  else{
    printf("NO\n");
  }
}

    

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
ll n;cin>>n;
bool flag = false;
for(int i= 0;i<100;++i)for(int j=0;j<100;++j)if(i*4+j*7==n)flag=true;
cout<<(flag?"Yes":"No")<<std::endl;
}


Measured memory_bytes: 256
/**
 * File              : E-tutorial.cpp
 * Author            : JCHRYS <jchrys@me.com> Date              : 16.03.2020
 * Last Modified Date: 17.03.2020
 * Last Modified By  : JCHRYS <jchrys@me.com>
 */

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s;

int get(int idx) {
    return s[idx] - '0';
}


int main() {
    cin >> s;
    s = '0' + s;
    int n = s.size();
    vector<vector<ll>> dp(n, vector<ll>(2, 0));
    //dp[i][j] -> min # paper need at index j, i == 0 ? not carry: carry;
    dp[0][0] = 0;
    dp[0][1] = 1;
    for (int i = 1; i < n; ++i) {
        dp[i][0] = min(dp[i - 1][0] + get(i), dp[i - 1][1] + 10 - get(i)); 
        dp[i][1] = min(dp[i - 1][0] + (get(i) + 1), dp[i - 1][1] + 10 - (get(i) + 1));
    }
    cout << dp[n - 1][0];
    
    return 0;
}


Measured memory_bytes: 55856
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl
#define printD(a) cout << setprecision(15) << (a) << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<auto>& a,int n);
double PI = 3.14159265358979;
int n;

//価値v,重さw
int Knapsack(int n,int W, vector<int>& v,vector<int>& w){
    W++;
    twovec(dp,n,W);
    dp[0][w[0]] = v[0];
    FOR(i,1,n){
        if(w[i] >= W) continue;
        dp[i][w[i]] = max(v[i],dp[i-1][w[i]]);
        REP(j,W){
            if(dp[i-1][j] != 0){
                dp[i][j] = max(dp[i][j],dp[i-1][j]);
                if(j+w[i] < W){
                    dp[i][j+w[i]] = dp[i-1][j] + v[i];
                }
            }
        }
    }
    int ans = 0;
    REP(i,W){
        ans = max(ans,dp[n-1][i]);
    }
    return ans;
}

int Knapsack_big(int n,int W, vector<int>& v,vector<int>& w){
    vector<int> dp(n*1000+1,W+1);
    dp[0] = 0;
    REP(i,n){
        for(int j = dp.size()-1; j >= v[i]; j--){
            if(dp[j] > dp[j-v[i]] + w[i]) dp[j] =  dp[j-v[i]] + w[i];
        }
    }
    //Debug(dp);
    for(int i = dp.size()-1;i >= 0; i--){
        if(dp[i] != W+1) return i;
    }

}

//価値v,重さw
int Knapsack_mult(int n,int W, vector<int>& v,vector<int>& w){
    W++;
    vec(dp,W);
    REP(i,n){
        if(w[i] >= W) continue;
        dp[w[i]] = max(v[i],dp[w[i]]);
        REP(j,W){
            if(j+w[i] >= W) break;
            if(dp[j] != 0){
                dp[j+w[i]] = max(dp[j] + v[i],dp[j+w[i]]);
            }
        }
        //Debug(dp);
    }
    //Debug(dp);
    int ans = 0;
    REP(i,W){
        ans = max(dp[i],ans);
    }
    return ans;
}


signed main(){
    int W;
    cin >> n >> W;
    vec(v,n);
    vec(w,n);
    REP(i,n){
        cin >> w[i] >> v[i];
    }
    print(Knapsack_big(n,W,v,w));
    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
//key以上の初めてのitr
int nibul(auto a,auto b){return lower_bound(All(a),b) - a.begin();}
//key以下の最後のitr
int nibuu(auto a,auto b){return upper_bound(All(a),b) - a.begin()-1;}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}


Measured memory_bytes: 1024
def calc_digit(n):
    digit = 0
    while n > 0:
        digit += 1
        n //= 10
    return digit

def main():
    N = int(input())
    i = 1
    digit = []
    ans = 10
    while i ** 2 <= N:
        if N % i == 0:
            tmp = calc_digit(N // i)
            if ans > tmp:
                ans = tmp
        i += 1
    print(ans)

    return 0


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	b := make([]int, n-1)
	for i, _ := range b {
		fmt.Scan(&b[i])
	}

	ans := 0
	for i, v := range b {
		if i == 0 {
			ans += v
		}
		if i == len(b)-1 {
			ans += v
			fmt.Println(ans)
			return
		}
		if v > b[i+1] {
			ans += b[i+1]
		} else {
			ans += v
		}
	}
}

Measured memory_bytes: 512
import numpy as np 

n, k = map(int, input().split())
h = np.array([int(i) for i in input().split()])

dp = np.array([0] * n)

for i in range(1, n):
    j = max(0, i-k)
    dp[i] = np.min(dp[j:i] + np.abs(h[i] - h[j:i])) #ブロードキャストしてるんか

print(dp[-1])

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

#define pb push_back
#define ll long long

using namespace std;

const int N = 1e6 + 10;

string s;

int mx;

int main() {
 cin >> s;
 mx = int(s.size());
 for (int i = 0; i < int(s.size()) - 1; i++) {
  if (s[i] != s[i + 1]) {
   mx = min(mx, max(i + 1, int(s.size()) - i - 1));
  }
 }
 cout << mx;
 return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
//			#include <ext/pb_ds/assoc_container.hpp>
//			#include <ext/pb_ds/tree_policy.hpp>

		using ll = long long;
		using ld = long double;
		#define rep(i, a, n) for(ll i = (a); i < (n); i++)
		#define per(i, a, n) for(ll i = (n-1); i >= (a); i--)
		#define F first
		#define S second
		#define endl "\n"
		#define all(x) begin(x), end(x)
		#define maxx(a, b) a = max(a, b)
		#define minn(a, b) a = min(a, b)
		#define db(x) cerr<<#x<<" = "<<x<<endl
		#define N 1111111
		#define mod 998244353
		#define rt return
		#define inf 1234567891123456789ll

		using namespace std;
//			random_device rd;
//			mt19937 mt(rd());
//			using namespace __gnu_pbds;
//
//			typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

		#define error(args...){string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

		void err(istream_iterator<string> it) {}
		template<typename T, typename... Args>
		void err(istream_iterator<string> it, T a, Args... args)
		{
			cerr<<*it<<" = "<<a<<endl;
			err(++it, args...);
		}

		ll modlaber(ll a, ll m = mod)
		{
			rt ((a+m)%m+m)%m;
		}

		int main()
		{
			ios_base::sync_with_stdio(0);
			cin.tie(0);
			cout.tie(0);

			ll n; cin>>n;
			ll ans = 0;
			rep(i,0,n)
			{
				ll j; cin>>j;
				ans += i%2 == 0 && j&1;
			}
			cout<<ans;

			rt 0;
		}




















Measured memory_bytes: 3604
N = int(input())
X = input()
def popcount(n):
    tmp = n
    cnt = 0
    while tmp:
        cnt += tmp % 2
        tmp >>= 1
    return cnt
def f(n):
    tmp = n
    cnt = 0
    while tmp:
        cnt += 1
        ff = popcount(tmp)
        tmp %= ff
    return cnt
cnt = 0
LL = [0 for _ in range(200010)]
for i in range(200010):
    LL[i] = f(i)
for i in range(N):
    cnt += X[i] == '1'
A = [1 for _ in range(N+1)]
B = [1 for _ in range(N+1)]
for i in range(N):
    A[i+1] = A[i] << 1
    A[i+1] %= cnt + 1
for i in range(N):
    B[i+1] = B[i] << 1
    if cnt > 1:
        B[i+1] %= cnt - 1
    else:
        B[i+1] = 0
S = 0
T = 0
for i in range(N):
    S += X[i] == '1'
    T += X[i] == '1'
    if i != N-1:
        S <<= 1
        T <<= 1
        S %= cnt + 1
        if cnt > 1:
            T %= cnt - 1
        else:
            T = 0
C = [S for _ in range(N)]
D = [T for _ in range(N)]
for i in range(N):
    if X[i] == '1':
        D[i] -= B[N-1-i]
        if cnt == 1:
            print(0)
        else:
            D[i] %= cnt - 1
            print(LL[D[i]]+1)
    else:
        C[i] += A[N-1-i]
        C[i] %= cnt + 1
        print(LL[C[i]]+1)

Measured memory_bytes: 36228
n, k = map(int, input().split())
m = 10**9 + 7

cnt = [0 for i in range(k+1)]

for i in range(k, 0, -1):
    cnt[i] = pow((k//i), n, m)
    for j in range(i*2, k+1, i):
        cnt[i] -= cnt[j]

print(sum(i*cnt[i] for i in range(1, k+1)) % m)


Measured memory_bytes: 11332
def main():
    N = int(input())
    h = list(map(int, input().split())) + [0]
    ans = 0; conti = False
    for line in range(1, 101):
        for i in range(N+1):
            if h[i] >= line and conti:
                continue
            elif h[i] >= line and not conti:
                conti = True
                ans += 1
            elif h[i] < line and conti:
                conti = False
            elif h[i] < line and not conti:
                continue
            else:
                pass

    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::{BufWriter, Write};

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[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)*}
    };

    ($next:expr, mut $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, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn solve() {
    input!(
        n: i64,
    );

    let mut ans = n - 1;

    for i in 1..((n as f64).sqrt() as i64 + 1) {
        if n % i == 0 {
            ans = min(ans, i + n/i - 2);
        }
    }

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

fn main() {
    let stack_size = 1 << 28;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

using namespace std;

int n, ans;

int number_div(int n) {
	int res = 0;
	for (int i = 1; i * i <= n; i++)
		if (n % i == 0) {
			if (i * i == n)
				res++;
			else
				res += 2;
		}
	return res;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (i % 2 != 0 && number_div(i) == 8)
			ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 380
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  long a, b, c=0, d=0, e, f, g, h, n;
  cin >> a >> b >> n;
  a=max(a, b);
  if(n%a==0) co(n/a);
  else co(n/a+1);
  
  return 0;
}

Measured memory_bytes: 256
main=do
 getLine
 a<-map read.words<$>getLine
 b<-map read.words<$>getLine
 print$f a b
f a[]=0
f(x:y:as)(b:bs)=(if x+y<b then x+y else b)+f((if x<b then(max(x+y-b)0)else y):as)bs

Measured memory_bytes: 101756