akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	static FastScanner sc;
	static PrintWriter out;
	public static void main(String[] args){
		sc = new FastScanner();
		out = new PrintWriter(System.out);
		out.println(solve());
		out.flush();
	}

	static String solve(){
		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int max = X;
		int min = Y;
		for(int i=0;i<N;i++){
			max = Math.max(max, sc.nextInt());
		}
		for(int i=0;i<M;i++){
			min = Math.min(min, sc.nextInt());
		}
		if(max >= min) return "War";
		else return "No War";
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 23252
n = input()
p = list(map(int,input().split()))
count = 0
for i in range(1,len(p)-1):
    if (p[i] > p[i-1] and p[i] < p[i+1]) or (p[i] < p[i-1] and p[i] > p[i+1]):
        count += 1
print(count)


Measured memory_bytes: 38384
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

void read_separated_string(vector<int> &v, string str) {
  istringstream istr(str);
  string tmp;
  while (getline(istr, tmp, ' ')) {
    v.push_back(stoi(tmp));
  }
}

int binary_search(const vector<int> &v, int first, int last, int key) {
  int middle = (int) ( (first + last) / 2 );
  if (first > last) {
    return 0;
  } else if (key == v[middle]) {
    return 1;
  } else if (key < v[middle]) {
    return binary_search(v, first, middle-1, key);
  } else {
    return binary_search(v, middle+1, last, key);
  }
}

int main() {
  int N, Q;
  vector<int> n;
  vector<int> q;
  string str;

  cin >> N; cin.ignore();
  getline(cin, str);
  read_separated_string(n, str);
  cin >> Q; cin.ignore();
  getline(cin, str);
  read_separated_string(q, str);

  int count = 0;
  for (int i = 0; i < q.size(); ++i) {
    count += binary_search(n, 0, n.size()-1, q[i]);
  }
  cout << count << endl;
}

Measured memory_bytes: 3136
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

uint64_t seqlen(char *p) {
  uint64_t ctr = 0;
  for (; *p != '\0'; p++, ctr++) {
    if ((*p != 'A') && (*p != 'C') && (*p != 'G') && (*p != 'T')) break;
  }
  return ctr;
}


int main(int argc, char const* argv[])
{
  char str[11];
  memset(str, 0, 11);
  fgets(str, 11, stdin);
  uint64_t longest = 0;
  char *p = str;
  for (; *p != '\0'; p++) {
    longest = (longest < seqlen(p)) ? seqlen(p) : longest;
  }
  printf("%lu\n", longest);
  return 0;
}


Measured memory_bytes: 128
import java.util.*;







// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail

public class Main{
    public static void main(String args[] ) throws Exception {
        
        //Scanner
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] A = new long[n+1];
        long[] B = new long[n];
        for(int i=0;i<n+1;i++) {
            A[i] = scanner.nextLong();
            
        }
        for(int i=0;i<n;i++) {
            B[i] = scanner.nextLong();
        }
        long sum=0;
        for(int i=0;i<n;i++) {
            if(A[i]>B[i]) {
                A[i]-=B[i];
                sum+=B[i];
                B[i] = 0;
            }
            else {
                sum+=A[i];
                B[i]-=A[i];
                A[i]=0;
            }
            
            
            if(A[i+1]>B[i]) {
                A[i+1]-=B[i];
                sum+=B[i];
                B[i] = 0;
            }
            else {
                sum+=A[i+1];
                B[i]-=A[i+1];
                A[i+1]=0;
            }
        }
        System.out.println(sum);
    }
    
    
    
}


Measured memory_bytes: 83488
from heapq import heapify,heappush,heappop

def main():
    N,M = map(int,input().split())
    A = [-x for x in map(int,input().split())]
    heapify(A)
    for i in range(M):
        tmp = -heappop(A)
        tmp2 = tmp//2
        heappush(A,-tmp2)
    ans = 0
    for i in range(N):
        ans += A[i]

    ans = abs(ans)
    return ans

print(main())


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

