akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextLong();
            var l = new long[100];

            l[0] = 2;
            l[1] = 1;
            for (int i = 2; i <= 86; i++)
            {
                l[i] = l[i - 1] + l[i - 2];
            }

            Console.WriteLine(l[n]);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public string[] ArrayString(int N)
        {
            string[] Array = new string[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = next();
            }
            return Array;
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 11220
#include <iostream>

int main() {
  char X, Y;
  std::cin >> X >> Y;

  if ( X > Y ) {
    std::cout << ">" << std::endl;
  } else if ( X < Y ) {
    std::cout << "<" << std::endl;
  } else {
    std::cout << "=" << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {      
      Scanner sc = new Scanner(System.in);
      int[] dice = new int[6];
      for (int i=0; i<6; i++) {
        dice[i] = sc.nextInt();
      }
      int q = sc.nextInt();
      while (sc.hasNext()) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = 0;
        if (a == dice[0]) {
          if (b == dice[1]) {
            c = 3;
          } else if (b == dice[2]) {
            c = 5;
          } else if (b == dice[3]) {
            c = 2;
          } else if (b == dice[4]) {
            c = 4;
          }
        }
        if (a == dice[1]) {
          if (b == dice[0]) {
            c = 4;
          } else if (b == dice[2]) {
            c = 1;
          } else if (b == dice[3]) {
            c = 6;
          } else if (b == dice[5]) {
            c = 3;
          }
        }
        if (a == dice[2]) {
          if (b == dice[0]) {
            c = 2;
          } else if (b == dice[1]) {
            c = 6;
          } else if (b == dice[4]) {
            c = 1;
          } else if (b == dice[5]) {
            c = 5;
          }
        } 
        if (a == dice[3]) {
          if (b == dice[0]) {
            c = 5;
          } else if (b == dice[1]) {
            c = 1;
          } else if (b == dice[4]) {
            c = 6;
          } else if (b == dice[5]) {
            c = 2;
          }
        }        
        if (a == dice[4]) {
          if (b == dice[0]) {
            c = 3;
          } else if (b == dice[2]) {
            c = 6;
          } else if (b == dice[3]) {
            c = 1;
          } else if (b == dice[5]) {
            c = 4;
          }
        }        
        if (a == dice[5]) {
          if (b == dice[1]) {
            c = 4;
          } else if (b == dice[2]) {
            c = 2;
          } else if (b == dice[3]) {
            c = 5;
          } else if (b == dice[4]) {
            c = 3;
          }
        }        
        System.out.println(dice[c-1]);
      }
    }
}


Measured memory_bytes: 26484
if __name__ == "__main__":
    parent, children = {}, {}
    preorder, inorder, postorder = [], [], []
    n = int(input())
    for _ in range(n):
        i, left, right = input().split()
        children[i] = dict(right=right, left=left)
        for child in children[i].values():
            if child != "-1":
                parent[child] = i
    
    root = (set(children) - set(parent)).pop()
    parent[root] = "-1"
    
    def set_preorder(i):
        if i == "-1":
            return
        preorder.append(i)
        set_preorder(children[i]["left"])
        set_preorder(children[i]["right"])
    
    def set_inorder(i):
        if i == "-1":
            return
        set_inorder(children[i]["left"])
        inorder.append(i)
        set_inorder(children[i]["right"])

    def set_postorder(i):
        if i == "-1":
            return
        set_postorder(children[i]["left"])
        set_postorder(children[i]["right"])
        postorder.append(i)
                
    set_preorder(root)
    set_inorder(root)
    set_postorder(root)

    print("Preorder")
    print(" " + " ".join(preorder))
    print("Inorder")
    print(" " + " ".join(inorder))
    print("Postorder")
    print(" " + " ".join(postorder))


Measured memory_bytes: 5608
#include<bits/stdc++.h>
using namespace std;
#define faster cin.tie(0);ios_base::sync_with_stdio(0)
#define ll long long


int n; 
double arr[3001];
 

int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	//fun(n,cnt)=p*fun(n-1,cnt+1)+(1-p)*fun(n-1,cnt);
	vector<vector<double>> dp(n+1,vector<double>(n+1,0.0));
   
    for(int i=0;i<=n;i++) dp[i][0]=1.0;
 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=arr[i-1]*dp[i-1][j-1] + (1-arr[i-1])*dp[i-1][j];
		}
		
	}
	
	double ans=0.0;
	for(int j=n/2+1;j<=n;j++)
	{
		ans=max(ans,dp[n][j]);
	}
	
	cout<<setprecision(10);
	cout<<ans<<endl;
	
   
}


Measured memory_bytes: 70784
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
H = list(map(int, input().split()))
d = [float('inf')]*N


