akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize(2)
// Happy TLE and WA every day!
// by: zxb
#include<bits/stdc++.h>
#define mp				make_pair
#define rep(i,n)		for(int i = 0; i < n; i++)
#define foreach(i,c)	for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define BINF			0x7fffffff
#define INF				0x3f3f3f3f
#define LINF			3223372036854775807
#define END(s)			{cout<<s; return 0;}
#define CON(s)			{cout<<s; continue;}
#define BRE(s)			{cout<<s; break;}
#define pb				push_back
//#define int				long long
#define All(a)			a.begin(), a.end()  //with A in CAPITAL!!!
#define sz(a)			(int)a.size()
#define F				first
#define S				second
//#define usingFiles
using namespace std;

const int rp = 666666;
const bool debug = 1;
const bool I_good_vegetable_a = 1;

int n, m;
vector<int> a[100100];
int tag[100100];
vector<int> order;
int l[100100], r[100100];
int parent[100100];
bool known_parity[100100][2];
bool res = 1;

void dfs(int now, int par){
	l[now] = -INF, r[now] = INF;
	rep(i, a[now].size()){
		if(a[now][i] == par) continue;
		parent[a[now][i]] = now;
		dfs(a[now][i], now);
//		if(!res) return ;
		if(known_parity[a[now][i]][0]) known_parity[now][1] = 1;
		if(known_parity[a[now][i]][1]) known_parity[now][0] = 1;
		l[now] = max(l[now], l[a[now][i]] - 1);
		r[now] = min(r[now], r[a[now][i]] + 1);
	}
	if(tag[now] != -INF){
		l[now] = max(l[now], tag[now]);
		r[now] = min(r[now], tag[now]);
		known_parity[now][tag[now] % 2] = 1;
	}
	if(known_parity[now][1] && known_parity[now][0]) res = false;
	if(l[now] > r[now]) res = false;
	order.pb(now);
	return ;
}

int make(int now){
	if(parent[now] == -1) return l[now];
	l[now] = max(l[now], l[parent[now]] - 1);
	r[now] = min(r[now], r[parent[now]] + 1);
	while((l[now] % 2) == (tag[parent[now]] % 2)) l[now]++;
	return l[now];
}

signed main(){
	ios::sync_with_stdio(false);
	#ifdef usingFiles
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	cin >> n;
	rep(i, n - 1){
		int v, g;
		cin >> v >> g;
		v--, g--;
		a[v].pb(g);
		a[g].pb(v);
	}
	cin >> m;
	rep(i, n) tag[i] = -INF;
	rep(i, m){
		int v, g;
		cin >> v >> g;
		v--;
		tag[v] = g;
	}
	parent[0] = -1;
	dfs(0, -1);
	if(!res){
		cout << "No\n";
		return 0;
	}
	reverse(order.begin(), order.end());
	rep(i, order.size()){
		int now = order[i];
		tag[now] = make(now);
	}
	cout << "Yes\n";
	rep(i, n){
		cout << tag[i] << endl;
	}
	return 0;
}

/*
5
1 2
3 1
4 3
3 5
2
2 6
5 7
*/ 

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

typedef long long int ll;

int main(){
 ll N;
 cin >> N;
 ll ans = 0;
 ll A[100010];
 for(int i = 0;i < N;i++){
   cin >> A[i];
 }
 for(int i = 0;i < N;i++){
   if(A[A[i]-1] == i + 1){
     ans++;
   }
 }
 cout << ans / 2 << endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int A[3],B[3];
int deg[4];

int main(){
	for(int i = 0; i < 3; ++i){
		scanf("%d%d",A+i,B+i);
		--A[i];--B[i];
		++deg[A[i]];
		++deg[B[i]];
	}
	int n1 = 0, n2 = 0;
	for(int i = 0; i < 4; ++i){
		if(deg[i] == 1) ++n1;
		else if(deg[i] == 2) ++n2;
	}
	if( n1 == 2 && n2 == 2) puts("YES");
	else puts("NO");
	return 0;
}

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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  while (cin >> n >> m) {
    vector<pair<lli, lli>> p, q;
    for (int i = 0; i < n; ++i) {
      int a, b;
      cin >> a >> b;
      p.push_back(make_pair(a, b));
    }
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      q.push_back(make_pair(a, b));
    }
    for (int i = 0; i < n; ++i) {
      int k = 0;
      for (int j = 0; j < m; ++j) {
        lli x = abs(p[i].first - q[j].first) + abs(p[i].second - q[j].second);
        lli y = abs(p[i].first - q[k].first) + abs(p[i].second - q[k].second);
        if (x < y) {
          k = j;
        }
      }
      cout << k + 1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: map(str, sys.stdin.buffer.readline().split())
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

s = rr()
k = ri()
cnt = 0
i = 0
if len(set(s)) == 1:
  print(int(len(s)*k/2))
  exit()
while i < len(s)-1:
  if s[i] == s[i+1]:
    cnt += 1
    i += 1
  i += 1
cnt1 = 0
i1 = 0
s *= 2
while i1 < len(s)-1:
  if s[i1] == s[i1+1]:
    cnt1 += 1
    i1 += 1
  i1 += 1
print((cnt1 - cnt)*(k-1) + cnt)



Measured memory_bytes: 12500
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: isize,
        d: isize,
        xy: [(isize, isize); n]
    }

    let mut res = 0;
    let dd = d.pow(2);

    for (x_i, y_i) in xy {
        if dd >= (x_i.pow(2) + y_i.pow(2)) {
            res += 1;
        }
    }

    println!("{}", res);
}


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

#define mod 1000000007
#define vi vector<int>
typedef long long int ll;

