akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <stack>
#include <cctype>
#include <cmath>

using namespace std;

/* typedef */
typedef long long ll;

/* class */
class Node {
public:
    int p,
        l,
        r;
    string alpha;
    Node() {};
};

/* constant */
static const int NIL = -1;
static const int MAX = 60;
static const int INF = 1 << 30;
static const int mod = 1000000007;
static const double pi = 3.141592653589;

/* global variables */
using p_i_s = pair<int, string>;
Node T[MAX];
string S;
map<string, int> freq;  // frequency infomation
map<string, int> huff;  // huffman code length
priority_queue< p_i_s, vector<p_i_s>, greater<p_i_s>> PQ;
int indNode = 0;

/* function */
void makeHuffmanTree();
bool allDigit(string s);
int findRoot();
void makeHuffmanCode(int ind, int len);

/* main */
int main(){

    cin >> S;
    string key;
    for (int i = 0; i < S.size(); i++) {
        key = S[i];
        freq[key]++;
    }

    if (freq.size() == 1) {
        key = S[0];
        cout << freq[key] << '\n';
        return 0;
    }

    for (auto m : freq) {
        PQ.push(make_pair(m.second, m.first));
    }

    makeHuffmanTree();

    int root = findRoot();
    makeHuffmanCode(root, 0);

    int cnt;
    int ans = 0;
    for (auto m : freq) {
        key = m.first;
        cnt = m.second;
        ans += huff[key] * cnt;
    }

    cout << ans << '\n';

}


void makeHuffmanTree() {
    // variable
    int l_ind, r_ind, p_ind;
    p_i_s l, r;
    // init
    for (int i = 0; i < MAX; i++) {
        T[i].p = T[i].l = T[i].r = NIL;
        T[i].alpha = ".";
    }

    while (PQ.size() > 1) {
        l = PQ.top();
        PQ.pop();
        r = PQ.top();
        PQ.pop();
        if (allDigit(l.second))
            l_ind = stoi(l.second);
        else {
            l_ind = indNode++;
            T[l_ind].alpha = l.second;
        }
        if (allDigit(r.second))
            r_ind = stoi(r.second);
        else {
            r_ind = indNode++;
            T[r_ind].alpha = r.second;
        }
        p_ind = indNode++;
        T[p_ind].l = l_ind;
        T[p_ind].r = r_ind;
        T[l_ind].p = p_ind;
        T[r_ind].p = p_ind;
        T[p_ind].alpha = to_string(p_ind);
        PQ.push(make_pair(l.first + r.first, to_string(p_ind)));
    }
}


bool allDigit(string s) {
    if (std::all_of(s.cbegin(), s.cend(), [](char ch) 
        { return isdigit(ch);}) ) 
        return true;
    else return false;
}


int findRoot() {
    int root_ind = 0;
    for (int i = 0; i < MAX; i++) {
        if (T[i].p == -1 && allDigit(T[i].alpha))
            root_ind = i;
    }
    return root_ind;
}


void makeHuffmanCode(int ind, int len) {
    // leaf Node
    if (T[ind].l == NIL && T[ind].r == NIL) {
        huff[T[ind].alpha] = len;
        return;
    }
    if (T[ind].l != NIL) 
        makeHuffmanCode(T[ind].l, len + 1);
    if (T[ind].r != NIL) 
        makeHuffmanCode(T[ind].r, len + 1);

}



Measured memory_bytes: 3428
<?php

$max = 1 - 10**9;
fscanf(STDIN, '%d', $count);
for ($i = 0; $i < $count; $i++) {
  fscanf(STDIN, '%d', $num);
  if($i == 0){
    $min = $num;
  }else{
    if($num - $min > $max){
      $max = $num - $min;
    }
  }
  
  if($min > $num){
    $min = $num;
  }
}

echo $max . PHP_EOL;



Measured memory_bytes: 9216
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
    }

    let s = (n as f64).sqrt() as usize;
    let mut a = 0;
    let mut b = 0;
    for i in (1..s+1).rev() {
        if n%i==0 {
            a = n/i;
            b = i;
            break;
        }
    }

    let mut cnt = 0;
    loop {
        cnt += 1;
        a /= 10;
        if a==0 {
            break;
        }
    }

    let mut cnt1 = 0;
    loop {
        cnt1 += 1;
        b /= 10;
        if b==0 {
            break;
        }
    }
    println!("{}", max(cnt,cnt1));
}


Measured memory_bytes: 2168
#include<iostream>

using namespace std;

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

  int J[m+1][n+1], O[m+1][n+1], I[m+1][n+1];

  for(int i = 0; i <= m; i++){
    for(int j = 0; j <= n; j++){
      J[i][j] = 0;
      O[i][j] = 0;
      I[i][j] = 0;
    }
  }

  for(int i = 1; i <= m; i++){
    for(int j = 1; j <= n; j++){
      char c;
      cin >> c;
      if(c == 'J') J[i][j]++;
      else if(c == 'O') O[i][j]++;
      else I[i][j]++;
    }
  }

  for(int i = 1; i <= m; i++){
    for(int j = 0; j <= n; j++){
      J[i][j] += J[i-1][j];
      O[i][j] += O[i-1][j];
      I[i][j] += I[i-1][j];
    }
  }
  for(int i = 0; i <= m; i++){
    for(int j = 1; j <= n; j++){
      J[i][j] += J[i][j-1];
      O[i][j] += O[i][j-1];
      I[i][j] += I[i][j-1];
    }
  }

  for(int i = 0; i < k; i++){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans_j , ans_o, ans_i;
    ans_j = J[c][d] - J[a-1][d] - J[c][b-1] + J[a-1][b-1];
    ans_o = O[c][d] - O[a-1][d] - O[c][b-1] + O[a-1][b-1];
    ans_i = I[c][d] - I[a-1][d] - I[c][b-1] + I[a-1][b-1];

    cout << ans_j << " " << ans_o << " " << ans_i << endl;
  }
}



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