def solve():
    if N <= 3:
        print(abs(H[0]-H[-1]))
    else:
        d[0] = 0
        d[1] = abs(H[1]-H[0])
        d[2] = abs(H[2]-H[0])
        for i in range(3, N):
            d[i] = min(d[i-1]+abs(H[i]-H[i-1]), d[i-2]+abs(H[i]-H[i-2]))
        print(d[-1])


def solve2():
    a = 0
    b = abs(H[1]-H[0])
    for i in range(2, N):
        a, b = b, min(abs(H[i]-H[i-1])+b, abs(H[i]-H[i-2])+a)
    print(b)


solve2()


Measured memory_bytes: 14012
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {


	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		long p = 0, g = 0, score = 0;
		char turn;
		for(int i=0;i<s.length();i++)
		{
			if(p < g)
			{
				turn = 'p';
				p++;
			}
			else 
			{
				turn = 'g';
				g++;
			}
			
			if(s.charAt(i) == 'g')
			{
				if(turn == 'p')
					score++;
			}
			else
			{
				if(turn == 'g')
					score--;
			}
		}
		System.out.println(score);
	}
}

Measured memory_bytes: 34804
def findcard(cards):
    master = list(map(str, range(1,14)))
    spade = []
    hart = []
    club = []
    dia = []
    for w in cards:
        mark = w[0]
        num = w[1]
        if mark == "S":
            spade.append(num)
        elif mark == "H":
            hart.append(num)
        elif mark == "C":
            club.append(num)
        elif mark == "D":
            dia.append(num)

    for i in master:
        if i not in spade:
            print("S "+ i)

    for i in master:
        if i not in hart:
            print("H "+ i)

    for i in master:
        if i not in club:
            print("C " + i)

    for i in master:
        if i not in dia:
            print("D " + i)


n = int(input())
cards = []
for i in range(n):
    cards.append(input().split())

findcard(cards)

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n,0);
  int s,i,c;
  s=0;
  c=0;
  for(i=0;i<n;i++){
    cin >> a.at(i);
    s=s+a.at(i);
  }
  
  for(i=0;i<n;i++){
    if(a.at(i)*4*m>=s){
      c++;
    }
  }
  
  if(c>=m){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define MOD 1000000007
template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

template <class X>
vector<vector<X>> matmul(const vector<vector<X>> &mat1, const vector<vector<X>> &mat2) {
    int n = mat1.size();
    vector<vector<X>> ret(n, vector<X>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++) ret[i][j] = (ret[i][j] + (mat1[i][k] * mat2[k][j]) % MOD) % MOD;
    return ret;
}

template <class X>
vector<vector<X>> bipow(const vector<vector<X>> &mat, long long m) {
    int n = mat.size();
    vector<vector<X>> ret(n, vector<X>(n, 0));
    if (m == 0) {
        for (int i = 0; i < n; i++) ret[i][i] = 1;
        return ret;
    }
    if (m % 2 == 0) {
        ret = matmul(mat, mat);
        return bipow(ret, m / 2);
    } else
        return matmul(mat, bipow(mat, m - 1));
}

int main(){
    long long N, K;
    cin >> N >> K;
    vector<vector<long long>> a(N, vector<long long>(N));
    REP(i, N) REP(j, N)
        cin >> a[i][j];
    auto mat = bipow(a, K);
    long long ans = 0;
    REP(i, N) REP(j, N)
        ans = (ans + mat[i][j]) % MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define intput(i) cout << i << endl
#define ll long long
#define stringput(s) cout << (string)(s) << endl

int main(){
  int a, b;
  cin >> a >> b;
  int sum = a+b;
  int dif = a-b;
  int pro = a*b;
  int m = max(max(sum,dif),pro);
  cout << m << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int A, B, K;
    cin >> A >> B >> K;
    int cnt = 0;
    for(int i = 100; i >= 1; i--){
        if(A%i == 0 && B%i == 0){
            cnt++;
            if(cnt == K){
                cout << i << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
int main(){
  int m,s,g,p[200];
  while(cin>>m>>s>>g,m){
    int ans=-1,an;
    for(int i=0;i<m;i++)cin>>p[i];
    sort(p,p+m,greater<int>());
    for(int i=g;i>=s;i--)if(ans<p[i-1]-p[i])ans=p[i-1]-p[i],an=i;
    cout<<an<<endl;
  }
  return 0;
}

Measured memory_bytes: 1176
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
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;
}
const long long INF=1LL << 60;
long long a,b;
long long dp[100200][110];
long long w[110],v[110];


int main(){
   long long a,b;
   cin>>a>>b;
   vector<long long> vec(a);
   rep(i,a){
       cin>>vec.at(i);
   }
   if((a-b)%(b-1)!=0){
    cout<<1+(a-b)/(b-1)+1<<endl;
   }
   else{
       cout<<1+(a-b)/(b-1)<<endl;
   }
}





Measured memory_bytes: 1024
use std::io;
use std::str::FromStr;

fn input_int_tuple() -> (i32, i32, i32, i32) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<i32> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1], vec[2], vec[3])
}


fn main() {
    let (w, h, x, y) = input_int_tuple();
    print!("{} ", (w as f64) * (h as f64) / 2f64);
    if x as f64 == w as f64 / 2f64 && y as f64 == h as f64 / 2f64 {
        println!("1");
    } else {
        println!("0");
    }
}


Measured memory_bytes: 4352
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
bool DEBUG = 0; void log(A ...)(lazy A a){ if(DEBUG) print(a); }
void main(string[] args){ args ~= ["", ""]; string cmd = args[1]; if(cmd == "-debug") DEBUG = 1;
if(cmd == "-gen") gen; else if(cmd == "-jury") jury; else solve; } 
void print(){ writeln(""); } void print(T)(T t){ writeln(t); } void print(T, A ...)(T t, A a){ std.stdio.write(t, " "), print(a); }
string unsplit(T)(T xs){ return xs.array.to!(string[]).join(" "); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; } T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
T lowerTo(T)(ref T x, T y){ if(x > y) x = y; return x; } T raiseTo(T)(ref T x, T y){ if(x < y) x = y; return x; }

// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //
void gen(){}
void jury(){}
void solve(){
  long n = scan!long;
  long ans;
  foreach(long d; 1 .. n + 1){
    long k = n / d;
    // d + 2d + 3d + ... + kd
    ans += d * k * (k + 1) / 2;
  }
  ans.writeln;
}


Measured memory_bytes: 3268
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1023333,mo=1e9+7,inv2=(mo+1)/2;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}
int fac[N],ifac[N];
void iniC(int n){
	fac[0]=1;rep(i,1,n)fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);
	per(i,n-1,0)ifac[i]=1LL*ifac[i+1]*(i+1)%mo;
}
inline int C(int n, int m){return m>=0&&m<=n?1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo:0;}
int n,m,k,res,f[N];
int main() {
	read(n);read(m);read(k);iniC(N-1);
	f[0]=1;
	rep(i,1,m+k){
		f[i]=((1LL*f[i-1]*2-C(i-1,m)-C(i-1,i-1-k))%mo+mo)%mo;
	}
	rep(i,n,n+m+k)
		res=(res+1LL*C(i-1,n-1)*f[i-n]%mo*power(3,n+m+k-i))%mo;
	cout<<res;
	return 0;
}


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

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