int main (void)
{
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while(t--){
  	//cout << "Case #" << c - t << ": ";
	int n,d = 61;
	cin >> n;
	vector<ll> base(d,0),a(n);
	for(int i = 0;i < n;i++) cin >> a[i];
	string s;
	cin >> s;
	bool flag = 0;
	for(int j = n - 1;j > -1;j--){
		if(s[j] - '0'){
			for(int i = 0;i < d;i++){
				if(a[j]&(1LL<<i)){
					if(!base[i]){
						flag = 1;
						break;
					}
					a[j] ^= base[i];
				}
			}
		}
		else{
			for(int i = 0;i < d;i++){
				if(a[j]&(1LL<<i)){
					if(!base[i]){
						base[i] = a[j];
						break;
					}
					a[j] ^= base[i];
				}
			}
		}
		if(flag) break;
	}
	cout << flag << "\n";	
  }
  return 0;
}


Measured memory_bytes: 3616
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <math.h>
 
#define REP(i,n)for (int i=0;i<(n);i++)
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ll long long
using namespace std;
typedef pair<int,int> P;

const double INF = 100000.0;

double dp[30][1<<9];
int n,m,p,a,b;
int z[30][30];
int t[8];

int main(){
	int x,y,c;
	while(1){
		cin>>n>>m>>p>>a>>b;
		if(n+m+p+a+b==0)break;
		a--;b--;
		REP(i,n)cin>>t[i];
		REP(i,m)REP(j,m)z[i][j]=-1;
		REP(i,p){
			cin>>x>>y>>c;x--;y--;
			z[x][y]=z[y][x]=c;
		}
		REP(i,m)REP(j,1<<9)dp[i][j]=INF;
		dp[a][0]=0;
		queue<P>q;
		q.push(MP(a,0));
		while(q.size()){
			P p=q.front();q.pop();
			int now=p.first,bit=p.second;
			//cout<<now<<" "<<bit<<endl;
			REP(i,m){
				if(z[now][i]==-1)continue;
				REP(j,n){
					if(bit>>j&1)continue;
					if(dp[i][bit|1<<j]>dp[now][bit]+(double)z[now][i]/(double)t[j]){
						dp[i][bit|1<<j]=dp[now][bit]+(double)z[now][i]/(double)t[j];
						q.push(MP(i,bit|1<<j));
					}
				}
			}
		}
		double ans=INF;
		REP(i,1<<9)ans=min(ans,dp[b][i]);
		if(ans==INF)cout<<"Impossible"<<endl;
		else cout<<ans<<endl;
	}
}


Measured memory_bytes: 3448
use std::cmp::min;
use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        x: usize,
    }

    let mut value: Vec<usize> = vec![];
    let mut seq: Vec<Vec<usize>> = vec![];
    for _ in 0..n {
        input! {
            c: usize,
            an: [usize; m],
        }
        value.push(c);
        seq.push(an);
    }

    let mut ans = None;
    for mask in 0..(1<<n) {
        let mut tmp_total = 0;
        let mut xs = vec![0; m];
        for i in 0..n {
            if mask & (1 << i) == (1 << i) {
                tmp_total += value[i];
                for j in 0..m {
                    xs[j] += seq[i][j];
                }
            }

            if xs.iter().all(|&v| v >= x) {
                ans = match ans {
                    Some(v) => Some(min(v, tmp_total)),
                    None => Some(tmp_total),
                };
                // println!("{}: {:?}",tmp_total, xs);
            }
        }
    }

    match ans {
        Some(v) => println!("{}", v),
        None => println!("-1"),
    }

}


Measured memory_bytes: 2160
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;

