akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

bool C[26];

int main() {
  string S;
  cin >> S;
  for (int i = 0; i < S.size(); ++i) {
    C[S[i] - 'a'] = true;
  }
  for (int i = 0; i < 26; ++i) {
    if (!C[i]) {
      printf("%c\n", (char)(i + 'a'));
      return 0;
    }
  }
  printf("None\n");
}

Measured memory_bytes: 3284
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
string grid[100];
string w = "",bl = "";
int now = 0;
bool flag = 1;
void make(int a,int b){
    if (flag && a == 1){
        int c;
        if (b%50 == 0) c = b/50;
        else c = b/50+1;
        rep(i,3*c){
            grid[i+now] = w;
        }
        rep(i,c){
            rep(j,50){
                if (b == 0) break;
                grid[now+3*i+1][2*j] = '#';
                b--;
            }
        }
        now += 3*c;
        cout << now << " " << 100 << '\n';
        rep(i,now){
            PRINT(grid[i]);
        }
    }
    else if (b == 1){
        int c;
        if (a%50 == 0) c = a/50;
        else c = a/50+1;
        rep(i,3*c){
            grid[i+now] = bl;
        }
        rep(i,c){
            rep(j,50){
                if (a == 0) break;
                grid[now+3*i+1][2*j] = '.';
                a--;
            }
        }
        now += 3*c;
        cout << now << " " << 100 << '\n';
        rep(i,now){
            PRINT(grid[i]);
        }
    }
    else{
        if (flag){
            rep(i,3){
                grid[i+now] = w;
            }
            a--;
            rep(i,50){
                if (b == 1){
                    break;
                }
                grid[now+1][i*2] = '#';
                b--;
            }
            now += 3;
            flag = 0;
            make(a,b);
        }
        else{
            rep(i,3){
                grid[i+now] = bl;
            }
            b--;
            rep(i,50){
                if (a == 1){
                    break;
                }
                grid[now+1][i*2] = '.';
                a--;
            }
            now += 3;
            flag = 1;
            make(a,b);
        }
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin >> a >> b;
    rep(i,100){
        w += '.';
        bl += '#';
    }
    make(a,b);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;

namespace chrono = std::chrono;
using namespace std::literals;

[[gnu::constructor]]
void fast_iostream() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
}

int main() {
  int n; cin >> n;
  std::vector<int> x(n);
  for (int i = 0; i < n; ++i) {
    cin >> x[i];
  }
  std::vector<int> ix(n);
  std::iota(ix.begin(), ix.end(), 0LL);
  std::sort(ix.begin(), ix.end(), [&](int i, int j) {
    return x[i] < x[j];
  });
  std::vector<int> ans(n);
  for (int i: ix) {
    if (x[i] <= x[ix[n/2 - 1]]) {
      ans[i] = x[ix[n/2]];
    } else {
      ans[i] = x[ix[n/2 - 1]];
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << ans[i] << endl;
  }
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int B = 500;
const int N = 250000;

int n;
bool same[B]={};
ll all_add[B]={};
ll a[N]={};

void update_same(int bid)
{
    bool ok = true;
    rep(i,B-1) ok &= (a[bid*B+i]==a[bid*B+i+1]);
    same[bid] = ok;
}

int check()
{
    rep(i,B)
    {
        if(!same[i]) return 0;
        if(a[i*B]+all_add[i]!=0) return 0;
    }
    return 1;
}

void add(int l, int r, int x)
{
    int lb = l/B, rb = r/B;
    if(lb==rb)
    {
        for(int i=l; i<=r; ++i) a[i] += x;
    }
    else
    {
        // left
        for(int i=l; i<(lb+1)*B; ++i) a[i] += x;
        // mid
        for(int i=lb+1; i<rb; ++i) all_add[i] += x;
        // right
        for(int i=rb*B; i<=r; ++i) a[i] += x;
    }
    update_same(lb);
    update_same(rb);
}

int query(int l, int r, int x)
{
    if(l<n/2 && r>=n/2)
    {
        add(l, n/2-1, x);
        add(n-1-r, n/2-1, -x);
    }
    else
    {
        if(r<n/2) add(l, r, x);
        else add(n-1-r, n-1-l, -x);
    }
    return check();
}

int main()
{
    scanf(" %d", &n);

    vector<int> s(n);
    rep(i,n) scanf(" %d", &s[i]);

    // init
    rep(i,n/2) a[i] += s[i];
    for(int i=n/2; i<n; ++i) a[n-1-i] -= s[i];

    rep(i,B) update_same(i);

    // query
    int Q;
    scanf(" %d", &Q);
    while(Q--)
    {
        int l,r,x;
        scanf(" %d %d %d", &l, &r, &x);
        --l;
        --r;
        printf("%d\n", query(l,r,x));
    }

    return 0;
}

Measured memory_bytes: 6748
import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.math;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readA(T)(size_t n,ref T t){t=new T(n);auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(ElementType!T);r.popFront;}}
void readM(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=readln.splitter;foreach(ref v;t){v[i]=r.front.to!(ElementType!(typeof(v)));r.popFront;}}}
void readS(T)(size_t n,ref T t){t=new T(n);foreach(ref v;t){auto r=readln.splitter;foreach(ref j;v.tupleof){j=r.front.to!(typeof(j));r.popFront;}}}

void main()
{
  int n; readV(n);
  int[] t, x, y; readM(n, t, x, y);

  if ((x[0]+y[0])%2 != t[0]%2 || x[0]+y[0] > t[0]) {
    writeln("No");
    return;
  }

  foreach (i; 1..n)
    if ((x[i]+y[i])%2 != t[i]%2 || (x[i]-x[i-1]).abs+(y[i]-y[i-1]).abs > t[i]-t[i-1]) {
      writeln("No");
      return;
    }

  writeln("Yes");
}


Measured memory_bytes: 2428
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using vll = vector<ll>;

void solve();

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

  solve();

  return 0;
}