// template starts
typedef long long int ll;

void solve(){
	// code starts from here
	ll N, K;
	cin >> N >> K;
	vector<ll> vec(N);
	input(vec,N);
	for(ll i = 0; i < N; i++) vec[i]--;
	
	set<ll> s;
	map<ll,ll> mp;
	ll len = 0;
	
	ll index = 0;
	vector<ll> cyc;
	ll start;
	while(true){
		if(s.find(index) != s.end()){
			start = mp[index];	
			break;
		}
		
		len++;
		s.insert(index);
		mp[index] = len-1;
		
		cyc.pb(index);
		index = vec[index];

	}
//	for(int i = 0; i < len; i++) cout << cyc[i] +1 << " ";
//	cout << endl;
	
	if(K <= start) cout << cyc[K]+1 << endl;
	else{
		K -= (start);
		vector<ll> temp;
		for(int i = start; i < cyc.size(); i++) temp.pb(cyc[i]);
		cout << temp[K%temp.size()]+1<< endl;
	}
}

int main(){
 	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	int T;
	T = 1;
	while(T--){
		solve();
	}

	return 0;
}


Measured memory_bytes: 27840
N = int(input())
ans = 0
for i in range(1, N+1):
  if i % 2 == 0:
    continue
  a = 0
  for j in range(1, i+1):
    if i % j == 0:
      a += 1
  if a == 8:
    ans += 1
print(ans)

Measured memory_bytes: 63852
function main(input){
	var I = parseInt(input, 10);
	if(I % 2 === 0){
		var a = I / 2;
      	var Ans = a*a;
    }else{
		var a = Math.floor(I / 2);
      	var A = a+1;
      	var Ans = a * A;
    }
  	console.log(Ans);
}
 
main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