ll nCr(ll n, ll r) {
	if (r > n) { return 0; }
	if (r * 2 > n) r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (ll i = 1; i <= r; ++i) {
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
ll sumdigit(ll n) {
	ll dig = 0, sum = 0;
	while (n) {
		dig = n % 10;
		sum = sum + dig;
		n = n / 10;
	}
	return sum;
}



int main() {
	const int group[12] = { 0,2,0,1,0,1,0,0,1,0,1,0 };
	int x, y;
	std::cin >> x >> y;
	if (group[x - 1] == group[y - 1]) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int x = s.nextInt();
		int y = s.nextInt();
		int z = s.nextInt();
		int w;

		w = z;
		z = y;
		y = x;
		x = w;

		System.out.println(x + " " + y + " " + z);

		s.close();

	}

}


Measured memory_bytes: 39252
require 'pp'

# 入力値を数値で返却する
def gets_i()
  gets.chomp.to_i
end

# 入力値を文字の配列で返却する
def gets_nsp_list()
  gets.chomp.split("")
end

N = gets_i
s_list = gets_nsp_list
t_list = gets_nsp_list

count = 0
(1..N).each do |i|
  if s_list.slice(N-i,N) == t_list.slice(0,i)
    count = i
  end
end
puts N * 2 - count


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

int main(){
    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    rep(i, n-2){
        if("ABC" == s.substr(i, 3)) ++cnt;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define N 100010
typedef long long LL;
LL a[N];
int n;
int main(){
    cin>>n;
    LL ans = 0LL;
    for(int i = 1; i <= n; i++){
        int j;
        scanf("%d", &j);
        a[j]++;
        ans += j;
    }
    int q;
    cin>>q;
    for(int i = 1; i <= q; i++){
        LL b, c;
        scanf("%lld%lld", &b, &c);
        if(a[b] > 0){
            ans += (c - b) * a[b];
            a[c] += a[b]; a[b] = 0LL;
        }
        printf("%lld\n", ans);
    }

    return 0;
} 

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

lstDiv = []
k = 1
while k * k <= m:
    div, r = divmod(m, k)
    if r == 0:
        lstDiv.append(k)
        lstDiv.append(div)
    k += 1

lstDiv = sorted(lstDiv, reverse=True)

for div in lstDiv:
    if div * n <= m:
        print(div)
        break

Measured memory_bytes: 3060
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }


int main () {
  int a,b,x;
  double result;
  cin >> a >> b >> x;
  if(x <= a*a*b/2) {
    result = atan2((double)b, (double) 2*x/a/b);
  } else {
    result = atan2((double) 2*b - (double)2*x/a/a, (double)a);
    // cout << result << endl;
  }
  pd(result * 180.0/M_PI);
}


Measured memory_bytes: 256
import copy
n,k = map(int,input().split())
d = input().split()
nd = list(map(str,range(10)))
for i in d:
  nd.remove(i)
l = len(str(n))
if "0" in nd:
  a1 = 1
else:
  a1 = 0
alist = nd[a1:]
for _ in range(l-1):
  tlist = []
  for i in alist:
    for j in nd:
      tlist.append(i+j)
  alist = copy.copy(tlist)
alist.append(nd[a1]+nd[0]*l)
for i in alist:
  if n <= int(i):
    print(i)
    exit()

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

int main (void) {
    int a, b, c;
    cin >> a >> b >> c;

    if (a == b) {
        cout << c << endl;
    }else if (b == c) {
        cout << a << endl;
    }else if (c == a) {
        cout << b << endl;
    }


    return 0;
}


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


void maxHeapify(int*, int);
void buildMaxHeap(int*);

unsigned int *A;
int num;
int main(){

  int i;

  scanf("%d", &num);
  
  A = malloc(sizeof(int)*num+1);

  for(i = 1; i <= num; i++){
    scanf("%d", &A[i]);
  }

  buildMaxHeap(A);
  
  for(i = 1; i <= num; i++){
    printf(" %d",A[i]);
  }
  printf("\n");
  
  return 0;
}

void maxHeapify(int* A, int i){
  int l, r, largest, temp;

  l = 2*i;
  r = 2*i+1;

  if (l <= num && A[l] > A[i]){
    largest = l;
  }
  else{
    largest = i;
  }

  if(r <= num && A[r] > A[largest]){
    largest = r;
  }

  if(largest != i){
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    maxHeapify(A, largest);
  }
}

void buildMaxHeap(int *A){
  int i;
  
  for(i = num/2; i > 0; i--){
    maxHeapify(A, i);
  }
}



Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
int dist;
int cnt[2020];
int main(){
	#ifdef FILIN
		#ifndef LOCAL
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	cin>>n>>x>>y;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			dist=j-i;
			dist=min(dist,abs(i-x)+abs(j-y)+1);
			dist=min(dist,abs(i-y)+abs(j-x)+1);
			cnt[dist]++;
		}
	} 
	for(int i=1;i<n;i++)
		cout<<cnt[i]<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
const int P=1e9+7;

int n;
char str[M];
int cnt[30];

void Solve(){
	for(int i=1;i<=n;i++)cnt[str[i]-'a']++;
	long long ans=1;
	for(int i=0;i<26;i++)if(cnt[i])(ans*=cnt[i]+1)%=P;
	ans--;if(ans<0)ans+=P;
	printf("%lld\n",ans);
}

int main(){
	scanf("%d%s",&n,str+1);
	Solve();
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;

class UnionFind {
  public:
  // 親の番号を格納。ルートだった場合は-(その集合のサイズ)
  vector<ll> parents;

  UnionFind(ll N) {
    parents = vector<ll>(N, -1);
  }

  // iがどのグループに属しているか
  ll root(ll i) {
    if (parents[i] < 0) {
      return i;
    } else {
      return parents[i] = root(parents[i]);
    }
  }

  // iが属しているグループの大きさ
  ll size(ll i) {
    return -parents[root(i)];
  }

  // root(a)とroot(b)を接続する
  bool connect(ll a, ll b) {
    ll rootA = root(a);
    ll rootB = root(b);
    if (rootA == rootB) {
        return false;
    } else {
      // 大きいほう(a)に小さいほう(b)をくっつける
      // 大小が逆の場合はスワップ
      if (size(rootA) < size(rootB)) {
        swap(rootA, rootB);
      }

      // aグループのサイズを増やす
      parents[rootA] += parents[rootB];
      // bの親をaのルートに変更する
      parents[rootB] = rootA;

      return true;
    }
  }

};

int main() {
  ll N, M;
  cin >> N >> M;
  vector<ll> A(M), B(M);
  for (ll i = 0; i < M; i++) {
    cin >> A[i];
    cin >> B[i];
  }

  vector<ll> sum(M + 1, 0);
  // 橋が全部崩壊した
  sum[M] = N * (N - 1) / 2;
  UnionFind Uni(N);
  for (ll i = M - 1; i >= 0; i--) {
    ll a = A[i];
    ll b = B[i];
    ll rootA = Uni.root(a-1);
    ll rootB = Uni.root(b-1);
    if (rootA != rootB) {
      sum[i] = sum[i + 1] - Uni.size(rootA) * Uni.size(rootB);
    } else {
      sum[i] = sum[i + 1];
    }
    Uni.connect(a-1, b-1);
  }
  for (ll i = 1; i < M + 1; i++) {
    cout << sum[i] << endl;
  }
  return 0;
}


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

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007)
#define IINF (1<<28)
#define LINF (1LL<<60)
#define rep(i, n)      REP(i, 0, (n))
#define repc(i, n)     REPC(i, 0, (n))
#define REP(i, n, m)   for (int i = (int)(n); i <  (int)(m); i++)
#define REPC(i, n, m)  for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
#define yesno(cond)       YESNO((cond), "Yes", "No")
#define YESNO(cond, a, b) cout << ((cond) ? (a) : (b)) << "\n"

struct SegmentTree {
  long long n;
  std::vector<long long> node;

  void init(long long _n) {
    n = 1;
    while(n < _n) n *= 2;
    node.resize(2*n-1, 0);
  }

  void update(long long i, long long v) {
    long long k = i+n-1;
    node[k] = v;
    while(k > 0) {
      k = (k-1)/2;
      node[k] = std::max(node[2*k+1], node[2*k+2]);
    }
  }

  long long find(long long s, long long t) {
    return _find(s, t, 0, 0, n);
  }

  long long _find(long long s, long long t, long long k, long long l, long long r) {
    if(r <= s || t <= l) return 0;
    if(s <= l && r <= t) return node[k];
    long long m = (r+l)/2, kl = 2*k+1, kr = 2*k+2;
    return std::max(_find(s, t, kl, l, m), _find(s, t, kr, m, r));
  }
};

namespace solver {
  using namespace std;
  typedef long long ll;

  static const int MAX = 200020;
  int N, hs[MAX], as[MAX];
  ll dp[MAX];
  SegmentTree st;

  void init() {
    cin >> N;
    rep(i, N) {
      cin >> hs[i];
      hs[i]--;
    }
    rep(i, N) {
      cin >> as[i];
    }
  }

  void solve() {
    st.init(N);
    ll maxv = 0;
    rep(i, N) {
      dp[hs[i]] = st.find(0, hs[i]) + as[i];
      st.update(hs[i], dp[hs[i]]);
      maxv = max(maxv, dp[hs[i]]);
    }
    cout << maxv << "\n";
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  solver::init();
  solver::solve();
  return 0;
}

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

#define st first
#define nd second
#define pb push_back

typedef long long   ll;
typedef double      db;
typedef long double ldb;

typedef pair <int, int> pii;
typedef pair <ll,  ll>  pll;
typedef pair <ll,  db>  pdb;
typedef pair <ldb, ldb> pldb;

template <typename T>
void   Debug (T begin, T end);
int    si    ();
ll     sl    ();
string ss    (int);
db     sf    ();
ldb    slf   ();
void   pi    (int, char = '\n');
void   pl    (ll, char = '\n');
void   pf    (db, char = '\n');
void   plf   (ldb, char = '\n');
void   ps    (string, char = '\n');

ll russian(ll, ll, ll);
ll fastpow(ll, ll, ll);
ll slowpow(ll, ll, ll);
ll _gcd(ll, ll);
ll _lcm(ll, ll);
ll extgcd(ll, ll, ll&, ll&);
ll _inv(ll, ll);

const int INF  = 1e9;
const ll  LINF = 1e18;

int main()
{
    int a = si(), b = si();
    if (a > 9 || b > 9)
        pi(-1);
    else
        pi(a * b);

    return 0;
}

template <typename T>
void Debug(T begin, T end)
{
    printf("\nDEBUG:\n");
    while (begin != end)
        printf("%d ", *begin),
        begin++;
    printf("\n\n");
}

template <typename T>
T scanf_t(string s)
{
    T a;
    scanf(s.c_str(), &a);
    return a;
}

template <typename T>
void printf_t(T a, string s, char end_l)
{
    s.push_back(end_l);
    printf(s.c_str(), a);
}

int si() { return scanf_t<int>("%d"); }
ll sl() { return scanf_t<ll>("%lld"); }
db sf() { return scanf_t<db>("%f"); }
ldb slf() { return scanf_t<ldb>("%Lf"); }

void pi(int a, char end_l) { printf_t<int>(a, "%d", end_l); }
void pl(ll a, char end_l) { printf_t<ll>(a, "%lld", end_l); }
void pf(db a, char end_l) { printf_t<db>(a, "%lf", end_l); }
void plf(ldb a, char end_l) { printf_t<ldb>(a, "%Lf", end_l); }

void ps(string a, char end_l)
{
    string s = "%s";
    s.push_back(end_l);
    printf(s.c_str(), a.c_str());
}

string ss(int NN)
{
    char T[NN];
    scanf("%s", T);
    return (string)T;
}

ll fastpow(ll a, ll k, ll m)
{
    ll r = 1LL;
    while (k)
    {
        if (k & 1LL)
            r = (r * a) % m;
        a = (a * a) % m;
        k >>= 1LL;
    }
    return r;
}

ll slowpow(ll a, ll k, ll m)
{
    ll r = 1LL;
    while (k)
    {
        if (k & 1LL)
            r = russian(r, a, m);
        a = russian(a, a, m);
        k >>= 1LL;
    }
    return r;
}

ll russian(ll a, ll k, ll m)
{
    ll r = 0LL;
    while (k)
    {
        if (k & 1LL)
            r = (r + a) % m;
        a = (a + a) % m;
        k >>= 1LL;
    }
    return r;
}

ll _gcd(ll a, ll b)
{
    while (b)
        swap(a %= b, b);
    return a;
}

ll _lcm(ll a, ll b)
{
    return a / _gcd(a, b) * b;
}

ll extgcd(ll a, ll b, ll& k, ll& l)
{
    if (b == 0)
    {
        k = 1; l = 0;
        return a;
    }
    ll res = extgcd(b, a % b, l, k);
    l -= a / b * k;
    return res;
}

ll _inv(ll a, ll p)
{
    return fastpow(a, p - 2, p);
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>

using namespace std;

void b_comparing_strings(void) {
	string a, b;
	cin >> a >> b;
	
	string ab="", ba="";
	for (int i = 0; i < stoi(b); i++) ab += a;
	for (int i = 0; i < stoi(a); i++) ba += b;

	if (ab < ba) cout << ab << endl;
	else         cout << ba << endl;

}

int main()
{
    b_comparing_strings();

    return 0;
}

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

int main(){
	int n;
	cin >> n;
	vector<double> p(n+1);
	rep(i,n){
		cin >> p[i+1];
	}
	if(n==1){
		cout << p[1] << endl;
		return 0;
	}
	vector<vector<double>> dp(n+10,vector<double>(n+10));
	dp[1][0] = 1-p[1];
	dp[1][1] = p[1];
	for(int i(2);i<=n;++i){
		dp[i][0] = dp[i-1][0] * (1-p[i]);
		for(int j(1);j<=i-1;++j){
			dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1-p[i]);
		}
		dp[i][i] = dp[i-1][i-1] * p[i];
	}
	double ans(0);
	for(int i(n);i>n/2;--i){
		ans += dp[n][i];
	}
	cout << setprecision(20) << ans << endl;
	return 0;
}

Measured memory_bytes: 71168
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> a(n-1);
for(int i=0;i<n-1;i++){
    cin>>a[i];
}
int sum = a[0];
for(int i=1;i<n-1;i++){
    sum += min(a[i],a[i-1]);
}
if(n == 1){
    cout<<(2*sum)<<endl;
}else{
    cout<<(sum+a[n-2])<<endl;
}
return 0;
}


Measured memory_bytes: 256
s = input()
q = int(input())
ans = ''
ans1 = ''
ans2 = ''
zengo = 1 #表は1、裏は-１
front = []
back = []
for i in range(q):
    a = list(input().split())
    if a[0] == '1':
        zengo *= -1
    else:
        if a[1] == '1':
            if zengo == 1:
                front.append(a[2])
            else:
                back.append(a[2])
        else:
            if zengo == 1:
                back.append(a[2])
            else:
                front.append(a[2])
front = list(reversed(front))
for i in range(len(front)):
    ans1 += front[i]
for i in range(len(back)):
    ans2 += back[i]
    
ans = ans1 + s + ans2
if zengo == -1:
    ans = ans[::-1]
print(ans)
    

Measured memory_bytes: 12052
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int MAXN = (int)1e5+10;
struct edge {
    int to, next;
}ed[MAXN << 1];

int head[MAXN], cnt;
void addedge(int u, int v) {
    ed[cnt].to = v;
    ed[cnt].next = head[u];
    head[u] = cnt++;
}

int sz[MAXN], fa[MAXN], dep[MAXN];
void dfs(int u, int pre) {
    sz[u] = 1;
    dep[u] = dep[pre] + 1;
    fa[u] = pre;
    for ( int i = head[u]; i != -1; i = ed[i].next ) {
        int v = ed[i].to;
        if ( v != pre ) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    int n;
    cin >> n;
    for ( int i = 1; i < n; i++ ) {
        int u, v;
        cin >> u >> v;
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    int d = (dep[n] - 2) / 2;
    int ans = n;
    while ( d ) {
        d--;
        ans = fa[ans];
    }
    if ( sz[ans] * 2 >= n ) cout << "Snuke" << endl;
    else cout << "Fennec" << endl;
    
    return 0;
}

Measured memory_bytes: 8064
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
      BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
       
      while(true){
      String[] num=buf.readLine().split(" ");
      int x=Integer.parseInt(num[0]);
      int y=Integer.parseInt(num[2]);
       
          if(num[1].equals("+")){
              System.out.println(x+y);
          }
          else if(num[1].equals("-")){
              System.out.println(x-y);
          }
          else if(num[1].equals("*")){
              System.out.println(x*y);
          }
          else if(num[1].equals("/")){
              System.out.println(x/y);
          }
          else{
                    break;
          }
            }
        }
    }

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

double xs, ys, xt, yt;
double mindist[1005][1005];
double x[1005], y[1005], r[1005];

double dist(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	read(xs, ys, xt, yt);
	int n; read(n);
	rep(i, 0, n) read(x[i], y[i], r[i]);

	rep(i, 0, n) rep(j, 0, n) {
		if (i == j) mindist[i][j] = 0;
		else {
			mindist[i][j] = max(dist(x[i], y[i], x[j], y[j]) - r[i] - r[j], 0.0);
		}
	}

	rep(i, 0, n) rep(j, 0, n) rep(k, 0, n)
		mindist[j][k] = min(mindist[j][k], mindist[j][i] + mindist[i][k]);

	double ans = 1e100;
	rep(i, 0, n) rep(j, 0, n) {
		double d = 0.0;
		d += max(0.0, dist(xs, ys, x[i], y[i]) - r[i]);
		d += mindist[i][j];
		d += max(0.0, dist(x[j], y[j], xt, yt) - r[j]);
		chmin(ans, d);
	}
	chmin(ans, dist(xs, ys, xt, yt));

	cout << fixed << setprecision(12);
	die(ans);
}


Measured memory_bytes: 8192
// inputに入力データ全体が入る
function Main(input) {
	var line = input.split("\n");
	var s = line[0];
	var t = line[1];

	var makeStringArray = function(str){
		var ary = [];
		for(var i = 0; i < str.length; i++){
			if(str[i] !== "\r") ary.push(str[i]);
		}

		return ary;
	}

	var arys = makeStringArray(s);
	var aryt = makeStringArray(t);
	var ascs = arys.sort(function(a,b){
		if(a >= b) return 1;
		else return -1;
	});
	var desct = aryt.sort(function(a,b){
		if(a >= b) return -1;
		else return 1;
	});

	var S = ascs.join("");
	var T = desct.join("");
	if(S < T) console.log("Yes");
	else console.log("No");
}

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

Measured memory_bytes: 7624
s = list(str(input()))
q = int(input())

from collections import deque
d = deque(s)
REVERSE = False

for _ in range(q):
    X = input().split()
    if X[0] == '1':
        REVERSE = not REVERSE
    else:
        if X[1] == '1' and not REVERSE:
            d.appendleft(X[2])
        elif X[1] == '2' and not REVERSE:
            d.append(X[2])
        elif X[1] == '1' and REVERSE:
            d.append(X[2])
        elif X[1] == '2' and REVERSE:
            d.appendleft(X[2])

if REVERSE:
    d.reverse()

print(*d, sep='')


Measured memory_bytes: 81616
#include<bits/stdc++.h>
using namespace std;
int a[100005],cnt;
int n,m,sw1,sw2;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){	
		scanf("%d",&a[i]);
		if (a[i]&1){
			cnt++;
			if (!sw1) sw1=i;
			else sw2=i;
		}
	}
	if (cnt>2){
		puts("Impossible");
		return 0;
	}
	if (sw1) swap(a[1],a[sw1]);
	if (sw2) swap(a[m],a[sw2]);
	for (int i=1;i<=m;i++)
		printf("%d ",a[i]);
	m=max(m,2); a[1]--; a[m]++;
	int tmp=(a[1]?1:2);
	printf("\n%d\n",m+1-tmp);
	for (int i=tmp;i<=m;i++)
		printf("%d ",a[i]);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

