akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

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

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

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

ll readLL(){
	ll i;
	scanf("%lld",&i);
	return i;
}

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

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

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

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

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

int main(){
	ll k=readLL();
	int i=7;
	using int128=__int128;
	int128 c=1;
	while(i<600){
		i++;
		c*=i;
		c/=(i-7);
	}
	string ans;
	for(;i>=1;i--){
		if(c>0){
			ll w=k/c;
			ans+=string(w,'L');
			k-=w*c;
			c*=(i-7);
			c/=i;
		}
		ans+="FESTIVA";
	}
	reverse(ALL(ans));
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define fff(i,a,b) for(int (i)=(a);(i)<=(b);i++)
#define pb push_back
#define len(a) (a).length()
#define all(a) (a).begin(),(a).end()
#define sz(a) (a).size()
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long ,long long > pll;
typedef unsigned long long ull;
typedef long double ld;
 
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t=1;
	int x,y;
	cin>>x>>y;
	bool moze=false;
	for(int i=0;i<=x;i++)
	{
		int pom=y-i*4;
		if(pom>=0 && pom%2==0 && (x-i)*2==pom) moze=true;
	}
	if(moze) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
 	return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#define MAX 1000000
using namespace std;

void eratos ( int n, vector<int> &v){
    bool prime[MAX+1];
    for ( int i = 0; i <= n; i++ ) prime[i] = false;
    for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
    prime[2] = true;
    int limit = (int)sqrt((double)n) + 1;
    for ( int i = 3; i <= limit; i += 2 ){
	if ( !prime[i] ) continue;
	for ( int j = i + i; j <= n; j += i ) prime[j] = false;
    }
    for ( int i = 0; i <=n; i++ ) if (prime[i]) v.push_back(i);
}

main(){
    int N, P;
    vector<int> primes;
    eratos(MAX, primes);

    int k;
    while(1){
	cin >> N >> P;
	if ( N == -1 && P == -1 ) break;
	int s = distance(primes.begin(), upper_bound(primes.begin(), primes.end(), N));

	vector<int> v;
	for ( int i = s; i < s+P; i++ ){
	    for ( int j = i; j < s+P; j++ ){
		v.push_back(primes[i] + primes[j]);
	    }
	}
	sort(v.begin(), v.end());
	cout << v[P-1] << endl;
    }
}

Measured memory_bytes: 2324
{-# OPTIONS_GHC -O3 -fexpose-all-unfoldings -fdicts-cheap -fdicts-cheap #-}
 
import Data.Int (Int32)
import Data.Array.IO
import Data.List (delete,insert,minimumBy,foldl1')
import Data.Ord (comparing)
 
acmArray :: IOUArray Int32 Int32 -> (Int32,Int32) -> IO (IOUArray Int32 Int32)
acmArray arr (x,y) = do
  s <- readArray arr x
  writeArray arr x (s + y)
  return arr
 
maxsnd (a,b) (c,d)
  | b > d           = (a,b)
  | b == d && a < c = (a,b)
  | otherwise       = (c,d)
 
filt (a,b) (c,d) = b >= d
filt2 (a,b) (c,d) = a /= c
 
toPut (x,y) = show x ++ " " ++ show y
 
listToTuple :: [(Int32,Int32)] -> (Int32,Int32)
listToTuple [(x,y)] = (x,y)
 
judge :: (Int32,Int32) -> (Int32,Int32) -> [(Int32,Int32)] -> IOUArray Int32 Int32 -> IO (Int32, Int32)
judge (a,b) (x,y) xs arr = do
  if (a /= x) && ((b > y) || (b == y && a < x)) then return (a,b)
     else do
       let (y',x') = head xs
       return (x',-y')
 
putresult arr xs n (a,b) = do
  s' <- getLine
  let [x,y'] = map (read :: String -> Int32) $ words s'
  y'' <- readArray arr x
  acmArray arr (x,y')
  y <- readArray arr x
 
  let xs' = insert (-y,x) (delete (-y'',x) xs)
 
  (a',b') <-  judge (a,b) (x,y) xs' arr
 
  putStrLn $ toPut (a',b')
 
  if n < 2 then return ()
  else do
--    test <- getAssocs arr
--    print xs'
    putresult arr xs' (n-1) (a',b')
 
main = do
  s <- getLine
  let [x,n] = map read $ words s
  arr <- newArray (1,x) 0 :: IO (IOUArray Int32 Int32)
  putresult arr [] n (1,0)

Measured memory_bytes: 43060
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;

stringstream input;

struct complex{
	bool ov;
	int re, im;

	complex( int re_, int im_, bool ov_ = false ):
		re(re_), im(im_), ov(ov_)
		{
			if( !ov ){
				ov = max( abs(re), abs(im) ) > 10000;
			}
		}

	complex operator -(){
		return complex( -re, -im, ov );
	}
	void operator +=( const complex &c ){
		*this = complex( re + c.re, im + c.im, ov | c.ov );
	}
	void operator -=( const complex &c ){
		*this = complex( re - c.re, im - c.im, ov | c.ov );
	}
	void operator *=( const complex &c ){
		*this = complex(
			re * c.re - im * c.im,
			re * c.im + im * c.re,
			ov | c.ov
		);
	}
};
const complex i( 0, 1 );

complex term();
complex factor();
complex expr();

complex expr(){
	complex c = term();
	char ch;
	for(;;){
		if( input.peek() == '+' ){
			input >> ch;
			c += term();
		}
		else if( input.peek() == '-' ){
			input >> ch;
			c -= term();
		}
		else break;
	}
	return c;
}

complex term(){
	complex c = factor();
	char ch;
	while( input.peek() == '*' ){
		input >> ch;
		c *= factor();
	}
	return c;
}

complex factor(){
	char ch;
	if( input.peek() ==  '(' ){
		input >> ch;
		complex c = expr();
		input >> ch;
		return c;
	}
	if( input.peek() == 'i' ){
		input >> ch;
		return i;
	}
	if( input.peek() == '+' ){
		input >> ch;
		return factor();
	}
	if( input.peek() == '-' ){
		input >> ch;
		return -factor();
	}
	
	int val;
	input >> val;
	return complex( val, 0, input.fail() );
}

int main(){
	for( string s; getline( cin, s ); ){
		input.clear();
		input.str(s);
		complex c = expr();

		if( c.ov ) cout << "overflow";
		else{
			if( c.re ){
				cout << c.re;
				if( c.im > 0 ) cout << '+';
			}
			else if( !c.im )
				cout << '0';

			if( c.im ){
				cout << c.im << 'i';
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<int,ll>Pil;
typedef pair<int,Pil>Piil;
typedef pair<P1,ll> P2;
typedef pair<string,string> Ps;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	int x,y,sx,sy,cost;
};

int main() {

	ll n;
	string s;
	cin>>n;
	cin>>s;

	ll r=0,w=0,ans;
	rep(i,n){
		if(s[i]=='W')w++;
		else r++;
	}
	ans=min(r,w);
	if(w==0||r==0)ans=0;
	ll t=INF;
	if(r>0){
		ll w2=0;
		t=0;
		rep(i,n){
			if(s[i]=='W')w2++;
			else{
				if(w2>0){
					t+=min(w2,r);
					r-=w2;
					w2=0;
				}
				r--;
			}
			if(r<=0)break;
		}
	}
	cout<<min(ans,t)<<endl;

	return 0;
}


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

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

	vector<int>a = x;
	sort(a.begin(), a.end());
	ll amed = a.at((n - 2) / 2 + 1);
	ll amedb = a.at((n - 2) / 2);

	for (int i = 0; i < n; i++) {
		if (x.at(i) < amed)cout << amed << endl;
		else cout << amedb << endl;
	}
}

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

using namespace std;

int main(){


	string s;
	cin >> s;
	string t;
	if(s.size() == 2){
		cout << s;
	}
	else{
	     reverse(s.begin(), s.end());
		cout<< s;
	}

	return 0;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 87;
const int M = N * 2;
int n,a[N],b[N],f[M];
void add(int i)
{
    for (; i < M; i += i & -i)
        ++f[i];
}
int qry(int i)
{
    int r=0;
    for (; i ; i ^= i & -i)
        r += f[i];
    return r;
}
bool ok(int k)
{
    memset(f,0,sizeof(f));
    int s = N;
    add(s);
    long long t = (n * (n + 1LL) / 2 + 1) / 2;
    for (int i = 1; i <= n; ++i) {
        s += a[i] >= k ? 1 : -1;
        t -= qry(s);
        add(s);
    }
    return t <= 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    copy_n(a+1,n,b);
    sort(b,b+n);
    int bn = unique(b,b+n) - b, ans = 0;
    for (int k = 1<<__lg(bn); k; k >>= 1)
        if ((ans | k) < bn && ok(b[ans | k]))
            ans |= k;
    cout << b[ans] << '\n';
}


Measured memory_bytes: 1792
import sys
s = int(input())
a = []
a.append(s)
N = 1000000

for i in range (0,N):
  if a[i] % 2 == 0:
    x = a[i] / 2
    a.append(x)
  else:
    x = 3 * a[i] + 1
    a.append(x)
  if a[i+1] in a[0:i]:
    print(i+2)
    sys.exit()

Measured memory_bytes: 3060
s = list(input())
K = int(input())

"""
Kを使用する
-> aにすることができる

残りのKはs[-1]に使用
"""

from collections import defaultdict
alpha = defaultdict(int)
for i in range(97, 97 + 26):
    alpha[chr(i)] = i - 97

for i in range(len(s)):
    if s[i] == "a":
        continue
    if 26 - alpha[s[i]] <= K:
        K -= 26 - alpha[s[i]]
        s[i] = "a"

if K > 0:
    s[-1] = chr(97 + (alpha[s[-1]] + K) % 26)

print(*s, sep="")

Measured memory_bytes: 7204
# coding: utf-8
# Your code here!
lis=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

N=int(input())

print(lis[N-1])

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

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

  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        if (i == j || j == k || k == i ) continue;
        if (l[i] < l[j] + l[k] && l[j] < l[k] + l[i] && l[k] < l[j] + l[i]){
          if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i]) continue;
          ans++;
        }
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://code-festival-2016-qualc.contest.atcoder.jp/tasks/codefestival_2016_qualC_c>
問題文============================================================
 アルピニストである高橋君と青木君は最近ある有名な山脈を踏破しました。
 この山脈はN 個の山からなっており、西から東に向けて山1,山2,…,山Nと一直線に並んでいます。
 高橋君は西から、青木君は東からこの山脈を踏破しました。
 
 山i の高さはhi ですが、二人とも各hi の値は忘れてしまいました。
 その代わり、各i(1≦i≦N) に対して、山i の山頂にたどり着いた時の、
 それまでに登った山(山i も含む)の高さの最大値を記録しています。
 高橋君の記録した値はTi で、青木君の記録した値はAi です。
 
 各山の高さhi が正の整数であることはわかっています。
 山の高さの列としてありうるものが何通りあるかを10^9+7 で割ったあまりを求めてください。
 
 ただし記録が間違っていてありうる山の高さの列が存在しないこともあります。
 この場合は0を出力してください。
 
 
=================================================================

解説=============================================================

================================================================
*/
const ll MOD = 1e9 + 7 ;
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<ll> T(N),A(N);
    for(auto &in:T) cin >> in;
    for(auto &in:A) cin >> in;
    
    vector<pll> l(N),r(N);
    ll maxh = -1;
    for(int i = 0; i < N;i++){
        if(maxh < T[i]){
            l[i] = {T[i],T[i]};
            maxh = T[i];
        }else{
            l[i] = {1,maxh};
        }
    }
    maxh = -1;
    for(ll i = N - 1; i >= 0; i--){
        if(maxh < A[i]){
            r[i] = {A[i],A[i]};
            maxh = A[i];
        }else{
            r[i] = {1,maxh};
        }
    }
    
    ll res = 1;
    for(int i = 0; i < N;i++){
    //    cout << l[i].first << " " << l[i].second << " " << r[i].first << " " << r[i].second << endl;
        res *= min(r[i].second,l[i].second) - max(r[i].first,l[i].first) + 1;
        if(res <= 0) {
            res = 0; break;
        }
        res %= MOD;
    }
    cout << res << endl;
	return 0;
}


Measured memory_bytes: 4992
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static class P {
		int front, cost;
		public P(int f, int c){
			front = f;
			cost = c;
		}
	}
	public static void main(String[] args) {
		InputReader r = new InputReader(System.in);
		int n = r.nextInt();
		int k = r.nextInt();
		ArrayList<Integer> adj[] = new ArrayList[n];
		for (int i = 0; i < adj.length; i++) {
			adj[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n - 1; i++) {
			int from = r.nextInt() - 1;
			int to = r.nextInt() - 1;
			adj[from].add(to);
			adj[to].add(from);
		}
		for(int i=0;i<n;i+=10){
			Collections.shuffle(adj[i]);
		}
		int res = 1 << 28;
		boolean[] vis = new boolean[n];
		for (int i = 0; i < n; i++) {
			LinkedList<P> q = new LinkedList<P>();
			q.add(new P(i,0));
			Arrays.fill(vis, false);
			vis[i] = true;
			HashSet<Integer> set = new HashSet<Integer>();
			int last = -1;
			while (!q.isEmpty()) {
				P f = q.removeFirst();
				int front = f.front;
				set.add(front);
				last = front;
				int cost = f.cost;
				if (cost == k) {
					continue;
				}
				for (int x : adj[front]) {
					if (!vis[x]) {
						q.add(new P(x, cost+1));
						vis[x] = true;
					}
				}
			}
			Arrays.fill(vis, false);
			vis[last] = true;
			q.add(new P(last,0));
			int diameter = -1;
			int reached = 0;
			HashSet<Integer> set2 = new HashSet<Integer>();
			while (!q.isEmpty()) {
				P f = q.remove();
				int front = f.front;
				int cost = f.cost;
				reached++;
				diameter = cost;
				if (diameter <= k) {
					last = front;
					set2.add(front);
					res = Math.min(res, n - reached);
				}
				for (int x : adj[front]) {
					if (!vis[x] && set.contains(x)) {
						q.add(new P(x, cost+1));
						vis[x] = true;
					}
				}
			}
		}
		System.out.println(res);
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public InputReader(FileReader stream) {
			reader = new BufferedReader(stream);
			tokenizer = null;
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
				return null;
			}
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}


Measured memory_bytes: 24148
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N;
  cin>>N;
  vector<ll> T(N);
  for(int i=0;i<N;i++)cin>>T[i];
  map<ll,ll> mp;
  for(ll i=0;i<N;i++)mp[i+T[i]]++;
  ll res=0;
  for(ll i=0;i<N;i++)res+=mp[i-T[i]];
  cout<<res<<endl;

  
}

Measured memory_bytes: 27340
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<numeric>
#include<utility>
using namespace std;
int main() {
	vector<int> a;
	int q, query[200000], x, p;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> query[i];
		if (query[i] == 0) {
			cin >> x;
			a.emplace_back(x);
		}
		else if (query[i] == 1) {
			cin >> p;
			cout << a[p] << endl;
		}
		else if (query[i] == 2) {
			a.pop_back();
		}
	}
	return 0;
}


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

const int maxn=2e5+7;
int a[maxn];


int main (){
    int n,x;cin>>n>>x;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int Min=1e9+7;
    for(int i=1;i<=n;i++){
        x-=a[i];
        Min=min(Min,a[i]);
    }
    cout<<(int)(n+x/Min)<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val h = (0 until n).map { sc.next().toLong() }
    println(problem153c(n, k, h))
}

fun problem153c(n: Int, k: Int, h: List<Long>): Long {
    var count = 0L
    var k = k
    val h = h.sortedDescending()
    for (i in 0 until n) {
        if (k != 0) {
            k--
        } else {
            count += h[i]
        }
    }
    return count
}

Measured memory_bytes: 61136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(i = 0; i < n; i++)
//2D::rep(i,j)rep(j,j)cin>>bin[i][j];
#define vec(n) vector<int> a(n)
#define A1 cout<<"No"<<endl
#define A2 cout<<"Yes"<<endl
#define A3 cout<<ans<<endl
#define AA(i) cout<<i<<endl
const int U=2e5+5;
const ll V=1000000007;

int main() {
  string S,T; cin>>S>>T;
  int i=S.size(),j;
  bool k=true;
  rep(j,i){
    if(S[j]!=T[j])k=false;
  }
  if(k)A2;
  else A1;
  return 0;
}

Measured memory_bytes: 3624
import java.util.*;

public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for (int i=0; i<n; i++){
      switch (sc.next()){
        case "insert":
          Node.insert(sc.nextInt());
          break;
        case "print":
          Node.print();
          break;
        case "find":
          System.out.println(Node.find(sc.nextInt())?"yes":"no");
          break;
        case "delete":
          Node.delete(sc.nextInt());
          break;
      }
    }
  }
}

class Node{
  private int key=-1;
  private Node p=null;
  private Node l=null;
  private Node r=null;
  private static Node root=null;

  public void pre(){
    System.out.print(" "+key);
    if (l!=null) l.pre();
    if (r!=null) r.pre();
  }

  public void in(){
    if (l!=null) l.in();
    System.out.print(" "+key);
    if (r!=null) r.in();
  }

  public void post(){
    if (l!=null) l.post();
    if (r!=null) r.post();
    System.out.print(" "+key);
  }

  public int childNum(){
    int c=0;
    if (l != null) c++;
    if (r != null) c++;
    return c;
  }

  private Node(int key, Node l, Node r){
    this.key = key;
    this.l = l;
    this.r = r;
  }

  public static void insert(int v){
    insert(new Node(v,null,null));
  }

  private static void insert(Node z){
    Node y = null;
    Node x = root;
    while (x != null){
      y = x;
      if (z.key < x.key){
        x = x.l;
      } else {
        x = x.r;
      }
    }
    z.p = y;
    if (y==null){
      root = z;
    } else if (z.key<y.key){
      y.l = z;
    } else {
      y.r = z;
    }
  }

  public static boolean find(int k){
    Node x = root;
    while (x != null){
      if (k == x.key) return true;
      else if (k < x.key){
        x = x.l;
      } else {
        x = x.r;
      }
    }
    return false;
  }

  public static void delete(int k){
    Node x = root;
    Node z = null;
    while (x != null){
      if (k == x.key) {
        z = x;
        break;
      }
      else if (k < x.key){
        x = x.l;
      } else {
        x = x.r;
      }
    }
    if (z==null) return;
    if (z.p==null){
      root = null;
      return;
    }
    switch(z.childNum()){
      case 0:
        if (z.p.l == z) z.p.l = null;
        else z.p.r = null;
        break;
      case 1:
        Node c;
        if (z.l != null) c = z.l;
        else c = z.r;
        if (z.p.l == z) z.p.l = c;
        else z.p.r = c;
        c.p = z.p;
        break;
      case 2:
        Node y = z.r;
        while (y.l!=null) y = y.l;
        z.key = y.key;
        if (y.childNum()==0){
          if (y.p.l == y) y.p.l = null;
          else y.p.r = null;
        } else {
          Node yc;
          if (y.l != null) yc = y.l;
          else yc = y.r;
          if (y.p.l == y) y.p.l = yc;
          else y.p.r = yc;
          yc.p = y.p;
        }
        break;
    }
  }

  public static void print(){
    root.in();
    System.out.println();
    root.pre();
    System.out.println();
  }
}


Measured memory_bytes: 200960
#include <iostream>

using namespace std;
typedef long long ll;

int main() {
    ll L, R, min1, min2, r, min1r, min2r;
    cin >> L >> R;
    min1 = R;
    min2 = R;
    min1r = 2019;
    min2r = 2019;
    if (R - L >= 2019) {
        cout << 0 << endl;
        return 0;
    }
    for (ll i = L; i <= R; i++) {
        for (ll j = i+1; j <= R; j++) {
            r = (i * j) % 2019;
            if (min1r > r) {
                min1r = r;
            }
        }
    }
    cout << min1r << endl;
//    for (ll i = L; i <= R; i++) {
//        r = i % 2019;
//        if (min1r > r) {
//            min1r = r;
//            min1 = i;
//        }
//    }
//    if (min1 == R) {
//        min2r = L % 2019;
//    } else {
//        min2r = min1r + 1;
//    }
//    cout << (min1r * min2r) % 2019 << endl;
//    for (ll i = L; i <= R; i++) {
//        r = i % 2019;
//        if (min2r > r && i != min1) {
//            min2r = r;
//            min2 = i;
//        }
//    }
//    cout << (min1r * min2r) % 2019 << endl;
//    for (ll i = L; i <= R; i++) {
//        r = i % 2019;
//        if (r < min1 && r < min2) {
//            min2 = min1;
//            min1 = r;
//        } else if (r < min2) {
//            min2 = r;
//        }
//    }
//    cout << (min1 * min2) % 2019 << endl;
//    return 0;

//    L = L % 2019;
//    R = R % 2019;
//    if (L > R) {
//        swap(L, R);
//    } else if (L == R) {
//        cout << 0 << endl;
//        return 0;
//    }
//    for (int i = L; i <= R; i++) {
//        if (min1 > i) {
//            min1 = i;
//        }
//    }
//    for (int i = L; i <= R; i++) {
//        if (min1 < i && min2 > i) {
//            min2 = i;
//        }
//    }
//    cout << (min1 * min2) % 2019;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

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

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 100000+5;

int n;
vi G[N];
bool vis[N][3];
int memo[N][3];

int DP(int u, int color, int p = 0){
	// color = 0 white
	// color = 1 black
	if(vis[u][color]) return memo[u][color];
	int ans = 1;
	int limit = color == 1? 1 : 2;
	for(int i=0; i<G[u].size(); i++){
		int v = G[u][i];
		if(v != p){
			int act = 0;
			for(int j=0; j<limit; j++){
				act = add(act,DP(v,j,u));
			}
			ans = mul(ans,act);
		}
	}
	vis[u][color] = true;
	return memo[u][color] = ans;
}

int main(){
	ri(n);
	int a, b;
	for(int i=1; i<n; i++){
		ri2(a,b);
		G[a].pb(b);
		G[b].pb(a);
	}
	cout << add(DP(1,0),DP(1,1)) << endl;
	return 0;
}


Measured memory_bytes: 16896
#include <stdio.h>
#include <utility>
#define MAX 100000
using namespace std;

int partition(int A[], int p, int r)
{
  int x = A[r];
  int i = p - 1;
  for (int j = p; j <= r - 1; j++)
  {
    if (A[j] <= x)
    {
      i = i + 1;
      swap(A[i], A[j]);
    }
  }
  swap(A[i + 1], A[r]);
  return i + 1;
}

int main()
{
  int n;
  int A[MAX];
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &A[i]);
  }

  int r = partition(A, 0, n - 1);
  for (int i = 0; i < n; i++)
  {
    if (i != r)
      printf("%d", A[i]);
    else
      printf("[%d]", A[i]);

    if (i < n - 1)
      printf(" ");
    else
      printf("\n");
  }
}


Measured memory_bytes: 3068
#include<iostream>
#include<algorithm>
#include<cmath>
using lint=int64_t;
using namespace std;

int main()
{
	int N,A,B,C;
	int l[8]={};
	int ans=1e9;
	
	cin >> N >> A >> B >> C;
	for(int i=0;i<N;i++)
		cin >> l[i];
	
	for(int bit=0;bit<pow(4,N);bit++)
	{
		int cnt[4]={};
		int len[4]={};
		int x=bit;
		for(int i=0;i<N;i++)
		{
			cnt[x%4]++;
			len[x%4]+=l[i];
			x/=4;
		}
		if(len[0]==0 || len[1]==0 || len[2]==0)continue;
		int tans=0;
		tans+=max((cnt[0]-1)*10,0)+abs(len[0]-A);
		tans+=max((cnt[1]-1)*10,0)+abs(len[1]-B);
		tans+=max((cnt[2]-1)*10,0)+abs(len[2]-C);
		
		ans=min(ans,tans);
	}
	cout << ans << endl;
	return 0;
}



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

using namespace std;

int main() {
	int a;
	int b;
	int c;
	int counter = 0;
	int maecounter = 0;
	while (1) {
		int k = 0;
		cin >> a;
		if (a == -1) {
			break;
		} else {
			while (a >= 4) {
				c = a;
				while (1) {
					b = c / 4;
					if (b == 0) {
						break;
					}
					k = b;
					counter++;
					c = c / 4;
				}
				if (maecounter > counter+1) {
					for (int i = 0; i < maecounter - (counter+1); i++) {
						cout << 0;
					}
				}
				cout << k;
				a = a - pow(4,counter) * k;
				maecounter = counter;
				counter = 0;
			}
			if (maecounter > counter+1) {
				for (int i = 0; i < maecounter - (counter+1); i++) {
					cout << 0;
				}
			}
			cout << a << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>

#define MAX 1000000
#define INF 2000000000

void merge(int[],int,int,int);
void mergeSort(int[],int,int);

int count=0;

int main()
{
  int i, n, array[MAX];
  int left, right;

  scanf("%d", &n);

  for( i=0; i<n; i++){
    scanf("%d", &array[i]);
  }

  left = 0;
  right = n;

  mergeSort( array, left, right);

  for( i=0; i<n-1; i++){
    printf("%d ", array[i]);
  }

  printf("%d\n%d\n", array[i], count);

  return 0;
}

void mergeSort( int A[], int left, int right){
  int mid;

  if( left + 1 < right ){
    mid = ( left + right ) / 2;
    mergeSort( A, left, mid);
    mergeSort( A, mid, right);
    merge( A, left, mid, right);
  }
  
}

void merge( int A[], int left, int mid, int right){
  int n1, n2, i, j, k;

  n1 = mid - left;
  n2 = right - mid;

  int l_array[n1+1], r_array[n2+1];


  for( i=0; i<n1; i++){
    l_array[i] = A[left+i];
  }

  for( i=0; i<n2; i++){
    r_array[i] = A[mid+i];

  }

  l_array[n1] = INF;
  r_array[n2] = INF;

  i = 0;
  j = 0;

  for( k=left; k<right; k++){
    if( l_array[i] <= r_array[j] ){
      A[k] = l_array[i];
      i++;
    }
    else{
      A[k] = r_array[j];
      j++;
    }    
    count++;
  }

}

Measured memory_bytes: 4508
#include<iostream>
#include<algorithm>
#include<string>
#include<set>

using namespace std;

#define INF ( 1 << 15 )

string array[10];
int n, k;
static set < string > ret;

void rec( string s, int bit, int cnt){
  if(cnt == k){
    ret.insert( s);
    return;
  }
  for(int i = 0 ; i < n ; i++ ){
    if((bit >> i) & 1) rec( s + array[i], bit&~(1<<i), cnt + 1);
  }
}
int main(){
  while(cin >> n >> k , n){
    for(int i = 0 ; i < n ; i++ ){
      cin >> array[i];
    }
    rec( "", (1 << n) - 1, 0);
    cout << ret.size() << endl;
    ret.clear();
  }
}

Measured memory_bytes: 1460
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define uxy pair<int, pair<int, int> >
using namespace std;
void TxtRead(){
    freopen("closing.in","r", stdin);
    freopen("closing.out","w", stdout);
}
void TheTime(){
    ios_base::sync_with_stdio(false);
	cin.tie();
}
const int N = 3e5+5;
const ll INF = 1e9+5;
const ll MOD = 1e9+7;
const double PI = 3.141592653589793116;

int n, w;
ll wr[N], vr[N];
ll dp[N];

int main()
{
    //TxtRead();
    TheTime();

    scanf("%d %d", &n, &w);
    for(int i=0; i<n; i++){
        scanf("%lld %lld", &wr[i], &vr[i]);
    }

    memset(dp, -1, sizeof(dp));
    dp[0]=0;
    for(int i=0; i<n; i++){
        for(int j=w; j>=wr[i]; j--){
            if(dp[j-wr[i] ]!=-1)
                dp[j]=max(dp[j], dp[j-wr[i] ]+vr[i]);
        }
    }
    ll ans=0;
    for(int i=0; i<=w; i++){
        ans=max(ans, dp[i]);
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 6400
#include <iostream>
#include <cassert>

using namespace std;

const static int N = 8;
const static int FREE = -1;
const static int NOT_FREE = 1;

int row[N], col[N], dpos[2 * N - 1], dneg[2 * N - 1];

bool X[N][N];

void initialize(){
  for(int i=0; i<N; ++i){
    row[i] = FREE;
    col[i] = FREE;
  }
  for(int i=0; i<2*N-1; ++i){
    dpos[i] = FREE;
    dneg[i] = FREE;
  }
}

void printBoard(){
  for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
      if(X[i][j]){
	if(row[i] != j) return;
      }
    }
  }
  for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
      cout << ( (row[i] == j) ? "Q" : ".");
    }
    cout << endl;
  }
}

void recursive(int i){
  if(i == N){
    printBoard();
    return;
  }

  for(int j=0; j<N; ++j){
    if(NOT_FREE == col[j] || NOT_FREE == dpos[i + j] || NOT_FREE == dneg[i - j + N - 1]) continue;
    row[i] = j;
    col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE;
    recursive(i + 1);
    row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE;
  }
}

int main(){
  initialize();

  for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j) X[i][j] = false;
  }

  int k;
  cin >> k;

  for(int i=0; i<k; ++i){
    int r, c;
    cin >> r >> c;
    X[r][c] = true;
  }

  recursive(0);


  return 0;
}