#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)

#define inl(...)  \
  ll __VA_ARGS__; \
  in(__VA_ARGS__)

#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__);

void in() {}
template <typename T, class... U>
void in(T& t, U&... u) {
  cin >> t;
  in(u...);
}

void out() {
  cout << endl;
}
template <typename T, class... U>
void out(const T& t, const U&... u) {
  cout << t;
  if (sizeof...(u))
    cout << " ";
  out(u...);
}

#define rep(i, n) for (long long i = 0; i < n; i++)

void solve();
#ifndef ONLINE_JUDGE
#include "./lib.hpp"
#endif

void solve() {
    ini(N);
    ins(S);

    int x = 0;
    int ret = 0;
    for (auto c : S) {
        if (c == 'I')
            x++;
        else
            x--;

        ret = max(x, ret);
    }
    out(ret);
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

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

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

    int K;
    cin >> K;

    int ans = 0;
    rep(i, K) {
        rep(j, K) {
            rep(k, K) ans += gcd(gcd(i+1, j+1), k+1);
        }
    }

    cout << ans << endl;
}

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

#define F first
#define S second
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;


int main(){
  int n;cin>>n;
  vector<int> a(n);
  vector<int> b(n);
  rep(i,n)cin>>a[i];
  rep(i,n){
  int j=a[i];
  b[j-1]=i+1;
  }
  rep(i,n){
  cout<<b[i]<<" ";
  }
return 0;
}

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

#define ll long long
#define sp ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define cps CLOCKS_PER_SEC
#define mod (ll)1000000007
#define f first
#define s second
#define debug1(x) cerr<<x<<"\n"
#define debug2(x,y) cerr<<x<<" "<<y<<"\n"
#define debug3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<"\n"
#define nl cerr<<"\n";
#define pq priority_queue
#define inf 0x3f3f3f3f
#define test cerr<<"abcd\n";
#define pi pair<int,ll>
#define pii pair<int,pi>
#define pb push_back
#define mxn 500005


ll xr(ll n){
int z=n%4;
if(!z)return n;
if(z==1)return 1;
if(z==3)return 0;
return n+1;
}
int main(){
sp;
ll a,b;
cin>>a>>b;
cout<<(xr(b)^xr(a-1));
return 0;}


Measured memory_bytes: 256
N = int(input())
G = [list(map(int,input().split())) for k in range(N)]
G = sorted(G, key = lambda x: (x[1],x[0]))

now = 0
for k in range(N):
    if now+G[k][0] > G[k][1]:
        print("No")
        exit(0)
    else:
        now += G[k][0]
print("Yes")


Measured memory_bytes: 69160
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
#define mod 200003
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
using pl = pair<ll,ll>;
using vvb=vector<vector<bool>>;
using vb= vector<bool>;
ll f(ll a,ll b,ll p){
	if(b==0) return 1;
	if(b%2==0){
		ll t=f(a,b/2,p);
		return t*t%p;
	}
	return a*(f(a,b-1,p))%p;
} 

//__builtin_popcount()
signed main(){
	int n; cin>>n;
	string s,t; cin>>s>>t;
	ll ans=0;
	rep(i,0,n){
		rep(j,0,n){
			if(s[i]==t[j]){
				ll cnt=0;
				ll a=i,b=j;
				while(a<n && b<n){
					if(s[a]!=t[b])break;
					a++; b++;
					cnt++;
				}
				chmax(ans,cnt);
			}
		}
	}
	cout<<2*n-ans<<endl;

	


	return 0;
}

Measured memory_bytes: 3644
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main(void)
{
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	if(abs(a-c) <= d){
		cout << "Yes";
		return 0;
	}else if(abs(a-b) <= d && abs(b-c) <= d){
		cout << "Yes";
		return 0;
	}
	cout << "No";
    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll 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;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}


struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};




int main(){
  ll k; cin >> k;
  ll now = 0;
  
  ll ans = -1;
  
  for(ll i=1; i <= 1000000; i++){
    now = (now*10 + 7);
    now %= k;
    if(now == 0){
      ans = i;
      break;
    }
  }
  
  cout << ans << endl;
  
  
}

Measured memory_bytes: 3608
#include<stdio.h>

int dp[50];