int main()
{
    char c;
    cin >> c;
    
    if(c=='A') cout << "T" << endl;
    if(c=='C') cout << "G" << endl;
    if(c=='G') cout << "C" << endl;
    if(c=='T') cout << "A" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
   int n;
   cin>>n;
   V<int> a(n);
   for(int i=0;i<n;i++)cin>>a[i];
   if(n==2){
       if(a[0]==1&&a[1]==1)cout<<"Possible"<<"\n";
       else cout<<"Impossible"<<"\n";
       return 0;
   }
   sort(all(a));
   bool c=true;
   if(a[0]==1&&a[1]==1)c=false;
   if(a[n-1]>n-1)c=false;
   if(a[n-1]==a[0])c=false;

   V<int> cnt(n+1,0);
   if(c){
       for(int i=0;i<n;i++)cnt[a[i]]++;
       if(cnt[a[0]]>2)c=false;
       if(a[n-1]%2==0&&cnt[a[0]]==2)c=false;
       for(int i=0;i<n;i++)if(a[i]!=a[0])if(cnt[a[i]]<2)c=false;
   }
   for(int i=1;i<n;i++){
       if(a[i]-a[i-1]>1)c=false;
   }
   if((a[n-1]+1)/2!=a[0])c=false;
    if(c)cout<<"Possible"<<"\n";
    else cout<<"Impossible"<<"\n";
}

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

  for(;scanf("%d",&n)!=EOF;){
    int a,b,c;
    int count=0;
    for(a=0;a<10;a++){
      for(b=0;b<10;b++){
	for(c=0;c<10;c++)
	  if(n-a-b-c>=0 && n-a-b-c<10)
	    count+=1;
      }
    }
    printf("%d\n",count);
  }

  return 0;
}

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

int main() {
  // ここにプログラムを追記
  int a,b;
  cin >> a >> b;
  int c=a+b;
  if(c%2==0){
    cout << c/2;
  }
  if(c%2==1){
    cout << c/2+1;
  }
}

Measured memory_bytes: 3600
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size

    def add(self, i, w):
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res



n = I()
A = LI()



def D(L):
    n = len(L)
    bit = BIT(2 * n + 1)
    ans = 0
    for i in range(n - 1, -1, -1):
        bit.add(L[i] + n, 1)
        ans += bit.sum(L[i] + n - 1)
    return ans



ALL = (n + 1) * n // 2
A2 = sorted(A)
# 求めるのは、1より-1の方が多かった区間の数
ng, ok = n, 0
while ng > ok + 1:
    mid = (ok + ng) // 2
    L = [0] + list(accumulate([1 if i >= A2[mid] else -1 for i in A]))
    if D(L) >= ALL // 2 + 1:
        ng = mid
    else:
        ok = mid


print(A2[ok])

Measured memory_bytes: 113084
#include <stdio.h>
 
int main(){
    int i,j;
    int a[101][101]={{0}};
    int x,y;
    scanf("%d %d",&x,&y);
    for(j=0;j<x;j++){
        for(i=0;i<y;i++){
            scanf("%d",&a[j][i]);
            a[j][y]+=a[j][i];
            a[x][i]+=a[j][i];
        }
        a[x][y]+=a[j][y];
    }
    for(j=0;j<=x;j++){
        for(i=0;i<=y;i++){
            printf("%d",a[j][i]);
            if(i!=y){
                printf(" ");
            }
        }
         
            printf("\n");
         
    }
    return 0;
}


Measured memory_bytes: 2112
import java.util.*;
import java.io.*;
public class Main {
	
	static Integer[][] memo;
	static char[] x;
	static char[] y;
	static StringBuilder sb;
  public static void main(String args[]) throws IOException {
	  
	  Scanner sc=new Scanner(System.in);
		  
		  x=sc.next().toCharArray();
		  y=sc.next().toCharArray();
		  
		  memo=new Integer[x.length][y.length];
		  sb=new StringBuilder("");
		  dp(0,0);
		  trace(0,0);
		  System.out.println(sb);
		  
  }
  
  public static void trace(int i,int j) {
	  
	  if(i==x.length||j==y.length) {
		  return;
	  }
	  
	  if(dp(i,j)==1+dp(i+1,j+1)&&x[i]==y[j]) {
		  sb.append(x[i]);
		  trace(i+1,j+1);
	  }else {
		  int w=dp(i+1,j);
		  int q=dp(i,j+1);
		  if(w>=q) {
			  trace(i+1,j);
		  }else {
			  trace(i,j+1);
		  }
	  }
	  
  }
  
  public static int dp(int i,int j) {
	  
	  if(i==x.length||j==y.length) {
		  return 0;
	  }
	  
	  if(memo[i][j]!=null) {
		  return memo[i][j];
	  }
	  
	  if(x[i]==y[j]) {
		  return memo[i][j]=1+dp(i+1,j+1);
	  }
	  
	  int lol=dp(i+1,j);
	  int lel=dp(i,j+1);
	  if(lol>=lel) {
		  return memo[i][j]=lol;
	  }else {
		  return memo[i][j]=lel;
	  }
  }
  static class Scanner {
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}

