akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAX 100000

struct TRAMP{
    char mark;
    int number,inputed_order;
};

TRAMP cards[MAX];

int n;

int Partition(int left,int right){
    int i = left-1,pivot = cards[right].number;
    for(int start = left; start < right; start++){
        if(cards[start].number <= pivot){
                i++;
                std::swap(cards[i],cards[start]);
        }
    }

    std::swap(cards[i+1],cards[right]);

    return i+1;
}

void quickSort(int left,int right){
    if(left < right){
        int q = Partition(left,right);
        quickSort(left,q-1);
        quickSort(q+1,right);
    }
}


int main(){

    bool stableFLG = true;
    scanf("%d",&n);

    for(int i = 0; i < n; i++){
        scanf("%s %d",&cards[i].mark,&cards[i].number);
        cards[i].inputed_order = i;
    }

    quickSort(0,n-1);

    for(int i = 1; i < n; i++){
        if(cards[i].number == cards[i-1].number && cards[i].inputed_order < cards[i-1].inputed_order){
        	stableFLG = false;
        	break;
        }
    }

    if(stableFLG){
        printf("Stable\n");
    }else{
        printf("Not stable\n");
    }

    for(int i = 0; i < n; i++)   printf("%c %d\n",cards[i].mark,cards[i].number);
}



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



int main()
{
  long long n;
  cin >> n;
  n--;
  cout << (n + 1) * n / 2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)

string divide[4] = {"dream", "dreamer", "erase", "eraser"};

