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

int main(){
  int a,b;
  string str;
  
  int tmp;
  bool chk = true;
  
  cin >> a >> b >> str;
  
  if(str.size() == a + b + 1){
    if(str.substr(0,a).size() != a) chk = false;
    if(str.substr(a + 1,b).size() != b) chk = false;
    
    for(int i = 0; i < a; i++){
      if(str.substr(i,1) == "-") chk = false;
    }
    
    if(str.substr(a,1) != "-") chk = false;
    
    for(int i = a + 1; i < a + b + 1; i++){
       if(str.substr(i,1) == "-") chk = false;
    }
  }else{
    chk = false;
  }
  
  if(chk == true) cout << "Yes";
  else cout << "No";
}


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

pos1 = A.index(1)
before1 = pos1
after1 = N-pos1-1

ans = 0
if(before1%(K-1)==0):
    ans += before1//(K-1)
else:
    ans += before1//(K-1)+1
    after1 -= (K-1)-before1%(K-1)

if(after1%(K-1)==0):
    ans += after1//(K-1)
else:
    ans += after1//(K-1)+1

print(ans)


Measured memory_bytes: 14008
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;

int main(){
	cin>>n;
	vi a(n);
	for(auto &i:a) cin>>i;
	int res=inf;
	for(int i=1;i<=100;i++){
		int tmp=0;
		for(auto j:a) tmp+=(j-i)*(j-i);
		res=min(res,tmp);
	}
	cout<<res<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
double PI = 3.1415926535897932;
long mod = 1000000007;

int main() {
  long n,m,w[110],v[110];
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
    cin >> w[i] >> v[i];
  
  long dp[110][110000];
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(j >= w[i])
        dp[i][j] = max(dp[i-1][j-w[i]] + v[i],dp[i-1][j]);
      else
        dp[i][j] = dp[i-1][j]; 
    }
  }
  cout << dp[n][m] << endl;
}

Measured memory_bytes: 81992
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdint>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;
	
ll M = 1000000007;

typedef pair<int, int> P;