Measured memory_bytes: 3128
import Control.Applicative ((<$>))
import Control.Monad (unless)
import Data.List (sortBy, unfoldr)
import Data.Set (Set)
import qualified Data.Set as S

main :: IO ()
main = do
  n <- readLn
  unless (n == 0) $ do
    mapM_ putStrLn $ solve n 
    main

solve :: Int -> [String]
solve n = showSquare $ (S.singleton [] : unfoldr f (1, S.singleton [1])) !! n
  where f (i,st) = Just (st, (i+1, S.foldl' g (S.singleton (replicate (i+1) 1)) st))
          where g s l = S.union s (S.fromList (take (length l) (zipWith (\l1 l2 -> sort (zipWith (+) l1 l2)) (ohs i) (repeat l))))

showSquare :: Set [Int] -> [String]
showSquare st = S.foldl' f [] st
  where f ls x = (unwords . map show) x : ls

sort = sortBy (flip compare)

ohs :: Int -> [[Int]]
ohs n = take n (map (take n) (iterate (0:) (1:repeat 0)))



Measured memory_bytes: 7584
// sort(b.begin(), b.end());//bという配列を小さい方からソート
//reverse(b.begin(), b.end());//bという配列を逆にソート 
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  string s,t;
  cin >> s >> t;
  vector<int>a(s.size());//s.size);
  vector<int>b(t.size());//t.size);
  rep(i,s.size()) a.at(i) = s.at(i);
  rep(i,t.size()) b.at(i) = t.at(i);
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());//bという配列を小さい方からソート
  reverse(b.begin(), b.end());//bという配列を逆にソート 
//  rep(i,s.size()) cout<< a.at(i) <<endl;
//  rep(i,t.size()) cout<< b.at(i) <<endl;
  int flag=0;
  int itticount=0;
  if(s.size() > t.size() ){
    for(int i=0; i < t.size() ; i ++){
      if(a.at(i) < b.at(i) ){
        flag = 1;
        break;
      }
      if(a.at(i) == b.at(i) ){
        itticount ++;
      }
    }//forend     
    if(itticount == s.size() && itticount == t.size() ) flag=0;
//    else if(itticount == t.size() ) flag=1;
  }//ifend
  else{
    for(int i=0; i < s.size() ; i ++){
      if(a.at(i) < b.at(i) ){
        flag = 1;
        break;
      }
      if(a.at(i) == b.at(i) ){
        itticount ++;
      }
    }//forend
    if(itticount == s.size() && itticount == t.size() ) flag=0;
    else if(itticount == s.size() ) flag=1;
  }//elseend
  if(flag==1) cout<<"Yes"<<endl;
  else cout << "No"<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    String s = sc.next();
    String ans = "a";
    if(s.matches("[A-Z]")) {
    	ans = "A";
    }
    
    System.out.println(ans);
  }
}


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