	public Scanner(FileReader f) {
		br = new BufferedReader(f);
	}

	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	public String nextLine() throws IOException {
		return br.readLine();
	}

	public double nextDouble() throws IOException {
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if (x.charAt(0) == '-') {
			neg = true;
			start++;
		}
		for (int i = start; i < x.length(); i++)
			if (x.charAt(i) == '.') {
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			} else {
				sb.append(x.charAt(i));
				if (dec)
					f *= 10;
			}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg ? -1 : 1);
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

}
}


Measured memory_bytes: 187316
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;


int main(){
    int N;
    cin >> N;
    vector<int> tree[100000];
    for(int i=0; i<N-1; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    ll num[100000];
    for(int i=0; i<N; i++){
        num[i]=-1;
    }

    ll c[100000];
    for(int i=0; i<N; i++){
        cin >> c[i];
    }
    sort(c,c+N,greater<int>());
    int cnt=0;
    queue<int> que;
    que.push(0);
    num[0]=c[0];
    cnt++;
    

    while(cnt<N){
        int temp=que.front();
        que.pop();
        for(auto x: tree[temp]){
            if(num[x]==-1){
                num[x]=c[cnt];
                que.push(x);
                cnt++;
            }
        }
    }
    
    ll ans = 0;
    for(int i=1; i<N; i++){
        ans += c[i];
    }
    cout << ans << endl;
    
    for(int i=0; i<N; i++){
        cout<<num[i];
        if(i==N-1){
            cout<<endl;
        }else{
            cout<<" ";
        }
    }
    return 0;
}





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

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 5e5 + 123;
const int M = 1e6 + 123;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

void solve(){
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
}

int main(){
    #ifdef KAZAKH
        freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++){
        //cout << "case #" << i << ": ";
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
ans_list = []

while True:
    N = int(input())
    if N == 0:
        break

    square = [[0, 0]]
    for i in range(N - 1):
        n, d = map(int, input().split())
        #print(n, d)
        if d == 0:
            square.append([square[n][0], square[n][1] - 1])
        elif d == 2:
            square.append([square[n][0], square[n][1] + 1])
        elif d == 1:
            square.append([square[n][0] - 1, square[n][1]])
        elif d == 3:
            #print(100, square, square[n - 1])
            square.append([square[n][0] + 1, square[n][1]])

    #print(square)

    mini = 10 ** 10
    minj = 10 ** 10
    maxi = -10 ** 9
    maxj = -10 ** 9

    if N == 1:
        ans_list.append([1, 1])
    else:
        for i in range(len(square)):
            mini = min(square[i][0], mini)
            minj = min(square[i][1], minj)
            maxi = max(square[i][0], maxi)
            maxj = max(square[i][1], maxj)

    #print(maxi, maxj, mini, minj)
        ans_list.append([maxj - minj + 1, maxi - mini + 1])

for i in ans_list:
    print(i[0], i[1])


Measured memory_bytes: 5628
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define MAX 300000
typedef long long ll;
typedef pair<ll,int> P;


long long  gcd(long long x,long long y){
  long long mindata,maxdata;
  mindata=min(x,y);
  maxdata=max(x,y);
  while(maxdata%mindata!=0){
    long long temp;
    temp=maxdata%mindata;
    maxdata=mindata;
    mindata=temp;
  }
  return mindata;
}



int main(){
  ll N,G[200000],H[200000];
  cin>>N;
  
  ll A[200000];
  for(ll i=0;i<N;i++){
    cin>>A[i];
  }
  G[0]=A[0];
  G[1]=gcd(A[0],A[1]);
  for(ll i=2;i<N-1;i++){
    G[i]=gcd(G[i-1],A[i]);
  }
  H[N-1]=A[N-1];
  H[N-2]=gcd(A[N-1],A[N-2]);
  for(ll i=N-3;i>0;i--){
    H[i]=gcd(H[i+1],A[i]);
  }

  ll ans=0;
  ans=max(H[1],G[N-2]);
  for(int i=1;i<=N-2;i++){
    ans=max(ans,gcd(G[i-1],H[i+1]));
  }
  cout<<ans<<endl;
  
  
}


Measured memory_bytes: 4864
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    cakes = [(0, 0, 0)]
    for _ in range(N):
        x, y, z = map(int, input().split())
        cakes.append((x, y, z))

    """
    dp[n][m][t] = (1~n番目までのケーキからm個のケーキをタイプtで選んだ時の合計の最大値)
    と定める。ここでタイプとは
        t=0 -> val = x + y + z
        t=1 -> val = x + y - z
        t=2 -> val = x - y + z
        t=3 -> val = x - y - z
        t=4 -> val = -x + y + z
        t=5 -> val = -x + y - z
        t=6 -> val = -x - y + z
        t=7 -> val = -x - y - z
    どのタイプにせよ更新式は同じで、dp[n][m] = max(dp[n-1][m], dp[n-1][m-1] + (n番目のdp = [0]aaa))
    """

    dp = [[[0] * 8 for _ in range(M + 1)] for _ in range(N + 1)]
    for n in range(1, N + 1):
        x, y, z = cakes[n]
        for m in range(1, min(M + 1, n + 1)):
            if n == m:
                dp[n][m][0] = dp[n - 1][m - 1][0] + (x + y + z)
                dp[n][m][1] = dp[n - 1][m - 1][1] + (x + y - z)
                dp[n][m][2] = dp[n - 1][m - 1][2] + (x - y + z)
                dp[n][m][3] = dp[n - 1][m - 1][3] + (x - y - z)
                dp[n][m][4] = dp[n - 1][m - 1][4] + (-x + y + z)
                dp[n][m][5] = dp[n - 1][m - 1][5] + (-x + y - z)
                dp[n][m][6] = dp[n - 1][m - 1][6] + (-x - y + z)
                dp[n][m][7] = dp[n - 1][m - 1][7] + (-x - y - z)
            else:
                dp[n][m][0] = max(dp[n - 1][m][0], dp[n - 1][m - 1][0] + (x + y + z))
                dp[n][m][1] = max(dp[n - 1][m][1], dp[n - 1][m - 1][1] + (x + y - z))
                dp[n][m][2] = max(dp[n - 1][m][2], dp[n - 1][m - 1][2] + (x - y + z))
                dp[n][m][3] = max(dp[n - 1][m][3], dp[n - 1][m - 1][3] + (x - y - z))
                dp[n][m][4] = max(dp[n - 1][m][4], dp[n - 1][m - 1][4] + (-x + y + z))
                dp[n][m][5] = max(dp[n - 1][m][5], dp[n - 1][m - 1][5] + (-x + y - z))
                dp[n][m][6] = max(dp[n - 1][m][6], dp[n - 1][m - 1][6] + (-x - y + z))
                dp[n][m][7] = max(dp[n - 1][m][7], dp[n - 1][m - 1][7] + (-x - y - z))
    print(max(dp[N][M]))

if __name__ == "__main__":
    main()


Measured memory_bytes: 221648
function Main(input) {
	input = input.split(" ");
	const a1 = parseInt(input[0]);
	const a2 = parseInt(input[1]);
	const a3 = parseInt(input[2]);

	if (a1==a2 && a2==a3 && a3==a1 ) {
		console.log("Yes");		
	} else {
		console.log("No");
	}

}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
s = input().rstrip()
n = len(s)

c = int(n/2)

for i in range(c):
    if s[i] != s[-i-1]:
        print('No')
        exit()

for i in range(int(c/2)):
    if s[i] != s[c-i-1]:
        print('No')
        exit()

for i in range(c+1, c+1+int(c/2)):
    if s[i] != s[-i-1]:
        print('No')
        exit()

print('Yes')


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

class Point{
public:
    int x, y, id;
    Point(int x, int y, int id): x(x), y(y), id(id){}
};

int main(){
    int N, M, T, P;
    while(cin >> N >> M >> T >> P, N|M|T|P){
        vector<int> D(T), C(T);
        for(int i=0; i<T; i++)
            cin >> D[i] >> C[i];
        
        vector<Point> points;
        for(int i=0; i<P; i++){
            int x, y; cin >> x >> y;
            points.emplace_back(x, y, i);
        }
        
        for(int i=T-1; i>=0; i--){
            vector<Point> tpoints;
            for(auto p: points){
                if(D[i] == 1){
                    if(p.x<C[i])
                        tpoints.emplace_back(C[i]-p.x-1, p.y, p.id);
                    tpoints.emplace_back(p.x+C[i], p.y, p.id);
                }else{
                    if(p.y<C[i])
                        tpoints.emplace_back(p.x, C[i]-p.y-1, p.id);
                    tpoints.emplace_back(p.x, p.y+C[i], p.id);
                }
            }
            points = tpoints;
        }
        vector<int> counts(P);
        for(auto p: points) if(p.x<N && p.y<M)
            counts[p.id]++;
        
        for(auto v: counts)
            cout << v << endl;
    }
    return 0;
}



Measured memory_bytes: 3176
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
typedef long double lld;
const ll INF = 1e18;
const ll MOD = 1e9+7;
 
ll fastpowMOD(ll a, ll p,ll MOD);
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; a %= MOD; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }
 
ll lcm(ll a,ll b){
	return (a*b)/__gcd(a,b);
}

void solve(){
	ll n,m,k;
	cin>>n>>m>>k;
	vector<ll> a(n+1,0),b(m+1,0);
	for(ll i=1;i<=n;i++){
		ll x;
		cin>>x;
		a[i] = a[i-1] + x;
	}
	for(ll i=1;i<=m;i++){
		ll x;
		cin>>x;
		b[i] = b[i-1] + x;
	}
	
	ll ans = 0;
	for(ll i=0;i<=n;i++){
		if(a[i]<=k){
			
			ll f = k-a[i];
		
			ll fromb = upper_bound(b.begin(),b.end(),f)-b.begin()-1;
			ans = max(i+fromb,ans);
			//if(i==n) cout<<fromb<<"\n";
		}
		
	}
	cout<<ans<<"\n";
	return;
	
}


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




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

using namespace std;

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

	int res = 100000000;
	int n,t,a,b;

	cin >> n >> t;

	for(int i=0;i<n;i++)
	{
		cin >> a >> b;
		if(b<=t)
		{
			res = min(a,res);
		}
	}

	if(res==100000000)
	{
		cout << "TLE" << '\n';
	}
	else
	{
		cout << res << '\n';
	}
	return 0;
}

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

