akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yassin
 */

#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstdlib>
#include <tuple>
#include <queue>
#include <functional>
#include <stack>
#include <numeric>
#include <cassert>
#include <sstream>

using namespace std;

class apc001_b {
public:
    void solve(istream& in, ostream& out) {
        int N;
        in >> N;
        vector<int> a(N), b(N);
        for (int i = 0; i < N; ++i) {
            in >> a[i];
        }
        for (int i = 0; i < N; ++i) {
            in >> b[i];
        }
        long long num_add_b = 0, need_add_b = 0;
        for (int i = 0; i < N; ++i) {
            if (a[i] < b[i]) {
                num_add_b += (b[i] - a[i]) / 2;
            } else {
                need_add_b += a[i] - b[i];
            }
        }
        out << (need_add_b <= num_add_b ? "Yes\n" : "No\n");
    }
};


int main() {
	std::ios::sync_with_stdio(false); cin.tie(nullptr);
	apc001_b solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<cstdio>
using namespace std;

int main(){

    int a,b,c;
    cin >> a >> b >> c;

    if(a < c && b > c)cout << "Yes\n";
    else if(a > c && b < c)cout << "Yes\n";
    else cout << "No\n";


    return 0;
}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};

signed main(){
    int N, D;
    cin >> N >> D;
    PRINT((int)ceil((double)N / (2 * D + 1)));
    return 0;
}

Measured memory_bytes: 256
// Problem Code: abc170_d

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int not_divisible(int N, vector<int>& A) {
	int cnt = 0, limit = *max_element(A.begin(), A.end());
	vector<int> freq(limit + 1);
	vector<bool> mark(limit + 1);

	for (int x: A)
		freq[x]++;
	sort(A.begin(), A.end());

	for (int i = 0; i < N; i++) {
		if (mark[A[i]])
			continue;
		for (int x = A[i]; x <= limit; x += A[i])
			if (x % A[i] == 0)
				mark[x] = true;
		cnt += freq[A[i]] == 1;
	}

	return cnt;
}

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	cout << not_divisible(N, A);
	return 0;
}

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


int main() {
	double a[3][3];
	rep(i, 3) {
		rep(j, 3)
			cin >> a[i][j];
	}
	int n;
	cin >> n;
	vector<int> b(n);
	rep(i, n)	cin >> b[i];

	//チェックしてokなら0にする．
	rep(k, n) {
		rep(i, 3) {
			rep(j, 3) {
				if (a[i][j] == b[k])	a[i][j] = 0;
			}
		}
	}
	

	bool check = 0;
	//横チェック
	rep(i, 3) {
		if (a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0)	check = 1;
	}
	//縦チェック
	rep(i, 3) {
		if (a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0)	check = 1;
	}
	//斜めチェック
	if (a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0)	check = 1;
	if (a[2][0] == 0 && a[1][1] == 0 && a[0][2] == 0)	check = 1;
		
	if (check)	cout << "Yes" << endl;
	else	cout << "No" << endl;



}

Measured memory_bytes: 256
from collections import defaultdict
from itertools import combinations
N = int(input())
dic = defaultdict(list)
for _ in range(N):
    s = input()
    if s[0] in "MARCH":
        dic[s[0]].append(s)

cmb = combinations(dic.keys(),3)
ans = 0
for a,b,c in cmb:
    ans += len(dic[a])*len(dic[b])*len(dic[c])
print(ans)

Measured memory_bytes: 16572
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
#define int long long