int fib(int n){
  if(n==0||n==1) return dp[n]=1;
  if(dp[n]!=-1) return dp[n];
  return dp[n]=fib(n-1)+fib(n-2);
}

int main(){
  int n,i;
  for(i=0;i<50;i++) dp[i]=-1;

  scanf("%d",&n);
  printf("%d\n",fib(n));

  return 0;
}



Measured memory_bytes: 2044
#include <bits/stdc++.h>
 using namespace std;
int main() { // input
  int N; cin >> N;
  vector<int> V(N);
  for (int i = 0; i<N; ++i){
    cin >> V[i];
  }
  vector<int> C(N);
  for (int i = 0; i<N; ++i){
    cin >> C[i];
  }
  // compute
  int ans = 0;
  for (int i = 0; i<N; ++i){
    if (V[i] > C[i]) {
      ans += V[i] - C[i];
    }
  }
  // output
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int N;
    cin >> N;
    int ans = 0;
    
    for(int i = 1;i <= N;i += 2){
        int count = 0;
        for(int j = 1;j <= i;j++){if(i % j == 0)count++;}
        if(count == 8)ans++;
    }
    cout << ans;
}


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

int main(){
    ll n, w;
    scanf("%lld%lld", &n, &w);
    vector<pair<ll, ll>> a(n);
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        a[i] = {x, y};
    }
    
    ll dp[n][w+1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= w; j++){
            dp[i][j] = 0;
        }
    }
    
    for(int i = 0; i <= w; i++){
        if(i >= a[0].first){
            dp[0][i] = a[0].second;
        }
    }
    
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= w; j++){
            if(j < a[i].first){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j-a[i].first] + a[i].second, dp[i-1][j]);
            }
        }
    }
    
//    for(int i = 0; i < n; i++){
//        for(int j = 0; j <= w; j++){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
        
    cout<<dp[n-1][w];
    
    
    return 0;
}

Measured memory_bytes: 81684
#include <iostream>
using namespace std; 
int main()
{

	int X,N,C,S,v;
	
	cin>>X;
	N=X/500;
	N=N*1000;
	C=X%500;
//	cout<<C;	
	S=C%5;
	//cout<<S;
	v=N+(C-S);
	cout<<v<<endl;
}

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

int main(){
  ll N;
  cin >> N;
  ll A[N], B[N], sumA = 0, sumB = 0, D[N], mainasuKousuu = 0, mainasuSum = 0, res = 0;
  rep(i, N) {
    cin >> A[i];
    sumA += A[i];
  }
  rep(i, N) {
    cin >> B[i];
    sumB += B[i];
  }
  if (sumB > sumA) {
    cout << -1 << endl;
    exit(0);
  }
  rep(i, N) {
    D[i] = A[i] - B[i];
    if (D[i] < 0) {
      mainasuKousuu += 1;
      mainasuSum += D[i] * (-1);
    }
  }
  res = mainasuKousuu;
  // cout << mainasuKousuu <<" " << mainasuSum <<endl;
  sort(D, D+N, greater<ll>() );
  rep(i, N) {
    if (mainasuSum <= 0) {
      cout << res << endl;
      exit(0);
    }
    res += 1;
    mainasuSum -= D[i];
  }



}