int MOD = 1000000007;
map<long long, long long> dp;
int n; 
vector<long long> A;

long long _hash(long long a, long long b, long long c) {
    auto A = vector<long long>{a, b, c};
    //sort(A.begin(), A.end());

    return A[0] * 100000 * 100000 + A[1] * 100000 + A[2];
}

long long f(long long a, long long b, long long c) {
    long long h = _hash(a, b, c);
    if(dp.find(h) != dp.end())
        return dp[h];

    long long idx = a + b + c;
    if(idx == n)
        return 1;

    auto& ret = dp[h];
    auto color = A[idx];
    if(color == a)
        ret = (ret + f(a + 1, b, c)) % MOD;
    if(color == b)
        ret = (ret + f(a, b+1, c)) % MOD;
    if(color == c)
        ret = (ret + f(a, b, c+1)) % MOD;

    return ret;
}

void solve() {
    cin >> n;
    A = vector<long long>(n);
    for(auto& a : A)
        cin >> a;

    cout << f(0, 0, 0) << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t;
    //cin >> t;
    //for(auto i = 0; i < t; ++i)
        solve();
}


Measured memory_bytes: 47872
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
	string s;
	getline(cin,s);
	for(int i=0; i<s.size(); i++)
	{
		if(s[i]==',')
			s[i]=' ';
	}
	
	cout<<s;
	return 0;
}