signed main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (4 * a * b < (c-a-b)*(c-a-b) && c - a - b > 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

double dist(P a, P b) {
  double dx = a.fi-b.fi;
  double dy = a.se-b.se;
  return sqrt(dx*dx + dy*dy);
}

int main() {
  int n;
  scanf("%d",&n);
  vp p(n);
  cin>>p;
  double ans = 0;
  int tot = 0;
  rep(i,n)rep(j,i) {
    ans += dist(p[i],p[j]);
    ++tot;
  }
  ans /= tot;
  ans *= n-1;
  printf("%.10f\n",ans);
  return 0;
}






















Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>   
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(ll i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	ll n,m,a,b,p,q;
	cin>>n>>m>>a>>b>>p>>q;
	if(a+b==2){
		ll t=p+q;
		ll T=min(n,m/t);
		ll out=m;
		loop(i,max(0ll,T-10),min(n+1,T+10))
			out=min(out,abs(t*i-m));
		cout<<out<<endl;
		return 0;
	}
	vi A,B;
	ll t=p;
	int co=0;
	while(1){
		A.pb(t);
		if(to_string(t).size()+to_string(a).size()>16)break;
		t*=a;
		if(a==1&&co==40)break;
		co++;
	}
	t=q;
	co=0;
	while(1){
		B.pb(t);
		if(to_string(t).size()+to_string(b).size()>16)break;
		t*=b;
		if(b==1&&co==40)break;
		co++;
	}
	//show1d(A);
	//show1d(B);
	vi in;
	rep(i,min((ll)A.size(),n))
		if(i<B.size()&&A[i]+B[i]<=3*m)in.pb(A[i]+B[i]);
	n=in.size()/2;
	ll N=1<<n;
	vi dp;
	rep(i,N){
		ll sum=0;
		rep(j,n)if(i&1<<j)sum+=in[j];
		if(sum<=3*m)dp.pb(sum);
	}
	sort(all(dp));
	ll nn=in.size()-n;
	N=1<<nn;
	ll out=m;
//	show1d(in);
	rep(i,N){
		ll sum=0;
		rep(j,nn)if(i&1<<j)sum+=in[n+j];
		if(sum>3*m)continue;
		auto it=upper_bound(all(dp),m-sum);
		if(it!=dp.end())out=min(out,abs(*it+sum-m));
		if(it==dp.begin())continue;
		it--;
		out=min(out,abs(*it+sum-m));
	}
//	show1d(dp);
	cout<<out<<endl;
}
















Measured memory_bytes: 11232
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
typedef pair<ll, ll> LP;
 
ll POW(ll m,ll n)
{
  if(n<0) return 0;
  if(n==0) return 1;
  return m*POW(m,n-1)%MOD;
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll CON(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return m*CON(m-1,n)/(m-n);
}
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
 
int main()
{
  string s[120];
  int a,m,n;
  m=100;
  n=0;
  cin >> a;
  rep(i,a)cin >> s[i];
  FOR(i,1,a){if(s[i-1][s[i-1].length()-1]!=s[i][0])m=0;
            }
  rep(i,a){
    rep(j,a){if(s[i]==s[j])n++;
            }
  }
  if(n==a&&m==100)printf("Yes");
  else printf("No");
}

Measured memory_bytes: 256
#!/usr/bin/env ruby
n, a, b = gets.chomp.split.map(&:to_i)
p = 10 ** 9 + 7

# 繰り返し二乗法
def recursive_pow_with_mod(a, n, mod)
 return 1 if n == 0
 return a % mod if n == 1
 return (a * recursive_pow_with_mod(a, n - 1, mod) ) % mod if n % 2 == 1
 recursive_pow_with_mod(a, n / 2, mod) ** 2 % mod
end

# 逆元
def modinv(a, mod)
 b = mod; u = 1; v = 0
 while b > 0
  t = a / b
  a -= t * b
  tmp = a; a = b; b = tmp
  u -= t * v
  tmp = u; u = v; v = tmp
 end
 u %= mod
 u < 0 ? u + mod : u
end

# 組み合わせ
def cmb(n, a, mod)
 numerator = 1
 denominator = 1
 a.times do |i|
  numerator *= n - i
  numerator %= mod
  denominator *= a - i
  denominator %= mod
 end
 numerator * modinv(denominator, mod) % mod
end

ans = recursive_pow_with_mod(2, n, p) - 1 - cmb(n,a,p) - cmb(n,b,p)

while ans < 0
  ans += p
end
puts ans


Measured memory_bytes: 14312
#include <iostream>

using namespace std;

int n, D;
int c[1001][1001];
int A[1001][1001][3];
int sum_A[2002][2002][3];

int count(int k, int x1, int y1, int x2, int y2) {
  return sum_A[x2][y2][k] - sum_A[x1 - 1][y2][k] - sum_A[x2][y1 - 1][k] + sum_A[x1 - 1][y1 - 1][k];
}

bool check(int b) {
  for (int oy = 1; oy <= D; oy++) {
    for (int ox = 1; ox <= D; ox++) {
      if (count(0, ox, oy, ox + b, oy + b)) continue;
      if (count(1, ox + b + 1, oy + b + 1, ox + D - 1, oy + D - 1)) continue;
      if (count(2, ox + b + 1, oy, ox + D-1, oy + b)) continue;
      if (count(2, ox, oy + b + 1, ox + b, oy + D - 1)) continue;
      return true;
    }
  }
  return false;
}

int main(void) {
  cin >> n >> D;
  int cnt_max = 0;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    c[x % D][y % D]++;
    cnt_max = max(c[x % D][y % D], cnt_max);
  }
  int a = 0;
  while (cnt_max > (a + 1) * (a + 1))
    a++;

  for (int j = 0; j < D; j++) {
    for (int i = 0; i < D; i++) {
      A[i][j][0] = c[i][j] > (a + 1) * (a + 1);
      A[i][j][1] = c[i][j] > a * a;
      A[i][j][2] = c[i][j] > a * (a + 1);
    }
  }

  for (int k = 0; k < 3; k++)
    for (int j = 1; j <= 2 * D; j++)
      for (int i = 1; i <= 2 * D; i++)
        sum_A[i][j][k] += sum_A[i][j-1][k] + sum_A[i-1][j][k] - sum_A[i-1][j-1][k] + A[(i-1) % D][(j-1) % D][k];

  int l = -1, r = D - 1;
  while (l + 1 < r) {
    int b = (l + r) / 2;
    if (check(b))
      r = b;
    else
      l = b;
  }
  cout << a * D + r << endl;

  return 0;
}


Measured memory_bytes: 62848
n=int(input())
d={}
dlist=list(map(int,input().split()))
for i in range(len(dlist)):
    d[dlist[i]]=d.get(dlist[i], 0)+1


m=int(input())
t={}
tlist=list(map(int,input().split()))
for i in range(len(tlist)):
    t[tlist[i]]=t.get(tlist[i], 0)+1


for tk,tv in t.items():
    if(d.get(tk, 0)<tv):
        print("NO")
        break
else:
    print("YES")



Measured memory_bytes: 56672
#include<stdio.h>
int main(void)
{
	int i,n;
	int x,y,b,p;
	int xb,yp,xbyp,xbyp2,xbyp3,xbyp4;
	int b2,p2,xb2,yp2;
	scanf("%d",&n);
	
		
		
	for(i=1;i<=n;i++){
		scanf("%d %d %d %d",&x,&y,&b,&p);
			
		if(b>=5 && p>=2){
			xbyp2=(xb+yp)*8/10;
		}	
			xb=x*b;
			yp=y*p;
			xbyp=xb+yp;
		
		if(b<5){
			b=5;
		}
		if(p<2){
			p=2;
		}
		
		xb2=x*b;
		yp2=y*p;
		xbyp3=(xb2+yp2)*8/10;
		
		xbyp2=(xb+yp)*8/10;
		
		if(xbyp3<=xbyp){
			printf("%d\n",xbyp3);
		}
		else if(xbyp<=xbyp3){
			printf("%d\n",xbyp);
		}
		else if(xbyp2<=xbyp){
			printf("%d\n",xbyp2);
		}
		
	}
		return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    int cnt=0;
    int ans=0;
    rep(i,n-1){
        if(h[i]>= h[i+1])cnt++;
        else{
            ans = max(ans,cnt);
            cnt = 0;
        }
    }
    ans = max(ans,cnt);
    cout << ans << endl;
}

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

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

  // ここにプログラムを追記
  int x, min = 0;
  for(int i=0; i<N; i++) {
    cin >> x;
    
    if(K>x) {
      if(x-0 < K-x) {
        min += x-0;
      }
      else {
      	min += K-x;
      }
    }
    else {
      if(x-0 < x-K) {
        min += x-0;
      }
      else {
      	min += x-K;
      }
    }
  }
  cout << min*2 << endl;
}