Measured memory_bytes: 2560
#include<iostream>
#include<algorithm>
using namespace std;
#include<vector>
int main()
{
    int n, dust;
    cin >> n >> dust;
    vector<pair <int, int> >s;
    vector<pair <int, int> >t;
    int c[100010];
    for(int i = 1; i <= n; i++){
        int in;
        cin >> in;
        pair<int, int> in2;
        in2.first = in;
        in2.second = i;
        s.push_back(in2);
        cin >> in;
        in2.first = in;
        t.push_back(in2);
        cin >> c[i];
    }
    sort(s.begin(), s.end(), greater<pair<int, int> >() );
    sort(t.begin(), t.end(), greater<pair<int, int> >() );
    int ans = 0;
    int T = 0;
    bool onair[31];
    for(int i = 0; i < 31; i++){
        onair[i] = false;
    }
    while(true){
        T++;
        vector<int> ch;
        while(!s.empty()){
            if(s.back().first != T){
                break;
            }
            if(onair[c[s.back().second]] == true){
                ch.push_back(c[s.back().second]);
            }
            onair[c[s.back().second]] = true;
            s.pop_back();
        }
        int on = 0;
        for(int i = 1; i <= 30; i++){
            if(onair[i] == true){
                on++;
            }
        }
        //if(on > ans) cout << T << endl;
        ans = max(ans, on);
        while(!t.empty()){
            if(t.back().first != T){
                break;
            }
            onair[c[t.back().second]] = false;
            t.pop_back();
        }
        while(!ch.empty()){
            onair[ch.back()] = true;
            ch.pop_back();
        }
        if(t.empty()){
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2412
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>
#include <bitset>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

vector<int> dist(int st, vector<vector<int>> &tree) {

	const int sz = (int)tree.size();
	vector<int> dist(sz, -1);

	queue<int> que;
	que.emplace(st);
	dist[st] = 0;
	while (!que.empty()) {

		auto now = que.front();
		que.pop();

		for (const auto &e : tree[now]) {
			if (dist[e] == -1) {
				dist[e] = dist[now] + 1;
				que.emplace(e);
			}
		}

	};

	return dist;

};

int diameter(vector<vector<int>> &tree) {
	auto d1 = dist(0, tree);
	int d1_max = max_element(d1.begin(), d1.end()) - d1.begin();
	DMP(d1);
	auto d2 = dist(d1_max, tree);
	return *max_element(d2.begin(), d2.end());
};



int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<vector<int>> tree(N);
	for (int i = 0; i < N - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		tree[x].emplace_back(y);
		tree[y].emplace_back(x);
	}

	int dia = diameter(tree);
	if ((dia - 1) % 3 == 0) cout << "Second" << "\n";
	else cout << "First" << "\n";;

	return 0;
}

Measured memory_bytes: 14324
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> ws;
  int ws_sum = 0;
  for (int i = 0; i < n; i++) {
    int w;
    cin >> w;
    ws.push_back(w);
    ws_sum += w;
  }

  int sum1 = 0;
  int sum2 = ws_sum;
  int ans = 1000000000;
  for (int i = 0; i < ws.size(); i++) {
    sum1 += ws[i];
    sum2 -= ws[i];
    if (sum1 > sum2) {
      ans = min(ans, sum1 - sum2);
    } else {
      ans = min(ans, sum2 - sum1);
    }
  }
  cout << ans << "\n";
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef double dd;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

#define FOR(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define DOW(i,b,a) for (int i = (b); i >= (a); i--)
#define pb(a) push_back(a)
#define ALL(a) (a).begin(),(a).end()
#define fi first
#define se second

template<typename T>
void print_array(T* arr, int num) {
   FOR(i, 0, num) cout << arr[i] << ' ';
   cout << endl;
}

template<typename T> 
void print_vector(vector<T> vec) {
   FOR(i,0,vec.size()) cout << vec[i] << ' ';
   cout << endl;
}

int n,a,b,mx,arr[100010],diff;

bool can(int x) {
    int base = x * b;
    int num = 0;
    FOR(i,0,n) {
        int k = arr[i] - base;
        if (k > 0) {
            num += k / diff + !!(k % diff);
            if (num > x) return 0;
        }
    }
    return num <= x;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    //freopen("test.txt", "r", stdin);
    cin >> n >> a >> b;
    diff = a - b;
    FOR(i,0,n) {
        cin >> arr[i];
        mx = max(mx, arr[i]);
    }
    int lo = 1, hi = mx / b + 10, ans = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (can(mid)) {
            ans = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }
    cout << ans;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

int cnt[100];

int main() {
  int n, m;
  cin >> n >> m;
  rep(i, n) {
    int k;
    cin >> k;
    rep(j, k) {
      int a;
      cin >> a;
      cnt[a]++;
    }
  }
  int ans = 0;
  rep(i, m + 1) if (cnt[i] == n) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 256
// #pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define String std::string
#define fi first
#define se second
#define mp std::make_pair
#define Pair std::pair<int, int>
#define Map std::map< int, int >
#define Vector std::vector<int>
 
using std::cin;
using std::cout;
using std::endl;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int N = 100000 + 5;
const int M = 1000 + 5;
const int K = 1e7 + 5;
const int MOD = 1e9 + 7;
const int inv2 = 500000004;
const int LOG = 40;
const ull BASE = 19260817;
const int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };
const int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };
const double PI = acos(-1);
 
template<class T>
inline T readT() {
    T res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + ch - '0';
    return res * f;
}
#define read readT<int>

struct Edge {
    int u, v, w;
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
} e[N];

std::map< String, int > map;
int end, n;
std::pair< int, String > a[N * 2];

inline bool cmp(const std::pair< int, String > &a, const std::pair< int, String > &b) {
    if (a.fi != b.fi) return a.fi > b.fi;
    else return a.se < b.se;
}

int main() {
    std::ios::sync_with_stdio(false);
    // scanf("%d", &n);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        String tmp;
        cin >> tmp;
        if (!map.count(tmp)) {
            map[tmp] = ++end;
            a[map[tmp]].se = tmp;
            a[map[tmp]].fi = 1;
        } else {
            a[map[tmp]].fi++;
        }
    }
    std::sort(a + 1, a + end + 1, cmp);
    int max = a[1].fi;
    for (int i = 1; i <= end; i++) {
        if (a[i].fi != max) break;
        cout << a[i].se << endl;
    }
    return 0;
}

Measured memory_bytes: 27904
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int n;
    cin>>n;
    V<int> a(n),c(n,0);
    cinf(n,a);
    map<int,int> mp;
    int m=0;
    for(int i=n-1;i>=0;i--){
        if(mp[i+1]%2!=a[i]){
            c[i]++;
            m++;
            for(int j=1;j*j<=i+1;j++){
                if((i+1)%j==0){
                    mp[j]++;
                    if((i+1)/j!=j){
                        mp[(i+1)/j]++;
                    }
                }
            }
        }
    }
    cout<<m<<endl;
    rep(i,n){
        if(c[i]>0) cout<<i+1<<' ';
    }
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
(全探索できるなら全探索しろ)
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'\n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え(=でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
*/

Measured memory_bytes: 11776
import sys

def gcd(a,b):
    a, b = max(a,b), min(a,b)
    while a % b > 0:
        a, b = b, a % b
    return b

def solve():
    input = sys.stdin.readline
    N, X = map(int, input().split())
    A = [int(a) for a in input().split()]
    Ans = abs(A[0] - X)
    for a in A:
        Ans = gcd(Ans, abs(a - X))
    print(Ans)
    return 0

if __name__ == "__main__":
    solve()

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

struct Node {
  Node *l, *r;
};

void test() {
  vector<Node*> p;
  for (int i = 0; i < 1000000; ++i) p.push_back(new Node());
}

int main() {
  test();
  int a, b, c;
  cin >> a >> b >> c;
  cout << ((a+b+c) == max({a,b,c})*2 ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 39272
import collections

def MI(): return map(int, input().split())
def LI(): return list(MI())

if __name__ == "__main__":
    N = int(input())
    A = dict(collections.Counter(LI()))
    for i in range(1, N+1):
        count = A.get(i)
        print(count if count is not None else 0)

Measured memory_bytes: 37592
package main

import "fmt"

func main() {
	var a string
	fmt.Scan(&a)
	for x := 0; x < 1<<3; x++ {
		v := int(a[0] - '0')
		for i := 0; i < 3; i++ {
			n := int(a[i+1] - '0')
			if x>>i&1 == 1 {
				n *= -1
			}
			v += n
		}
		if v == 7 {
			s := ""
			for i := 0; i < 3; i++ {
				s += string(a[i])
				if x>>i&1 == 1 {
					s += "-"
				} else {
					s += "+"
				}
			}
			s += string(a[3]) + "=7"
			fmt.Println(s)
			return
		}
	}
}


Measured memory_bytes: 1772
/*----------------------------------------------------------*\
|m, f, bが与えられる											|
|		↓													|
|場合分け													|
|i) 手持ちだけで足りる場合									|
|	→ m >= b(mがb以上である)									|
|	→ m, bの値によらず'0'を出力								|
|ii) 手持ちだけでは足りないが、Aくんから借りれば買える場合		|
|	→ m + f >= b(m + fがb以上である)							|
|	→ b - mを出力(→不足金額を出力)							|
|iii) 手持ちとAくんの所持金を合わせても買えない場合			|
|	→ m + f < b(m + fがb未満である)							|
|	→ m, f, bの値によらず"NA"を出力							|
|		↓													|
|	return 0;												|
\----------------------------------------------------------*/

#include <iostream>
using namespace std;

int main() {
	int m, f, b; cin >> m >> f >> b;
	if (m >= b) {
		cout << '0' << endl;
		return 0;
	}
	else if (m + f >= b) {
		cout << b - m << endl;
		return 0;
	}
	else if (m + f < b) {
		cout << "NA" << endl;
		return 0;
	}
}


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

long long cnt[66];
long long ans = 0;
const long long MOD = 1e9 + 7;

void bin(long long idx, long long x)
{
    if (idx < 0)
        return;
    
    if ((x >> idx) & 1)
        cnt[idx]++;
    
    bin(idx - 1, x);
}

int main()
{
    int n;
    long long t;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &t);
        bin(59LL, t);
    }
    
   
    
    for (int i = 59; i >= 0; i--)
    {
        ans += (((1LL << i) % MOD) * ((cnt[i] * (n - cnt[i])) % MOD)) % MOD; 
        ans %= MOD;
    }
    
    printf("%lld", ans);

    return 0;
}


Measured memory_bytes: 256
#include <cstring>
#include <string>
#include <iostream>
using namespace std;

int main(){
	string str;
	getline(cin,str);
	for(int i=0;i<str.size();i++){
		if(str[i]>='a'&&str[i]<='z'){
			str[i]+=('A'-'a');
		}
	}
	cout<<str<<endl;
	return 0;
}

Measured memory_bytes: 3160
#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

double coins[3000];
double dp[3010][3010];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> coins[i];
	dp[0][0] = 1.0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			dp[i + 1][j + 1] += dp[i][j] * coins[i];
			dp[i + 1][j] += dp[i][j] * (1 - coins[i]);
		}
	}

	double out = 0;
	for (int i = (n + 1) / 2; i <= n; i++)
		out += dp[n][i];
	cout << fixed << setprecision(10) << out << endl;
}

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