#define MOD 1e+9;

using namespace std;

auto f=[](){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
};

int main()
{
	
	f();
	int A, B , C;
	cin>>A>>B>>C;
	cout<<(((A==B && A!=C) || (B==C && B!=A) || (A==C && A!=B))?"Yes":"No");

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int n, x, ans = 0;
    cin >> n >> x;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        ans = __gcd(ans, a - x);
    }
    cout << abs(ans) << endl;

}


Measured memory_bytes: 384
from collections import deque
s=deque(list(input()))
p=0
for i in range(int(input())):
    a=list(map(str,input().split()))
    if len(a)==1:
        p^=1
    else:
        if p%2:
            if a[1]=="2":
                s.appendleft(a[2])
            else:
                s.append(a[2])
        else:
            if a[1]=="1":
                s.appendleft(a[2])
            else:
                s.append(a[2])
ans=""
if p%2==1:
    while s:
        ans+=s.pop()
else:
    while s:
        ans+=s.popleft()
print(ans)

Measured memory_bytes: 6628
import sys
from collections import Counter

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    h, w, m = nm()
    H = []
    W = []
    for i in range(m):
        hh, ww = nm()
        H.append(hh)
        W.append(ww)
    h_m = Counter(H).most_common()[0]
    w_m = Counter(W).most_common()[0]
    ans_1 = h_m[1]
    ans_2 = w_m[1]
    WW = []
    HH = []

    for i in range(m):
        if H[i] == h_m[0]:
            continue
        WW.append(W[i])

    for i in range(m):
        if W[i] == w_m[0]:
            continue
        HH.append(H[i])
    if WW:
        ans_1 += Counter(WW).most_common()[0][1]
    if HH:
        ans_2 += Counter(HH).most_common()[0][1]

    print(max(ans_1, ans_2))