Measured memory_bytes: 3588
n,m=map(int,input().split())
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n)
    self.rnk=[0]*(n)
    
  def Find_Root(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.Find_Root(self.root[x])
      return self.root[x]
  
  def Unite(self,x,y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x==y:
      return
    elif self.rnk[x] > self.rnk[y]:
      self.root[x]+=self.root[y]
      self.root[y]=x
    else:
      self.root[y]+=self.root[x]
      self.root[x]=y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y]+=1
        
  def isSameGroup(self,x,y):
    return self.Find_Root(x) == self.Find_Root(y)
  
  def Count(self,x):
    return -self.root[self.Find_Root(x)]


uf=UnionFind(n)
for iii in range(m):
  x,y,z=map(int,input().split())
  x-=1
  y-=1
  uf.Unite(x,y)

cnt=0
for iii in uf.root:
  if iii<0:
    cnt+=1
print(cnt)


    
  

Measured memory_bytes: 7700
# -*- coding: utf-8 -*-

count = 0
backslash_index = []
area_pond = []
pending_area=[]
for index,symbol in enumerate(input()):
	if symbol == "\\":
		backslash_index += [index]
	elif symbol == '/' and backslash_index:
		last_bs_index = backslash_index.pop()
		diff = index - last_bs_index 
		count += diff 
		while area_pond and area_pond[-1] > last_bs_index:
			diff += pending_area.pop()
			area_pond.pop()

		area_pond += [last_bs_index]
		pending_area += [diff]

print(count)
print(len(area_pond),*(pending_area))




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

#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define rf(i,n,a) for(int i=n ; i>=a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;
const int N = 1e6 + 5;
int f[N];
int ok[N];

int32_t main(){
   fast;
   int n;
   cin >> n;

   int a[n];
   f(i,0,n) cin >> a[i] , f[a[i]]++;

   int cnt = 0;

   f(i,0,n){
      f[a[i]]--;
      int ok = 1;
      for(int j=1 ; j*j <= a[i] ; j++){
         if(a[i] % j == 0){
            if(f[j] || f[a[i]/j]) ok = 0;
         }
      }
      cnt += ok;
      f[a[i]]++;
   }
   cout << cnt << "\n";
}

Measured memory_bytes: 12924
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int h,w,i,j,wk,x,y;
	char buf[51];
	int map[51][51],data[51][51];
	scanf("%d %d",&h,&w);
	for(i=0;i<h;i++)	{
		scanf("%s",buf);
		for(j=0;j<w;j++)	{
			map[i][j]=buf[j]-'0';
		}
	}
	for(i=0;i<h;i++)	{
		for(j=0;j<w;j++)	{
			if(i==0 && j==0)	{
				data[i][j]=0;
			}
			else if(i==0){
				data[i][j]=data[i][j-1]+map[i][j];
			}
			else if(j==0)	{
				data[i][j]=data[i-1][j]+map[i][j];
			}
			else {
				data[i][j]=map[i][j]+min(data[i-1][j],data[i][j-1]);
			}
		}
	}
	printf("%d\n",data[h-1][w-1]);
	return 0;
}