Measured memory_bytes: 3628
//In the name of God!
#include <bits/stdc++.h>

const int maxn = 1e5 + 12;
using namespace std;
map<int, int> mp;
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k, q, a;
    cin >> n >> k >> q;
    for(int i = 0; i < q; i++){
        cin >> a;
        mp[a]++;
    }
    for(int i = 1; i <= n; i++){
        if(k - q + mp[i] > 0)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

Measured memory_bytes: 5376
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

#include <x86intrin.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

ll a[200010];
ll dp[3][100010];

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

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

/*
  if (n % 2 == 0) {
    ll now = 0;
    for (int i = 0; i < n; i += 2) now += a[i];
    ll maximum = now;
    for (int i = n-2; i >= 0; i -= 2) {
      now += (a[i+1] - a[i]);
      if (now > maximum) maximum = now;
    }

    cout << maximum << endl;
  }
  else {
    vector<vector<ll> > dp(n+2, vector<ll>(3, (ll) -1e18));
    dp[0][0] = a[0];
    dp[1][1] = a[1];
    dp[2][2] = a[2];
    for (int i = 0; i < n; i++) {
      if (i+2 < n) dp[i+2][0] = max(dp[i+2][0], dp[i][0] + a[i+2]);
      if (i+2 < n) dp[i+2][1] = max(dp[i+2][1], dp[i][1] + a[i+2]);
      if (i+2 < n) dp[i+2][2] = max(dp[i+2][2], dp[i][2] + a[i+2]);
      if (i+3 < n) dp[i+3][1] = max(dp[i+3][1], dp[i][0] + a[i+3]);
      if (i+3 < n) dp[i+3][2] = max(dp[i+3][2], dp[i][1] + a[i+3]);
      if (i+4 < n) dp[i+4][2] = max(dp[i+4][2], dp[i][0] + a[i+4]);
    }

    cout << max(max(dp[n-3][0], dp[n-2][1]), dp[n-1][2]) << endl;
  }
*/

  dp[0][0] = a[0];
  for (int i = 1; i < n/2; i++) {
    dp[0][i] = dp[0][i-1] + a[i*2];
  }
  dp[1][0] = a[1];
  for (int i = 1; i < n/2; i++) {
    dp[1][i] = (dp[0][i-1] > dp[1][i-1] ? dp[0][i-1] : dp[1][i-1]) + a[i*2+1];
  }
  dp[2][0] = a[2];
  for (int i = 1; i < n/2; i++) {
    dp[2][i] = (dp[0][i-1] > dp[1][i-1] ? (dp[0][i-1] > dp[2][i-1] ? dp[0][i-1] : dp[2][i-1]) : (dp[1][i-1] > dp[2][i-1] ? dp[1][i-1] : dp[2][i-1])) + a[i*2+2];
  }

  ll ans = max(dp[0][n/2-1], dp[1][n/2-1]);
  if (n % 2 == 1) ans = max(ans, dp[2][n/2-1]);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 7560
n = int(input())
mod = pow(10, 9)+7

memo = [{} for _ in range(n+1)]

def judge(last4):
  for i in range(4):
    t = list(last4)
    if i >= 1:
      t[i], t[i-1] = t[i-1], t[i]
    if "".join(t).count("AGC") >= 1:
      return False
  return True

def dfs(cur, last3):
  if cur == n:
    return 1
  if last3 in memo[cur]:
    return memo[cur][last3]
  ans = 0
  for c in "AGCT":
    if judge(last3+c):
      ans = (ans+dfs(cur+1, last3[1:]+c))%mod
  memo[cur][last3] = ans
  return ans

print(dfs(0, "TTT"))

Measured memory_bytes: 9604
N,W = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
  for j in range(W+1):
    v = li[i][1]
    w = li[i][0]
    if j >= w:
      dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
    else:
      dp[i+1][j] = dp[i][j]
  
print(dp[N][W])

Measured memory_bytes: 120044
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
  int A,B;
  cin >> A >> B;
  if(B%A==0)cout << A+B;else cout <<B-A;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		while (true) {
			int N = sc.nextInt();
			if (N == 0) break;
			int[] start = new int[N];
			int[] end = new int[N];
			for (int i = 0; i < N; ++i) {
				start[i] = parse(sc.next());
				end[i] = parse(sc.next());
			}
			int ans = 0;
			for (int i = 0; i < N; ++i) {
				int c = 0;
				for (int j = 0; j < N; ++j) {
					if (start[j] <= end[i] - 1 && end[j] > end[i] - 1) ++c;
				}
				ans = Math.max(ans, c);
			}
			System.out.println(ans);
		}
	}

	static int parse(String time) {
		int h = Integer.parseInt(time.substring(0, 2));
		int m = Integer.parseInt(time.substring(3, 5));
		int s = Integer.parseInt(time.substring(6, 8));
		return h * 3600 + m * 60 + s;
	}
}