int main() {
	
	int n;
	double t, a;
	cin >> n >> t >> a;
	double min = 1001001;
	int ans;
	rep(i, n){
		int h;
		cin >> h;
		double tmp = abs(a - (t - h * 0.006));
		if(min > tmp){
			min = tmp;
			ans = i + 1;
		}
	}
	cout << ans << endl;
	
	
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    HashMap<Integer, Long> map = new HashMap<Integer, Long>();
    int N = sc.nextInt();
    long K = sc.nextLong();
    int ans = 0;
    long sum = 0;
    for(int i = 0; i < N; i++) {
      int a = sc.nextInt();
      long b = sc.nextLong();
      if(map.containsKey(a)) {
        map.put(a, map.get(a) + b);
      } else {
        map.put(a, b);
      }
    }
    ArrayList<Integer> list = new ArrayList<>(map.keySet());
    Collections.sort(list);
    for(int i = 0; i < list.size(); i++) {
      sum += map.get(list.get(i));
      if(sum >= K) {
        ans = list.get(i);
        break;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 86364
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

struct LCA {
	vector<vector<int>>table;
	vector<int>dep;
	vector<vector<int>>e;
	const int LOG = 25;
	void dfs(int now,int par,int d) {
		table[now][0] = par;
		dep[now] = d;
		fore(x,e[now]) {
			if (x != par)dfs(x,now,d + 1);
		}
	}
	//0-indexed
	//edgesは双方向
	void lcainit(int n,int root,vector<int>edges[]){
		e.resize(n);
		dep.resize(n);
		table.resize(n);
		for (int i = 0; i < n; i++) {
			fore(x, edges[i])e[i].pb(x);
		}
		for (int i = 0; i < n; i++)table[i].resize(LOG);
		dfs(root,-1,0);
		for (int k = 0; k + 1 < LOG; k++) {
			for (int i = 0; i < n; i++) {
				if (table[i][k] == -1)table[i][k + 1] = -1;
				else table[i][k + 1] = table[table[i][k]][k];
			}
		}
	}

	int query(int u, int v) {
		if (dep[u] > dep[v])swap(u, v);
		for (int i = LOG - 1; i >= 0; i--) {
			if(((dep[v]-dep[u]) >> i) & 1)v = table[v][i];
		}
		if (u == v)return v;
		for (int i = LOG - 1; i >= 0;i--) {
			if (table[u][i] != table[v][i]) {
				u = table[u][i];
				v = table[v][i];
			}
		}
		return table[u][0];
	}
};



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

	int n;
	cin >> n;
	vector<int>e[101010];
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int c;
			cin >> c;
			e[i].pb(c);
			e[c].pb(i);
		}
	}

	LCA lca;
	lca.lcainit(n,0,e);
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int u, v;
		cin >> u >> v;
		puts(lca.query(u, v));
	}

	return 0;
}


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

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


  string s;
  cin>>s;
  if(s=="ABC")
  	cout<<"ARC";
  else
  	cout<<"ABC";

  return 0;
}

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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <math.h>

int main() {

    long long int x[5];
    cin >> x[0] >> x[1] >> x[2] >> x[3] >> x[4];

    for ( long long int i = 0; i < 5; i++ ) {
        if ( x[i] == 0 ) cout << i+1 << endl;
    }

    return 0;

}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int K,X;
    cin >> K >> X;

    int down = X-(K-1);
    if (down < -1000000) {
        down = -1000000;
    }

    int up = X+(K-1);
    if (1000000 < up) {
        up = 1000000;
    }

    for (int i=down; i<=up; i++) {
        cout << i << " ";
    }

    return 0;
};


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
for i in range(N-2,-1,-1):
  if H[i]>H[i+1] and H[i]-H[i+1]==1:
    H[i] = H[i]-1
  elif H[i]<=H[i+1]:
    H[i] = H[i]
  else:
    print("No")
    exit()
print("Yes")


Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,x;
  cin>>N>>x;
  vector<int> A(N);
  for(int &i:A)
    cin>>i;
  int j=0;
  for(int i=1;i<N;i++){
    if(A[i]+A[i-1]<x)
      continue;
    j+=A[i]+A[i-1]-x;
    A[i]=max(x-A[i-1],0LL);
  }
  cout<<j<<endl;
}

Measured memory_bytes: 4028
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:16777216")
#pragma warning( disable : 6031)
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <limits>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-9)
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef tuple<int, int, int> tiii;
const long long mod = 1000000007;

void min_self(ll& a, ll b)
{
	a = min(a, b);
}