Measured memory_bytes: 1044
N = int(input())
A = list(map(int,input().split()))

ans = 0
s = 0

def mod(x):
    return int(x % int(1e+9 + 7))

for i in reversed(range(N-1)):
    s += A[i+1]
    s = mod(s)
    ans += A[i] * s

    ans = mod(ans) 

print(int(ans))

Measured memory_bytes: 31372
X = int(input())

maxAplus = int(pow(X, 1.0/5.0))
maxAsub = int(pow(X, 1.0/4.0))

for a in range(1, maxAplus+1):
    for b in range(a):
        if pow(a, 5) + pow(b, 5) == X:
            print(a, -b)
            exit()
        elif pow(a, 5) + pow(b, 5) > X:
            break

for a in range(1, maxAsub+1):
    for b in range(a):
        if pow(a, 5) - pow(b, 5) == X:
            print(a, b)
            exit()

Measured memory_bytes: 67972
from collections import defaultdict
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class Graph:
    """
    隣接リストによる無向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
        self.graph[dst].append((src, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra:
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        """
        startノードから各ノードまでの最短距離
        """
        return self.dist


def main():
    N,x,y = map(int, readline().split())

    # グラフの構築
    E = Graph()
    for i in range(1,N):
        if i == x:
            E.add_edge(x, y)
        E.add_edge(i, i+1)
    
    # 各頂点についてダイクストラ
    count = [0]*N
    for i in range(1,N):
        D = Dijkstra(E, i)
        dist = D.shortest_distance()
        for j in range(i+1,N+1):
            k = dist[j]
            count[k] += 1

    for k in range(1,N):
        print(count[k])


if __name__ == "__main__":
    main()


Measured memory_bytes: 119132
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <random>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
ll rand26() {
  random_device rnd;
  mt19937 mt(rnd());
  uniform_real_distribution<> rand(0, 25);
  return (ll)rand(mt);
}
int main()
{
  ll D; cin >> D;
  vector<ll> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<ll>> s(D, vector<ll>(26));
  vector<ll> t(D);  
  rep(i,D) {
    ll smax = -1;
    rep(j,26) {
      cin >> s[i][j];
      if(smax <= s[i][j]) {
	smax = s[i][j];
	t[i] = j;
      }
    }
  }

  
  ll m = 26*365;
  vector<ll> d(m), q(m);
  rep(i,26) {
    rep(j,365) {
      d[i*365 + j] = j;
      q[i*365 + j] = i;
    }
  }
  
  vector<set<ll>> st(26);
  rep(i,26) {
    st[i].insert(-1);
    st[i].insert(D);    
  }
  rep(i,D) {
    st[t[i]].insert(i);
  }

  ll res = 0;
  // ペナルティ
  vector<ll> pen(26, 0);
  rep(i,26) {
    auto it = st[i].begin();
    it++;
    while(it != st[i].end()) {
      auto it2 = it;
      it2--;
      ll x = *it - *it2 - 1;
      res -= x * (x + 1) / 2 * c[i];
      pen[i] += x * (x + 1) / 2 * c[i];
      it++;
    }
  }
  rep(i,D) {
    res += s[i][t[i]];
  }

  ll cntsum = 0;
  
  while(1) {
    ll cnt = 0;
    rep(i,m) {
      ll oldres = res;
      ll old = t[d[i]];
      ll neww = q[i];
      set<ll> oldst1 = st[old];
      set<ll> oldst2 = st[neww];    
      ll oldpen1 = pen[old];
      ll oldpen2 = pen[neww];
    
      res += s[d[i]][neww] - s[d[i]][old];
      st[old].erase(d[i]);
      st[neww].insert(d[i]);    
      // old
      res += pen[old];
      pen[old] = 0;
      auto it = st[old].begin();
      it++;
      while(it != st[old].end()) {
	auto it2 = it;
	it2--;
	ll x = *it - *it2 - 1;
	res -= x * (x + 1) / 2 * c[old];
	pen[old] += x * (x + 1) / 2 * c[old];
	it++;
      }
      // new
      res += pen[neww];
      pen[neww] = 0;
      it = st[neww].begin();
      it++;
      while(it != st[neww].end()) {
	auto it2 = it;
	it2--;
	ll x = *it - *it2 - 1;
	res -= x * (x + 1) / 2 * c[neww];
	pen[neww] += x * (x + 1) / 2 * c[neww];
	it++;
      }
      cnt++;
      
      if(oldres < res) {
	t[d[i]] = neww;
	cntsum += cnt;
	break;
      }
      else {
	t[d[i]] = old;
	st[old] = oldst1;
	st[neww] = oldst2;
	pen[old] = oldpen1;
	pen[neww] = oldpen2;      
      }
    }
    if(cntsum >= 560000) break;
  }

  rep(i,D) cout << t[i]+1 << "\n";
  
  return 0;
}


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

int main(){
  int64_t H,W;
  cin >> H >> W;
  int64_t ans;
  int judge = (H * W) % 2;
  
  if(H == 1 || W == 1){
    ans = 1;
  }  
  else{
    if(judge == 1){
    	ans = (H * W + 1) / 2;
  	}
  	else{
    	ans = (H * W) / 2;
  	}
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
/*g++ main.cpp -o main.out*/
/*./main.out*/
/*std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(n,a) memset(n,a,sizeof(n));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

string s;

int main()
{
    NO_TLE
    int n;
    cin>>n;
    cin>>s;
    string tmp=s;
    rep(i,n)
    {
        if(s[i]=='(')
        {
            rer(k,i+1,n)
            {
                if(s[k]==')')
                {
                    s[i]='1';
                    s[k]='2';
                    break;
                }
            }
        }
    }
    rep(i,n)
    {
        if(s[i]==')')
        {
            cout<<'(';
        }
    }
    cout<<tmp;
    rep(i,n)
    {
        if(s[i]=='(')
        {
            cout<<')';
        }
    }
    return 0;
}

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

int main() {
    long long N;
    cin >> N;
    vector<long long> a(N);
    for (long long i = 0; i < N; i++) {
        cin >> a[i];
    }
    long long ans = 0;
    for (long long i = 0; i < N; i++) {
        ans += a[i] - 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import itertools

N = int(input())
P = [int(i) for i in input().split(" ")]
Q = [int(i) for i in input().split(" ")]

permutations = sorted(P)
count = 0
p_index = 0
q_index = 0
for i in itertools.permutations(permutations,N):
    count+=1
    if "".join((str(j) for j in i)) == "".join([str(i) for i in P]):
        p_index = count
    if "".join((str(j) for j in i)) == "".join([str(i) for i in Q]):
        q_index = count
print(abs(p_index-q_index))

Measured memory_bytes: 3188
#include<iostream>

using namespace std;

int main()
{
  string s;
  cin>>s;
  if(s[5] == '0')
  {
    if(s[6] =='1')
      cout<<"Heisei"<<endl;
    else
    if(s[6] == '2')
      cout<<"Heisei"<<endl;
    else
    if(s[6] == '3')
      cout<<"Heisei"<<endl;
    else
    if(s[6] == '4')
      cout<<"Heisei"<<endl;
    else
      cout<<"TBD"<<endl;
  }
  else
    cout<<"TBD"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    int i,j=0;
    cin>>N;
    vector<int> vec(N);
    int countA=0,countB=0;
    for(i=0;i<N;i++ ){
    cin>>vec.at(i);
    }
    sort(vec.begin(),vec.end());
    for(i=N-1;i>=0;i--){
    if(j%2==0){
    countA+=vec.at(i);}
     else{
    countB+=vec.at(i);}
     j++;}
    cout<<countA-countB<<endl;
    }




Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;
const int maxn = 2e3+5;
struct Node
{
    int x,y;
} node[20];
int n;
int ans;
int vis[20];
int num[maxn][maxn][2];
int gcd(int a,int b)
{
    int c = 1;
    while(b)
    {
        c = b;
        b = a%b;
        a = c;
    }
    return a;
}
int get(int x,int y,int &a,int &b,int &c)
{
    if(x==0)
    {
        a= 0;
        b= 0;
        c = 0;
    }
    else if(y==0)
    {
        a = 0;
        b = 0;
        c = 1;
    }
    else if(x<0)
    {
        int cc = gcd(x,y);
        a = abs(x/cc);
        b = abs(y/cc);
        if(y<0)
            c = 0;
        else
            c = 1;
    }
    else
    {
        int cc = gcd(x,y);
        a = abs(x/cc);
        b = abs(y/cc);
        if(y>0)
            c = 0;
        else
            c = 1;
    }
}
void dfs(int t,int res,int cnt)
{
    if(cnt>n/2)
    {
        return ;
    }
    if(t>=n)
    {
        return ;
    }
//    if(res + (n-t)/2 <= ans)
//        return ;
    if(vis[t])
    {
        dfs(t+1,res,cnt);
        return ;
    }
    vis[t] = cnt;
    for(int i=0; i<n; i++)
    {
        if(vis[i])
            continue;
        vis[i] = cnt;
        int x =  node[i].x - node[t].x;
        int y = node[i].y - node[t].y;
        int nr = 0;
        int a=0,b=0,c=0;
        get(x,y,a,b,c);
        nr = num[a][b][c];
        num[a][b][c]++;
        //cout<<ans<<endl;
        ans = max(ans,res+nr);
//        if(cnt+1>n/2)
//            return ;
        dfs(t+1,res+nr,cnt+1);
        vis[i] = 0;
        num[a][b][c]--;
    }
    vis[t] = 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d%d",&node[i].x,&node[i].y);
    ans=0;
   // memset(vis,0,sizeof(vis));
   // memset(num,0,sizeof(num));
    dfs(0,0,1);
    printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 3620
#include<iostream>
#define fo(i,n) for(int i=1;i<=n;i++)
#define for(i,n) for(int i=0;i<n;i++)
#define ll long long 
using namespace std;
int main()
{
	int n,res=0;
	cin>>n;
	int t=n/1000;
	if(n%1000)
	 res=(t+1)*1000-n;
	else res=0;
	cout<<res<<"\n";
	
	return 0;
 } 

Measured memory_bytes: 3164
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        String S = sc.next();
        S = S.replace("ABC", "-");
        int count = 0;

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == '-') {
                count++;
            }
        }

        PrintWriter out = new PrintWriter(System.out);
        out.println(count);
        sc.close();
        out.flush();
    }
}

Measured memory_bytes: 35720
#include <iostream>

int main() {
  int n;
  std::cin >> n;
  int maxv = -1000000000;
  int min = 2000000001;
  for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    maxv = (a - min > maxv) ? a - min : maxv;
    min = (a < min) ? a : min;
  }
  std::cout << maxv << std::endl;
}

Measured memory_bytes: 3068
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String t = sc.next();
    int count = s.length();
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == t.charAt(i)) {
        count--;
      }
    }
    System.out.println(count);

  }
}


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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define INF (int)1e9  //
#define LINF (ll)4e18  //
#define MOD (int)(1e9)+7
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define PI 3.1415926535898

//------------------------------------------------------

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int Max = 0;
    int x = 0;

    rep(i, n) {
        if (s[i] == 'I') {
            x++;
            if (x > Max) Max = x;
        } else {
            x--;
        }
    }

    cout << Max << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

int main() {
	cout << fixed << setprecision(12);	
	int n;
	cin >> n;
	vector<pair<string, int> > v;
	for (int i = 0; i < n; i++) {
		string s;
		int t;
		cin >> s >> t;
		v.push_back(make_pair(s, t));
	}
	string q;
	cin >> q;
	int i = 0;
	while (v[i].first != q) {
		i++;
	}
	i++;
	int ret = 0;
	for (; i < n; i++) {
		ret += v[i].second;
	}
	cout << ret << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 3552
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
#define MOD 1000000007
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1e18
#define For(i,a,b) for (int i = a; i < b; i++)
#define Rep(i,a,b) for (int i = a; i <= b; i++)
#define ps(x,y) fixed << setprecision(y) << x 
#define pb push_back 
#define mp make_pair 

int countDigits(int n) {
    string val = to_string(n);
    return val.size();
}
 
int32_t main()
{
    fast;
    int n, ans, val; cin >> n;
    ans = countDigits(n);
    Rep(i, 1, sqrt(n) + 1) {
        if(n % i == 0) {
            val = max(i, n / i);
            ans = min(ans, countDigits(val));
        }
        
    }
    cout << ans;
    
    
    
    
    return 0;
}

Measured memory_bytes: 3732
/*
𝓐𝓾𝓽𝓱𝓸𝓻:-
𝓢𝓪𝓾𝓻𝓪𝓫𝓱𝓼𝓱𝓪𝓭𝓸𝔀
------------------------
*/
#include <bits/stdc++.h>

using namespace std;

#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopb(i,a,b) for(int i=a;i>=b;i--)
#define fore(name)  for(auto it=name.begin();it!=name.end();it++)
#define w  int t;cin>>t;while(t--)
#define pb(x) push_back(x)
#define in(y) insert(y)
#define bitscount 32
#define make(x,y) make_pair(x,y)
#define LOAD_FACTOR_set(name) name.reserve(32768);name.max_load_factor(0.25);
#define LOAD_FACTOR_map(name) name.reserve(1024);name.max_load_factor(0.25);
#define lcm(a,b) ((a*b))/(__gcd(a,b))
#define int long long int
#define REDBULL ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define endl "\n"
#define all(x) (x).begin(), (x).end()


struct HASH {
    size_t operator()(const pair<int, int>&x)const {
        return ((int)x.first) ^ (((int)x.second) << 32);
    }
};
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
typedef pair<int, int> pi;
#define UNMAP(name) unordered_map<int,int,custom_hash> name
#define MAX 10000000000000
#define log 24
bool testOverlap(int x1, int x2, int y1, int y2) {
    if (x1 <= y2 && y1 <= x2)
        return true;
    return false;
}
int visited[100001];
vector<int> graph[100001];
void dfs(int u)
{
    visited[u] = 1;
    for (auto it : graph[u])
    {
        if (visited[it])
            continue;
        dfs(it);
    }
}
void solve()
{


    int n, m;
    cin >> n >> m;
    loop(i, 1, n + 1)
    visited[i] = 0;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    int count = -1;
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            dfs(i);
            count++;
        }
    }

    cout << count << endl;

}
int32_t main()
{
    REDBULL
    // w
    solve();

    return 0;
}

Measured memory_bytes: 11112
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000000 - 1
int main(){
	int n,i,input;
	int tn, tmp;
	int tetra_n[181];
	int *tetra_sum, *tetra_sum_odd;
	char a[10];
	for (n = 0; n <= 180; n++) tetra_n[n] = n*(n+1)*(n+2) / 6;
	tetra_sum = (int *) malloc(sizeof(int) * (MAX+1));
	tetra_sum_odd = (int *) malloc(sizeof(int) * (MAX+1));
	tetra_sum[0] = 0;
	tetra_sum_odd[0] = 0;
	for (i = 1; i <= MAX; i++){ 
		tetra_sum[i] = MAX; 
		tetra_sum_odd[i] = MAX;
	}
	for (n = 1; n <= 180; n++){
		tn = tetra_n[n];
		if (tn % 2 == 0) {
			for (i = tn; i <= MAX; i++){
				tmp = tetra_sum[i-tn] + 1;
				if (tmp < tetra_sum[i]) tetra_sum[i] = tmp;
			}
		} else {
			for (i = tn; i <= MAX; i++){
				tmp = tetra_sum[i-tn] + 1;
				if (tmp < tetra_sum[i]) tetra_sum[i] = tmp;
				tmp = tetra_sum_odd[i-tn] + 1;
				if (tmp < tetra_sum_odd[i]) tetra_sum_odd[i] = tmp;
			}
		}
	}
	while (1){
		input = atof(fgets(a, sizeof(a) / sizeof(a[0]), stdin));
		if (input == 0) break;
		printf("%d %d\n", tetra_sum[input], tetra_sum_odd[input]);
	}
	free(tetra_sum);
	free(tetra_sum_odd);
 	return 0;
}

Measured memory_bytes: 8148
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

#define REP(i, k, n) for(int i = k; i < n; i++)
#define rep(i, n) for(int i = 0; i < n; i++) 
#define mp make_pair

using namespace std;
typedef pair<int, int> P;
typedef pair<P, P> PP;

int dp[305][55];

int main() {
	int N, M, L;
	cin >> N >> M >> L;

	vector<PP> v(M);
	rep(i, M) {
		int d, a, k, t;
		cin >> d >> a >> k >> t;
		v[i] = mp(mp(d, a-1), mp(k, -t));
	}

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

	memset(dp, 0, sizeof(dp));

	rep(i, M) {
		int di = v[i].first.first;
		int ai = v[i].first.second;
		int ki = v[i].second.first;
		int ti = v[i].second.second;
		int time = ai + di * N;

		ti *= -1;

		rep(j, L) {
			int res = 0;
			rep(k, 5 * N) {
				dp[j][k] = max(res, dp[j][k]);
				if(time == k) {
					dp[j+1][k+ki] = max(dp[j+1][k+ki], dp[j][k] + ti);
				}
				res = max(res, dp[j][k]);
			}
		}
	}

	int ans = 0;
	rep(i, 305) {
		rep(j, 55) {
			ans = max(ans, dp[i][j]);
		}
	}

	// rep(i, L + 1) {
	// 	rep(j, 5 * N) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1276
//{{{By oToToT
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <random>
#include <utility>
#include <stack>
#include <sstream>
#include <functional>
#include <deque>
#include <cassert>
using namespace std;
/* include everything for Kotori~ <3 */

using lld = int64_t;
using llu = uint64_t;
using llf = long double;
using PII = pair<int,int>;
using PIL = pair<int,lld>;
using PLI = pair<lld,int>;
using PLL = pair<lld,lld>;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
/* define some types for Ruby! */

#define FF first
#define SS second
#define SZ(x) (int)((x).size())
#define ALL(x) begin(x), end(x)
#define PB push_back
#define WC(x) while(x--)
/* make code shorter for Di~a~ */

template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
	s<<"[";
	for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
	s<<"]";
	return s;
}
template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.FF<<","<<p.SS<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
/* make output easier for Ainyan~n~ */

bool debug = 0;
#define DUMP(x) if(debug) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<'\n'
template<typename T>
void DEBUG(const T& x){if(debug) cerr<<x;}
template<typename T, typename... Args>
void DEBUG(const T& head,const Args& ...tail){
	if(debug){cerr<<head; DEBUG(tail...);}
}
/* Let's debug with Nico~Nico~Ni */
//}}}
const int N = 200000 + 5;
const int C = 1<<30;

map<int,int,greater<int>> st;

int main(int argc, char* argv[]){
	if(argc>1 and string(argv[1])=="-D") debug=1;
	if(!debug){ios_base::sync_with_stdio(0);cin.tie(0);}
	int n; cin >> n;
	for(int i=1;i<=n;i++){
		int x; cin >> x;
		st[x]++;
	}
	int ans=0;
	for(auto it=st.begin();it!=st.end();++it){
		for(int64_t cur=1;cur<=C;cur<<=1){
			if(cur<it->FF) continue;
			if(st.find(cur-it->FF)==st.end())
				continue;
			if(it->FF*2==cur) {
				ans+=it->SS/2;
				it->SS &= 1;
				continue;
			}
			int dlt = min(it->SS, st[cur-it->FF]);
			ans+=dlt;it->SS-=dlt;st[cur-it->FF]-=dlt;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
3 29 
*/

Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

// dp[i][j][k] := (i個目までみた,j個選んだ,総和がkであるものの個数)
long long dp[60][60][2600];

int main()
{
  int N, A;
  cin >> N >> A;
  vector<long long> x(N);
  for (int i = 0; i < N; i++)
    cin >> x[i];

  dp[0][0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= 50; j++) {
      for (int k = 0; k <= 2500; k++) {
        // i個目を使わない場合
        dp[i + 1][j][k] += dp[i][j][k];
        // i個目を使う場合
        if (k + x[i] <= 2500) {
          dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
        }
      }
    }
  }

  long long ans = 0;
  for (int i = 1; i <= N; i++) {
    ans += dp[N][i][i*A];
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
static const int INF = 1000010000;
static const ll MOD = 998244353;
 
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue

//int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};

template< typename Monoid >
struct SegmentTree
{
  using F = function< Monoid(Monoid, Monoid) >;
 
  int sz;
  vector< Monoid > seg;
 
  const F f;
  const Monoid M1;
 
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
 
  void set(int k, const Monoid &x)
  {
    seg[k + sz] = x;
  }
 
  void build()
  {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  void update(int k, const Monoid &x)
  {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  Monoid query(int a, int b)
  {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
 
  Monoid operator[](const int &k) const
  {
    return seg[k + sz];
  }
};

int main(){
    int a, b;
    cin >> a >> b;
    if(a + b == 15) cout << "+" << endl;
    else if(a * b == 15) cout << "*" << endl;
    else cout << "x" << endl;
}

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

int main(){
    int n;
    cin>>n;
    
    int count = 0;
    for(int i=1;i<=n;i++){
        int temp;
        cin>>temp;
        
        temp = temp^i;
        if(temp != 0) count++;
    }
    
    //cout<<count<<endl;
    if(count <= 2) cout<<"YES";
    else cout<<"NO";
}

Measured memory_bytes: 256
// F.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	cout.precision(10);
#ifdef _MSC_VER
	while (true)
#endif
	{
		int n = -1, m = -1;
		cin >> n >> m;
		if (n <= 0) return 0;
		vector<vector<int>> fwd(n);
		vector<double> dp(n, 0);
		for (int i = 0; i < m; ++i) {
			int a, b;
			cin >> a >> b;
			fwd[a - 1].push_back(b - 1);
		}
		double ans = 1e9;
		for (int i = 0; i < n - 1; ++i) {
			for (int j = n - 2; j >= 0; --j) {
				double sum = 0, mx = 0;
				for (int next : fwd[j]) {
					double d = dp[next] + 1;
					sum += d;
					mx = max(mx, d);
				}
				if (i == j && fwd[j].size() >= 2) {
					dp[j] = (sum - mx) / (fwd[j].size() - 1);
				} else {
					dp[j] = sum / fwd[j].size();
				}
			}
			ans = min(ans, dp[0]);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <climits>
using namespace std;
int main(){
  long long a,b,c,d;
  cin >> a >> b >> c >> d;
  long long f = a*c;
  long long g = a*d;
  long long h = b*c;
  long long i = b*d;
  long long max = -1000000000000000000;
    if(f>max){
        max = f;
    }
    if(g>max){
    max = g;
    }
    if(h>max){
    max = h;
    }
     if(i>max){
    max = i;
    }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 3620
import java.io.*
import java.util.*

val pw = PrintWriter(System.out)
fun solve(N: Long, X: Long, x: LongArray){
    val ans = x.map{ Math.abs(it - X) }.reduce{ a,b -> gcd(a,b) }
    println(ans)
    return
}

fun gcd(x: Long, y: Long): Long = if (y == 0L) x else gcd(y, x % y)

fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toLong()
    val X = sc.next().toLong()
    val x = LongArray(N.toInt())
    for (i in 0 until N.toInt()) {
        x[i] = sc.next().toLong()
    }
    solve(N, X, x)
}



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

int main()
{
  int n;
  cin>>n;
  
  vector<vector<int>> a(n,vector<int>(3));
  for(int i=0;i<n;i++)
    cin>>a[i][0]>>a[i][1]>>a[i][2];
  
  vector<vector<int>> x(n,vector<int>(3,-1));
  
  x[0][0]=a[0][0];
  x[0][1]=a[0][1];
  x[0][2]=a[0][2];
  
  for(int i=1;i<n;i++)
  {
    for(int j=0;j<3;j++)
    {
      for(int k=0;k<3;k++)
      {
        if(j==k)
          continue;
        x[i][k]=max(x[i][k],x[i-1][j]+a[i][k]);
      }
    }
  }
  
  cout<<max(x[n-1][0],max(x[n-1][1],x[n-1][2]))<<endl;
}

Measured memory_bytes: 11136
n = int(input())
a = input().split()

o = [int(i) for i in a]
for idx in range(0, int(n / 2)):
    w = o[idx]
    o[idx] = o[n - idx - 1]
    o[n - idx - 1] = w

for idx in range(n):
    print(o[idx], end = '')
    if idx == n - 1:
        break
    print(' ', end = '')
print()

Measured memory_bytes: 7768
#include<stdio.h>
int D;
int main(){
	scanf("%d", &D);
	if(D==25){
		printf("Christmas\n");
	}else if(D==24){
		printf("Christmas Eve\n");
	}else if(D==23){
		printf("Christmas Eve Eve\n");
	}else if(D==22){
		printf("Christmas Eve Eve Eve\n");
	}
}


Measured memory_bytes: 128