using namespace std;

int main(){

    int  L,R,d;

    cin >> L >> R>>d;

    int temp=0;
    for(int i=L;i<R+1;++i){
        if(i % d ==0){
            temp++;
        }
    }

    cout<<temp<<endl;


}



Measured memory_bytes: 3620
//    _____ _     _                _           _     _ _     _     
//    \_   \ |_  (_)___  __      _| |__   __ _| |_  (_) |_  (_)___ 
//     / /\/ __| | / __| \ \ /\ / / '_ \ / _` | __| | | __| | / __|
//  /\/ /_ | |_  | \__ \  \ V  V /| | | | (_| | |_  | | |_  | \__ \
//  \____/  \__| |_|___/   \_/\_/ |_| |_|\__,_|\__| |_|\__| |_|___/
//                                                                 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int sz=1e6+9;
int n;
int a;

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a;
		if((a&1)==0){
			if(a%5==0||a%3==0) continue;
			else{
				cout<<"DENIED";
				return 0;
			}
		}
	}	
	cout<<"APPROVED";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<map>
using namespace std;
typedef long long ll;



int main() {
	int N; cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) cin >> v[i];
	sort(v.begin(), v.end());

	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans += v[i];
	}
	
	bool check = false;

	// 全部足して10の倍数でなければそれが解
	if (ans % 10 != 0) {
		cout << ans << endl;
		check = true;
	}
	
	// 小さい値から引いてく
	for (int i = 0; i < N && check == 0; i++) {
		if ((ans - v[i]) % 10 != 0) {
			cout << ans - v[i] << endl;
			check = true;
		}
	}

	if (check == false) cout << 0 << endl;

	return 0;
}

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

/* define const */

/* finish defineing const */

int n, a, b;
long k[55] = {1};
long rk[55] = {1};
vector<long> v;

long combination(long n, long r)
{
    long nn = n;
    long rmx = max(r, n - r);
    long rmn = min(r, n - r);

    long ans = 1;

    bool *b = (bool *)malloc((int)sizeof(bool) * (rmn + 1));
    for (long i = 0; i <= rmn; i++)
    {
        b[i] = false;
    }
    /*
    for (int i = 0; i <= rmn; i++)
    {
        cout << b[i] << " ";
    }
    cout << endl;
*/
    for (long i = nn; i > rmx; i--)
    {
        long tmp = i;
        for (long j = rmn; j >= 2; j--)
        {
            if (tmp % j == 0 && b[j] == false)
            {
                tmp /= j;
                b[j] = true;
            }
        }
        ans *= tmp;
        //        cout << tmp << " ";
    }
    //    cout << endl;
    /*
    cout << "~~" << ans << endl;
    for (int i = 0; i <= rmn; i++)
    {
        cout << b[i] << " ";
    }
    cout << endl;
*/
    for (long i = 2; i <= rmn; i++)
    {
        if (b[i] == false)
        {
            ans /= i;
        }
    }
    return ans;
}

long cnt_num(long j, long x)
{
    long n = 0;
    long r = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == x && i <= j)
        {
            n++;
            r++;
        }
        else if (v[i] == x)
        {
            n++;
        }
    }
    //    cout << n << " " << r << endl;
    //    cout << "n = " << n << ", r = " << r << endl;
    return combination(n, r);
}

int main()
{
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++)
    {
        long tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    // input

    // make_table();

    sort(v.begin(), v.end(), greater<long>());
    /*
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
*/
    long double avg_m = -1;
    long cnt = 0;
    for (int i = b; i >= a; i--)
    {
        long double avg_tmp = 0;
        long s, b;
        long cnt_t;

        for (int j = 0; j < i; j++)
        {
            //            cout << v[j];
            avg_tmp += v[j];
        }
        //      cout << "===" << avg_tmp << endl;

        avg_tmp /= i;
        cnt_t = cnt_num(i - 1, v[i - 1]);
        //        cout << "=" << avg_tmp << endl;
        if (avg_tmp > avg_m)
        {
            avg_m = avg_tmp;
            cnt = cnt_t;
        }
        else if (avg_tmp == avg_m)
        {
            cnt += cnt_t;
        }
    }
    cout << fixed << avg_m << endl;
    cout << cnt << endl;
}