int dis(int x,int k) {
    int sum = 0;
    if (x <= k/2) {
        sum += 2*x;
    }
    else {
        sum += 2*(k-x);
    }
    return sum;
}

int main() {
    int n,k,idou;
    cin >> n >> k;
    idou = 0;
    for (int i=0 ; i < n ; i++) {
        int x;
        cin >> x;
        idou += dis(x,k);
    }
    cout << idou;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N;
    cin >> N;
    vector<int> W(N);
    rep(i,N) cin >> W.at(i);
    vector<int> V(N);
    V[0] = W[0];
    for (int i = 1; i < N; i++) V[i] = V[i-1] + W[i];
    int mi = 1<<30;
    rep(i,N) {
        int S1 = V[i];
        int S2 = V[N-1] - V[i];
        mi = min(mi, abs(S2 - S1));
    }
    cout << mi << endl;
}

Measured memory_bytes: 256
import math
a,b,x = [ int(r) for r in input().split(' ') if len(r) > 0]

if 2*x >= a*a*b:
    # 半分より多い
    print(90-math.degrees((math.atan2(a,2*(b-x/a**2)))))
else:
    # 半分より少ない
    print(90-math.degrees(math.atan2((2*x)/(a*b),b)))

Measured memory_bytes: 9380
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = float('inf')