if __name__ == '__main__':
    main()


Measured memory_bytes: 77304
const main = (standardInput) => {
  a = standardInput.split("\n")
  n = parseInt(a[0])
  m = {}
  for(var i = 0; i<n; i++){
    s = a[i+1]
    if(!m[s]) m[s] = 0
    m[s]++
  }
  ['AC', 'WA', 'TLE', 'RE'].forEach((ss)=>{
    console.log(ss + " x " + (m[ss]||0) )
  })
}

main(require('fs').readFileSync('/dev/stdin', 'UTF-8'));

Measured memory_bytes: 37032
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll cnt[3000];

int main(){
    string s;
    cin>>s;

    int tot=0;
    int p=1;
    int n=s.size();
    for(int i=n-1;i>=0;i--){
        tot=(tot+(s[i]-'0')*p)%2019;
        cnt[tot]++;
        p=(p*10)%2019; 
    }

    ll ans=0;
    rep(i,2019){
        if(cnt[i]>=2) ans+=(cnt[i]*(cnt[i]-1))/2;
    }
    ans+=cnt[0];
    
    cout<<ans<<endl;
}




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

static const int INF=1e9;
static const int MOD=1000000007;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int N; cin >> N;
    string s,t; cin >> s >> t;
    for(int i=0;i<N;i++){
        cout << s[i] << t[i];
    }
    cout << endl;
}


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


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


	ll h[n];

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

	   ll dp[n];
       dp[0]=0;
	   dp[1]=abs(h[1]-h[0]);
	   
     //  cout<<dif[1]<<" "<<dif[0]<<" "<<abs(dif[1]-dif[0])<<"#";
   
	   for(int i=2;i<n;i++)
	   {
              ll  minn=1e+14;
           for(int j=1;j<=k && j<=i;j++)
           {
           	minn=min(minn, dp[i-j]+abs(h[i]-h[i-j]));
            //  cout<<minn<<"QQ";
           }

           //cout<<endl;
             dp[i]=minn;

	   }
        //cout<<"$$$$"<<endl;
        //  for(int i=0;i<n-1;i++)
	      //   cout<<dp[i]<<" ";

     cout<<dp[n-1];

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long m, n;
    scanf("%lld %lld",&n,&m);
    long long  count = 0;
    if (m >= 2*n)
    {
        m = m - 2 * n;
        count += n;
        n = 0;
        count += m / 4;
    }
    else
    {
        count += m / 2;
    }
    printf("%lld\n",count);
    return 0;
}


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