int main()
{
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
	int n, w;
	cin >> n >> w;
	vector<ll> dp(1e5 + 2, LLONG_MAX / 2);
	dp[0] = 0;
	for (int i = 0; i < n; i++)
	{
		int cw, cv;
		cin >> cw >> cv;
		for (int i = sz(dp) - cv - 1; i >= 0; i--)
		{
			min_self(dp[i + cv], dp[i] + cw);
		}
	}
	int res = 0;
	for (int i = 0; i < sz(dp); i++)
	{
		if (dp[i] <= w)
			res = i;
	}

	cout << res;
	return 0;
}

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cout << name << ": " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<"| ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int32_t main(){
    boost;

    
    //code
   	
   	int n ,l;

   	cin >> n >> l;

   	vector<pair<int,int>> v;

   	int s = 0;
   	for(int i = 1 ; i <= n ; ++i){
   		int x = l + i - 1;
   		s += l+i-1;

   		if(x < 0)
   			v.push_back({abs(x),0});
   		else
   			v.push_back({abs(x),1});
   	}

   	sort(v.begin() , v.end());

   	if(v[0].second == 1){
   		cout << s - v[0].first;
   	}
   	else{
   		cout << s + v[0].first;
   	}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int ans=max(a,b);
	if(a==ans)
	{
		ans+=max(a-1,b);
	}
	else
	{
		ans+=max(a,b-1);
	}
	cout<<ans<<endl;
}

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

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

  string s;
  cin >> s;

  int cnt=0, ans=0;
  rep(i ,(int)s.size()){
    if(s[i]!='A'&&s[i]!='T'&&s[i]!='C'&&s[i]!='G')cnt=0;
    else cnt++;
    if(ans<cnt)ans=cnt;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3596
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<fstream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

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

    // input
    ll X, Y, Z, K;
    cin >> X >> Y >> Z >> K;

    vector<ll> A(X);
    vector<ll> B(Y);
    vector<ll> C(Z);

    FOR(i, 0, X){
        cin >> A[i];
    }

    FOR(i, 0, Y){
        cin >> B[i];
    }

    FOR(i, 0, Z){
        cin >> C[i];
    }

    vector<ll> AB;
    for(ll a : A){
        for(ll b : B){
            AB.push_back(a+b);
        }
    }
    sort(ALL(AB), greater<ll>());
    
    if(AB.size()>K){
        AB.resize(K);
    }

    vector<ll> ABC;
    for(ll ab : AB){
        for(ll c : C){
            ABC.push_back(ab + c);
        }
    }
    sort(ALL(ABC), greater<ll>());

    FOR(i, 0, K){
        p(ABC[i]);
    }

    return 0;
}

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

typedef long long ll;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int n;
	cin >> n;
	int q[n];
	FOR(i,0,n){
		int p;
		cin >> p;
		q[p-1] = i;
	}
	int ans = 1;
	int t = 1;
	FOR(i,1,n){
		if(q[i-1] < q[i]){
			t++;
		}else{
			t = 1;
		}
		ans = max(ans, t);
	}
	ANS(n - ans);
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<cctype>
using namespace std;

int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int a,b;
	cin>>a>>b;
	cout<<(a-1)*(b-1)<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  int count=0;
  for(int i=1;i<=n;i++){
    if(i<10) count++;
    if(100<=i and i<1000) count++;
    if(10000<=i and i<100000) count++;
  }
  cout<< count<<endl;

}

Measured memory_bytes: 384
import sys
import numba

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@numba.njit('(i8,)', cache=True)
def main(N):
    x = 0
    for a in range(1, N+1):
        for b in range(1, N//a+1):
            x += a*b
    return x

N = int(read())
print(main(N))


Measured memory_bytes: 106232
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

\

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 親が同じか判別
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 根を繋ぎ直す
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 親が同じか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 連結成分の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


def resolve():
    n, m = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(m)][::-1]
    uf = UnionFind(n)

    res = [(n * (n - 1)) // 2]
    for a, b in AB:
        if not uf.same(a - 1, b - 1):
            pre1 = uf.size(a - 1)
            pre2 = uf.size(b - 1)
            pre_score = (pre1 * (pre1 - 1)) // 2 + (pre2 * (pre2 - 1)) // 2

            uf.union(a - 1, b - 1)
            now = uf.size(a - 1)
            now_score = (now * (now - 1)) // 2

            res.append(res[-1] + pre_score - now_score)
        else:
            res.append(res[-1])

    for i in reversed(range(m)):
        print(res[i])


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 34808
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    string s1,s2,s3;
    cin >>s1>>s2>>s3;
    
    cout << char(s1[0]+'A'-'a') <<char(s2[0]+'A'-'a')<<char(s3[0]+'A'-'a')<< endl;

    return 0;
    

}

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

#define IOS             ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define watch(x);       cout << "\n" <<  #x << " is: " << x << "\n";
#define ll              long long int
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define pb              push_back
#define nl              cout<<"\n"
#define gcd(a,b)        __gcd(a,b)
#define sq(a)           (a)*(a)
#define loop(i,a,b)     for (ll i = a; i <= b; i++)
#define rloop(i,a,b)    for (int i = a; i >= b; i--)
#define sz(a)           a.size()
#define mod             1000000007
#define PI              2*acos(0.0)