Measured memory_bytes: 68440
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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; }

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

    int h,w,n;cin>>h>>w>>n;
    int m=max(h,w);
    cout<<((n+m-1)/m)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAXN 505
 int a[105];


int main()
{
    int mi=1000000,n,sum=0;
    cin>>n;
    for(int i=0;i<n;i++){
            cin>>a[i];
       sum+=a[i];
       if(a[i]%10!=0)mi=min(mi,a[i]);
    }
    if(sum%10!=0)cout<<sum;
     else cout<<max(0,sum-mi);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}
#define forN(i,n) for(i=0;i<n;i++)
#define forR(i,s,n) for(i=s;i<n;i++)
#define ll long long
#define pb(t,d,n) {t p;int i;forN(i,n){cin>>p;d.push_back(p);}}

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;

typedef vector<pair<int,int>> vpii;
typedef pair<int,int> pr;

int main(){
    int a,i,res;
    string s;
    cin >> a >> s;
    cout << (a>=3200?s:"red") << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>

int main(){
  int N;
  scanf("%d",&N);
  int target=N+(N%2==0);
  std::vector<std::pair<int,int> > edges;
  for(int i=1;i<=N;i++){
    for(int j=i+1;j<=N;j++){
      if(i+j!=target){
	edges.emplace_back(i,j);
      }
    }
  }
  printf("%d\n",(int)edges.size());
  for(auto e:edges){
    printf("%d %d\n",e.first,e.second);
  }
  return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(),m=sc.nextInt(),x=sc.nextInt();
		int[] cost = new int[n];
		int[][] array = new int[n][m];
		for(int i=0;i<n;i++) {
			cost[i]=sc.nextInt();
			for(int j=0;j<m;j++) {
				array[i][j]=sc.nextInt();
			}
		}
		int costing=2000000;
		for(int i=0;i<(1<<n);i++) {
			int[] cost_array = new int[m];
			int temp=0;
			for(int j=0;j<n;j++) {
				if((1<<j&i)!=0) {
					temp+=cost[j];
					for(int k=0;k<m;k++) {
						cost_array[k]+=array[j][k];
					}
				}
			}
			int flag=0;
			for(int k=0;k<m;k++) {
				if(cost_array[k]<x) {
					flag=1;
					break;
				}
			}
			if(flag==0) {
				if(costing>temp) {
					costing=temp;
				}
			}
		}
		if(costing==2000000) System.out.println(-1);
		else System.out.println(costing);
	}
}