int main() {
	char a,b;
  	cin >> a >> b;
  	if(a == 'H' && b == 'H'||a == 'D' && b == 'D'){
      cout << 'H' << endl;
    }else{
      cout << 'D' << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<ios>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<string>
#include<numeric>
#include<set>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using vi = vector<int>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
using vpii = vector<pii>;

int main(){
  int N;
  cin >> N;
  vi A(N+1), B(N);
  rep(i, N+1) cin >> A[i];
  rep(i, N) cin >> B[i];

  int tmp;
  long cnt = 0;
  rep(i, N){
    tmp = min(A[i], B[i]);
    cnt += tmp;
    B[i] -= tmp;

    tmp = min(A[i+1], B[i]);
    cnt += tmp;
    A[i+1] -= tmp;
  }

  cout << cnt << endl;
  
  return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

text = input()

def factrial(n):
    a = 0
    for i in range(1, n+1):
        a += i
    return a

def palindrome(s):
    l = len(s)
    for i in range(l // 2):
        if s[i] != s[l - 1 - i]:
            return False
    return True

r1 = (palindrome(text))
r2 = (palindrome(text[0:len(text) // 2]))
r3 = (palindrome(text[-(-len(text) // 2):]))
print('Yes' if r1 and r2 and r3 else 'No')


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define INF 1000000
using namespace std;
int main(){
    vector<int> vec(101);
    rep(i,101) vec[i] = 0;
    int n,tmp=0;
    vector<int> ans;
    while(cin >> n){
        vec[n]++;
    }
    rep(i,vec.size()){
        if(tmp <= vec[i]) tmp = vec[i];
    }
    rep(i,vec.size()){
        if(tmp == vec[i]) ans.push_back(i);
    }
    sort(ans.begin(),ans.end());
    rep(i,ans.size()) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 3124
#include<stdio.h>

void CountingSort(int);

int A[2000001];
int B[2000001];
int C[10001];
int n;

int main(){

  int i,k;

  scanf("%d",&n);
  k=0;
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    if(A[i]>=k) k=A[i];
  }
 
  CountingSort(k);

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

void CountingSort(int k){

  int i,j;

  for(i=0;i<=k;i++)
    C[i]=0;

  for(j=1;j<=n;j++)
    C[A[j]]++;

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

  for(j=n;j>0;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
}

Measured memory_bytes: 16264
#C
import math
N,K = map(int,input().split())
p=0
for i in range(N):
    #   print(i)
    if i+1 >= K:
        X =0
    else:
        X = math.ceil((math.log2(K/(i+1))))
    p +=(1/2)**X
p = p/N
print(p)

Measured memory_bytes: 3060
A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

ans=min(a)+min(b)
for i in range(M):
  x,y,c=map(int,input().split())
  res=a[x-1]+b[y-1]-c
  ans=min(res,ans)
print(ans)

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

using ll = long long;

int N;
int H[105];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

pair<ll,ll> hoge(int L,int R,int v) {
	ll dp1=1,dp2=1;
	int i;
	
	if(L>R) return {-1,1};
	
	int mi=1<<30;
	for(i=L;i<=R;i++) mi=min(mi,H[i]);
	int W=R-L+1;
	for(i=L;i<=R;i++) if(mi!=H[i]) W--;
	
	int pre=L-1;
	for(i=L;i<=R;i++) {
		if(mi==H[i]) {
			auto r=hoge(pre+1,i-1,mi);
			if(r.first>=0) {
				(dp1*=r.first)%=mo;
				(dp2*=r.first+r.second)%=mo;
			}
			
			pre=i;
		}
	}
	auto r=hoge(pre+1,R,mi);
	if(r.first>=0) {
		(dp1*=r.first)%=mo;
		(dp2*=r.first+r.second)%=mo;
	}
	
	(dp2=dp2*modpow(2,W)+(modpow(2,mi-v)+mo-2)*dp1)%=mo;
	(dp1*=modpow(2,mi-v))%=mo;
	
	return {dp1,dp2};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) cin>>H[i];
	cout<<hoge(1,N,0).second<<endl;
}

int main()
{
        solve();
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int N,d[111];
  int i,k;
  cin >> N;
  for(i=0;i<=N-1;i++)
    cin >> d[i];
  int sum = 0;
  for(i=0;i<=N-2;i++)
    for(k=i+1;k<=N-1;k++)
      sum += d[i]*d[k];
  cout << sum << endl;
}

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

using namespace std;

int n, a, b, c, d;
int main() {
	scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
	b -= a;
	for (int i = 0; i < n; i ++) {
		long long L = i * 1ll * c - (n - 1 - i) * 1ll * d;
		long long R = i * 1ll * d - (n - 1 - i) * 1ll * c;
		if (L <= b && b <= R) return puts("YES"), 0;
	}
	puts("NO");
}

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

ll solve() {
    ll X, Y;
    cin >> X >> Y;
    ll ans = 0;
    if ( X == 3 ) ans += 100000;
    else if ( X == 2 ) ans += 200000;
    else if ( X == 1 ) ans += 300000;

    if ( Y == 3 ) ans += 100000;
    else if ( Y == 2 ) ans += 200000;
    else if ( Y == 1 ) ans += 300000;

    if ( X == 1 && Y == 1 ) ans += 400000;

    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

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

int main(){
    int n; cin >> n;
    int next=1;
    int ans=0;
    for(int i=0;i<n;i++){
        int a;cin >> a;
        if(next==a) next++;
        else ans++;
    }
    if(ans==n) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC167
{
    class Program
    {
        static void Main(string[] args)
        {
            b();
        }

        public static void b()
        {
            long[] abck = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long a = abck[0], b = abck[1], c = abck[2], k = abck[3];
            long ans = 0;
            if(a <= k)
            {
                ans += a;
                k -= a;
            }
            else
            {
                ans += k;
                Console.WriteLine(ans);
                return;
            }
            k -= b;
            if(k <= 0)
            {
                Console.WriteLine(ans);
                return;
            }
            if(c <= k)
            {
                ans -= c;
            }
            else
            {
                ans -= k;
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 28240
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first;
#define se second;
#define print(x,y) (cout << (x) << (y))
#define inf INT_MAX
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,bool> pib;
typedef vector<pii> vii;
typedef vector<pib> vib;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<string,string> pss;
typedef vector<pss> vss;
const int MOD = 1e9 + 7; //998244353;

int main(){
    boost;
    int a , b;cin >> a  >> b;
    cout << (a*(a-1) + b*(b-1)) / 2;
    return 0;
}



Measured memory_bytes: 256
//FA専用
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long LINF=1e18;
template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}
template<typename T>
void chmin(T &a,T b){
  if(a>b)a=b;
}
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  int a,b,c;cin>>a>>b>>c;
  swap(a,b);
  swap(a,c);
  std::cout << a<<" "<<b<<" "<<c << '\n';
}


Measured memory_bytes: 256
<?php
$C=str_split(fgets(STDIN));
foreach($C as $c){
	$n=ord($c);
	if($n<65){}
	elseif($n<91){$c=chr($n+32);}
	elseif($n<97){}
	elseif($n<123){$c=chr($n-32);}
	echo $c;
}

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

int main() {
  string s, t;
  cin>>s>>t;
  int sn = s.length();
  int tn = t.length();
  int sa_acc[sn+1], sb_acc[sn+1], ta_acc[tn+1], tb_acc[tn+1];
  for (int i=0; i<sn+1; i++) {
    sa_acc[i] = 0;
    sb_acc[i] = 0;
  }
  for (int i=0; i<tn+1; i++) {
    ta_acc[i] = 0;
    tb_acc[i] = 0;
  }
  for (int i=0; i<sn; i++) {
    if (s[i] == 'A') {
      sa_acc[i+1] = sa_acc[i] + 1;
      sb_acc[i+1] = sb_acc[i];
    } else {
      sa_acc[i+1] = sa_acc[i];
      sb_acc[i+1] = sb_acc[i] + 1;
    }
  }
  for (int i=0; i<tn; i++) {
    if (t[i] == 'A') {
      ta_acc[i+1] = ta_acc[i] + 1;
      tb_acc[i+1] = tb_acc[i];
    } else {
      ta_acc[i+1] = ta_acc[i];
      tb_acc[i+1] = tb_acc[i] + 1;
    }
  }
  int q;
  cin>>q;
  for (int i=0; i<q; i++) {
    int a, b, c, d;
    cin>>a>>b>>c>>d;
    --a;
    --b;
    --c;
    --d;
    int sa = sa_acc[b+1] - sa_acc[a];
    int sb = sb_acc[b+1] - sb_acc[a];
    int ta = ta_acc[d+1] - ta_acc[c];
    int tb = tb_acc[d+1] - tb_acc[c];
    if ((sa * 2 + sb) % 3 == (ta * 2 + tb) % 3) {
      cout<<"YES"<<endl;
    } else {
      cout<<"NO"<<endl;
    }
  }
}

Measured memory_bytes: 2560
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}

int gcd(ll(a), ll(b)) {
	ll c = a;
	while (a % b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return b;
}



int main() {
	int N,L;
	cin >> N >> L;
	vector<string> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec.at(i);
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < N; i++) {
		cout<< vec.at(i);
	}


	
}

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

int main() {
  int n; cin >> n; int c; vector<int> b;
  for(int i=0; i<n; i++) {cin >> c; b.push_back(c);}
  bool update = true; stack<int> s;
  while(!b.empty() && update) {
    update = false;
    for(int i=b.size()-1; i>=0; i--) {
      if (b[i] == i+1) {
        s.push(b[i]); b.erase(b.begin()+i);
        update++;
        break;
      }
    }
  }
  if (!update) return puts("-1") * 0;
  for(int i=0; i<n; i++) {
    cout << s.top() << endl;
    s.pop();
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using P = pair<int,int>;
using vl = vector<ll>; using vvl = vector<vl>;
#define mp make_pair
#define pb push_back
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for (int i=(n-1);i >= 0;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)((v).size())
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
#define Sort(v) sort(all(v))
#define Rev(v) reverse(all(v))
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << H << " ";
    debug_out(T...);
}
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
    for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
    return os;
}
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
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;}
const ll INF = 1LL << 60;
const ll mod = 1000000007;
const int dx[8] = {1,0,-1,0,1,1,-1,-1}; const int dy[8] = {0,1,0,-1,1,1,-1,-1};

ll n;
ll a[3000];
bool flag[3000][3000];
ll dp[3000][3000]; // dp[i][j] = [i, j]が残ってるときから始めた最大スコア

ll dfs(ll l, ll r) {
    if(flag[l][r]) return dp[l][r];
    flag[l][r] = true;
    if(l == r) return dp[l][r] = a[l];
    return dp[l][r] = max(a[l]-dfs(l+1, r), a[r]-dfs(l, r-1));
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
    rep(i,n) cin >> a[i];
    cout << dfs(0, n-1) << endl;
}

Measured memory_bytes: 58756
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

n,m = map(int,input().split())

ansl=-1
ansr=10**6

for _ in range(m):
    l,r=map(int,input().split())
    ansl=max(ansl,l)
    ansr=min(ansr,r)

print(max(ansr-ansl+1,0))

Measured memory_bytes: 9076
#include <bits/stdc++.h>
using namespace std;
typedef  long long int ll;
#define INFI LLONG_MAX
int main(){
	 ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
int a,b,c;
cin >>a >> b >> c;
if((a==b&&a!=c)||(a==c&&b!=c)||(b==c&&b!=a)){
	cout << "Yes";
}
else{
	cout << "No";
}



}



Measured memory_bytes: 384