int main(){
  int a[5];
  int k;
  rep(i, 5) cin >> a[i];
  cin >> k;
  if(a[4] - a[0] > k) cout << ":(" << endl;
  else cout << "Yay!" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define DL double
#define MLL map<LL,LL>::iterator
#define MSL map<string,L>::iterator
#define MLS map<LL,string>::iterator
#define MSS map<string,string>::iterator
#define MCL map<char,LL>::iterator
#define SL set<LL>::iterator
#define SS set<string>::iterator sl
#define G getline
#define SZ size()
#define IN insert
#define C clear()
#define B begin()
#define F front()
#define T top()
#define E end()
#define EM empty()
#define V vector
#define Q queue
#define DQ deque
#define PQ priority_queue
#define ST stack
#define FI first
#define SE second
#define PI acos(-1)
#define PS push
#define PP pop()
#define PSF push_front
#define PSB push_back
#define PPF pop_front()
#define PPB pop_back()
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
V<LL>v,w;
map<LL,LL>u;
int main()
{
    FAST;
    LL n,m,i,j,k,p,q,o,l,s,t,z;
    cin>>n;
    k=0;
    for(i=0; i<n; i++)
    {
        cin>>o;
        v.PSB(o);
        u[o]++;
    }
    k=0;
    for(MLL it=u.B; it!=u.E; it++)
    {
        k+=(it->SE*(it->SE-1))/2;
    }
    for(i=0; i<n; i++)
    {
      cout<<k-(u[v[i]]-1)<<endl;
    }

    return 0;
}


Measured memory_bytes: 11376
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <map>
#include <set>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;

struct edge {
    i64 from, to, cost;
    edge(i64 from, i64 to) : from(from), to(to), cost(1) {}
    edge(i64 from, i64 to, i64 cost) : from(from), to(to), cost(cost) {}
};
using Graph = vector<vector<edge>>;

constexpr i64 INF = std::numeric_limits<i64>::max();
constexpr i64 SINF = std::numeric_limits<i64>::max() / 10;
const i64 dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
//const i64 dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//const i64 dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//const i64 dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e : t) fill_v(e, v);
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

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

i64 lcm(i64 a, i64 b) {
    return a * b / gcd(a, b);
}

int main() {
    long long N;
    cin >> N;
    vector<i64> A(N);
    for(int i = 0; i < N; ++i) cin >> A[i];
    i64 l = A[0];
    for (int i = 0; i < N; ++i) {
        l = lcm(A[i], l);
    }
    i64 sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += l / A[i];
    }
    cout << (double)(l) / (double)sum << endl;
}