Measured memory_bytes: 37380
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int find(int a[],int l,int r)
{
    int max=a[l];
    int pos=l;
    for(int i=l;i<=r;i++)
    {
        if(a[i]>=max)
        {
            max=a[i];
            pos=i;
        }
    }
    return pos;
}
void change(int a[],int i)
{
    int temp1=a[i];
    int temp2=a[i+1];
    int temp3=a[i+2];
    a[i]=temp3;
    a[i+1]=temp1;
    a[i+2]=temp2;
}
// Return n'th term of a series defined using belo
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int c=n-2;
    ll sum=a[n-1];
    int i=n-2;
    while(c>0)
        {
            if(c==1)
            {
                sum+=a[i];
                c--;
            }
            else
            {
                sum+=2*a[i];
                c-=2;
                i--;
            }
        }
        cout<<sum;


}





Measured memory_bytes: 5204
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int a[200];
int n,x;
ll d[200][100001];
ll inv[203];
ll go(int N,int X)
{
	if(N==n)return X;
	ll &ret=d[N][X];
	if(ret!=-1)return ret;
	ret=0;
	ret=(ret+inv[n-N]*go(N+1,X%a[N]))%MOD;
	ret=(ret+(inv[n-N]*go(N+1,X))%MOD*(n-N-1))%MOD;
	return ret;
}
int main() {
	fup(i,1,202,1)inv[i]=POW(i,MOD-2);
	MEM_1(d);
	scanf("%d%d",&n,&x);
	fup(i,0,n-1,1)scanf("%d",a+i);
	sort(a,a+n);
	reverse(a,a+n);
	ll ans=go(0,x);
	fup(i,1,n,1)ans=(ans*i)%MOD;
	printf("%lld",ans);
}