int main()
{
    IOS
    int T=1;
    //cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        deque<char>q;
        loop(i,0,sz(s)-1) q.pb(s[i]);
        int q1;
        cin>>q1;
        int flag=0;
        while(q1--)
        {
            int t;
            cin>>t;
            if(t==1) flag^=1;
            else
            {
                int f;
                char c;
                cin>>f>>c;
                if(f==1)
                {
                    if(flag)
                    q.pb(c);
                    else q.push_front(c);
                }
                else
                {
                    if(!flag)
                    q.pb(c);
                    else q.push_front(c);
                }
            }
        }
        if(!flag)
        for(auto p:q) cout<<p;
        else{
            reverse(all(q));
            for(auto p:q) cout<<p;
        }

    }
    return 0;
}


Measured memory_bytes: 4060
import sys
import os

s=list(input())
a=(s[0],s[1])
N1=int(a[0])*10+int(a[1])
b=(s[2],s[3])
N2=int(b[0])*10+int(b[1])

if N1 > 12 or N1 == 0:
    if N2 > 12 or N2 == 0:
        print("NA")
    else:
        print("YYMM")
else:
    if N2 > 12 or N2 == 0:
        print("MMYY")
    else:
        print("AMBIGUOUS")

Measured memory_bytes: 3064
def is_prime(x)
  for i in (2...x)
    return false if x % i == 0
    return true if i * i > x
  end
end

$isp = Array.new(2, false)
for i in (2..10000)
  $isp.push(is_prime(i))
end

def count(n)
  ans = 0
  (1..n).each do |i|
    ans += 1 if $isp[i] and $isp[n + 1 - i]
  end
  ans
end

while line = gets
  puts count(line.to_i)
end

Measured memory_bytes: 6924
(declaim (optimize (sped 3) (debug 0) (safety 0)))

(defun fact (n)
  (loop for a = 1 then (mod (* a i) 1000000007)
        for i from 2 to n
        finally (return a)))