Measured memory_bytes: 256
<?php
fscanf(STDIN, '%d', $x);

while (true) {
    if (!is_prime($x)) $x++;
    else break;
}

echo $x.PHP_EOL;

function is_prime($n) {
    $lim = floor(sqrt($n));
    for ($i = 2; $i <= $lim; $i++) {

        if ($n % $i == 0) {
            return false;
        }
    }
    return true;
}

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

#define ll long long
#define INF 99999999
#define rep(i,n) for(int i=0,temp=(int)(n);i<temp;++i) //vec.size()がnの時等の高速化
#define loop(i,start,end) for(int i=start,temp=(int)(end);i<end;++i)
#define rfor(v,x) for(const auto& x : v) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort(v, v+n)
#define vsort(v) sort(v.begin(), v.end())
#define vfsort(v,lambda) sort(v.begin(),v.end(),lambda)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vin(v) rep(i,v.size()) {cin >> v[i];}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//(lambda (x y) (< x y)) => [](int x, int y) -> int { return x<y; }

int main(){
  int n,m,X,Y;cin >> n >> m >> X >> Y;
  vint x(n),y(m);vin(x);vin(y);
  vsort(x);vsort(y);
  for(int i=X+1;i<=Y;++i){
    if(x[n-1]<i&&y[0]>=i){
      cout << "No War" << endl;
      return 0;
    }
  }
  cout << "War" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>

const int N = 100;
const int W = 10000;

struct item {
    int value;
    int weight;
} items[N+1];

int main() {
    using namespace std;

    int n, w;
    cin >> n >> w;
    for( int i=0; i<n; ++i ) {
        cin >> items[i+1].value >> items[i+1].weight;
    }

    int dp[W+1] = {};
    for( int i=1; i<=n; ++i ) {
        for ( int j=items[i].weight; j<=w; ++j ) {
            dp[j] = max( dp[j], dp[j-items[i].weight] + items[i].value );
        }
    }

    cout << dp[w] << std::endl;
}

Measured memory_bytes: 1208
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string ToString ( int x )
{
	string s = "";
	
	while ( x )
	{
		s += ((x % 10) + '0');
		x /= 10;
	}

	reverse(s.begin(), s.end());

	return s;
}

void solve( int x, int p, string s )
{
	if ( !x )
	{
		s[s.size() - 1] = '\n';
		cout << s;
		return;
	}

	for ( int i = x; i > 0; --i )
	{
		if ( p >= i ) {
			solve( x - i, i, (s + ToString( i ) + " ") );
		}
	}
}

int main ( void )
{
	int n;

	while ( cin >> n, n )
	{
		solve( n, n, "" );
	}

	return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	
	string s;

	cin >> s;

	int a = stoi(s.substr(5, 2));

	if (a>=5) {
		cout << "TBD" << endl;
	}

	else {
		cout << "Heisei" << endl;
	}

}

Measured memory_bytes: 256
n = int(input())
tmp = list(map(int,input().split()))
now = 0
nowsum = 0
start = 0
end = 0
ans = 0
while(True):
    if end == n:
        print(ans)
        quit()
    if tmp[end] ^ nowsum == nowsum + tmp[end]:
        now += 1
        ans += now
        nowsum += tmp[end]
        end += 1
    else:
        nowsum -= tmp[start]
        start += 1
        now -= 1


Measured memory_bytes: 24840
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
using graph = vector<vector<ll>>;

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	if (a + b + c >= 22) {
		cout << "bust" << endl;
	}
	else {
		cout << "win" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <string_view>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout(a) cout << fixed << setprecision((int)(a))

//typedef===============
typedef long long       ll;
typedef long double     ld;
typedef pair<int, int>  Pii;
typedef pair<ll, ll>    Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ll MOD2   = 998244353;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define eb emplace_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (n); ++(i))
#define reps(i, n)      for(int i = 1; (i) <= (n); ++(i))
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; --(i))
#define repbit(bit, n)  for(int bit = 0; (bit) < (1 << (n)); ++(bit))
#define ifbit(bit, i)   if((bit) & (1 << (i)))
#define CtoI(c)         int((c)) - int('0')
#define ItoC(c)         char((c) + '0')