bool ps1(const P &element1, const P &element2)
{ //first昇順
	return element1.first < element2.first;
}
bool ps2(const P &element1, const P &element2)
{ //first降順
	return element1.first > element2.first;
}
bool ps3(const P &element1, const P &element2)
{ //second昇順
	return element1.second < element2.second;
}
bool ps4(const P &element1, const P &element2)
{ //second降順
	return element1.second > element2.second;
}
int digits(int n)
{
	int count = 0;
	while (n > 0)
	{
		n /= 10;
		count++;
	}
	return count;
}
ll combination(ll n, ll r)
{
	if (r * 2 > n)
		r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (ll i = 1; i <= r; ++i)
	{
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}
vector<int> divisor(int n)
{
	vector<int> value;
	FOR(i, 1, pow(n, 0.5) + 1)
	{
		if (i <= sqrt(n))
		{
			if (n % i == 0)
			{
				value.push_back(i);
				if (i * i != n)
				{
					value.push_back(n / i);
				}
			}
		}
	}
	return value;
}
int main()
{
	string s;
	cin>>s;
	if(s.substr(0,4)=="YAKI"){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}

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

using namespace std;

#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORD(i, m, n) for (int i = m; i >= n; i--)
#define REP(i, n) for (int i = 0; i < n; i++)
#define REP1(i, n) for (int i = 0; i <= n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

using ll = long long;
using ull = unsigned long long;
using ld = long double;

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

	int a,b,c;
	cin>>a>>b>>c;
	int ab,bc,ca;
	int ans=0;
	while(1){
		if(a==b&&b==c&&a%2==0){
			cout << -1 << endl;
			return 0;
		}
		if(a%2==1||b%2==1||c%2==1){
			break;
		}
		ab=a/2+b/2;
		bc=b/2+c/2;
		ca=c/2+a/2;
		a=bc;
		b=ca;
		c=ab;
		ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3604
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXR 12
#define MAXC 10005
int R,C;
int map[MAXR][MAXC];
int op[MAXR];
int main()
{
	while(1)
	{
		scanf("%d%d",&R,&C);
		if(R==0&&C==0)
			break;
		for(int i=1;i<=R;i++)
			for(int j=1;j<=C;j++)
				scanf("%d",&map[i][j]);
		int ans=0;
		for(int op=0;op<(1<<R);op++)
		{
			int sum=0;
			for(int j=1,s;j<=C;j++)
			{
				s=0;
				for(int i=1;i<=R;i++)
					if(op&(1<<(i-1)))
						s+=map[i][j]^1;
					else
						s+=map[i][j];
				if(s<=R/2)
					s=R-s;
				sum+=s;
			}
			ans=max(ans,sum);
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 3004
S = list(input())
T = list(input())

ANS = False
save_left = 0
save_right = 0
for i in range(len(S) - len(T) + 1):
    count = 0
    left = i
    right = i + len(T)

    for sv, tv in zip(S[left:right], T):
        if sv != tv and sv != '?':
            break
        count += 1

    if count == len(T):
        save_left = left
        save_right = right
        ANS = True
     
if ANS:
    S[save_left:save_right] = T
    for w in S:
        if w == '?':
            print('a', end='')
        else: 
            print(w, end='')
else:
    print('UNRESTORABLE')

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
// #define LOCAL
const int MAXN=60;
int N;
int a[MAXN];
void solve()
{
    cin>>N;
    int mx,mi,imx=1,imi=1;
    cin>>a[1];
    mx=mi=a[1];
    for(int u=2;u<=N;u++){
        cin>>a[u];
        if(mx<a[u])mx=a[u],imx=u;
        if(mi>a[u])mi=a[u],imi=u;
    }
    cout<<2*N-1<<"\n";
    if(abs(mx)>=abs(mi)){
        for(int u=1;u<=N;u++){
            cout<<imx<<" "<<u<<"\n";
        }
        for(int u=2;u<=N;u++){
            cout<<u-1<<" "<<u<<"\n";
        }
    }
    else {
        for(int u=1;u<=N;u++){
            cout<<imi<<" "<<u<<"\n";
        }
        for(int u=N-1;u>=1;u--){
            cout<<u+1<<" "<<u<<"\n";
        }
    }
}
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    solve();
}

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

//#define PI 3.141592653589

using namespace std;



int main()
{
	int hen1, hen2, taikaku;
	int tyouhoukei=0, hisigata=0;
	
	while (scanf("%d,%d,%d", &hen1, &hen2, &taikaku) != EOF)
	{
		if (taikaku*taikaku == hen1*hen1 + hen2*hen2) tyouhoukei++;
		if (hen1 == hen2) hisigata++;
	}
	cout << tyouhoukei << endl << hisigata << endl;
	
	return 0;
}

Measured memory_bytes: 1208
def find_indices(a, b, L):
    # aからbのパターンをみつける
    return [i for i in range(L) if a[i:].startswith(b)]

def solve():
    N,M = map(int, input().split())
    A = [input() for _ in range(N)]
    B = [input() for _ in range(M)]
    idx = 0
    start_pos = {}
    for S_a in A:
        indices = set(find_indices(S_a, B[idx], N))
        if not start_pos:
            start_pos = indices
        else:
            start_pos = start_pos&indices
        
        if start_pos:
            idx += 1
        else:
            start_pos = {}
            idx = 0
            
        if idx == M:
            break
    
    print('Yes' if start_pos else 'No')
    
solve()

Measured memory_bytes: 3064
let solve s_lst =
    let rec solve' lst result =
        match lst with
        | x1::x2::xs ->
            let next_result =
                if x1 <> x2 then result + 1
                else result
            solve' (x2::xs) next_result
        | _ -> result

    solve' s_lst 0

let () =
    let s_lst = stdin.ReadLine () |>
                List.ofSeq
    solve s_lst |> printfn "%d"  

Measured memory_bytes: 12232
n, k = map(int, input().split())
p = 10**9+7
F = {}
s = 0
for i in range(k, 0, -1):
    F[i] = pow(k//i, n, p)
    for j in range(2*i, k+1, i):
        F[i] -= F[j]
    s = (s + F[i] * i) % p
print(s)

Measured memory_bytes: 20756
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

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

    int x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2;

    int absX = abs(x1 - x2);
    int absY = abs(y1 - y2);

    if (x1 > x2) {
        if (y1 > y2) {
            x3 = x2 + absY;
            y3 = y2 - absX;
            x4 = x3 + absX;
            y4 = y3 + absY;
        } else {
            x3 = x2 - absY;
            y3 = y2 - absX;
            x4 = x3 + absX;
            y4 = y3 - absY;
        }
    } else {
        if (y1 > y2) {
            x3 = x2 + absY;
            y3 = y2 + absX;
            x4 = x3 - absX;
            y4 = y3 + absY;
        } else {
            x3 = x2 - absY;
            y3 = y2 + absX;
            x4 = x3 - absX;
            y4 = y3 - absY;
        }
    }
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}


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

using namespace std;

int main()
{
    int n,m,c,r=0;

    cin>>n;

    for(int i=1; i<=n; i++)
    {
        m=i;
        c=0;

        while(m!=0)
        {
            m/=10;
            c++;
        }

        if(c%2!=0)
        {
            r++;
        }
    }

    cout<<r<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
int main(){
    int n;
    cin >> n;
    int check[8];
    rep(i,8){
        check[i] = false;
    }
    int a;
    int ans = 0;
    rep(i,n){
        cin >> a;
        if(a>=3200) ans++;
        else check[a/400] = 1;
    }
    int ans2 = 0;
    rep(i,8){
        ans2+=check[i];
    }
    if(ans2==0){
      ans2=1;
      ans--;
    }
    cout << ans2 << " " << ans+ans2 << endl;
}

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

int main()
{
    int h, w, k, ans;
    cin >> h >> w >> k;
    vector<string> bored(h);
    for (int i = 0; i < h; i++)
    {
        cin >> bored[i];
    }

    vector<int> line;
    for (int bit = 0; bit < (1 << (h + w)); bit++)
    {
        vector<string> tmp(h);
        tmp = bored;
        int count = 0;
        for (int i = 0; i < h + w; i++)
        {
            if (bit & (1 << i))
            {
                line.push_back(i);
            }
        }
        for (auto v : line)
        {
            bool horw = true;
            if (v >= h)
            {
                v -= h;
                horw = false;
            }

            if (horw)
            {
                for (int i = 0; i < w; i++)
                {
                    tmp.at(v).at(i) = '.';
                }
            }
            else
            {
                for (int i = 0; i < h; i++)
                {
                    tmp.at(i).at(v) = '.';
                }
            }
        }
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (tmp.at(i).at(j) == '#')
                    count++;
            }
        }
        if (count == k)
            ans++;
        line.clear();
    }

    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

bool can[40001] = {};

int main() {
  int n;
  cin >> n;
  vi a(n);
  REP(i, n) { cin >> a[i]; }
  REP(i, (1 << n)) {
    int sum = 0;
    REP(j, n) {
      if ((i >> j) % 2 == 1)
        sum += a[j];
    }
    can[sum] = true;
  }

  int q;
  cin >> q;
  REP(i, q) {
    int m;
    cin >> m;
    cout << (can[m] ? "yes" : "no") << endl;
  }
  return 0;
}



Measured memory_bytes: 3108
#include <iostream>

using namespace std;

int n , k , ans = 1e9;
int main()
{
    cin>>n>>k ;
    //solve(0 , 0 , 1e9 , 0) ;
    if(n % k == 0)
        cout<<0;
    else
    cout<<1;
    return 0 ;
}


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

using namespace std;

typedef unsigned long long ull;

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

    int a,b,c;
    cin >> a >> b >> c;
    if (c >= a && c <= b)
        cout << "Yes" << endl;
    else
        cout << "No";
    return 0;
}

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

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

int main(){
    char a; cin >> a;
    if(a-'a'>=0){
        cout << 'a' << endl;
    }else{
        cout << "A" << endl;
    }
}


Measured memory_bytes: 3544
# https://atcoder.jp/contests/abc070/tasks/abc070_d

# 都度のクエリーに答えていると時間が足りない。
# 必ずKを通過すると決まっているので、各頂点とKの距離を
# 事前に計算しておく。O(V + E)

from heapq import heappush, heappop
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((c, b))
    graph[b].append((c, a))
q, k = map(int, input().split())
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    queries.append((x, y))


def dijkstra_with_heap(graph, start, v):
    distance = [float('infinity')] * v
    distance[start] = 0
    stack = [[0, start]] # cost, vertex
    while stack:
        _, vertex = heappop(stack)
        edges = graph[vertex]
        for d, t in edges:
            if d + distance[vertex] < distance[t]:
                distance[t] = d + distance[vertex]
                heappush(stack, (d, t))
    return distance


distance = dijkstra_with_heap(graph, k - 1, n)

for x, y in queries:
    ans = distance[x] + distance[y]
    print(ans)

Measured memory_bytes: 112216
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int sum[2160][2160];
Int dp[2160][2160];
Int res = 1;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> S(n), T(m);
    for(int i = 0;i < n;i++)cin >> S[i];
    for(int i = 0;i < m;i++)cin >> T[i];

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(S[i] == T[j]){
                if(i-1 >= 0 && j-1 >= 0)
                    dp[i][j] += sum[i-1][j-1];
                dp[i][j] = (dp[i][j] + 1) % MOD;
            }
            sum[i][j] += dp[i][j];
            if(i-1 >= 0)sum[i][j] += sum[i-1][j];
            if(j-1 >= 0)sum[i][j] += sum[i][j-1];
            if(i-1 >= 0 && j-1 >= 0)sum[i][j] -= sum[i-1][j-1];
            sum[i][j] %= MOD;
            if(sum[i][j] < 0)sum[i][j] += MOD;
            res += dp[i][j];
            res %= MOD;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 71936
#include <iostream>

using namespace std;

const int N = 100;

int main() {
	int n;
	cin >> n;
	bool relation[N+1][N+1] = {false};
	
	for (int i=0;i<n;i++) {
		int x,k;
		cin >> x >> k;
		x--;//转换为零起点
		for (int j = 0;j<k;j++) {
			int y;
			cin >> y;
			y--;//转换为零起点
			relation[x][y] = true; 
		}
	}
	
	for (int i= 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			cout << (short)relation[i][j];
			if (j != n-1) {
				cout << " ";
			} else {
				cout << endl;
			}
		}
	}
} 


Measured memory_bytes: 3112
n,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
print(max(dp[n]))

Measured memory_bytes: 119916
#include <iostream>
using namespace std;
using ll = long long;

ll f(ll b, ll n) {
  if (n < b) {
    return n;
  }
  return f(b, n / b) + (n % b);
}

ll solve(ll n, ll s) {
  ll b = 2;
  while (n / b >= b) {
    if (f(b, n) == s) {
      return b;
    }
    ++b;
  }
  for (ll k = n / b; k >= 1; k--) {
    ll rem = s - k;
    if (rem < 0) {
      continue;
    }
    ll sb = max(b, n / (k + 1) + 1);
    ll sm = n % sb;
    if (rem > sm || (sm - rem) % k != 0) {
      continue;
    }
    return sb + (sm - rem) / k;
  }
  if (s == n) {
    return n + 1;
  }
  return -1;
}

int main() {
  ll n, s;
  cin >> n >> s;
  cout << solve(n, s) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)


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

    int a = N / 2;
    if (s.substr(a) + s.substr(a) == s){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(void) {
  int N, M;
  if(scanf("%d %d", &N, &M)==1);
  int A[M];
  int i=0;
  while (i<M) {
    if(scanf("%d", &A[i])==1);
    i++;
  }
  while (M>0) {
    M -= 1;
    N -= A[M];
  }
  if (N<0) {
    printf("-1");
  }
  else {
    printf("%d", N);
  }
  return 0;
}

Measured memory_bytes: 1728
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class A
{
	public static void Main()
	{
		string[] args = Console.ReadLine().Split(' ');
		int a = Int32.Parse(args[0]);
		int b = Int32.Parse(args[1]);

		Console.WriteLine((b >= a) ? a : a-1);
	}
}





Measured memory_bytes: 11092
/*+lmake
 * STD = c++14
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;

#define MAXN 100000
void [[noreturn]] out(int t=0) 
{
	debug(t);
	puts("NO");
	exit(0);
}
LL a[MAXN+10];	
struct Edge
{
	int to,next;
}e[2*MAXN+10];
int head[MAXN+10];
void addEdge(int a,int b)
{
	static int c=0;
	e[++c]=(Edge){b,head[a]};
	head[a]=c;
	e[++c]=(Edge){a,head[b]};
	head[b]=c;
}
LL dp(int now,int fa)
{
	LL sum=0;
	LL mx=0;
	for(int i=head[now]; i!=0; i=e[i].next) {
		int v=e[i].to;
		if (v==fa) continue;
		LL son=dp(v,now);
		mx=max(mx,son);
		sum+=son;
	}
	if (mx==0) return a[now];
	//debug(now,a[now],sum);
	if (a[now]>sum ) out(1);
	if (sum>2*a[now]) {
		debug(now,a[now],sum);	
		out(0);
	}
	
	LL t=sum-a[now];
	if ((sum-mx)<t) out(2);
	return 2*a[now]-sum;
}
int main(){	
#ifdef WAAUTOMATON	
	freopen("in.txt","r",stdin);
#endif
	int n;
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}
	for(int i=1; i<n; ++i) {
		int x,y;
		cin>>x>>y;
		addEdge(x,y);
	}
	int x=-1;
	for(int i=1; i<=n; ++i) {	
		if (head[i]!=0 && e[head[i]].next==0) {
			x=i;
			break;
		}
	}
	debug(x);
	LL t=dp(x,0);
	puts("YES");
	return 0;
}


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

int main() {
  int h1,h2,m1,m2,k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  int t = (h2-h1)*60+m2-m1;
  cout << t-k << endl;
}

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

using namespace std;

int main()
{
	int n, d, x, a;
	cin >> n >> d >> x;
	
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		
		for (int j = 1; j <= d; j += a)
			x++;
	}
	
	cout << x;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define scl(n) scanf("%lld", &n)
#define pcl(n) printf("%lld\n", n)
#define pcl1(n) printf("%lld ", n)
#define dev(x) cout << #x << " " << x << " ";
#define PTT pair<ll, ll>

map<ll, ll> mp, mp1;
map<ll, ll>::iterator itr;

int main()
{
    ll n, t, c;
    scl(n);
    scl(t);
    vector<PTT> v;
    PTT p;
    for (int i = 0; i < n; i++)
    {
        scl(p.second);
        scl(p.first);
        v.push_back(p);
    }
    sort(v.begin(), v.end());
    
    ll mn = 1e10;
    for (int i = 0; i < n; i++)
    {
        if (v[i].first <= t)
        {
            mn = min(v[i].second, mn);
        }
        else
        {
            break;
        }
    }
    if (mn >=1000000)
    {
        cout << "TLE" << endl;
    }
    else
    {
        cout << mn << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

struct knapsack{
    int value = 0;
    int weight = 0;
};

int N, W;
vector<knapsack> vk;
int memo[101][10001];

int dp(int i, int j){
    if(memo[i][j] > 0){
        return memo[i][j];
    }
    
    int result;
    
    if(i == N){
        result = 0;
    }else if(vk[i].weight > j){
        result = dp(i+1, j);
    }else{
        result = max(dp(i+1,j), dp(i+1, j-vk[i].weight) + vk[i].value);
    }
    
    return memo[i][j] = result;
}

int main(){
    int v, w;
    
    scanf("%d %d", &N, &W);
    
    for(int i = 0;i < N;i++){
        scanf("%d %d", &v, &w);
        vk.push_back({v, w});
    }
    
    memset(memo, 0, sizeof(memo));
    printf("%d\n", dp(0, W));
    
    return 0;
}

Measured memory_bytes: 6628
#include<iostream>
#include<vector>
using namespace std;
struct UF{
	int n;
	vector<int>parent,rank;
	UF():n(0){}
	UF(int n_):n(n_),parent(n_),rank(n_,0)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	void unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(rank[a]<rank[b])
		{
			parent[a]=b;
		}
		else
		{
			parent[b]=a;
			if(rank[a]==rank[b])rank[a]++;
		}
	}
};
main()
{
	int n,q;cin>>n>>q;
	UF a(n);
	for(int i=0;i<q;i++)
	{
		int c,x,y;cin>>c>>x>>y;
		if(c)cout<<a.same(x,y)<<endl;
		else a.unite(x,y);
	}
}


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

//Submission #3535255 - AtCoder Beginner Contest 113 | AtCoder 
// https://abc113.contest.atcoder.jp/submissions/3535255
public class Program_ABC113_C_kuuso1
{
    public static void Main()
    {
        int N, M;
        int[] P, Y;

        var d = ria();
        N = d[0];
        M = d[1];
        P = new int[M];
        Y = new int[M];
        for (int i = 0; i < M; i++)
        {
            d = ria();
            P[i] = d[0];
            Y[i] = d[1];
        }

        var di = new Dictionary<int, List<int[]>>();
        for (int i = 0; i < M; i++)
        {
            if (!di.ContainsKey(P[i]))
            {
                di.Add(P[i], new List<int[]>());
            }

            di[P[i]].Add(new[] { i, Y[i] });
        }

        String[] ans = new String[M];
        foreach (var pr in di.Keys)
        {
            var l = di[pr].ToList();
            l.Sort((p, q) => p[1].CompareTo(q[1]));
            for (int i = 0; i < l.Count; i++)
            {
                ans[l[i][0]] = String.Format("{0:D06}{1:D06}", pr, i + 1);
            }
        }

        Console.WriteLine(String.Join("\r\n", ans));
    }  //main

    static int[] ria(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }

}


Measured memory_bytes: 47044
// ConsoleApplication.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdio.h"
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;
using NUM = double;

template<typename T>
struct Point {
	T x, y;
	Point<T> operator+(const Point<T>& rhs)const {
		Point<T> p;
		p.x = this->x + rhs.x;
		p.y = this->y + rhs.y;
		return p;
	}
	Point<T> operator-(const Point<T>& rhs)const {
		Point<T> p;
		p.x = this->x - rhs.x;
		p.y = this->y - rhs.y;
		return p;
	}
	Point<T> operator*(const T rhs) const {
		Point<T> p(*this);
		p.x = this->x * rhs;
		p.y = this->y * rhs;
		return p;
	}
};

template<typename T>
bool isZero(const T val)
{
	return fabs(val) < 1e-10;
}

template<typename T>
T innerProduct(const Point<T>& p0, const Point<T>& p1)
{
	double x0 = p0.x;
	double y0 = p0.y;
	double x1 = p1.x;
	double y1 = p1.y;
	return x0 * x1 + y0 * y1;
}

template<typename T>
T outerProduct(const Point<T>& p0, const Point<T>& p1)
{
	double x0 = p0.x;
	double y0 = p0.y;
	double x1 = p1.x;
	double y1 = p1.y;
	return x0 * y1 - y0 * x1;
}

template<typename T>
T norm(const Point<T>& p)
{
	double x = p.x;
	double y = p.y;
	return x*x + y*y;
}

template<typename T>
void readPoint(Point<T>& p)
{
	cin >> p.x;
	cin >> p.y;
}

template<typename T>
void outputComponentesOfPoint(const Point<T>& p)
{
	cout << fixed;
	cout << setprecision(8) << p.x;
	cout << " ";
	cout << setprecision(8) << p.y;
	cout << endl;
}

int main()
{

	Point<NUM> p1,p2;
	readPoint(p1);
	readPoint(p2);
	const Point<NUM> b = p2 - p1;
	const NUM b_b_ = norm(b);

	int q; cin >> q;
	for (int i = 0; i != q; ++i) {
		Point<NUM> p;
		readPoint(p);
		const Point<NUM> a = p - p1;
		const NUM ab = innerProduct(a, b);
		const Point<NUM> projectedPoint = p1 + b*(ab / b_b_);
		outputComponentesOfPoint(projectedPoint);
	};

	return 0;
}


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

int main() {
  ll n,k;
  cin >> n >>k;
  vector<ll>a(n);
  vector<ll>f(n);
  rep(i,n) cin >> a.at(i);
  rep(i,n) cin >> f.at(i);
  sort(a.begin(),a.end());
  sort(f.begin(),f.end(),greater<ll>());
  
  ll l=-1,r=1e12;
  while(l+1<r){
  	ll c=(l+r)/2;
  	ll sum=0;
  	rep(i,n) sum+=max((ll)0,a.at(i)-c/f.at(i));
  	if(sum<=k) r=c;
  	else l=c;
  }
  cout << r <<endl;
}


Measured memory_bytes: 3328
# -*- coding: utf-8 -*-
N = int(input())
S = input()

count = 0
for i in range(10):
  n1 = S.find(str(i))
  if not(n1 == -1 or n1 >= N-2):
    S2 = S[n1+1:]
    for j in range(10):
      n2 = S2.find(str(j))
      if not(n2 == -1 or n2 >= N-1):
        S3 = S2[n2+1:]
        for k in range(10):
          n3 = S3.find(str(k))
          if(n3 != -1):
            count += 1

print(count)


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

using namespace std;

vector<vector<int>> g;
vector<int> a;
vector<int> ans;
multiset<int> s;

void dfs(int x, int p = -1){
	s.insert(a[x]);
	auto it = s.lower_bound(a[x]);
	auto del = -1;
	if(++it != s.end()){
		del = *it;
		s.erase(it);
	}
	ans[x] = s.size();
	for(int y : g[x]){
		if(y != p)
			dfs(y, x);
	}
	if(del != -1)
		s.insert(del);
	s.erase(s.find(a[x]));
}

int main(void){
	int n;
	cin >> n;
	a.resize(n + 1);
	ans.resize(n + 1);
	g.resize(n + 1);
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	for(int i = 1 ; i < n ; i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1);
	for(int i = 1 ; i <= n ; i++){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 30060
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;


int main(){
    int n;
    cin>>n;
    string ans="";
    //cout<<n%10<<endl;
    if(n%10==2||n%10==4||n%10==5||n%10==7||n%10==9){
        ans="hon";
    }else if(n%10==0||n%10==1||n%10==6||n%10==8){
        ans="pon";
    }else{
        ans="bon";
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3596
#include <iostream>

using namespace std;
typedef long long ll;

ll k;
ll t[100005];

const ll MI = 2;
const ll MX = 1000000000000000000;

bool oklo(ll x) {
	for (int i = 0; i < k; ++i) {
		x -= x%t[i];
		if (x < 2) return false;
	}
	return (x >= 2);
}

bool okhi(ll x) {
	for (int i = 0; i < k; ++i) {
		x -= x%t[i];
		if (x < 2) return false;
	}
	return (x <= 2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> k;
	for (int i = 0; i < k; ++i) {
		cin >> t[i];
	}
	ll lo = MI-1;
	for (ll a = (1LL<<62); a >= 1; a /= 2) {
		if (lo+a <= MX && !oklo(lo+a)) lo += a;
	}
	if (!oklo(lo+1)) {
		cout << "-1\n";
		return 0;
	}
	ll hi = lo+1;
	for (ll a = (1LL<<62); a >= 1; a /= 2) {
		if (hi+a <= MX && okhi(hi+a)) hi += a;
	}
	if (oklo(lo+1) && okhi(hi)) {
		cout << lo+1 << " " << hi << "\n";
	}
	else {
		cout << "-1\n";
	}
	return 0;
}

Measured memory_bytes: 1024
package main

import (
	"fmt"
)

func main() {
	var a, b int

	fmt.Scan(&a, &b)

	ans := 0
	n := 2

	for i := 0; i < n; i++ {
		if a > b {
			ans += a
			a--
		} else {
			ans += b
			b--
		}
	}

	fmt.Print(ans)

}


Measured memory_bytes: 1768
import itertools

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  graph[a].append(b); graph[b].append(a)

path = list(itertools.permutations(range(1, N), N-1))
ans = 0
for p in path:
  now = 0
  res = True
  for child in p:
    if child not in graph[now]:
      res = False
      break
    now = child
  ans += res

print(ans)

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

ll N,mo;
ll ways2[3030][3030],ways[3030];
static const int N_=3020;
static ll C_[N_][N_];
ll p2[3030][3030];
ll p22[3030];

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


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	
	FOR(i,N_) C_[i][0]=C_[i][i]=1;
	for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	
	FOR(x,3020) p2[0][x]=p2[x][0]=1;
	FOR(x,3020) {
		p2[x+1][1]=p2[x][1]*2%mo;
		for(y=2;y<=3020;y++) p2[x][y]=p2[x][y-1]*p2[x][1]%mo;
	}
	
	ways2[0][1]=1;
	
	ll ret=modpow(2,modpow(2,N,mo-1));
	for(i=1;i<=N;i++) {
		ll hoge=modpow(2,modpow(2,N-i,mo-1));
		for(j=1;j<=i+1;j++) {
			(ways2[i][j]=ways2[i-1][j-1]+ways2[i-1][j]*j)%=mo;
			(ways[i]+=ways2[i][j]*p2[N-i][j-1]%mo*hoge)%=mo;
		}
		if(i%2) ret-=C_[N][i]*ways[i]%mo;
		else ret+=C_[N][i]*ways[i]%mo;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 215040
# coding:utf-8
import fractions


def main():
    N = int(input())
    num = list(map(int, input().split()))

    gcd_max = 0
    gcd_list_front = []
    gcd_list_back = []

    gcd_list_front.append(num[0])
    gcd_list_back.append(num[-1])

    for i in range(1, N-1):
        gcd_list_front.append(fractions.gcd(gcd_list_front[i-1], num[i]))
        gcd_list_back.append(fractions.gcd(gcd_list_back[i-1], num[-i-1]))

    gcd_list_back.reverse()
    gcd_max = max(gcd_list_back.pop(0), gcd_list_front.pop(-1))

    for i in range(len(gcd_list_front)):
        temp_gcd = fractions.gcd(gcd_list_front[i], gcd_list_back[i])
        if temp_gcd > gcd_max:
            gcd_max = temp_gcd

    print(gcd_max)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 16120
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll ac(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int dp[3002][3002];
int main()
{
	int n, t, A, B;
	cin >> n >> t;
	vector<int> a(n), b(n);
	vector<pair<int, int>> data(n);
	rep(i, 0, n)cin >> A >> B, data[i] = {A, B};
	sort(all(data));
	rep(i, 0, n)a[i] = data[i].first, b[i] = data[i].second;
	vector<int> kouho;
	int M = 0;
	rep(i, 0, t) {
		rep(i2, 0, n) {
			if (i + a[i2] < t)dp[i2 + 1][i + a[i2]] = max(dp[i2][i] + b[i2], dp[i2 + 1][i + a[i2]]);
			else {
				M = max(max(dp[i2][i] + b[i2], dp[i2 + 1][i + a[i2]]), M);
			}
			dp[i2 + 1][i] = max(dp[i2][i], dp[i2 + 1][i]);
		}
	}
	printf("%d\n", M);
	return 0;
}

Measured memory_bytes: 38948
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    a,b = map(int, input().split())
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    print(lcm(a,b))


if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        for (int i=1;i<n+1;i++){
            if (Integer.toString(i).length()%2==1){
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 28240
#include <iostream>

using namespace std;

struct List{
	int id, cnt;
	List *nxt;
};

void _delete(List *p){
	if (p == nullptr) return;
	_delete(p->nxt);
	delete p;
}

void erase(List *p, int id){
	if (p == nullptr) return;
	if (p->id == id) p->id = -1;
	erase(p->nxt, id);
}

int find(List *p, int pos){
	if (p == nullptr) return -1;
	if (p->cnt > pos) return p->id;
	return find(p->nxt, pos - p->cnt);
}

List* add(List *p, int id, int cnt){
	if (!cnt) return p;
	if (p == nullptr)return new List{id, cnt, nullptr};
	if (p->id < 0){
		p->id = id;
		if (p->cnt > cnt){
			List *nl = new List{ -1, p->cnt - cnt, p->nxt };
			p->cnt = cnt;
			p->nxt = nl;
			return p;
		}
		cnt -= p->cnt;
	}
	p->nxt = add(p->nxt, id, cnt);
	return p;
}

int main(){
	List *head = new List();
	int n;
	while (cin >> n, n){
		while (n--){
			char c;
			cin >> c;
			if (c == 'W'){
				int id, cnt;
				cin >> id >> cnt;
				head->nxt = add(head->nxt, id, cnt);
			}
			else if (c == 'D'){
				int id;
				cin >> id;
				erase(head->nxt, id);
			}
			else if (c == 'R'){
				int pos;
				cin >> pos;
				cout << find(head->nxt, pos) << '\n';
			}
		}
		cout << '\n';
		_delete(head->nxt);
		head->nxt = nullptr;
	}

	return 0;
}

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

int main(void) {
	int count = 0;
	int maxCount = 0;
	bool rainFlag = false;
	string s;
	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R') {
			count++;
			rainFlag = true;
		}
		else {
			count = 0;
			rainFlag = false;
		}
		maxCount = max(maxCount, count);
	}

	cout << maxCount << endl;

	return 0;
}


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

int main(){
	
	int t , n ;
	int k[5] = { 0,6000,4000,3000,2000 } ;
	
	for( int i=0 ; i<4 ; i++ ){
		cin >> t >> n ;
		cout << k[t] * n << endl ;
	}
	
return 0; 
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#define sz(a) int((a).size()) 
#define pb push_back 
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define F(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define VE(i,v) for(int i = 0;i < (v).size();i++)

using namespace std;
#define trace(...) cerr<<__FUNCTION__<<":"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
	cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
	const char *comma=strchr(names+1,',');
	cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef unsigned int ui;
typedef vector<ll> vl; 
typedef vector<vl> vvl; 
typedef pair<ll,ll> pll;
typedef vector<pll> vpll; 
 
vector<int> id;
vector<int> od;
vi adj[100001];

int dfs(int u, int d)
{
	
	if(od[u]!=0)
		return od[u];
	trace(u, id[u], od[u]);
	int tod = 0;
	for(auto v: adj[u])
	{
		if(id[v]<(d+1))
			id[v] = d+1;
		tod = max(tod, dfs(v, id[v]));
	}
	if(sz(adj[u])==0)
		od[u] = 0;
	else
		od[u] = tod+1;
	//trace(u, id[u], od[u]);
	return od[u];
}


int main()

{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	T=1;

	for(int tc=1; tc<=T;tc++)
	{
		int H,W;
		cin >> H>>W; 
		vector<string> arr(H);
		for(int i =0; i < H;i++)
			cin >> arr[i];
		vector<vector<ll> > dp(H, vector<ll>(W,0));
		dp[0][0] = 1LL;
		for(int i = 1; i < W; i++)
			if((arr[0][i]=='.')&&(dp[0][i-1]!=0))
				dp[0][i] = 1LL;
		for(int i = 1; i < H; i++)
			if((arr[i][0]=='.')&&(dp[i-1][0]!=0))
				dp[i][0] = 1LL;
		for(int i=1; i < H; i++)
		{
			for(int j =1; j < W; j++)
			{
				if(arr[i][j]=='.')
				{
					if(dp[i-1][j]!=0)
						dp[i][j] = (dp[i-1][j] + dp[i][j])%MOD;
					if(dp[i][j-1]!=0)
						dp[i][j] = (dp[i][j] + dp[i][j-1])%MOD;
				}
			}
		}
		


			
		
		cout<<dp[H-1][W-1]<<"\n";
	}
 
 
 
	return 0;
}
 
 



Measured memory_bytes: 11520
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
#define inf 10000000000000000
#define N 998244353
#define speed ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.x<<','<< P.y<<')';}
template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}


int f[3001][3001];
//edge cases when n=1 , m=1. wrong variable in loop. if<->while
signed main()
{
	speed
	//global var
	for(int i=0;i<3001;++i){f[0][i]=0;}
	
	int n,s;cin>>n>>s;

	vector<int> inp(n);
	for(int i=0;i<n;++i)
	{
		cin>>inp[i];
	}
	vector<int> prefix(s+1,0);
	if(s>=inp[0]){f[0][inp[0]]=1;prefix[inp[0]]=1;}
	
	
	int ans=0;
	for(int ix=1;ix<n;++ix)
	{
		for(int sum=s;sum>inp[ix];--sum)
		{
			f[ix][sum]=prefix[sum-inp[ix]];f[ix][sum]%=N;
			prefix[sum]+=f[ix][sum];prefix[sum]%=N;
		}
		if(s>=inp[ix]){f[ix][inp[ix]]=ix+1;prefix[inp[ix]]+=(ix+1);prefix[inp[ix]]%=N;}
		ans+=(f[ix][s]*(n-ix));
		ans%=N;
	}
	cout<<ans<<"\n";

}

Measured memory_bytes: 70528
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;

ll natural(ll a, ll b){
    if(a-b>0){
        return a-b;
    }else{
        return 0;
    }
}

int main(){
    ld n,a,b,c,d,e;
    cin>>n>>a>>b>>c>>d>>e;
    vector<ld> nums={a,b,c,d,e};
    ld min=MIN(nums);
    ll time=ceil(n/min)+4;
    cout<<time;
    return 0;
}


Measured memory_bytes: 3672
#include <cstdio>
using namespace std;
int main(void){
    int n;
    long maxv, buy, sell;
    
    scanf("%d", &n);
    scanf("%ld", &buy);
    for (int i = 1; i < n; i++){
        scanf("%ld", &sell);
        if (maxv < sell - buy || i == 1) maxv = sell - buy;
        if (buy > sell) buy = sell;
    }
    printf("%d\n", maxv);
    return 0;
}

Measured memory_bytes: 2736
def main():
  n = int(input())
  data_ = list(map(int, input().split()))

  # can not divide 2       : 1
  # divide 2 by once       : 2
  # divide 2 by over twice : 4
  data = []
  for d in data_:
    if d % 2 == 1:
      data.append(1)
    else:
      tmp = int(d / 2)
      if tmp % 2 == 1:
        data.append(2)
      else:
        data.append(4)

  # 2が存在しないとき
  if data.count(2) == 0:
    if data.count(1) <= data.count(4) + 1:
      print("Yes")
      return
    else:
      print("No")
      return

  if data.count(1) <= data.count(4):
    print("Yes")
  else:
    print("No")

if __name__ == "__main__":
  main()

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

struct Sq
{
	unsigned long xmax;
	unsigned long li;
};

int main()
{
	string st;
	long a = 0, hmax = 0;
	vector<long> h = { 0 };
	vector<Sq> S = { Sq{0, 0} };

	cin >> st;

	for (unsigned long i = 0; i < st.size(); i++) {

		switch (st[i]) {
			case '/':
				if (h[i] == hmax)
					hmax++;
				else {
					for (unsigned long j = 0; j < h.size(); j++) {
						if (h[h.size() - j - 1] == h[i] + 1) {
							if (S.back().xmax !=0 && (S.back().xmax < h.size() - j))
								S.push_back(Sq{ h.size() - 1 , j});
							else if (S.size() > 1 && (S[S.size() - 2].xmax > h.size() - j)) {
								S.back().li += j;
								while (S.size() > 1 && (S[S.size() - 2].xmax > h.size() - j)) {
									S[S.size() - 2].li += S.back().li;
									S.pop_back();
								}
							}
							else{
								S.back().li += j;
								S.back().xmax = h.size() - 1;
							}
							break;
						}
					}
				}
				h.push_back(h[i] + 1);
				break;
			case '\\':
				h.push_back(h[i] - 1);
				break;
			case '_':
				h.push_back(h[i]);
				break;
		}
	}

	for (unsigned long i = 0; i < S.size(); i++)
		a += S[i].li;

	cout << a << endl;

	if (a > 0) {
		cout << S.size();
		for (unsigned long i = 0; i < S.size(); i++)
			cout << " " << S[i].li;
	}
	else
		cout << "0";

	cout << endl;

	return 0;
}

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

int main() {
  int X ; 
  cin >> X ; 
  int ans = 0 ; 
  
  for(int i = 1 ; i <= X ;i++){
    for(int j = 2 ; j <= 100 ; j++){
      int P = pow(i , j) ; 
      if(P <= X){
        ans = max(P , ans) ; 
      }
    }
  }
  cout << ans << endl ; 
}

Measured memory_bytes: 4224
#include <algorithm>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

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

LL lcm(LL a, LL b) {
  if ((a == 0) || (b == 0)) return 0;
  return ((a / gcd(a, b)) * b);
}

int main() {
  LL A, B; std::cin >> A >> B;
  std::cout << lcm(A, B) << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define mod 1000000007
#define int long long
#define ll long long
#define EPS 0.00000000000001
#define ld long double
#define inf 1e6
#define N 51

int n;
double x[1005], y[1005], X, Y, d, e;
double dist(double a, double b) {
    return a*a + b*b;
}
//copied from https://ideone.com/vju6Uh
int32_t main()
{
    IOS;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &x[i], &y[i]);
        X += x[i]; Y += y[i];
    }
    X /= n; Y /= n;
    double P = 0.1;
    for (int i = 0; i < 30000; i++) {
        int f = 0;
        d = dist(X - x[0], Y - y[0]);
        for (int j = 1; j < n; j++) {
            e = dist(X - x[j], Y - y[j]);
            if (d < e) { d = e; f = j; }
        }
        X += (x[f] - X)*P;
        Y += (y[f] - Y)*P;
        P *= 0.999;
    }
    printf("%.7lf",sqrt(d));


    return 0;

}
 


Measured memory_bytes: 256
IDENTIFICATION                   DIVISION.
PROGRAM-ID.                      ABC_065_A.
ENVIRONMENT                      DIVISION.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 INP    PIC X(32).
    01 X      PIC 9(10).
    01 A      PIC 9(10).
    01 B      PIC S9(10).
PROCEDURE                        DIVISION.
MAIN.
    ACCEPT INP.

    UNSTRING INP
    DELIMITED BY SPACE
    INTO X A B.

    SUBTRACT A FROM B.

    IF B <= 0 THEN
        DISPLAY "delicious"
    ELSE
        IF B <= X THEN
            DISPLAY "safe"
        ELSE
            DISPLAY "dangerous"
        END-IF
    END-IF.

    STOP RUN.


Measured memory_bytes: 384
#include<stdio.h>
int main(void){
	int a,b;
	char op;
	while(1){
		scanf("%d %c %d",&a,&op,&b);
		if(op=='?'){
			break;
		}
		if(op=='+'){
			printf("%d\n",a+b);
		}else if(op=='-'){
			printf("%d\n",a-b);
		}else if(op=='*'){
			printf("%d\n",a*b);
		}else if(op=='/'){
			printf("%d\n",a/b);
		}
	}
	return 0;
}

Measured memory_bytes: 600