Measured memory_bytes: 256
{-# LANGUAGE
    BangPatterns, MultiWayIf, TupleSections, TypeApplications #-}
{-# OPTIONS_GHC -O2 #-}


import Control.Arrow
import Control.Concurrent
import Control.Monad
import qualified Data.ByteString.Builder as B
import qualified Data.ByteString.Char8 as C
import Data.Complex
import Data.Char
import Data.Function
import Data.Function.HT
import qualified Data.IntMap.Strict as IM
import qualified Data.IntSet as IS
import Data.List
import Data.Monoid
import Data.Ord
import qualified Data.Sequence as Sq
import Data.Vector.Algorithms.Search
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Debug.Trace
import System.IO


------------------
-- #   Read   # --
------------------

r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine



main :: IO ()
main = do
    s <- getLine
    t <- getLine
    print $ length $ filter not $ zipWith (==) s t


Measured memory_bytes: 19912
#include <bits/stdc++.h>
using namespace std;
using ll = int_fast64_t;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr)
#define digit(N) cout << fixed << setprecision((N))
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

int H, W, K;
vector<string> grid;
vector<vector<int>> d;

void bfs(int sx, int sy)
{
	queue<pair<int, int>> que;
	que.push({sx, sy});
	d[sx][sy] = 0;
	int dx[] = {-1, 0, 1, 0};
	int dy[] = {0, 1, 0, -1};

	while (!que.empty())
	{
		auto v = que.front();
		que.pop();

		for (int i = 0; i < 4; i++)
		{
			for (int j = 1; j <= K; j++)
			{
				int nx = v.first + dx[i] * j, ny = v.second + dy[i] * j;
				if (nx < 0 || nx >= H || ny < 0 || ny >= W)
					break;
				if (grid[nx][ny] == '@')
					break;

				if (d[nx][ny] != -1 && d[nx][ny] <= d[v.first][v.second])
					break;

				if (d[nx][ny] != -1)
					continue;

				d[nx][ny] = d[v.first][v.second] + 1;
				que.push({nx, ny});
			}
		}
	}
}

int main()
{
	fast();

	cin >> H >> W >> K;
	int sx, sy, gx, gy;

	cin >> sx >> sy >> gx >> gy;
	sx--, sy--, gx--, gy--;
	grid = vector<string>(H);
	d = vector<vector<int>>(H, vector<int>(W, -1));

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

	bfs(sx, sy);

	cout << d[gx][gy] << "\n";
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define STR(i,str) for(int i=0;(str)[i];i++)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX3(a,b,c) ((a)>(b)?(a)>(c)?(a):(c):(b)>(c)?(b):(c))
#define MIN3(a,b,c) ((a)<(b)?(a)<(c)?(a):(c):(b)<(c)?(b):(c))
#define RNG(a,b) ((a)>(b)?(a)-(b):(b)-(a))
#define RNG3(a,b,c) ((a)>(b)?(b)>(c)?(a)-(c):(c)>(a)?(c)-(b):(a)-(b):(b)>(c)?(c)>(a)?(b)-(a):(b)-(c):(c)-(a))
#define MAXS(a,b) {if((a)<(b))(a)=(b);}
#define MINS(a,b) {if((a)>(b))(a)=(b);}

#define INF 2147483647

int main(){
	int n, k, *a, ans = 0;
	scanf("%d%d", &n, &k);
	a = (int *)malloc(sizeof(int) * n);
	for(int i = 0; i < n; i++){
		scanf("%d", a + i);
		int k = i, tmp = a[i];
		while(tmp > a[(k-1)/2]) a[k] = a[(k-1)/2], a[k = (k-1)/2] = tmp;
	}
	for(int i = n - 1; i >= n - k; i--){
		ans += a[0];
		int k = 0, tmp = a[0] = a[i];
		a[i] = -INF;
		for(;;)
			if(k < i/2)
				if(tmp < a[k*2 + 1])
					if(a[k*2 + 1] > a[k*2 + 2])
						a[k] = a[k*2 + 1], a[k = k*2 + 1] = tmp;
					else goto Label;
				else if(tmp < a[k*2 + 2]) Label:
					a[k] = a[k*2 + 2], a[k = k*2 + 2] = tmp;
				else break;
			else break;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 128
//author rhythmicankur
                                                                  //god_is_almighty
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
#include<bits/stdc++.h>
#define f 		first
#define s 		second
#define int     long long
#define ll      int
#define ld 		long double
#define pb 		push_back
#define eb 		emplace_back
#define mk 		make_pair
#define vi 		vector<int>
#define pii 		pair<int,int>
#define pip             pair<int,pii>
#define vpi 		vector<pii>
#define sbcount(x) __builtin_popcountll(x)
#define REP(i,n) for (int i = 1; i <= n; i++)
#define trav(a, x)      for(auto& a : x)
#define all(x)          x.begin(), x.end()
#define fill(a,val)	memset(a,val,sizeof(a))
#define 	PI acos(-1)
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define M1 	998244353
#define M2 	1000000007
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); } 
#define test4(x,y,z,a) 		    cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<"  |  "<<#a<<": "<<a<<endl;
#define test1(x)                cerr<<#x<<": "<<x<<endl
#define test2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define test3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
ll power(ll a,ll b,ll m=M2){ll answer=1;while(b){if(b&1)answer=(answer*a)%m;b/=2;a=(a*a)%m;}return answer;}
using namespace std;
void ctrl(){cout<<"Control"<<endl;}
int make_num(string p){stringstream geek(p); int x = 0; geek >> x;return x;}
string make_str(int x){ostringstream str1; str1 << x; string geek = str1.str(); return geek;}

signed main()
{	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin.exceptions(cin.failbit);
	int A;
    cin>>A;
    int x = A + A*A + A*A*A;
    cout<<x;

return 0;
}

Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
long long int fib[1000],i,n;
int main()
{
	cin>>n;
	memset(fib,0,sizeof(fib));
	fib[0]=2;
	fib[1]=1;
	for(i=2;i<=n;i++)
		fib[i]=fib[i-1]+fib[i-2];
	cout<<fib[n];
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;
int divr[maxn];
/*ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}*/
void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
 
 
 
 
 














int main()
{
     int n;
     cin>>n;
     int a[n];
     for(int i=0;i<n;i++)cin>>a[i];
     int cost=0;
     for(int i=1;i<=100;i++)
     {
          int l=-1;
          for(int j=0;j<n;j++)
          {
               if(a[j]&&l==-1)
               {
                    a[j]-=1;l=j;
               }
               else if(a[j]&&l!=-1){
                    a[j]-=1;
               }
               else if(a[j]==0&&l!=-1){
                    cost++;l=-1;
               }
          }
          if(l!=-1){cost++;l=-1;}
     }
     cout<<cost;
}




















 
 
 
 
 

















Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
struct matrix{
	int a[2][2];
	matrix(){memset(a,0,sizeof a);}
	matrix(int A,int B,int C,int D){a[0][0]=A,a[0][1]=B,a[1][0]=C,a[1][1]=D;}
	int*operator[](int x){return a[x];}
};
matrix operator*(matrix a,matrix b){
	matrix c;
	for(int j=0;j<2;++j)
		for(int i=0;i<2;++i)
			for(int k=0;k<2;++k)
				c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%mod;
	return c;
}
matrix pow(matrix x,ll y){
	matrix ret(1,0,0,1);
	while(y){
		if(y&1)ret=ret*x;
		x=x*x;y>>=1;
	}
	return ret;
}
char map[1010][1010];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),m=gi();ll K=gi();
	for(int i=1;i<=n;++i)scanf("%s",map[i]+1);
	bool L=0,U=0;
	for(int i=1;i<=n;++i)L|=map[i][1]==map[i][m]&&map[i][1]=='#';
	for(int i=1;i<=m;++i)U|=map[1][i]==map[n][i]&&map[1][i]=='#';
	int cnt=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			cnt+=map[i][j]=='#';
	if((L&U)||!K)return puts("1"),0;
	if(!(L|U))return printf("%d\n",pow({cnt,0,0,0},K-1)[0][0]),0;
	if(U){
		int mx=std::max(n,m);
		for(int i=1;i<=mx;++i)
			for(int j=i;j<=mx;++j)
				std::swap(map[i][j],map[j][i]);
		std::swap(n,m);
	}
	int a=0,b=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<m;++j)a+=map[i][j]=='#'&&map[i][j+1]=='#';
		b+=map[i][1]=='#'&&map[i][m]=='#';
	}
	matrix s=matrix{1,1,0,0}*pow({cnt,0,mod-a,b},K-1);
	printf("%d\n",s[0][0]);
	return 0;
}


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

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    unordered_set<string> st;
    for(int i=0; i<n; ++i) {
        string s; cin >> s;
        st.insert(s);
    }
    cout << st.size();
    return 0;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<char> vec(W+2,'#');
  for (int i=0;i<W+2;i++){
    cout << vec.at(i);
  }
  cout << endl;
  string str;
  for (int j=0;j<H;j++){
    cin >> str;
    for (int i=0;i<W;i++){
      vec.at(i+1)=str.at(i);
    }
    for (int i=0;i<W+2;i++){
      cout << vec.at(i);
    }
    cout << endl;
  }
  vec = vector<char>(W+2,'#');
  for (int i=0;i<W+2;i++){
    cout << vec.at(i);
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s; cin >> s;
	int k; cin >> k;
	int n = s.size();
	for(int i = 0; i < n; i++){
		int dist = ('z' - s[i] + 1) % 26;
		if(dist <= k){
			s[i] = 'a';
			k -= dist;
		}
	}
	if(k){
		k %= 26;
		s.back() = ((s.back() - 'a' + k) % 26) + 'a';
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 512
/****************************>>>>HEADFILES<<<<****************************/
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
using namespace std;
/****************************>>>>>DEFINE<<<<<*****************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define FIN             freopen("input.txt","r",stdin)
#define rep(i,a,b)      for(int i = a;i <= b;i++)
#define MP(a,b)         make_pair(a,b)
#define PB(a)           push_back(a)
#define fst             first
#define snd             second
/****************************>>>>>>DEBUG<<<<<<****************************/
#define out(x)          cout<<x<<"  ";
/****************************>>>>SEPARATOR<<<<****************************/
int v[50];
int c[50];
int t[50];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    rep(i,1,n)cin>>v[i];
    rep(i,1,n)cin>>c[i];
    rep(i,1,n)t[i]=v[i]-c[i];
    int ans=0;
    rep(i,1,n)if(t[i]>0)ans+=t[i];
    cout<<ans<<endl;
}


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

using namespace std;
using ll = long long;

const long long MOD = 1000000007;
int main() {
    ll N = 0;
    cin >> N;
    ll K = 0;
    cin >> K;
    ll countp = 0, countz = 0, countn = 0;
    vector<ll> A(N,0);
    for(ll i = 0; i < N; i++) {
    cin >> A.at(i);
    if (A.at(i) > 0)countp++;
    else if (A.at(i) == 0)countz++;
    else countn++;
    }

    sort(A.begin(),A.end());
    ll ans = 1;
    ll getp;
    ll getn;
    
    if ((countp + countz == 0)&&((K-1)%2))
    {
        //cout << 1 << endl;
        for (size_t i = 0; i < K; i++)
        {
            
            ans = ((ans*A.at(i)%MOD)+MOD)%MOD;
        }
        cout << ans << endl;
        return 0;
    }else if ((countp + countz == 0)&&(K%2))
    {
        //cout << 1 << endl;
        for (size_t i = 0; i < K; i++)
        {
            
            ans = ((ans*A.at(N-1-i)%MOD)+MOD)%MOD;
        }
        cout << ans << endl;
        return 0;
    }
    

    if (K%2)
    {
        getn = 0;
        getp = 0;
        ans = A.at(N-1);
        for (size_t i = 0; i < K-1; i += 2)
        {
            if (A.at(N-2-getp)*A.at(N-3-getp) >= A.at(getn)*A.at(getn+1))
            {
                ans = ((ans*A.at(N-2-getp)%MOD)+MOD)%MOD;
                ans = ((ans*A.at(N-3-getp)%MOD)+MOD)%MOD;
                getp += 2;
            }
            else
            {
                ans = ((ans*A.at(getn)%MOD)+MOD)%MOD;
                ans = ((ans*A.at(1+getn)%MOD)+MOD)%MOD;
                getn += 2;
            }
            
        }
        cout << ans << endl;
        
        
    }else
    {
        getn = 0;
        getp = 0;
        for (size_t i = 0; i < K; i += 2)
        {
            //cout << ans << endl;
            if (A.at(N-2-getp)*A.at(N-1-getp) >= A.at(getn)*A.at(getn+1))
            {
                ans = ((ans*A.at(N-2-getp)%MOD)+MOD)%MOD;
                ans = ((ans*A.at(N-1-getp)%MOD)+MOD)%MOD;
                getp += 2;
            }
            else
            {
                ans = ((ans*A.at(getn)%MOD)+MOD)%MOD;
                //cout << ans << endl;
                //cout << ans*A.at(1+getn) << endl;
                ans = ((ans*A.at(1+getn)%MOD)+MOD)%MOD;
                getn += 2;
            }
            
        }
        cout << ans << endl;
    }
    
    



    return 0;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
ll const INF = 314159;

int main()
{
    ios_base::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    if(n<=8 && m<=8)
    {
        cout<<"Yay!"<<endl;
    }
    else
    {
        cout<<":("<<endl;
    }
    return 0;
}
//920430017


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N;cin >> N;
  bool sat = true;
  rep(i,N){
    int x;cin >> x;
    if(x%2==0){
      if(x%3!=0 && x%5!=0) sat = false;
    }
  }
  if(sat) cout << "APPROVED" << endl;
  else cout << "DENIED" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp> 
//using boost::multiprecision::cpp_int;
using namespace std;
#define ll long long int
#define F first
#define S second
//#define endl "\n"
//#define nl cout<<endl;
#define pb push_back
#define ull unsigned long long 
#define f(i,a,b) for(ll i=a;i<b;i++)
#define Knucklehead ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define mod 100000007
#define mat vector<vector<ll>>
mat cn(ll n, ll m){return vector< vector<ll> >(n, vector<ll>(m));}
bool compare(char &s1,char &s2){return s1 > s2;} 
bool sortmahstyle(const pair<ll,ll> &a,  const pair<ll,ll> &b) 
{ 
    if(a.second > b.second )
        return true;
    if( a.second==b.second && a.first > b.second )
       return true;
    return false;
}
bool cmp(int n, pair<int, int> const& p)
{
    return (p.first < n);
}
//me
ll const mod = 1e9+7;//998244353;
ll const inf = 1e18;
ll const maxn = 1e5+1;


void solve()
{    
     
     
     ll a,b ; cin >> a >> b;

     if(a>=13)
          cout << b ;
     else if(a>=6 && a<=12)
          cout << b/2; 
     else
          cout << 0;
}

int main() {
Knucklehead 
//*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
/**/ 
        
          ll t;
          /**/t=1;
          /*/cin>>t;/**/
          f(testcases,0,t){
               //cout << "Case #" <<testcases+1<<": ";
               solve();
          }
 
 
    return 0;
}

Measured memory_bytes: 3520
#include <iostream>
using namespace std;
#define MAX 10000
#define NIL -1

struct Node   {int p, l, r;};
Node T[MAX];
int n;
void preParse(int u)
{
    if(u == NIL)  return;
    cout << " " << u;
    preParse(T[u].l);
    preParse(T[u].r);
}
void inParse(int u)
{
    if(u == NIL)   return;
    inParse(T[u].l);
    cout << " " << u;
    inParse(T[u].r);
}
void postParse(int u)
{
    if(u == NIL)   return;
    postParse(T[u].l);
    postParse(T[u].r);
    cout << " " << u;
}
int main()
{
    int v, l, r, root;
    cin >> n;
    for(int i=0; i<n; i++)
        T[i].p = NIL;
    for(int i=0; i<n; i++)
    {
        cin >> v >> l >> r;
        T[v].l = l;
        T[v].r = r;
        if(l != NIL)   T[l].p = v;
        if(r != NIL)   T[r].p = v;
    }
    for(int i=0; i<n; i++)
    {
        if(T[i].p == NIL)
            root = i;
    }
    cout << "Preorder" << endl;
    preParse(root);
    cout << endl;
    cout << "Inorder" << endl;
    inParse(root);
    cout << endl;
    cout << "Postorder" << endl;
    postParse(root);
    cout << endl;
    return 0;
}

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader in = new BufferedReader(
			new InputStreamReader(System.in));
		while (true) {
			String[] inputs = in.readLine().split(" ");
			int h = Integer.parseInt(inputs[0]);
			int w = Integer.parseInt(inputs[1]);
			if ((h == 0) && (w == 0)) {
				break;
			}
			for (int i = 0; i < w; ++i) {
				System.out.print("#");
			}
			System.out.println();
			for (int j = 2; j < h; ++j) {
				System.out.print("#");
				for (int i = 2; i < w; ++i) {
					System.out.print(".");
				}
				System.out.println("#");
			}
			for (int i = 0; i < w; ++i) {
				System.out.print("#");
			}
			System.out.println();
			System.out.println();
		}
		in.close();
	}
}

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