//functions=============
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };

/*--------additional--------*/



/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    ll n; cin >> n;

    ll ans = INF18;
    ll max = sqrt(n);
    for(int i = 1; i <= max; ++i){
        if(n % i == 0){
            ll j = n / i;
            chmin(ans, i + j - 2);
        }
    }

    cout << ans << endl;

return 0;
}

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

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
    ~debug() { cerr << endl; }
    eni(!=) cerr << boolalpha << i; ris; }
    eni(==) ris << range(begin(i), end(i)); }
    sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
    }
    sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
    }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

# define forn(i, n) for (ll i = 0; i < int(n); i++)
# define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
# define all(V) V.begin(), V.end()
# define rall(V) V.rbegin(), V.rend()
# define len(V) (int)V.size()
# define ll long long
# define ld long double
# define ff first
# define ss second
# define pb push_back
# define mp make_pair
# define endl '\n'
# define M_PI 3.14159265358979323846

void solve()
{
    string s; cin >> s;
    if(s[0] == '7' || s[1] == '7'|| s[2] == '7') cout << "Yes";
    else cout << "No";
}

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


Measured memory_bytes: 3608
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#define deb(x) cout << #x << " is " << x << "\n";
#define int long long
#define mod 1000000007

const double PI = 2 * acos(0.0);
const long long INF = 1e18L + 5;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin >> s;
	if (s[0] == '7' || s[1] == '7' || s[2] == '7') {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}


Measured memory_bytes: 3636