Measured memory_bytes: 156544
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

pair<int, int> p[100010];
int rmn[100010];

int main() {
	int N;
	cin >> N;
	for(int i=0; i<N; ++i){
		int L, R;
		cin >> L >> R;
		p[i]=make_pair(L, R);
	}
	sort(p, p+N);
	int mnrid=0;
	for(int i=1; i<N; ++i){
		if(p[mnrid].second>p[i].second){
			mnrid=i;
		}
	}
	int mx=0;
	for(int i=0; i<N-1; ++i){
		if(i!=mnrid){
			mx=max(mx, p[i].second-p[i].first+1);
		}
	}
	int ans=mx+max(0, p[mnrid].second-p[N-1].first+1);
	rmn[N-1]=p[N-1].second;
	for(int i=N-2; i>mnrid; --i){
		rmn[i]=min(rmn[i+1], p[i].second);
	}
	for(int i=mnrid; i<N-1; ++i){
		int cand=max(0, p[mnrid].second-p[i].first+1)+max(0, rmn[i+1]-p[N-1].first+1);
		ans=max(ans, cand);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const long long int Mod=1e9+7;
int main(){
	long long int a  ,b ,c ,n ,i ,j ,m ,res=1;
	cin>>m>>n;
//	cout<<"\n";
	while(n){
		if(n%2){
			res=(res*m)%Mod;
		}
		m=(m*m)%Mod;
		n/=2;
	}
	cout<<res;
	cout<<"\n";
}


Measured memory_bytes: 3120
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll gcd(ll a, ll b){
	if(b==0) return a;
	return gcd(b, a%b);
}

int main()
{
	ll n, m;
	string s, t;
	cin>>n>>m;
	cin>>s; cin>>t;
	ll l=n/gcd(n, m)*m;
	for(ll i=0; i<n; i++){
		if(i*l/n%(l/m)==0){
			if(s[i]!=t[i*m/n]){
				cout<<-1<<endl;
				return 0;
			}
		}
	}
	cout<<l<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, c = 0;
    cin >> N;
 	int n= N;
    while (N /= 10 != 0)
    {
        c += N % 10;
        N /= 10;
    }
  
   if (n%c == 0) {
      cout << "Yes" <<endl;}
	else  {
    cout << "No"<< endl;}
 
}

Measured memory_bytes: 3636