const int INF=1e9+1;
const int V_MAX=1e5+1;

int main() {
  int n,W; cin>>n>>W;
  vector<int> w(n),v(n);
  rep(i, n) cin>>w[i]>>v[i];

  vector<vector<int>> dp(n+1, vector<int>(V_MAX, INF));
  dp[0][0]=0;
  rep(i, n) {
    rep(j, V_MAX) {
      if (j-v[i]>=0) dp[i+1][j]=min(dp[i][j], dp[i][j-v[i]]+w[i]);
      else dp[i+1][j]=dp[i][j];
    }
  }
  int res=0;
  rep(i, V_MAX) {
    if (dp[n][i]<=W) res=max(res, i);
  }
  cout<<res<<endl;
}


Measured memory_bytes: 40192
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

int n, x;
int length[51], p[51];
int ans = 0;

void calc(int lv, int r){
    if(lv == 0){
        if(r == 0) ans++; 
        return;
    }
    if(r == length[lv] - 1){
        ans += p[lv]; return;
    }
    if(r == 0) return;
    if(r <= length[lv - 1]){
        calc(lv - 1, r - 1); return;
    }
    calc(lv - 1, length[lv - 1] - 1);
    ans++;
    calc(lv - 1, r - (length[lv - 1] + 1) - 1);
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    x--;
    length[0] = 1;
    p[0] = 1;
    rep(i, 1, 51){
        length[i] = length[i - 1] * 2 + 3;
        p[i] = p[i - 1] * 2 + 1;
    }
    calc(n, x);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <sstream>
#include <complex>
#include <climits>
using namespace std;

#define REP(i,a,n) for(int i=(a);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define EPS 1e-8

int money[256];
int main(){
	money['I'] = 1; money['V'] = 5;
	money['X'] = 10; money['L'] = 50;
	money['C'] = 100; money['D'] = 500;
	money['M'] = 1000;
	
	string in;
	while(cin>>in){
		bool f = false;
		int sum = 0;
		for(int i=in.size()-1; i>=0; i--){
			if( i<in.size()-1 && f ){
				if( money[in[i]]>=money[in[i+1]] ){
					sum += money[in[i]];
				}else{
					sum -= money[in[i]];
					f = false;
				}
			}else{
				sum += money[in[i]];
				f = true;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
 	
  string s;
  cin>>s;
  int sum=0;
  for (auto i:s){
    sum+=i-'0';
  }
  if (sum%9==0) cout<<"Yes";
    else cout<<"No";
  
  
}


Measured memory_bytes: 3760
nx = list(map(int, input().split()))
ln = list(map(int, input().split()))
n = nx[0]
x = nx[1]

dn = 0
count = 1
for i in range(0, n, 1):
    dn += ln[i]
    if dn > x:
        break
    count += 1
print(count)

Measured memory_bytes: 3060
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

int n;
bool used[505][505];
int potential[505];
int level[505][505];
int c;

void dfs(int cur, int val) {
    for (int i = 0; i < n; i++) {
        if (i == cur) continue;
        if (level[i][cur] < 0 && level[cur][i] < 0) {
            if (potential[i] < 0) {
                potential[i] = potential[cur] + 1;
                level[i][cur] = level[cur][i] = val;
                c++;
                dfs(i, val);
            } else {
                if (potential[i] % 2 != potential[cur] % 2) {
                    level[i][cur] = level[cur][i] = val;
                    c++;
                }
            }
        }
    }
}

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

    cin >> n;

    fill(level[0], level[n], -1);

    c = 0;
    int l = 1;
    while (c < n * (n - 1) / 2) {
        fill(potential, potential + n, -1);
        for (int j = 0; j < n; j++) {
            if (potential[j] < 0) {
                potential[j] = 0;
                dfs(j, l);
            }
        }
        l++;
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cout << level[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

Measured memory_bytes: 1536
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
vector<pair<ll,ll>> edge[100010];
bool black[100010];
ll dcount = 0;
void dfs(ll p,ll now, bool c){
    dcount++;
    black[now] = c;
    
    for (auto e : edge[now]) {
        if(e.first == p){
            continue;
        }
        if(e.second %2 == 0){
            dfs(now,e.first,c);
        }else{
            dfs(now,e.first,!c);
        }
    }
}

int main() {
    ll n;
    
    std::cin >> n;
    for (int i = 0; i < n-1; i++) {
        ll tmp_1,tmp_2,tmp_3;
        std::cin >> tmp_1>>tmp_2>>tmp_3;
        tmp_1--;
        tmp_2--;
        edge[min(tmp_1,tmp_2)].push_back({max(tmp_1,tmp_2),tmp_3});
        edge[max(tmp_1,tmp_2)].push_back({min(tmp_1,tmp_2),tmp_3});
    }
    dfs(-1,0,true);
    for (int i = 0; i < n; i++) {
        if(black[i]){
            std::cout << "0" << std::endl;
        }else{
            std::cout << "1" << std::endl;
        }
    }
    
}


Measured memory_bytes: 10368
n,m = map(int,input().split())
h = list(map(int,input().split()))
g = [1]*n
for i in range(m):
    a,b = map(int,input().split())
    if h[a-1] >= h[b-1]:
        g[b-1] = 0
    if h[b-1] >= h[a-1]:
        g[a-1] = 0
print(sum(g))

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

signed main(){
    int n,w;cin>>n>>w;
    const int v=(int)1e5;
    int dp[n+1][v+1];
    fill(dp[0],dp[n+1],w+1);
    dp[0][0]=0;
    int ans=0;
    rep(i,n){
        int ww,vv;cin>>ww>>vv;
        rep(j,v+1){
            if(j>=vv){
                dp[i+1][j]=min(dp[i][j],dp[i][j-vv]+ww);
            }else{
                dp[i+1][j]=dp[i][j];
            }
            if(dp[i+1][j]<=w){
                ans=max(ans,j);
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 79104
#include <stdio.h>


int main(){
	int k[12], v1, v2, x;
	double h, d;

	while( scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
	&k[1],&k[2],&k[3],&k[4],&k[5],&k[6],&k[7],&k[8],&k[9],&k[10],&v1,&v2) != EOF ){

		x = 0;
		for(int i=1 ; i<=10 ; i++){
			x += k[i];
		}
		h = (double)x/(v1+v2);
		d = (double)v1*h;
		x = 0;
		for(int i=1 ; i<=10 ; i++){
			x += k[i];
			if( d <= x ){
				printf("%d\n", i);
				break;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const N=input[0].split(' ')[0]-0;
  const K=input[0].split(' ')[1]-0;
  var A=input[1].split(' ').map(e=>{
    return e-0;
  }).sort((a,b)=>{
    return a-b;
  });
  var F=input[2].split(' ').map(e=>{
    return e-0;
  }).sort((a,b)=>{
    return b-a;
  });
  var possible=0;
  for(var i=0;i<N;i++){
    possible=Math.max(possible,A[i]*F[i]);
  }
  var impossible=-1;
  var temp;
  var sum;
  while(possible-impossible>1){
    temp=Math.ceil((impossible+possible)/2);
    sum=0;
    for(var i=0;i<N;i++){
      sum+=Math.max(0,A[i]-Math.floor(temp/F[i]));
    }
    if(sum<=K){
      possible=temp;
    }else{
      impossible=temp;
    }
  }
  console.log(possible);
}




//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 62392
a, b, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
X = []
Y = []
C = []
for i in range(m):
  x, y, c = map(int, input().split())
  x -= 1
  y -= 1
  X.append(x)
  Y.append(y)
  C.append(c)
  
Waribiki = []
Waribiki.append(min(A) + min(B))
for i in range(m):
  Waribiki.append(A[X[i]] + B[Y[i]] - C[i])
print(min(Waribiki))

Measured memory_bytes: 92012
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
#define EPS (1e-10)
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
// 素数かどうか判定
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	vector<int>a(n); rep(i, n)cin >> a[i];
	int sum = 0;
	rep(i, n) {
		sum ^= a[i];
	}
	if ((sum^sum) == sum)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#define mod 1000000007

int main(){
    long long int dp[100100] = {0},b[100100]={0};
    long long int n,m,i;
    long long int x;

    scanf("%lld %lld",&n,&m);
    for(i = 0 ; i < m ; i++){
        scanf("%lld",&x);
        b[x] = -1;
    }
    
    dp[0] = 1;
    for(i = 1; i <= n ; i++){
       // printf("%d",i);
        
        if(b[i] == -1){
            dp[i] = 0;
        }else{
            if(i == 1){
                dp[i] = 1;
            }else{
             dp[i] = (dp[i-1] + dp[i-2])%mod;
            }
        }
          
        
    }
    printf("%lld\n",dp[n]);

    return 0;
}

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

struct Dinic{
  const Int INF=1<<28;
  
  struct edge {
    Int to,cap,rev;
    edge(){}
    edge(Int to,Int cap,Int rev):to(to),cap(cap),rev(rev){}
  };

  Int n;
  vector<vector<edge> > G;
  vector<map<Int,Int> > M;
  vector<Int> level,iter;

  Dinic(){}
  Dinic(Int sz):n(sz),G(n),M(n),level(n),iter(n){}
  
  void add_edge(Int from,Int to,Int cap){
    M[from][to]=G[from].size();
    M[to][from]=G[to].size();
    G[from].push_back(edge(to,cap,G[to].size()));
    // undirected
    //G[to].push_back(edge(from,cap,G[from].size()-1));
    // directed
    G[to].push_back(edge(from,0,G[from].size()-1));
  }
  
  void bfs(Int s){
    fill(level.begin(),level.end(),-1);
    queue<Int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
      Int v=que.front();que.pop();
      for(Int i=0;i<(Int)G[v].size();i++){
	edge &e = G[v][i];
	if(e.cap>0&&level[e.to]<0){
	  level[e.to]=level[v]+1;
	  que.push(e.to);
	}
      }
    }
  }
  
  Int dfs(Int v,Int t,Int f){
    if(v==t) return f;
    for(Int &i=iter[v];i<(Int)G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[v]<level[e.to]){
	Int d = dfs(e.to,t,min(f,e.cap));
	if(d>0){
	  e.cap-=d;
	  G[e.to][e.rev].cap+=d;
	  return d;
	}
      }
    }
    return 0;
  }
  
  Int flow(Int s,Int t,Int lim){
    Int fl=0;
    for(;;){
      bfs(s);
      if(level[t]<0||lim==0) return fl;
      fill(iter.begin(),iter.end(),0);
      Int f;
      while((f=dfs(s,t,lim))>0){
	fl+=f;
	lim-=f;
      }
    }
  }

  Int flow(Int s,Int t){
    return flow(s,t,INF);
  }

  //cap==1 only
  bool back_edge(Int s,Int t,Int from, Int to){
    for(Int i=0;i<(Int)G[from].size();i++) {
      edge& e=G[from][i];
      if(e.to==to) {
	if(e.cap==0&&flow(from,to,1)==0) {
	  flow(from,s,1);
	  flow(t,to,1);
	  return 1;
	}
      }
    }
    return 0;
  }
};



template <typename T>
vector<T> dijkstra(Int s,vector<vector<pair<Int, T> > > & G,T INF){
  using P = pair<T, Int>;
  Int n=G.size();
  vector<T> d(n,INF);
  vector<Int> b(n,-1);
  priority_queue<P,vector<P>,greater<P> > q;
  d[s]=0;
  q.emplace(d[s],s);
  while(!q.empty()){
    P p=q.top();q.pop();
    Int v=p.second;
    if(d[v]<p.first) continue;
    for(auto& e:G[v]){
      Int u=e.first;
      T c=e.second;
      if(d[u]>d[v]+c){
	d[u]=d[v]+c;
	b[u]=v;
	q.emplace(d[u],u);
      }
    }
  }
  return d;
}

//INSERT ABOVE HERE
signed main(){
  Int n,m,s,t;
  cin>>n>>m>>s>>t;
  s--;t--;

  using P = pair<Int, Int>;
  vector<vector<P> > G(n);
  vector<vector<P> > rG(n);
  map<P, Int> C;
  for(Int i=0;i<m;i++){
    Int u,v,d,c;
    cin>>u>>v>>d>>c;
    u--;v--;
    G[u].emplace_back(v,d);
    rG[v].emplace_back(u,d);
    C[P(u,v)]=c;
  }

  const Int INF = 1e15;
  auto ds=dijkstra(s,G,INF);
  auto dt=dijkstra(t,rG,INF);

  Dinic f(n);
  for(Int v=0;v<n;v++){
    for(auto p:G[v]){
      Int u,d;
      tie(u,d)=p;
      if(ds[v]+d==ds[u]&&ds[v]+d+dt[u]==ds[t]){
	f.add_edge(v,u,C[P(v,u)]);
      }
    }
  }

  cout<<f.flow(s,t)<<endl;
  return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<ll> cum(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());
    rep(i,n){
        if(i == 0){
            cum[i] = a[i];
            continue;
        }
        cum[i] = cum[i-1] + a[i];
    }
    // rep(i,n) cout << a[i] <<endl;
    // rep(i,n) cout << cum[i] <<endl;
    int cnt = 1;
    for(int i = n-2;i >= 0;i--){
        //cout << cum[i] << " " << a[i+1] << endl;
        if(cum[i]*2 < a[i+1]) break;
        // cout << cnt << endl;
        // cout << " " << cum[i] << endl;
        cnt++;
    }

    cout << cnt << endl;
}


Measured memory_bytes: 4588
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = int(input())
if 400 <= N and N <= 599:
    ans = 8
elif 600 <= N and N <= 799:
    ans = 7
elif 800 <= N and N <= 999:
    ans = 6
elif 1000 <= N and N <= 1199:
    ans = 5
elif 1200 <= N and N <= 1399:
    ans = 4
elif 1400 <= N and N <= 1599:
    ans = 3
elif 1600 <= N and N <= 1799:
    ans = 2
elif 1800 <= N and N <= 1999:
    ans = 1


print(ans)



# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)


Measured memory_bytes: 9208
#include <stdio.h>
int main(void){
    // Your code here!

    int a, b; 
   char op; 
     while(1){ 
         scanf("%d %c %d", &a, &op, &b); 
         if(op=='?'){ 
             break; 
     	}else if(op=='+'){ 
    	    printf("%d\n", a+b); 
     	}else if(op=='-'){ 
     	    printf("%d\n", a-b); 
     	}else if(op=='*'){ 
     	    printf("%d\n", a*b); 
    	}else if(op=='/'){ 
   	    printf("%d\n", a/b); 
         } 
     } 
    return 0; 
 } 


Measured memory_bytes: 2036
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// typedef
typedef long long ll;

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

// repetition
#define FOR(i,m,n) for(ll i = ((ll) m); i < ((ll) n); ++i)
#define REP(i,n) FOR(i,0,n)

int solve(const string& X, const string& Y) {
    int xlen = X.length()+1, ylen = Y.length()+1;
    int* dp = new int[xlen*ylen];
    for(int i = 0; i < xlen; i++) {
        for(int j = 0; j < ylen; j++) {
            if(i == 0 || j == 0) {
                dp[i*ylen+j] = 0;
                continue;
            }
            dp[i*ylen+j] = max(
                dp[(i-1)*ylen+(j-1)] + (X[i-1] == Y[j-1]? 1 : 0),
                max(dp[(i-1)*ylen+j], dp[i*ylen+(j-1)])
            );
        }
    }
    int ret = dp[xlen*ylen - 1];
    delete[] dp;
    return ret;
}

int main() {
    int q; cin >> q;
    REP(i, q) {
        string X, Y;
        cin >> X >> Y;
        cout << solve(X, Y) << endl;
    }
    return 0;
}

/*
Longest Common Subsequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp

dp[i][j] = X1...XiとY1...Yjの最長共通部分列
dp[i][j] = 
dp[i-1][j-1] + 1            if Xi == Yj
max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) otherwise
*/


Measured memory_bytes: 7112
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#define ll long long

using namespace std;

ll a[1100100];

ll isort(int n,int g) {
	ll cnt = 0;
	for (int i = g; i < n; i++) {
		ll v = a[i];
		int j = i - g;
		while (j >= 0 && a[j] > v) {
			a[j + g] = a[j];
			j = j - g;
			cnt++;
		}
		a[j + g] = v;
	}
	return cnt;
}

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

	ll cnt = 0;
	vector<int> g;
	for (int k = N; k > 0; k = (k - 1) / 3) {
		g.push_back(k);
	}
	if (g.back() != 1)g.push_back(1);

	for (int i = 0; i < g.size(); i++) {
		cnt += isort(N, g[i]);
	}

	cout << g.size() << endl;

	for (int i = 0; i < g.size();i++) {
		if (i != 0)cout << " ";
		cout << g[i];
	}
	cout << endl << cnt << endl;

	for (int i = 0; i < N; i++) {
		cout << a[i] << endl;
	}








}





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

using namespace std;

#define int long long

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

#define rep(i,a,b) for (int i = a; i <= (int)b; ++i)
#define f first
#define s second

#define single_test

const int maxn = 3001;
double dp[maxn][maxn];
int n;
vector<double> a;
bool vis[maxn][maxn];

double go(int pos, int cnt) {
    if (pos == n) {
        if (cnt > n - cnt) {
            return 1;
        }
        return 0;
    }
    auto &ref = dp[pos][cnt];
    if (vis[pos][cnt]) {
        return ref;
    }
    vis[pos][cnt] = true;
    double ans = (1 - a[pos]) * go(pos + 1, cnt);
    ans += a[pos] * go(pos + 1, cnt + 1);
    return ref = ans;
}

void solve() {
    cin >> n;
    a.resize(n);
    for (auto &x: a) {
        cin >> x;
    }
    double x = go(0, 0);
    cout << fixed << setprecision(10);
    cout << x << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Measured memory_bytes: 58848