int main(){
    string s; cin >> s;
    reverse(ALL(s));
    rep(i, 4) reverse(ALL(divide[i]));
    bool can = true;
    for(int i = 0; i < s.size();){
        bool can2 = false;
        rep(j, 4){
            string d = divide[j];
            if(s.substr(i, d.size()) == d) {
                can2 = true;
                i += d.size();
            }
        }
        if(!can2) {
            can = false;
            break;
        }
    }
    if(can) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

int main() {
    int r, d, a;
    cin >> r >> d >> a;
    int x = 1;

    for(int i = 0; i < 10; i++){
        x = r * a - d;
        cout << x << endl;
        a = x;
    }

}

Measured memory_bytes: 256
// In The Name Of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pll;
typedef unsigned long long ull;
typedef vector<pair<int, int> > vpll;
const int maxx = 1e5 + 19;

map<int, int> M;
int n, a[maxx] = {}, b[maxx] = {}, ans = 0;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        M[b[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        if (i % 2 != M[a[i]] % 2)
            ans++;
    }
    cout << ans / 2;
    return 0;
}


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

using namespace std;

int main()
{


   long long int n,m,i;
   cin>>n;
   cin>>m;
   long long int arr[n],sum=0,hang;
   for(i=0;i<m;i++)
    cin>>arr[i];
    sum=accumulate(arr,arr+m,sum);
     hang=n-sum;
     if(hang<0)
     {
         cout<<"-1"<<"\n";
     }
     else
        cout<<hang<<"\n";

}


Measured memory_bytes: 3716
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<utility>
#include<set>
using namespace std;
string a,b;

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

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

int main() {
	long long a, b, c;
	cin >> a >> b >> c;
	if(c >= a)
		c -= a, a = 0;
	else
		a -= c, c = 0;
	if(c >= b)
		b = 0;
	else
		b -= c;
	cout << a << ' ' << b;
}


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

char convert(char input)
{
    if(input == 'H'){
      return 'D';
    }
    else if(input == 'D'){
      return 'H';
    }
}

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

  if(a == 'H'){
    cout << b << endl;
  }
  else if(a == 'D'){
    cout << convert(b) << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
typedef long long ll;
using namespace std;
int main(void){
    int n,m;cin>>n>>m;
    vector<int> a(m);
    rep(i,m) cin>>a[i];
    sort(a.rbegin(),a.rend());
    int tr[10]={0,2,5,5,4,5,6,3,7,6};
    string dp[n+1003];//i本のマッチ棒を使ってできる最大の整数
    dp[0]="";
    rep(i,n){
        if(i!=0&&dp[i].size()==0) continue;
        rep(j,m){
            int x=a[j];//最上段に着ける整数候補
            string now=dp[i];
            string nw=((char)(x+'0'))+now;
            if(dp[i+tr[x]].size()==0)dp[i+tr[x]]=nw;
            //if(dp[i+tr[x]]=="71")cout<<nw<<" "<<i<<endl;
            if(dp[i+tr[x]].size()<nw.size())dp[i+tr[x]]=nw;
            if(dp[i+tr[x]][0]-'0'<nw[0]-'0')dp[i+tr[x]]=nw;
            //if(dp[i+tr[x]]=="71")cout<<nw<<endl;
        }
    }
    string res=dp[n];
    //reverse(res.begin(),res.end());
    //rep(i,n+1)cout<<dp[i]<<" "<<i<<endl;
    cout<<res<<endl;
}


Measured memory_bytes: 35072
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		s += '2';
		int n = s.length(), ans = n - 1;
		for(int i = 0; i < n - 1; ++i) {
			if(s.charAt(i) != s.charAt(i + 1)) {
				int tmp = Math.max(i + 1,  n - i - 2);
				ans = Math.min(ans,  tmp);
			}
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 27820
n, m = list(map(int, input().split()))

def divisor(x) :
    d = []
    i = 1
    while i**2 <= x :
        if x%i == 0 :
            d.append(i)
            d.append(x//i)
        i += 1
    return d

maximum = 0
for d in divisor(m) :
    if d >= n :
        maximum = max(maximum, m//d)
print(maximum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> l(N);
  rep(i, N) cin >> l[i];

  sort(all(l), greater<int>());
  int ans = 0;

  rep(i, K) { ans += l[i]; }

  cout << ans << endl;
}

Measured memory_bytes: 256
def insertionSort(A,N):
    for i in range(1,N):
        v=A[i]
        j=i-1
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j-=1
        A[j+1]=v
        print(str(A).replace(",",'').replace("[",'').replace("]",''))


N=int(input())
sl=input()
print(sl)
lis=list(map(int,sl.split()))
insertionSort(lis,N)

Measured memory_bytes: 7676
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll l,r; cin>>l>>r;
    ll mn=2050;
    if(r-l+1>=2019){
        cout<<0<<endl;
    }
    else {
        for(ll i=l;i<=r-1;i++){
            for(ll j=l+1;j<=r;j++){
                mn=min((i*j)%2019,mn);
            }
        }
        cout<<mn<<endl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int n, i, a;
	scanf("%d", &n);
	int day[n], value;
	for(i = 0; i < n; i++){
		scanf("%d", &day[i]);
	}
	for(a = n - 1; a >= 0; a--){
		value = day[a];
		printf("%d", value);
		if(a)printf(" ");
	}
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
#define endl '\n'
#define fi first
#define se second
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define pb push_back
#define mk make_pair
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int ans = 0;
	sort(v.begin(), v.end(), greater<int>());
	for (int i = 0; i < n ; i++) {
		for (int j = i + 1 ; j < n ; j++) {
			for (int r = j + 1 ; r < n; r++) {
				set<int>s;
				s.insert(v[i]);
				s.insert(v[j]);
				s.insert(v[r]);
				if (s.size() == 3) {
					if (v[i] < v[j] + v[r])ans++;
				}
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3648
#include<bitset>
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rep1n(i, n) for(int i=1;i<=(int)(n);i++)
#define repe(i, a, n) for(int i=(a);i<(int)(n);i++)
#define repi(i, a, n) for(int i=(a);i<=(int)(n);i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout<<(cond? "Yes":"No")<<endl;
#define YES(cond) cout<<(cond? "YES":"NO")<<endl;
int main() {
	int a, b;
	cin >> a >> b;
	char wh = '.', bl = '#';
	int h, w;
	h = w = 100;
	vector<string>t(h, string(w, wh));
	repe(i, h / 2, h) {
		t[i] = string(w, bl);
	}
	int bcnt = 1;
	[&]() {
		rep(i, h / 2) {
			rep(j, w) {
				if (bcnt >= b)return;
				t[i][j] = bl;
				j++;
				bcnt++;
			}
			i++;
		}
	}();
	int acnt = 1;
	[&]() {
		repe(i, h / 2 + 1, h) {
			rep(j, w) {
				if (acnt >= a)return;
				t[i][j] = wh;
				j++;
				acnt++;
			}
			i++;
		}
	}();
	cout << h << " " << w << endl;
	rep(i, h) {

		rep(j, w)cout << t[i][j];
		cout << endl;
	}

	return 0;
}





Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE FlexibleContexts #-}

import Data.Bits
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IMS
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS
import qualified Data.Sequence as Seq
import Data.Sequence (Seq)
import qualified Data.Array.IArray as A
import qualified Data.Array.MArray.Safe as A
import qualified Data.Array.MArray as A
import Data.Array (Array)
import Data.Array.Unboxed (UArray)
import Data.Array.IArray (IArray)
import Data.Array.MArray.Safe (MArray)
import Data.Array.IO.Safe (IOArray, IOUArray)
import Data.Array.ST.Safe (STArray, STUArray, runSTArray, runSTUArray)
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Monad.ST
-- import Control.Monad.ST.Safe
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Control.Monad.State.Strict
import Data.Int
import System.IO
import Data.Function
import Control.Monad.Primitive
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Generic.Mutable as VGM
import Data.STRef
import Data.IORef

main :: IO ()
main = do
  [n,q] <- map read . words <$> getLine :: IO [Int]
  as <- VU.unfoldrN n (BS.readInt . BS.dropWhile (==' ')) <$> BS.getLine
  let asum = VU.scanl' (+) 0 as
      aIntSum = VU.map fst $ VU.scanl' (\(!x,!y) a -> (y+a,x)) (0,0) as
  xs <- VU.unfoldrN q (BSL.readInt . BSL.dropWhile (<'!')) <$> BSL.getContents
  VU.forM_ xs $ \x ->
    print (query n as asum aIntSum x :: Int)

query n as asum aIntSum x
  = asum VU.! n - asum VU.! (n-divpt) + aIntSum VU.! (max 0 $ n-divpt*2)
  where
    ind_geqx = geq_binSearch x (-1) n
    -- How many entries >= x can takahashi take?
    divpt = divpt_binSearch 0 (n-ind_geqx+1)
    divpt_binSearch :: Int -> Int -> Int
    divpt_binSearch !ok !ng
      | ng - ok <= 1 = ok
      | (n-mid) - lowind +1 >= mid = divpt_binSearch mid ng
      | otherwise                  = divpt_binSearch ok mid
      where
        mid = (ng + ok) `shiftR` 1
        lowind = geq_binSearch (2*x - as VU.! (n-mid)) (-1) ind_geqx
    geq_binSearch :: Int -> Int -> Int -> Int
    geq_binSearch !goal !ng !ok
      | ok - ng <= 1 = ok
      | as VU.! mid >= goal = geq_binSearch goal ng mid
      | otherwise = geq_binSearch goal mid ok
      where
        mid = (ng + ok) `shiftR` 1


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

typedef long long ll;

ll N;
vector<ll> D;
ll R;

int main() {
  cin >> N;
  D.resize(N);
  for (ll i = 0; i < N; ++i) cin >> D[i];
  for (ll i = 0; i < N; ++i)
    for (ll j = i + 1; j < N; ++j) R += D[i] * D[j];
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int binpow(int a, int b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    double pi=3.1415926;
    int n;
    cin>>n;
    cout<<pi*2*n;
    return 0;
}

Measured memory_bytes: 3780
import sys;input=sys.stdin.readline
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
    import sys
    mod = pow(10, 9) + 7
    sys.setrecursionlimit(pow(10, 8))

NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import deque
N, = map(int, input().split())
d = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

vs = set([1])
stack = [1]
vs_bfs = list()
parents = [0] * (N+1)
while stack:
    v = stack.pop()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        stack.append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d[v]:
        if u == parents[v]:
            continue
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt, mod), t)
        st -= tt
    dp1[v] = t

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
    dp1[v] = mul(
            div2(dp1[p], cmb(N-1, sss[v], mod)),
            cmb(N-1, N-sss[v], mod))

for x in dp1[1:]:
    print(x)


Measured memory_bytes: 124036
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::{ min, max };

macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

#[allow(dead_code)]
const M: u64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let ell: Vec<char> = sc.cin::<String>().chars().collect();
    let mut memo: Vec<Vec<u64>> = vec![vec![0; 2]; ell.len()];
    memo[0][0] = 2;
    memo[0][1] = 1;
    for i in 1..ell.len() {
        match ell[i] {
            '0' => {
                memo[i][0] = memo[i-1][0];
                memo[i][1] = memo[i-1][1] * 3;
                memo[i][1] %= M;
            },
            '1' => {
                memo[i][0] = memo[i-1][0] * 2;
                memo[i][0] %= M;
                memo[i][1] = memo[i-1][1] * 3 + memo[i-1][0];
                memo[i][1] %= M;
            },
            _ => {}
        }
    }
    // for i in 0..ell.len() { trace!(&memo[i]); }
    put!((memo[ell.len()-1][0] + memo[ell.len()-1][1]) % M);
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


Measured memory_bytes: 10492
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define li long
#define pb push_back
#define mem(arr,x) memset(arr,x,sizeof(arr))

ll a[101],n;
ll dp[101][100001];

ll totalWays(ll start,ll k)
{
	if(k==0) return 1;
	if(start<0) return 0;
	if(dp[start][k]!=0) return dp[start][k];
	ll i,ans=0;
	for(i=0;i<=min(a[start],k);i++)
	{
		if(k-i>=0)
		ans=(ans%MOD+totalWays(start-1,k-i)%MOD)%MOD;
	}
	return dp[start][k]=ans%MOD;
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll k,i,j,l;
    cin>>n>>k;
    for(i=0;i<n;i++)
    	cin>>a[i];

    mem(dp,0);

    // top-down
    // cout<<totalWays(n-1,k)<<endl;

    dp[0][0]=1;
    for(i=1;i<=k;i++) dp[0][i]+=dp[0][i-1];

    for(i=1;i<=n;i++)
    {
    	for(j=0;j<=k;j++)
    	{
    		if(j-a[i-1]>0)
    			dp[i][j]=(dp[i-1][j]%MOD-dp[i-1][j-a[i-1]-1]%MOD+MOD)%MOD;
    		else
    			dp[i][j]=dp[i-1][j]%MOD;
    	}
    	for(j=1;j<=k;j++)
    	{
    		dp[i][j]+=dp[i][j-1];
    		dp[i][j]%=MOD;
    	}
    }
    // for(i=0;i<=n;i++)
    // {
    // 	for(j=0;j<=k;j++)
    // 		cout<<dp[i][j]<<" ";
    // 	cout<<endl;
    // }
    cout<<(dp[n][k]-dp[n][k-1]+MOD)%MOD;
    return 0;
}

Measured memory_bytes: 82576
import queue
def main():
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    
    k = int(input())
    q_list = []
    while(len(q_list) <= k):
        value = q.get()
        for i in [-1,0,1]:
            if 0 <= (value%10) + i and (value%10) + i <= 9:
                tmp = 10*value + (value%10) + i
                q.put(tmp)
        q_list.append(value)
    print(q_list[k-1])
    return 

if __name__ == "__main__":
    main()

Measured memory_bytes: 16672
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define MOD ll(1e9+7)
#define MAX_N 100005

ll factorial[MAX_N];
int cnt[MAX_N];

void make_factorial_tableMOD(){
    factorial[0] = 1;
    for(int i = 1; i < MAX_N; i++){
        factorial[i] = factorial[i-1]*i%MOD;
    }
}

ll bisection_powerMOD(ll x,ll y){
    if(y==0)        { return 1; }
    ll t = bisection_powerMOD(x*x%MOD,y/2);
    if(y%2==1)      { t = t*x%MOD; }
    return t;
}

ll nCrMOD(int n, int r){
    if(r<0){return 1;}
    ll a = factorial[n];
    ll b = a*bisection_powerMOD(factorial[r],(MOD-2))%MOD;
    ll c = b*bisection_powerMOD(factorial[n-r],MOD-2)%MOD;
    return c % MOD;
}

int main(){
    int n, a;
    cin >> n;
    int l, r, lo, ro;
    for(int i = 0; i < MAX_N; i++){
        cnt[i] = -1;
    }
    for(int i = 0; i < n+1; i++){
        cin >> a;
        if(cnt[a]==-1){cnt[a] = i;}
        else{l = cnt[a]; r = i;}
    }
    lo = l; ro = n - r;
    make_factorial_tableMOD();
    ll u, v;
    for(int i = 0; i < n+1; i++){
        u = nCrMOD(n+1,i+1);
        v = lo + ro >= i ? nCrMOD(lo+ro,i) : 0LL;
        cout << (u - v + MOD)%MOD << endl;
    }

    return 0;

}


Measured memory_bytes: 2432
S=input()
N=len(S)

dp=[[0 for i in range(N)] for j in range(3)]
sp=[["" for i in range(N)] for j in range(3)]

sp[1][0]=S[0]
sp[2][0]=""
if N>=2:
  for i in range(1,N):
    sp[1][i]=S[i]
    sp[2][i]=S[i-1:i+1]
#print(sp[1])
#print(sp[2])

dp[1][0]=1
dp[2][0]=0

if N==1:
  print(max(dp[1][0],dp[2][0]))
  exit()

dp[1][1]=max(dp[1][0]+1 if sp[1][0]!=sp[1][1] else 0,dp[2][0]+1)
dp[2][1]=1
if N==2:
  print(max(dp[1][1],dp[2][1]))
  exit()

for i in range(2,N):
  dp[1][i]=max(dp[1][i-1]+1 if sp[1][i-1]!=sp[1][i] else 0,dp[2][i-1]+1)
  dp[2][i]=max(dp[1][i-2]+1,dp[2][i-2]+1 if sp[2][i-2]!=sp[2][i] else 0)
#print(*dp[1])
#print(*dp[2])
print(max(dp[1][N-1],dp[2][N-1]))



Measured memory_bytes: 36764
import java.util.Scanner;

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

        int N = sc.nextInt();
        int A[] = new int[N];

        for(int i = 0; i < N; i++)
            A[i] = sc.nextInt();

        int count = 0;
        int flag = 1;
        int tmp;

        while (flag != 0) {
            flag = 0;
            for(int j = N - 1; j > 0; j--) {
                if(A[j] < A[j-1]) {
                    tmp = A[j];
                    A[j] = A[j - 1];
                    A[j - 1] = tmp;
                    flag = 1;
                    count++;
                }
            }
        }
        System.out.print(A[0]);
        for(int i = 1; i < N; i++)
            System.out.print(" " + A[i]);
        System.out.println("");
        System.out.println(count);
    }
}


Measured memory_bytes: 26308
s=input()
first=int(s[0]+s[1])
second=int(s[2]+s[3])
if 1<=first<=12 and 1<=second<=12:
	print("AMBIGUOUS")
elif 1<=first<=12 and (second==0 or second>=13):
		print("MMYY")
elif (first==0 or first>=13) and 1<=second<=12:
		print("YYMM")
else:
		print("NA")

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

template <typename T>
map<T, int> prime_fact(T n) {
  map<T, int> m;
  m[1] = 0;  // 1は素数で割れない
  for (T p = 2; p * p <= n; p++) {
    if (n % p) continue;  // 素因数でない
    int num = 0;
    while (!(n % p)) {  // 素因数で何回割れるかを計算する
      num++;
      n /= p;
    }
    m[p] = num;
  }
  if (n > 1) {  // n自身が素数のときは、素因数は自身のみ
    m[n] = 1;
  }

  return m;
}

int main() {
  ll n;
  cin >> n;
  auto pf = prime_fact<ll>(n);

  ll ans = 0;
  for (auto p : pf) {
    auto pcnt = p.second;
    ll cnt = 1;
    while (pcnt >= cnt) {
      ans++;
      pcnt -= cnt;
      cnt++;
    }
  }

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


Measured memory_bytes: 3616
import math
N=int(input())
kf = (math.sqrt(8*N+1)+1)/2
k = int(kf)
if k!=kf:
    print("No")
else:
    print("Yes")
    print(k)
    for i in range(1,k+1):
        print(k-1, end=' ')
        elements = []
        for j in range((i-1)*(i-2)//2+1,i*(i-1)//2+1):
            elements.append(j)
        for q in range(i+1,k+1):
            elements.append(i + (q-1)*(q-2)//2)
        last = elements.pop()
        for e in elements:
            print(e, end=' ')
        print(last)

Measured memory_bytes: 4488
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  ll ans = 10000000000000;
  for(int i = -100; i <= 100; ++i){
    ll cost = 0;
    rep(j, n){
      cost += pow(a[j] - i, 2);
    }
    ans = min(ans, cost);
  }
  cout  << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <algorithm>

using namespace std;

int main () {
    char x[1001];

    while (true) {
        scanf("%s", x);

        if (x[0] == '0') break;

        int sum = 0;
        for (int i = 0; i < strlen(x); i++) {
            sum += (x[i] - '0');
        }

        cout << sum << endl;
    }
}


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

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

  if((a == 'H' && b == 'H') || (a == 'D' && b == 'D')){
    cout << 'H' << endl;
  }else if((a == 'D' && b == 'H') || (a == 'H' && b == 'D')){
      cout << 'D' << endl;
  }
}


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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	string s;
	cin >> s;

	int ans = INT_MAX;
	for (int i = 0; i < (int)s.size() - 2; i++) {
		ans = min(ans, abs(753 - stoi(s.substr(i, 3))));
	}
	cout << ans << endl;
	return 0;
}


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

int main() {
  int N, T, A;
  cin >> N >> T >> A;
  
  vector<int> sites(N, 0);
  
  for (int i = 0; i < N; i++) cin >> sites.at(i);
  
  double smallestDiff = A + 1000;
  int answer = 0;
  
  for (int i = 0; i < N; i++) {
    if (T - 0.006 * sites.at(i) >= A) {
      if (T - 0.006 * sites.at(i) - A < smallestDiff) {
        smallestDiff = T - 0.006 * sites.at(i) - A;
        answer = i + 1;
      }
    } else {
      if (A - (T - 0.006 * sites.at(i)) < smallestDiff) {
        smallestDiff = A - (T - 0.006 * sites.at(i));
        answer = i + 1;
      }
    }
  }
  
  cout << answer << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	io := newIo()
	defer io.Flush()
	N := io.NextInt()
	X := make([]float64, N)
	Y := make([]float64, N)
	for i := range X {
		X[i], Y[i] = io.NextFloat(), io.NextFloat()
	}
	petterns := 1
	for i := 2; i <= N; i++ {
		petterns *= i
	}
	distance := 0.0
	for i := 0; i < N-1; i++ {
		for j := i + 1; j < N; j++ {
			distance += math.Sqrt(math.Pow(X[i]-X[j], 2) + math.Pow(Y[i]-Y[j], 2))
		}
	}
	fmt.Println(distance * 2 / float64(N))
}

type io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func newIo() *io {
	return &io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *io) PrintIntLn(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func (io *io) PrintStringLn(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}


Measured memory_bytes: 640
W,H,N = map(int,input().split())
x1mx = 0
x2mi = W
y3mx = 0
y4mi = H

for i in range(N):
    x,y,a = map(int,input().split())
    if a == 1:
        if x > x1mx:
            x1mx =x
    elif a == 2:
        if x < x2mi:
            x2mi =x
    elif a == 3:
        if y > y3mx:
            y3mx =y
    elif a ==4:
        if y < y4mi:
            y4mi =y

if x1mx >=x2mi or  y3mx >= y4mi:
    print(0)
else:
    print((x2mi - x1mx)*(y4mi - y3mx))

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

int main(){
  int N, T;
  cin >> N >> T;
  int ans = 0;
  int cost = 1e9;
  for (int i=1; i<=N; i++){
    int c, t;
    cin >> c >> t;
    if (t<=T&&c<cost){
      ans = i;
      cost = c;
    }
  }
  if (ans==0) cout << "TLE" << endl;
  else cout << cost << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int n,x,i;
	scanf(" %d",&n);
	for(i=1;i<=n;i++){
		if(i%3==0){
			printf(" %d",i);
continue;
		}
		x=i;
		while(x){
			if(x%10==3){
				printf(" %d",i);
				break;
			}
			x /=10;
		}
		
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
int main(){
  int r,D;
  cin >> r >> D;
  vector<int> x(11,0);
  cin >> x.at(0);
  for (int i = 1; i < 11; i++){
    x.at(i) = r * x.at(i - 1) - D;
    cout << x.at(i) << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define case int t; cin>>t; while(t--)
using namespace std;

int main()
{
int n;
cin>>n;
vector<vector<int> > v;
v.resize(n,vector<int>(3));
loop(i,0,n){
    loop(j,0,3){
        scanf("%d",&v[i][j]);
    }
}
loop(i,1,n){
    loop(j,0,3){
        v[i][j]=v[i][j]+max(v[i-1][(j+1)%3],v[i-1][(j+2)%3]);
    }
}
int ans=max(v[n-1][0],max(v[n-1][1],v[n-1][2]));
cout<<ans<<endl;
return 0;
}

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

string s;
bool flag=false;

int main()
{
    cin>>s;
    for (int i = 0; i < s.size()-1; ++ i) {
        if (s[i] == s[i+1]) {
            cout << i+1 << " " << i+2 << endl;
            flag = true;
            break;
        } else if (i < s.size()-2 && s[i] == s[i+2]) {
            cout << i+1 << " " << i+3 << endl;
            flag = true;
            break;
         }
    }
    if(flag == false) cout << -1 << " " << -1 << endl;
     return 0;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main()
{
    double v,hei;
    int flo;
    while(cin>>v)
    {
      //hei=v*v/2*9.8;
      hei=v*v/19.6;
      //cout<<hei<<endl;
      flo=(hei+5)/5+1;
      cout<<flo<<endl;
    }
}

Measured memory_bytes: 1224
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<functional>
using namespace std;
typedef long long LL;
inline LL read()
{
	LL kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
int main()
{
	LL x=read();
	LL asd=0;
	asd+=(x/500)*1000;
	x%=500;
	asd+=(x/5)*5;
	printf("%lld\n",asd);
}

Measured memory_bytes: 256
h,w=map(int, input().split())
s=[list(input()) for _ in range(h)]

dx=[1,0]
dy=[0,1]

dp=[[10**9]*(w) for _ in range(h)]
if s[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

for i in range(h):
    for j in range(w):
        for d in range(2):
            new_i=i+dx[d]
            new_j=j+dy[d]
            if h<=new_i or w<=new_j:
                continue
            add=0
            if s[new_i][new_j]=='#' and s[i][j]=='.':
                add=1
            dp[new_i][new_j]=min(dp[new_i][new_j], dp[i][j]+add)

print(dp[-1][-1])


Measured memory_bytes: 9160
require 'prime'

x = gets.chomp.to_i

h = {}
(0..999).each do |i|
  h[i] = i ** 5
  h[-i] = - h[i]
end

def search(x, h)
  (-999..999).to_a.each do |a|
    (-999..999).to_a.each do |b|
      return [a, b] if h[a] - h[b] == x
    end
  end

  return nil
end

ab = search(x, h)
raise if ab.nil?
puts ab.map(&:to_s).join(' ')


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

struct UnionFind{
    vector<int> parent;
    vector<int> rank;
    UnionFind(int n):rank(n+1,0),parent(n+1){
        rep(i,n+1) parent[i]=i;
    }

    int find(int x){
        if (parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if (x==y) return;
        else if(rank[x]<rank[y]) parent[x]=y;
        else{
            parent[y]=x;
            if (rank[x]==rank[y]){
                rank[x]+=1;
            }
        }
    }
};

int main(){
    int n,m;
    cin >> n >>m;
    vector<P> edge;
    rep(i,m){
        int a,b;
        cin >> a >> b;
        P p(a,b);
        edge.push_back(p);
    }
    int count=0;
    rep(i,m){
        UnionFind uf(n);
        rep(j,m){
            if(j==i) continue;
            uf.unite(edge[j].first,edge[j].second);
        }
        if(uf.find(edge[i].second)!=uf.find(edge[i].first)) count++;
    }
    cout << count << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define F first
#define S second
#define pss pair<string,string>
#define pcc pair<char,char>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define piii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define vs vector<string>
#define vl vector<ll>
#define vs vector<string>
#define vll vector<pll>
#define vss vector<pss>
#define vcc vector<pcc>
#define MP make_pair
using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	a=min(a,10);
	cout<<b+100*(10-a)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=0x61=97 '0'=0x30=48
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef string str;
typedef pair<int,int> pairii;
typedef vector<bool> veci;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
int main() {
  string s;
  veci v(26,0);
  cin>>s;
  rep(i,s.size()){
    v[s[i]-97]=1;
  }
  rep(j,26){
    if(!(v[j])){cout<<(char)(j+97)<<endl;return 0;}}
    cout<<"None"<<endl;
}

Measured memory_bytes: 512
a = (1..gets.to_i).inject([]) { |a, i| a << gets.split.map(&:to_i) }
b = (1..3).inject([]) { |b, i| b << Array.new(101, 0) }
3.times { |i| a.size.times { |j| b[i][a[j][i]] += 1 } }
a.size.times { |i| puts (0..2).inject(0) { |sm, j|
    sm + (b[j][a[i][j]] > 1 ? 0 : a[i][j]) } }

Measured memory_bytes: 6112
#include<bits/stdc++.h>
using namespace std;
long long n,a[410],dp[410][410],pref[410];
long long f(long long l,long long r)
{
//	printf("%lld %lld\n",l,r);
	if(r<=l || l>=r) return 0;
	if(dp[l][r]!=-1) return dp[l][r];
	for(long long i=l;i<r;i++)
	{
	//	printf("c = %lld %lld %lld\n",i,i+1,a[i]+a[i+1]);
		if(dp[l][r]==-1)dp[l][r] = f(l,i)+f(i+1,r); 
		else dp[l][r] = min(dp[l][r],f(l,i)+f(i+1,r));
	}
	return dp[l][r]+=pref[r]-pref[l-1];
}
int main()
{
	scanf("%lld",&n);
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		pref[i] = pref[i-1]+a[i];
	}	
	printf("%lld\n",f(1,n));
//	printf("c : \n");
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=i+1;j<=n;j++)
//		{
//			printf("%d %d %lld\n",i,j,dp[i][j]);
//		}
//	}
	return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef vector<int>vi;
 
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fi first
#define se second
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" " ;
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lowbit(a) ((a)&-(a))
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
const int N=4e5+5;
pii e[N];
int n,m,in[N],tin[N],out[N],tout[N]; 
vi G[N],pg[N];
double ans ,dp[N],f[N],p[N];
int x = 0,y = 0;
bool vis[N];
void solve(){
	f[n] = 0;
	rep(i,1,n){
		vis[i] = true;
		if(tin[i])
			p[i] = 1.0/tin[i];
		else p[i] = 0;
		f[i] = 0;
	}
	queue<int> q;
	q.push(n);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(auto v:G[u]){
			if(x!=u || y!=v){
				tin[v]--;
				f[v] += (1+f[u])*p[v];
				if(tin[v] == 0)q.push(v);
			}
		}
	}
	if(vis[1]){
		f[1] = 2000000000;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	rep( i , 1 , m + 1){
		cin>>e[i].fi>>e[i].se;
		G[e[i].se].pb(e[i].fi);
		pg[e[i].fi].pb(e[i].se);
		in[e[i].fi]++;	
	}
	rep( i , 1, n + 1)
		tin[i] = in[i];
	solve();
	rep( i , 1, n + 1)
		dp[i] = f[i];
	ans = dp[1];

	rep(i , 1, n ){
		double mx = 0;
		int v = -1;
		rep( j , 1 ,n + 1)
			tin[j] = in[j],tout[j] = out[j]; 
		
		for(int j = 0 ; j < sz(pg[i]);++j){
			int now = pg[i][j];
			if(mx < dp[now]){
				mx = dp[now];
				v = now;
			}
		}
		if(v!=-1){
			tin[i]--;
			
		}
		x=v,y=i;
	/*	dd(x)
		de(y)*/
		solve(); 
		ans = min(ans,f[1]);
	}
	printf("%0.8f\n",ans);
	return 0;
}

Measured memory_bytes: 35328
import java.util.*;

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

        int n = scanner.nextInt();
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < n; i++) {
            map.put(i, 0);
        }

        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int length = calcLength(i, j, x, y);
                map.put(length, map.get(length) + 1);
            }
        }

        for (int i = 1; i < n; i++) {
            System.out.println(map.get(i));
        }
    }

    private static int calcLength(int i, int j, int x, int y) {
        int a = j - i;
        int b = Math.abs(x - i) + 1 + Math.abs(j - y);
        int c = Math.abs(y - i) + 1 + Math.abs(j - x);

        return Math.min(a, Math.min(b, c));
//        if (i <= x && j >= y) {
//            return ((j - i) - (y - x)) + 1;
//        } else if (i <= x && j < y) {
//            int lengthl = j - i;
//            int lengthr = (y - j) + (x - i) + 1;
//            return Math.min(lengthl, lengthr);
//        } else if (i > x && j >= y) {
//            int lengthl = j - i;
//            int lengthr = (i - x) + (j - y) + 1;
//            return Math.min(lengthl, lengthr);
//        } else {
//            return j - i;
//        }
    }
}


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

int main()
{
  int a[3][3];
  for (int i=0; i<3; i++) {
    for (int j=0; j<3; j++)
      cin >> a[i][j];
  }
  int n;
  cin >> n;
  int b;
  for (int k=0; k<n; k++) {
    cin >> b;
    for (int i=0; i<3; i++) {
      for (int j=0; j<3; j++)
        if (a[i][j] == b) a[i][j] = 0;
    }
  }
  for (int i=0; i<3; i++) {
    for (int j=0; j<3; j++) {
      if (a[i][j] != 0) break;
      if (j == 2) {
        cout << "Yes";
        return 0;
      }
    }
  }
  for (int j=0; j<3; j++) {
    for (int i=0; i<3; i++) {
      if (a[i][j] != 0) break;
      if (i == 2) {
        cout << "Yes";
        return 0;
      }
    }
  }
  for (int k=0; k<3; k++) {
    if (a[k][k] != 0) break;
    if (k == 2) {
      cout << "Yes";
      return 0;
    }
  }
  for (int k=0; k<3; k++) {
    if (a[k][2-k] != 0) break;
    if (k == 2) {
      cout << "Yes";
      return 0;
    }
  }
  cout << "No";
  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

main(){
  int a,b,c,d,p;
  int i;
  int ansX=0,ansY=0;

  scanf("%d",&a );
  scanf("%d",&b );
  scanf("%d",&c );
  scanf("%d",&d );
  scanf("%d",&p );

  // X社の水道料金
  ansX = a*p;

  // Y社の水道料金
  if(c>=p){
    ansY = b;
  }else{
    ansY = b+d*(p-c);
  }

  if(ansX>ansY){
    printf("%d\n",ansY );
  }else{
    printf("%d\n",ansX );
  }
}



Measured memory_bytes: 2120
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
#define Mod 1e9+7
const LL mod=1e9+7;
const LL inf=1e10;
using namespace std;
int main()
{
    LL a,n;
    scanf("%lld%lld",&a,&n);
    if(n==100)
		n++;
	printf("%d",n);
    if(a==1)
        printf("00\n");;
    if(a==2)
        printf("0000\n",n);
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_p
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

int N;
vector<int> g[112345];
LL dp[112345][2];
constexpr int mod = 1e9+7;
void dfs(int v,int p){
    LL allw = 0;
    dp[v][0]=1;
    dp[v][1]=1;
    for(int u:g[v]){
        if(u==p)continue;
        dfs(u,v);
        dp[v][1]*=dp[u][0];
        dp[v][0]*=(dp[u][0]+dp[u][1])%mod;
        dp[v][0]%=mod;
        dp[v][1]%=mod;
    }
}
int main(){
    cin>>N;
    for(int i:range(N-1)){
        int x,y;
        cin>>x>>y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0,0);
    cout<<(dp[0][0]+dp[0][1])%mod<<endl;
    return 0;
}

Measured memory_bytes: 14592
#include<stdio.h>
#define Mod 1000000007
long long powermod(long long a,long long b)
{
	long long ans=1;
	a=a%Mod;
	while(b>0)
	{
		if(b%2 == 1)
			ans=(ans*a)%Mod;
		b=b/2;
		a=(a*a)%Mod;
	}
	return ans;
}
int main()
{
	int N,flag=1,a[100000+10],b[100000+10]={0};
	scanf("%d",&N);
	for(int i=0; i<N; i++)
	{
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	if(N % 2 == 0)
	{
		for(int i=1; i<N; i+=2)
		{
			if(b[i] != 2)
				flag=0;
		}
	}	
	else
	{
		if(b[0] != 1)
			flag=0;
		for(int i=2; i<N; i+=2)
		{
			if(b[i] != 2)
				flag=0;
		}
	}
	if(flag)
		printf("%lld\n",powermod(2,N/2));
	else
		printf("0\n");
	return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  a = a + b;
  c = c + d;
  if (a == c) {
    cout << "Balanced" << endl;
  }else if(a < c) {
    cout << "Right" << endl;
  }
  else {
    cout << "Left" << endl;
  }
}

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

//bool cmp(pair<int, int>a, pair<int, int>b){if(a.first==b.first) return a.second > b.second;  else return a.first<b.first;   }
//bool valid(int i, int j){ return 0 <= i&&i < n && 0 <= j&&j < m; }
#define ll long long
#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define Sc(a) scanf ("%I64d", &a)
#define sc(a) scanf ("%d", &a)
#define fi first
#define se second
#define siz 10000005

const ll INF = (1ll<<62);
const ll mod = 1e8;
typedef pair<int,int> pii;
typedef pair<int,pii > pip;
typedef pair< pair<int ,int> , pair<int ,int > > ppp;
vector<tuple<int,int,int> >tup;




//variables



int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
      //freopen("katryoshka.in","r",stdin);
     //freopen("output.txt","w",stdout);
    //memset(dist, MEMSET_INF, sizeof dist);
   //memset(dp, -1, sizeof dp);


    int n,K; cin>>n>>K;
    int dp[100005],arr[100005];

    memset(dp,127,sizeof dp);

    for(int i=0;i<n;i++)
        cin>>arr[i];

    dp[0]=0;
    for(int i=0;i<n;i++){
        for(int k=1;k+i<n&&k<=K;k++){
            dp[k+i]=min(dp[k+i],dp[i]+abs(arr[i]-arr[k+i]));
        }
    }

    cout<<dp[n-1];

    return 0;
}


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

typedef long long ll;
#define type(a) typeid(a).name();
#define print(arr) cout << "[" ;for(unsigned int i=0;i<(unsigned int) arr.size();i++){ (i==arr.size()-1)?cout << arr[i]:cout << arr[i] << ",";}cout << "]" << endl
#define Arr(arr,l) cout << "[" ;for(unsigned int i=0;i<(unsigned int) l;i++){ (i==l-1)?cout << arr[i]:cout << arr[i] << ",";}cout << "]" << endl
#define console(arr) cout << "["<<endl; for(ll i=0;i<(ll)arr.size();++i){cout << " [";for(ll j=0;j<(ll)arr[i].size();++j){(j==(int)arr[i].size()-1)?cout << arr[i][j]:cout << arr[i][j] << ",";}cout << "]"<<endl;} cout << "]"<<endl
int main(){
   int n;
   cin >> n;
   if(n==1){
	   cout << "Yes";
   }else{
   bool check = false;
   for(int i=1;i<10;++i){
	   if(n%i == 0 && n/i < 10){
		   check = true;
		   break;
	   }
   }
   if(check==true){
	   cout << "Yes";
   }else{
	   cout << "No";
   }
  }
}  

















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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
int A[1000],B[1000],C[1000];
int deg[1000];
vpint G[1000];
int dist[1000];
void dfs(int v,int p,int d){
    dist[v]=d;
    for(auto &e:G[v]){
        if(e.fi==p)continue;
        dfs(e.fi,v,d+e.se);
    }
}
void solve(){
    memset(deg,-1,sizeof(deg));
    rep(i,N)G[i].clear();
    rep(i,N-1){
        deg[A[i]]++;deg[B[i]]++;
    }

    int ans=0;
    rep(i,N-1){
        if(deg[A[i]]&&deg[B[i]]){
            G[A[i]].pb(pint(B[i],C[i]));
            G[B[i]].pb(pint(A[i],C[i]));
            ans+=C[i]*3;
        }
        else{
            ans+=C[i];
        }
    }

    int v=-1;
    rep(i,N)if(deg[i])v=i;
    if(v==-1){
        cout<<ans<<endl;
        return;
    }

    dfs(v,-1,0);
    rep(i,N)if(deg[i]&&dist[i]>dist[v])v=i;
    dfs(v,-1,0);
    rep(i,N)if(deg[i]&&dist[i]>dist[v])v=i;
    ans-=dist[v];
    cout<<ans<<endl;
}

signed main(){
    while(cin>>N,N){
        rep(i,N-1){
            cin>>B[i];B[i]--;
            A[i]=i+1;
        }
        rep(i,N-1)cin>>C[i];
        solve();
    }
    return 0;
}

Measured memory_bytes: 3252