a = int(input())    # 数字

for i in range(8):
    M = 2000 - 200 * i
    m = 1800 - 200 * i
    if m <= a < M:
        print(i + 1)


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

int main(void){
  string s;
  cin >> s;
  int ans = 0;
  char temp = s[0];
  for(int i = 1; i < s.length(); i++){
    if(s[i] == temp) continue;
    ans++;
    temp = s[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
using pii = pair<int, int>;
const int MM = 2e5+10;

int n, m, par[MM];
char s[MM];
pii bit[MM];
//# of moves, last i

void update(int i, pii v){
    for(; i > 0 && i < MM; i += i&-i)
        bit[i] = min(bit[i], v);
}

pii query(int i){
    pii ret = {1e8, 1e8};
    for(; i > 0; i -= i&-i)
        ret = min(ret, bit[i]);
    return ret;
}

int main(){
    
    for(int i = 0; i < MM; i++)
        bit[i] = {1e8, 1e8};
    
    scanf("%d %d %s", &n, &m, s);
    
    if(s[n] == '1' || s[0] == '1')
        return 0*puts("-1");
    
    update(n, {0, n});
    for(int i = n-1; i >= 0; i--){
        if(s[i] == '1') continue;
        pii v = query(i+m);
        par[i] = v.second;
        update(i, {v.first+1, i});
    }
    
    if(par[0] == 1e8)
        return 0*puts("-1");
    
    int cur = 0;
    while(cur != n){
        printn(par[cur] - cur), pc(32);
        cur = par[cur];
    }
    
    return 0;
}

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

using namespace std;

typedef long long ll;

ll n;
vector<int> score, points;
vector<vector<int>> graph;
	
void bfs(int root) {
	bool visited[n] = {};

	queue<int> q;
	int i = n-1;
	q.push(root);
	visited[root] = true;

	while (!q.empty()) {
		int s = q.front();
		q.pop();
		score[s] = points[i];

		for (auto x: graph[s]) {	
			if (visited[x]) continue;
			visited[x] = true;
			q.push(x);
		}
		i--;
	}
}

void solve() {
	cin >> n;

	graph.resize(n);

	for (int i = 0; i < n-1; i++) {
		ll u,v;
		cin >> u >> v;
		u--;	v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	points.resize(n);
	
	for (int i = 0; i < n; i++)	cin >> points[i];

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

	ll ans = accumulate(points.begin(), points.end(), 0);
	ans -= points[n-1];

	cout << ans << endl;	
	
	score.resize(n, -1);

	int root = -1;
	
	for (int i = 0; i < n; i++) {
		if (graph[i].size() == 1) {
			root = i;
			break;
		}
	}

	bfs(root);

	for (auto x: score) {
		cout << x << ' ';
	}
	cout << endl;
	return ;
}

int main() {
	ll t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}


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

using namespace std;

using Freq = array<int,26>;

void mini(Freq& a, const Freq& b) {
    for (int i = 0; i < 26; i++) {
        a[i] = min(a[i], b[i]);
    }
}

void solve() {
    int n; cin >> n;
    Freq cnt;
    fill(cnt.begin(), cnt.end(), 1000);
    for (int _ = 0; _ < n; _++) {
        string s; cin >> s;
        Freq tmp = {};
        for (char c:s) tmp[c-'a']++;
        mini(cnt, tmp);
    }
    for (int i = 0; i < 26; i++) {
        char x = 'a'+i;
        for (int _ = 0; _ < cnt[i]; _++) {
            cout << x;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


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

#define FILE
#define fr first
#define se second

using namespace std;

const long long N = 2e5 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);

    int cnt = 0;
    int h1, x1, h2, x2;
    cin >> h1 >> x1 >> h2 >> x2;
    while(h1 > 0 && h2 > 0){
        if(cnt == 0){
            h2 -= x1;
        }
        else{
            h1 -= x2;
        }
        cnt = 1 - cnt;
    }
    if(h2 <= 0){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
}



Measured memory_bytes: 3616
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;

#define rep(i, a, b) for (int (i)=(a);(i)<=(b);(i)++)
#define Rep(i, a, b) for (int (i)=(a)-1;(i)<(b);(i)++)
#define REP(i, a, b) for (int (i)=(a);(i)>=(b);(i)--)
#define reg(i, x) for (int (i)=head[x];(i);i=e[i].next)
#define clr(a) memset(a,0,sizeof(a))
#define Sort(a, len) sort(a + 1, a + len + 1)
#define Sort2(a, len, cmp) sort(a + 1, a + len + 1, cmp)
#define ass(a, sum) memset(a, sum, sizeof(a))

#define ull unsigned long long
#define ll long long
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define Pii pair<int, int>

const int N = 100010 ;
const int iinf = INT_MAX/2 ;
const ll linf = LLONG_MAX/2 ;
const int MOD = 1e9+7 ;

inline int read(){
    int X = 0,w = 0 ;
	char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
    while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
    return w ? -X : X;
}

void write(int x){
     if(x < 0) putchar('-'),x = -x;
     if(x > 9) write(x / 10);
     putchar(x%10 + '0');
}

void print(int x) {
	cout << x << endl ;
	exit(0) ;
}

void douout(double x){
	 printf("%lf\n", x + 0.0000000001) ;
}

string s ;

int main(){
	cin >> s ;
	char a = s[0] ;
	int flag = -1 ;
	for (int i = 1; i < s.size(); i++) {
		if (s[i] > a) flag = 1 ;
		if (s[i] < a) flag = 0 ;
		if (flag != -1) break ;
	} 
	if (flag != 1) {
		for (int i = 0; i < s.size(); i++) cout << a  ;
		cout << endl ;
	}
	else {
		a += 1 ;
		for (int i = 0; i < s.size(); i++) cout << a  ;
		cout << endl ; 
	}
}

/*
写代码时请注意：
	1.是否要开Long Long？数组边界处理好了么？
	2.特殊情况处理好了么？
	3.做一些总比不做好。
	4.最大值和最小值问题可不可以用二分答案？
	5.有没有贪心策略？否则能不能dp？
	6.实数精度有没有处理？
*/


Measured memory_bytes: 256
A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
x = []
y = []
c = []
for i in range(0, M):
  xi, yi, ci = map(int, input().split())
  x.append(xi)
  y.append(yi)
  c.append(ci)
#print (a)

min_price_wo_waribiki = min(a) + min(b)
#print(min_price_wo_waribiki)

min_price_w_waribiki = min([a[x[i]-1] + b[y[i]-1] - c[i] for i in range(0, M)])
#print(min_price_w_waribiki)

min_price = min(min_price_wo_waribiki, min_price_w_waribiki)
print(min_price)

Measured memory_bytes: 28712
<?php
// $n = (int)trim(fgets(STDIN));
$input = explode(' ', trim(fgets(STDIN)));

$a = (int)$input[0];
$b = (int)$input[1];

if ($b === 1) {
	echo '0';
	exit();
}
$total = 1;
$cnt = 0;
while ($total < $b) {
	$total -= 1;
	$total += $a;
	$cnt += 1;
}
echo $cnt;

Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool comapre(pair<ll int,ll int> a,pair<ll int,ll int> b)
{return a.first<b.first;
}
int main()
{
   ll int n,w;
   cin>>n>>w;
   pair<ll int,ll int> a[n];
   for(ll int i=0;i<n;i++)
  {  ll int e,f;
    cin>>e>>f;
a[i]=make_pair(e,f);
  }
sort(a,a+n,comapre);

//for(auto i: a)
//cout<<i.first<<" "<<i.second<<endl;
ll int dp[n][w+1];
memset(dp,0,sizeof dp);
for(ll int i=0;i<n;i++)
{for(ll int j=0;j<=w;j++)
  dp[i][j]=0;

}
ll int x=a[0].first;
//cout<<x<<" weight\n";
for(ll int i=0,j=0;j<=w;j++)
{if(x<=j)
  dp[i][j]=a[0].second;}

for(ll int i=1;i<n;i++)
{ll int we=a[i].first;
for(ll int j=1;j<=w;j++)
{if(j<we)
  dp[i][j]=dp[i-1][j];
else
{dp[i][j]=max(a[i].second+dp[i-1][j-we],dp[i-1][j]);

}
}

}  




cout<<dp[n-1][w]<<endl;


}

Measured memory_bytes: 78336
#include <stdio.h>

int main(void){
  int n;
  char s[50];
  scanf("%d %s", &n, s);
  int count = 0;
  
  for(int i=0; i<n; i++){
    if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
      count ++;
    }
  }
  
  printf("%d", count);
  return 0;
}


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int sum = a+b+c;
    int maxi = max(a,max(b,c));
    if(sum%2 == (maxi*3)%2){
        cout << ((maxi*3)-sum)/2;
    } else {
        cout << (((maxi+1)*3)-sum)/2;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MAX max<ll>
#define MIN min<ll>
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define drop(x) cout << (x) << '\n', exit(0)
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
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 devc(ll x, ll y) { return (x + y - 1) / y; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> ans;

    if(A < devc(N, B) || A > N - B + 1) drop(-1);

    ll L;
    rep(I, N + 1) if(I + devc(N - I,B) == A) L = I;

    rep1(i, L) ans.pb(i);
    ll tp;
    for (ll i = L + 1; i <= N; ++i){
        if((i - L - 1) % B == 0) L += B, tp = min(L, N);
        ans.pb(tp);
        --tp;
    }
    for(auto a : ans) cout << a << " ";
    print("");

    return 0;
}

Measured memory_bytes: 6384
#include<iostream>
#include<string>
#include <cstdlib>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include <iomanip>
#include<stack>
#include <unordered_map>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
// #define pi acos(-1)
// #include<bits/stdc++.h>
typedef long long ll;
#define INF 0x7f7f7f7f //2139062143
#define INF1 0x3f3f3f3f //1061109567
#define INF2 2147483647
#define llINF 9223372036854775807
#define pi 3.14159265358979323846264338327950254
#define pb push_back
#define ll long long
#define debug cout << "debug\n";
#define STDIN freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
#define Quick ios::sync_with_stdio(false);cin.tie(NULL);
#define scai(x) scanf("%d", &x)
#define sca2i(x, y) scanf("%d %d", &x, &y)
#define scaf(x) scanf("%lf", &x)
#define sca2f(x, y) scanf("%lf %lf", &x, &y)
#define For(m,n) for (int i = m;  i < n; i++)
#define PII pair<int,int>
#define PLL pair<long, long>
#define lowbit(x) (x&-x)

const int maxn = 50;
#define ERR 1e-6
#define fabs(a) (a < 0 ? -(a) : a)
#define square(a) ((a) * (a))


int main()
{
    //STDIN
    int n; cin >> n;
    cout << n/500*1000 + n%500/5*5 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long x,k,d;
  cin>>x>>d>>k;
  if(x<0) x *=(-1);
  long long b = x%k;
  long long c = x/k;
  if(c>d){
    cout<<x-k *d<<endl;
    
  }
  else if( c == d){
    cout<<b<<endl;
    
  }
  else if(c<d){
    if((d-c)%2ll ==0) cout<<b<<endl;
    else cout<<k-b<<endl;
  }
  
}


Measured memory_bytes: 3672
s = list(input())
t = list(input())

s = sorted(s)
S = "".join(s)

t = sorted(t)
t = t[::-1]
T = "".join(t)

L = [S, T]


LL = sorted(L)
if S == T:
	print("No")
else:
	if LL[0] == S:
		print("Yes")
	else:
		print("No")

Measured memory_bytes: 3064
while True:
    n = int(input())
    if n == 0:
        break

    a = sorted(list(map(int, input().split())))
    
    # 要素間の差を求め、最も差の小さい値を抽出する
    b = []
    for i, x in enumerate(a[:-1]):
        b.append(abs(x - a[i+1]))
    print(min(b))



Measured memory_bytes: 5636
using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            string str = Console.ReadLine();

            string[] str2 = str.Split(' ');

            var list = new List<int>();

            foreach (var s in str2)
            {
                list.Add(int.Parse(s));
            }

            list.Sort();

            Console.WriteLine(String.Join(" ", list));


        }
    }
}



Measured memory_bytes: 17968
a,b,c = gets.chomp.split.map(&:to_i).sort
diff = (c-a) + (c-b)

if c % 2 == a % 2 && c % 2 == b % 2
  puts diff/2 
elsif a % 2 == b % 2
  puts (diff-2)/2 + 1
else
  puts (diff+1)/2 + 1
end

Measured memory_bytes: 1788
package main

import (
	"fmt"
)

func main() {
	var n,x int
	fmt.Scan(&n,&x)

	l := make([]int,n)
	for i := 0; i < n; i++ {
		fmt.Scan(&l[i])
	}

	d := 0
	ans := 1
	for i := 0; i < n; i++ {
		d = d + l[i]
		if x < d {
			break
		}

		ans++
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
import java.lang.Math;
import java.util.Scanner;


public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);

        long a = 0;
        long b = 0;
        char[] op = {0};

        while (true) {
            a = sc.nextInt();
            String str = sc.next();
            op = str.toCharArray();
            b = sc.nextInt();

            if (op[0] == '?') break;

            switch (op[0]) {
            case '+':
                System.out.println(a+b); break;

            case '-':
                System.out.println(a-b); break;

            case '*':
                System.out.println(a*b); break;

            case '/':
                System.out.println(a/b); break;
            }
        }
    }
}


Measured memory_bytes: 26448
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>

#define rep(i,j,k) for(int i=j;i<k;i++)
#define drep(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
#define Sort(x) sort((x).begin(),(x).end())
#define fi first
#define se second
#define vi vector<int>
#define INF 1000000000
#define MOD 1000000009
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;

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

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

bool isPrime(int x){
    if(x==1)return false;
    if(x==2)return true;
    if(x%2==0)return false;
    for(int i=3;i<=sqrt(x);i+=2){
        if(x%i==0)return false;
    }
    return true;
}

int kaizyo(int x){
    if(x==1)return x;
    else return x*kaizyo(x-1);
}

typedef struct Point{
    int x;
    int y;
} P;

int main() {
    int n;cin>>n;
    rep(i,0,n){
        string s;
        cin>>s;
        Sort(s);
        string s1=s;
        sort(s.begin(),s.end(),greater<int>());
        string s2=s;
        int ma=stoi(s1),mi=stoi(s2);
        cout<<mi-ma<<endl;
    }

    return 0;
}



Measured memory_bytes: 3004