(format t "~A~%" (let ((n (read))
                       (m (read)))
                   (case (abs (- n m))
                     (1 (if (> n m)
                            (mod (* (expt (fact m) 2) n) 1000000007)
                            (mod (* (expt (fact n) 2) m) 1000000007)))  
                     (0 (mod (* 2 (expt (fact n) 2)) 1000000007))
                     (t 0))))

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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	//insert code
	int n;
	cin>>n;
	vi a(n);
	rep(i,0,n)cin>>a[i];
	vector<vector<ll>>dp(n,vector<ll>(n));
	for (int i=n-1;i>=0;i--){
		for (int j=i;j<n;j++){
			if (i==j)dp[i][j]=a[i];
			else{
				dp[i][j]=max(a[i]-dp[i+1][j],a[j]-dp[i][j-1]);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
	return 0;
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
#define P pair<int,int>
#define fr first
#define se second
using namespace std;
typedef long long ll;
const int maxx=1e5+10;
const ll mod=1e9+7;
char s[maxx];
int n;
struct S{
    int bt[maxx];
    void init(){memset(bt,0,sizeof bt);}
    int lowbit(int x){return x&-x;}
    void add(int x,int val){
        while(x<=n){
            bt[x]+=val;
            x+=lowbit(x);
        }
    }
    ll ask(int x){
        ll res=0;
        while(x){
            res+=bt[x];
            x-=lowbit(x);
        }
        return res;
    }
}a[200];
int main(){
    cin>>n;
    scanf("%s",s+1);
    a[1].init(); // R
    a[2].init(); // G
    a[3].init(); // B
    ll ans=0;

    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(s[i]==s[j]) continue;
            if(s[i]!='R'&&s[j]!='R'){
                ans+=a[1].ask(j);
                if(2*j>i&&s[2*j-i]=='R') ans--;
            }else if(s[i]!='G'&&s[j]!='G'){
                ans+=a[2].ask(j);
                if(2*j>i&&s[2*j-i]=='G') ans--;
            }else{
                ans+=a[3].ask(j);
                if(2*j>i&&s[2*j-i]=='B') ans--;
            }
        }
        if(s[i]=='R') a[1].add(i,1);
        if(s[i]=='G') a[2].add(i,1);
        if(s[i]=='B') a[3].add(i,1);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4984
#include <iostream>
#include <functional>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

namespace _{struct _{_(){ // initialize
  cin.tie(0); ios::sync_with_stdio(false);
}}_;}
template <typename T, size_t size>
inline size_t len(const T (&)[size]) { return size; }
#define println(s) cout << s << '\n';
#define str to_string
#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()


int main() {
  while (1) {
    int in;
    cin >> in;
    if (in == 0) break;
    int n = 1000 - in;

    int c = 0;
    c += n / 500;
    n %= 500;

    c += n / 100;
    n %= 100;

    c += n / 50;
    n %= 50;

    c += n / 10;
    n %= 10;

    c += n / 5;
    n %= 5;

    c += n / 1;
    n %= 1;

    println(str(c));
  }
  return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>

int main() {
    int A, B, pos = 0;
    char S[20];
    scanf("%d %d %s", &A, &B, S);
    for (int i = 0; S[i] != '\0'; i++) {
        S[i] == '-' ? pos += i + 1 : pos += 0;
    }
    pos == A + 1 ? puts("Yes") : puts("No");
    return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for (int i = (n); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll dp[101][100001];

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

    ll wight[n], value[n];
    rep(i, n) cin >> wight[i] >> value[i];

    rep(i, 101) rep(j, 100001) dp[i][j] = 1e9 + 3;
    dp[0][0] = 0;
    rep(i, n)
    {
        rep(j, 100001)
        {
            if (j - value[i] >= 0)
                dp[i + 1][j] = min(dp[i][j], dp[i][j - value[i]] + wight[i]);
            else
                dp[i + 1][j] = dp[i][j];
        }
    }
    ll res = 0;
    rep(i, 100001)
    {
        if (dp[n][i] <= w)
            res = i;
    }
    OP(res);
    return 0;
}

Measured memory_bytes: 79104
#include <iostream>

using namespace std;

int main(){
  int r;
  std::cin >> r;

  if( r < 1200 ){
    std::cout << "ABC" << '\n';
  }else if( r < 2800 ){
    std::cout << "ARC" << '\n';
  }else{
    std::cout << "AGC" << '\n';
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

constexpr int P = 1000000007;

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

    int n;
    cin >> n;

    int p[3] = {};
    ll r = 1;

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

        ll t = 0;
        for (int j = 0; j < 3; j++) {
            if (p[j] == a) {
                if (t == 0) p[j]++;
                t++;
            }
        }
        r = r * t % P;
    }

    cout << r << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <string, int> psi;
typedef pair <psi, int> psii;

psii a[110];

char buf[100];

string read(){
	scanf("%s", buf);
	return buf;
}

int main(){
	int n; scanf("%d", &n);
	for (int i = 0; i < n; i++){
		a[i].fi.fi = read(), a[i].se = i + 1;
		scanf("%d", &a[i].fi.se);
		a[i].fi.se *= -1;
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++){
		printf("%d\n", a[i].se);
	}
	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
N=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for item in a:
    d[item-1]+=1
    d[item]+=1
    d[item+1]+=1
b=sorted(d.items(),key=lambda x:x[1],reverse=True)
print(b[0][1])

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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i+1 < n; ++i) {
        if(s.substr(i, 2) == "AC") {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

int main() {
  long long n, k;
  cin >> n >> k;
  
  long long c = 1;
  for(int i=0; i<n; i++){
    if(i==0){
      c *= k;
    }else{
      c *= (k-1);
    }
  }  
  
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
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, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
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=10**9+7

n=I()
F=sorted(LI(),reverse=True)
flg=[0]*len(F)
flg[0]=1
a=1
flg[0]=1
now=[F[0]]
for i in range(n):
    cnt=0
    for j in range(len(F)):
        if flg[j]==0 and F[j]<now[cnt]:
            cnt+=1
            flg[j]=1
            now+=[F[j]]
        if cnt==a:
            now.sort(reverse=True)
            a*=2
            break
    else:
        print("No")
        exit()

print("Yes")





















Measured memory_bytes: 129184
/*
    ?????????????????¨??????
*/

#define __1__

#ifdef __1__
#include <iostream>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i = 0;i < (n);i++)
#define _MAX 7
#define INF 7e10
#define MIN(a,b) (a)>(b)?(b):(a)
using namespace std;
typedef long long int lint;


int dist,n,m;
lint tm[_MAX][_MAX+2]; //tm[][0]?????????????????????,tm[][m+1]???????????´??????
lint S[_MAX];
lint D[_MAX];

lint rettm(){
    lint ans = 0;
    rep(i,n){
        ans = max(ans,tm[i][m+1]);
    }
    return ans;
}

void maketm(int x){
    rep(i,m){
        tm[x][i+1]=tm[x][0]+D[i]*S[x];
    }
    tm[x][m+1]=tm[x][0]+S[x]*dist;
    return;
}

void show(){
    rep(i,n){
        rep(j,m+2){
            printf("%4lld ",tm[i][j]);
        }
        cout << endl;
    }
    cout << endl;
    return;
}

int flag[5]={0};

bool check(){
    rep(i,n-1){
        if(tm[i][0]>=tm[i+1][0]){
            return false;
        }
    }
    rep(i,n){
        rep(j,n){
            if(i<j&&tm[i][m+1]>tm[j][m+1]){
                bool hoge = 0;
                rep(k,m){
                    if(tm[i][k+1]==tm[j][k+1]){
                        rep(l,n){
                            if(l!=i&&l!=j&&tm[i][k+1]==tm[l][k+1])
                                return false;
                        }
                        hoge = true;
                    }
                }
                if(hoge == 0)
                    return false;
            }
        }
    }
    return true;
}

lint dfs(int d){
    lint ans = INF;
    if(d==n){
        if(check()){
//            show();
            return rettm();
        }else{
            return 7e10;
        }
    }
    rep(i,n){
        if(flag[i]==1)
            continue;
        flag[i]=1;
        if(i==0){
            tm[i][0]=0;
            maketm(i);
            ans = min(dfs(d+1),ans);
        }else if(flag[i-1]==1){
            tm[i][0]=tm[i-1][0]+1;
            maketm(i);
            ans = min(dfs(d+1),ans);
        }
        rep(j,n){
            if(j==i||flag[j]==0)
                continue;
            rep(k,m){
                tm[i][0]=tm[j][k+1]-D[k]*S[i];
                maketm(i);
                ans = min(dfs(d+1),ans);
            }
            tm[i][0]=tm[j][m+1]-dist*S[i];
            maketm(i);
            ans = min(dfs(d+1),ans);
        }
        flag[i]=0;
    }
    return ans;
}
    
int main() {
    cin >> dist >> n;
    rep(i,n){
        cin >> S[i];
    }
    cin >> m;
    rep(i,m){
        cin >> D[i];
    }
    cout << dfs(0) << endl;
    return 0;
}
#endif

Measured memory_bytes: 1172
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <string>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
int main() {
    vector<long long> a(3);
    cin>>a[0]>>a[1]>>a[2];
    sort(a.begin(), a.end());
    long long ans = 0;
    if(a[2] % (long long)2 != 0) ans = a[0] * a[1];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int k, a, b;
	cin >> k >> a >> b;
	
	bool ok = false;
	for (int i = k; i <= 1000; i += k) {
		if (i >= a && i <= b) {
			ok = true;
			break;
		}
	}
	
	cout << (ok ? "OK" : "NG") << endl;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<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);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

ll func(ll b, ll n){
    ll ret = 0;
    while (n > 0){
        ret += n % b;
        n /= b;
    }
    return ret;
}

int main() {
    ll N, S;
    cin >> N >> S;

    ll ans = longinf;

    if (N == S){
        cout << N + 1 << endl;;
        return 0;
    }

    ll p;
    for (ll b = 2; b * b <= N; b++){
        if(func(b, N) == S){
                cout << b << endl;
                return 0;
        }
        p = b;
    }

    for(ll p = 1; p * p < N; p++){
        if(p > S) break;
        if((N - S + p) % p==0){
            ll b = (N - S + p) / p;
            if(b > S - p){
                chmin(ans ,b);
            }
        }
    }

    cout << (ans == longinf ? -1 : ans) << endl;
    
    return 0;
}


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val Array(datX, datY) = readLine.split(" ").map(_.toInt)

    var ans = false
    (0 to datX) foreach {i =>
      val turtle = i
      val crane = datX - i

      if (ans == false) {
        if (turtle * 4 + crane * 2 == datY) ans = true
      }
    }

    println(if(ans) "Yes" else "No")
  }
}


Measured memory_bytes: 54788
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct lpl{
	int t1, t2;
	bool operator < (const lpl &A)const{return (t1 == A.t1 ) ? (t2 < A.t2) : (t1 < A.t1);}
};
int N, K, L, fa1[maxn], fa2[maxn];
map<lpl, int> mp;

int find1(int t){
	return (fa1[t] == t) ? (t) : (fa1[t] = find1(fa1[t]));
}

int find2(int t){
	return (fa2[t] == t) ? (t) : (fa2[t] = find2(fa2[t]));
}

inline void connect1(int a, int b){
	int A = find1(a), B = find1(b);
	fa1[A] = B;
}

inline void connect2(int a, int b){
	int A = find2(a), B = find2(b);
	fa2[A] = B;
}

inline void check(){
	for(int i = 1; i <= N; ++i) printf("i = %d %d %d\n", i, fa1[i], fa2[i]);
}

int main()
{
	scanf("%d%d%d", &N, &K, &L);
	for(int i = 1; i <= N; ++i){
		fa1[i] = i; fa2[i] = i;
	}
	for(int a, b, i = 1; i <= K; ++i){
		scanf("%d%d", &a, &b);
		connect1(a, b);
	}
	for(int a, b, i = 1; i <= L; ++i){
		scanf("%d%d", &a, &b);
		connect2(a, b);
	}
	for(int i = 1; i <= N; ++i){
		fa1[i] = find1(i), fa2[i] = find2(i);
		mp[(lpl){fa1[i], fa2[i]}]++;
	}
	for(int i = 1; i <= N; ++i) printf("%d ", mp[(lpl){fa1[i], fa2[i]}]);
	return 0;
}

Measured memory_bytes: 13568
#include<iostream>
using namespace std;
int N,M,P;
int X[100],sum;
int main(){
  while(cin>>N>>M>>P&&N){
    sum=0;
    for(int i=0;i<N;i++)cin>>X[i],sum+=X[i];
    sum*=(100-P);
    if(X[M-1])cout<<sum/X[M-1]<<endl;
    else cout<<0<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <map>
#include <queue>
#include <string>
using namespace std;

int prime[1000000],n;
bool isprime[1000001];

int sieve(int n){
	int p=0;
	for(int i=0;i<=n;i++)isprime[i]=true;
	isprime[0]=isprime[1]=false;
	for(int i=0;i<=n;i++){
		if(isprime[i]){
			prime[p++]=i;
			for(int j=i*2;j<=n;j+=i)isprime[j]=false;
		}
	}
	return p;
}

int main(){
	sieve(1000000);
	while(cin>>n){
		if(n==0)return 0;
		int ans=0;
		for(int i=0;i<n;i++)ans+=prime[i];
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			Question.Exec();
		}
	}

	public static class Question
	{
		public static void Exec()
		{
			var array = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
			long N = long.Parse(Console.ReadLine());
			long Q = array[0];
			long H = Math.Min(array[1], 2 * Q);
			long S = Math.Min(array[2] , 2 * H);
			long D = array[3];
			var dict = new Dictionary<double, long>();

			long answer = 0;
			long min = long.MaxValue;

			if (N > 1) {
				if (2 * S <= D) {
					answer = N * S;
				} else {
					if (N % 2 == 0) {
						answer = (N / 2) * D;
					} else {
						answer = (N / 2) * D + (N % 2) * S;
					}
				}
			} else {
				answer = N * S;
			}

			if (min > answer) {
				min = answer;
			}

			Console.WriteLine($"{min}");

			Console.ReadKey();
		}
	}
}

Measured memory_bytes: 13280
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX-1;
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;
struct edge { ll from; ll to; ll cost; };

ll f1(ll a,ll b) {
	ll height_1 = a / 2;
	ll height_2 = a - height_1;

	ll temp = -1;
	for (ll i = 0; i <= b; i++) {
		vector<ll>comp;
		comp.push_back(height_1 * i);
		comp.push_back(height_2 * i);
		comp.push_back(a * (b - i));
		sort(all(comp));
		if(temp == -1){
			temp = comp[2] - comp[0];
		}
		else {
			temp = min(temp, comp[2] - comp[0]);
		}
	}
	return temp;
}
ll f2(ll a, ll b) {
	if (a % 3 == 0)return 0;
	else return (a / 3 + 1)*b - (a / 3)*b;

}

int main(){
	ll H, W;
	cin >> H >> W;
	ll res = min(min(f1(W, H), f1(H, W)), min(f2(H, W), f2(W, H)));
	cout << res << endl;
	
	return 0;
}

Measured memory_bytes: 256
n,a,b = list(map(int, input().split()))
h = []
for i in range(n):
    h.append(int(input()))

import math as m

imin = 1
imax = sum([hh // a + 1 for hh in h])

while ( imax > imin+1 ):
    num = imin + (imax-imin)//2
    acnt = sum([m.ceil((hi- b*num)/(a-b)) for hi in h  if (hi- b*num)>0])
    if ( acnt<=num ):
        imax = num
    else:
        imin = num
print(imax)

Measured memory_bytes: 11044
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long LL;
int poww(int x,int y)
{
    int sum=1;
    for(int i=1;i<=y;i++)
        sum*=x;
    return sum;
}
int main()
{
    int n;
    scanf("%d",&n);
    int head,wei,t,ans=0,num=1,sum,t1,t2;
    t=n;
    while(t/10>0) t/=10,num++;
    t1=t;t2=n%10;
    for(int i=1;i<=n;i++)
    {
        head=i;
        while(head/10>0) head/=10;
        wei=i%10;
        if(wei==0) continue;
        if(head==wei) ans+=1;
        t=wei*10+head;
        if(t<=n) ans++;
        else continue;
        for(int j=1;j<=num-3;j++) ans+=poww(10,j);
        if(wei<t1&&num>2) ans+=poww(10,num-2);
        if(wei==t1&&num>2)
        {
            sum=(n-t1*poww(10,num-1)-t2)/10;
            if(head<=t2) ans+=sum+1;
            else ans+=sum;
        }
    }
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 256
n, k = [int(e) for e in input().split()]
arr = [int(e) for e in input().split()]
dp = [0]*len(arr)
 
for i in range(1,len(arr)):
  dp[i] = min(dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i))
print(dp[-1])



Measured memory_bytes: 53344
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {
    
    new Main().run();
  }

  public void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String op;
      String[] words;
      Tree tree = new Tree();
      StringBuilder buf = new StringBuilder();

      for(int i=0,k=0; i<n; i++,k=0){
        words = br.readLine().split(" ");
        op  = words[k++];
        if ( op.equals("insert") ) { 
          tree.insert(Integer.parseInt(words[k++]));
        }
        else {
          buf.append(tree.getRoundPath());
        }
      }

      System.out.print(buf);

    }
    catch(IOException e) {
      System.out.println("IOException!");
    }
  }
}

class Tree {

  static final BTreeNode NIL = new BTreeNode();
  BTreeNode root;
  StringBuilder buf;

  public Tree() {
    root = NIL;
    buf = new StringBuilder();
  }

  public void insert(int val) {
    BTreeNode y = NIL;
    BTreeNode x = root;
    BTreeNode z = new BTreeNode();
    z.key = val;

    while( !x.equals(NIL) ) {
      y = x;
      if( z.key < x.key )
        x = x.left;
      else
        x = x.right;
    }
    z.parent = y;

    if( y.equals(NIL) ){
      root = z;
    }
    else if( z.key < y.key )
      y.left = z;
    else
      y.right = z;
  } 
  void preParse(BTreeNode u) {
    if( !u.equals(NIL) ) {
      buf.append(" ").append(u.key);
      preParse(u.left);
      preParse(u.right);
    }
  }
  void inParse(BTreeNode u) {
    if( !u.equals(NIL) ) {
      inParse(u.left);
      buf.append(" ").append(u.key);
      inParse(u.right);
    }
  }

  String getRoundPath() {
    buf.setLength(0);

    inParse(root);
    buf.append("\n");
    preParse(root);
    buf.append("\n");

    return buf.toString();
  }
}

class BTreeNode {
  int key;
  BTreeNode parent,left,right;

  public BTreeNode() {
    this.key = -1;
    this.parent =
    this.left =
    this.right = Tree.NIL;
  }

  @Override
  public boolean equals(Object o) {
    if(o == this) return true;
    if(o == null) return false;
    if(!(o instanceof BTreeNode)) return false;

    BTreeNode node = (BTreeNode)o;
    if(!(this.key == node.key)) return false;

    return true;
  }
}


Measured memory_bytes: 126552
/**
 *    author:  tourist
 *    created: 29.09.2018 15:26:49       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
	map<int,int>mp[2];
	for(int i = 0;i < n;i++) {
	 int x;
	 cin >> x;
	 mp[i & 1][x] ++;
	}
	vector<pair<int,int>>v[2];
	for (int u = 0;u < 2;u++){
		for(auto &p : mp[u]) {
			v[u].emplace_back(p.second,p.first);
		}
		if(v[u].size() == 1) {
			v[u].emplace_back(0 , -1);
		}
		sort(v[u].rbegin(),v[u].rend());
	}
	int ans = 0;
	for (int i = 0;i < 2;i++) {
		for (int j = 0;j < 2;j++) {
			if(v[0][i].second != v[1][j].second){
				ans = max(ans,v[1][j].first+v[0][i].first);
			}
		}
	}
	cout << n - ans << endl;
} 


Measured memory_bytes: 8932
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
  ll a, v, b, w, t;
  cin >> a >> v;
  cin >> b >> w;
  cin >> t;

  ll le, vs;

  le = abs(a - b); //min = 1;
  vs = v - w;

  if(vs * t >= le) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

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

int main() {
  int r,d,x;
  cin >> r >> d >> x;
  vector<long> vec(11);
  vec.at(0) = x;
  for(int i=0;i<10;i++){
    vec.at(i+1) = r*vec.at(i) - d;
  }
  for(int i=1;i<11;i++){
    cout << vec.at(i) << endl;
  }
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
  int n,m,x,y;
  cin>>n>>m>>x>>y;
  vector <int> vx(n);
  vector <int> vy(m);
  int i;
  for(i=0;i<n;i++ ){
    cin>>vx[i];
  }
  for(i=0;i<m;i++ ){
    cin>>vy[i];
  }
  int flag = 0;
  sort(vx.begin(),vx.end());
  sort(vy.begin(),vy.end());
  if(vx[n-1]<vy[0]){
    for(i=x+1;i<=y;i++){
      if(vx[n-1]<i&&vy[0]>=i)
        flag++;
    }
  }
  if(flag==0)
    cout<<"War";
  else cout<<"No War";
  return 0;
}

Measured memory_bytes: 256