akhauriyash/Code-Regression huggingface dataset:
// Problem : A - αlphabet
// Contest : AtCoder - AtCoder Beginner Contest 171
// URL : https://atcoder.jp/contests/abc171/tasks/abc171_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

char s;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
	cin>>s;
	 if(s>='A' && s<='Z'){
	 	cout<<'A';
	 }
	 else{
	 	cout<<'a';
	 }



    return 0;
}


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


void solve(long long r){
    cout<<r*r<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::cout<<std::fixed<<std::setprecision(10);//誤差小数10桁まで
    long long r;
    scanf("%lld",&r);
    solve(r);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
const LL INF = 1e14;
const LL MOD = 1e9 + 7;

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;}

VVLL ct(100005, VLL(2, -1));
VI par(100005, -1);

LL dfs(auto &T, auto now, auto black)
{
  if (ct[now][black] != -1) return ct[now][black];
  if (now != 0 && T[now].size() == 1) return ct[now][black] = 1;
  LL res = 1;
  if (black)
  {
   REPx(x, T[now])
   {
     if (par[x] == -1) par[x] = now;
     if (x == par[now]) continue;
     res *= dfs(T, x, 0);
     res %= MOD;
   }
  }
  else
  {
   REPx(x, T[now])
   {
     if (par[x] == -1) par[x] = now;
     if (x == par[now]) continue;
     LL tmp = 0;
     tmp += dfs(T, x, 0);
     tmp %= MOD;
     tmp += dfs(T, x, 1);
     tmp %= MOD;
     res *= tmp;
     res %= MOD;
   }
  }
  return ct[now][black] = res;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  VVI T (n, VI());
  REP(i, n-1)
  {
   int x, y;
   cin >> x >> y;
   x--; y--;
   T[x].emplace_back(y);
   T[y].emplace_back(x);
  }
  par[0] = 0;
  cout << (dfs(T, 0, 0) + dfs(T, 0, 1)) % MOD << endl;

  return 0;
}

Measured memory_bytes: 19968
#include <iostream>

using namespace std;

int main(void)
{
    int N, W;
    cin >> N >> W;

    unsigned long dp[1000 * N + 1];
    for (int i = 0; i <= 1000 * N; i++) {
        dp[i] = 1000000000 + 1;
    }
    dp[0] = 0;

    for (int i = 1; i <= N; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int j = 1000 * N; j >= value; j--) {
            dp[j] = min(dp[j], dp[j - value] + weight);
        }
    }

    for (int j = 1000 * N;;j--) {
        if (dp[j] <= W) {
            cout << j << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

using ll = long long;
template <ll MOD = 1000000007>
struct Mint{
    ll x;

    Mint() : x(0) {}
    Mint(ll t){
        x = t % MOD;
        if(x < 0) x += MOD;
    }
    
    Mint pow(ll n){
        Mint res(1), t(x);
        while(n > 0){
            if(n & 1) res *= t;
            t *= t;
            n >>= 1;
        }
        return res;
    }

    Mint inv() const {
        ll a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Mint(u);
    }

    Mint & operator += (Mint a){
        x += a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    Mint & operator -= (Mint a){
        x += MOD - a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    Mint & operator *= (Mint a){
        x = 1LL * x * a.x % MOD;
        return *this;
    }
    Mint & operator /= (Mint a){
        return (*this) *= a.inv();
    }

    Mint operator + (Mint a) const { return Mint(x) += a; }
    Mint operator - (Mint a) const { return Mint(x) -= a; }
    Mint operator * (Mint a) const { return Mint(x) *= a; }
    Mint operator / (Mint a) const { return Mint(x) /= a; }

    Mint operator - () const{ return Mint(-x); }

    bool operator == (const Mint a){ return x == a.x; }
    bool operator != (const Mint a){ return x != a.x; }
    bool operator < (const Mint a){ return x < a.x; }

    friend ostream & operator << (ostream & os, const Mint &a){
        return os << a.x;
    }

    friend istream & operator >> (istream & is, Mint &a){
        ll t;
        is >> t;
        a = Mint<MOD>(t);
        return (is);
    }
};

signed main(){
    int n,k;
    cin >> n >> k;
    int a[n];
    REP(i,n){
        cin >> a[i];
    }
    Mint<> dp[n + 1][k + 1];
    dp[0][0] = 1;
    for(int i = 0; i < n; i++){
        Mint<> sum[k + 2];
        for(int j = 0; j <= k; j++){
            sum[j + 1] = sum[j] + dp[i][j];
        }
        for(int j = 0; j <= k; j++){
            dp[i + 1][j] += sum[j + 1] - sum[max(0, j - a[i])];
            /*
            for(int l = 0; l <= a[i]; l++){
                if(j - l < 0) continue;
                dp[i + 1][j] += dp[i][j - l];
            }
            */
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

Measured memory_bytes: 79872
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return

#B
def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()


Measured memory_bytes: 38640
/*---------------Go Code GO---------------*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using Order_Set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
//(order) Set.order_of_key(); (pointer) Set.find_by_order();

#define     PI              acos(-1.0)
#define     O_O             ios_base::sync_with_stdio(false); cin.tie(NULL)
#define     precision(a)    fixed<<setprecision(a)
#define     endl            '\n'
#define     Flush           cout<<flush
#define     LLMX            0x3fffffffffffffff




int main()
{
    long long N,M, ans =0;
    cin>>N>>M;
    while(M--)
    {
        int k;
        cin>>k;
        ans+=k;
    }
    ans = (N-ans<0)? -1:N-ans;

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long n, a, b, ans;
    cin >> n >> a >> b;
    long tmp = n / (a + b);
    ans = tmp * a;
    if (n % (a + b) != 0)
    {
        if (n % (a + b) <= a)
            ans += n % (a + b);
        else
        {
            ans += a;
        }
    }
    cout << ans << endl;
}

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

using namespace std;
 
#define MD 1000000007
typedef long long int ll;

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

Measured memory_bytes: 256
N, X = map(int, input().split(" "))
L = list(map(int, input().split(" ")))

ans = 1
cur_X = 0
pos_N = 0

for i in range(N):
    ans += 1
    cur_X += L[i]

    if cur_X > X:
        ans -= 1
        break

print(ans)

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> graph(N);
    rep(i,0,N-1){
        int a,b;
        cin >> a >> b;
        --a;
        --b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> par(N,-1),con(N,-1);
    function<bool(int,int)> dfs=[&](int u,int p){
        par[u]=p;
        for(auto v:graph[u]){
            if(v==p) continue;
            if(dfs(v,u)) con[u]=v;
        }
        return u==N-1 or con[u]!=-1;
    };
    dfs(0,-1);

    int turn=0,f=0,s=N-1;
    vector<int> col(N,-1);
    col[0]=0;
    col[N-1]=1;
    for(;;){
        if(turn%2==0){
            int nf=con[f];
            if(col[nf]>=0) break;
            col[nf]=0;
            f=nf;
        }else{
            int ns=par[s];
            if(col[ns]>=0) break;
            col[ns]=1;
            s=ns;
        }
        ++turn;
    }

    int x=1,y=1;
    vector<bool> done(N);
    queue<int> que;
    que.push(0);
    done[0]=done[N-1]=true;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(auto v:graph[u]){
            if(col[v]==1 or done[v]) continue;
            done[v]=true;
            ++x;
            que.push(v);
        }
    }

    que.push(N-1);
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(auto v:graph[u]){
            if(col[v]==0 or done[v]) continue;
            done[v]=true;
            ++y;
            que.push(v);
        }
    }

    print(x);
    print(y);

    if(x>y) cout << "Fennec" << endl;
    else cout << "Snuke" << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 16256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, p, w, g, y;
    cin >> n;
    for (int i=0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'P') p++;
        else if (c == 'W') w++;
        else if (c == 'G') g++;
        else if (c == 'Y') y++;
    }
    if (p == 0 || w == 0 || g == 0 || y == 0) cout << "Three" << endl;
    else cout << "Four" << endl;
}

Measured memory_bytes: 256
using Microsoft.VisualBasic.CompilerServices;
using System;
using System.Linq;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int MOD = 1000000007;
            int n = int.Parse(Console.ReadLine());
            long[] A = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long[] W = new long[n + 1];
            for(int i = 0; i < n; i++)
            {
                W[i + 1] = W[i] + A[i];
            }
            long sum = 0;
            for(int i = 0; i < n-1; i++)
            {
                long s = (W[n] - W[i+1]) % MOD;
                long t = A[i] * s;
                sum += t;
                sum %= MOD;
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 49012
def main():
  N = int(input())
  A = [int(i) for i in input().split()]
  A.sort()
  res = 1
  for i in range(N):
    res = res * A[i]
    if res == 0:
      print(res)
      return
    elif res > 10 ** 18:
      print(-1)
      return
  if res > 10 ** 18:
    print(-1)
  else:
    print(res)

if __name__ == "__main__":
  main()

Measured memory_bytes: 21700
#include<stdio.h>
int main()
{
	int n,m,i,c,d,j;
	char a[1000],b[1000][1000];
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%s",b[i]);
	for(i=1;i<=m+2;i++)
	printf("#");
	printf("\n");
	for(i=1;i<=n;i++)
	{
		printf("#");
		printf("%s",b[i]);
		printf("#\n");
    }
    for(i=1;i<=m+2;i++)
	printf("#");
	return 0;
 } 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);

int n, m;
int a[MAXN];

void read()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
		cin >> a[i];
}

void solve()
{
	vector<int> odd, even;
	for(int i = 0; i < m; i++)
		if(a[i] % 2 == 0) even.push_back(a[i]);
		else odd.push_back(a[i]);

	if(odd.size() > 2)
	{
		cout << "Impossible" << endl;
		return;
	}

	if(m == 1 && a[0] == 1)
	{
		cout << 1 << endl;
		cout << 1 << endl;
		cout << 1 << endl;
		return;
	}

	if(m == 1)
	{
		cout << a[0] << endl;
		cout << 2 << endl;
		cout << a[0] - 1 << " " << 1 << endl;
		return;
	}

	while(odd.size() < 2)
	{
		odd.push_back(even.back());
		even.pop_back();
	}

	vector<int> li1, li2;
	if(!odd.empty()) 
	{
		li1.push_back(odd.back());
		if(odd.back() != 1) li2.push_back(odd.back() - 1);
		odd.pop_back();
	}

	for(int x: even)
	{
		li1.push_back(x);
		li2.push_back(x);
	}
	
	if(!odd.empty()) 
	{
		li1.push_back(odd.back());
		li2.push_back(odd.back() + 1);
		odd.pop_back();
	}

	for(int x: li1) cout << x << " "; 
	cout << endl;
	cout << li2.size() << endl;
	for(int x: li2) cout << x << " "; 
	cout << endl;	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}



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

int main(){
  int N,A,B; cin>>N>>A>>B;
  cout<<min(A,B)<<" "<<max(0,A+B-N)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
using namespace std;

const int MAXN = 1000000;
int N;
string s;
int dp[MAXN][2];

int main()
{
    cin >> s;
    N = s.length();
    fill(&dp[0][0], &dp[MAXN - 1][2], (int)1e9);
    dp[N - 1][0] = s[N - 1] - '0', dp[N - 1][1] = 10 - (s[N - 1] - '0');
    for (int i = N - 2; i >= 0; i--)
    {
        int digit = s[i] - '0';
        dp[i][0] = min(dp[i + 1][0] + digit, dp[i + 1][1] + digit + 1);
        dp[i][1] = min(dp[i + 1][0] + 10 - (digit), dp[i + 1][1] + 10 - (digit + 1));
    }
    cout << min(dp[0][0], dp[0][1] + 1) << endl;
    // system("pause");
}

Measured memory_bytes: 9204
import java.util.*;

public class Main{
    public static void main(String[] args) /*throws Exception*/{
    Scanner x = new Scanner(System.in);
    int n = x.nextInt();
    int[] arr =new int[n];
    for(int i = 0;i < n;i++){
	arr[i] = x.nextInt();
    }
    Arrays.sort(arr);
    System.out.println(arr[n-1] - arr[0]);
}
}


Measured memory_bytes: 23636
/*
    B - Christmas Eve Eve
    https://atcoder.jp/contests/abc115/tasks/abc115_b
*/
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> price(n);

    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }

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

    int sum = 0;
    for (size_t i = 0; i < price.size() - 1; i++) {
        sum += price[i];
    }
    sum += price.back() / 2;
    cout << sum << endl;
}

Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let d: usize = iter.next().unwrap().parse().unwrap();

    println!("{}", (n - 1) / (2 * d + 1) + 1);
}


Measured memory_bytes: 4352
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
class Program
{

    static long[] memo = Enumerable.Repeat(-1L, 50).ToArray();

    static void Main(string[] args)
    {
        long n = long.Parse(Console.ReadLine());

        Console.WriteLine(fib(n));
        
    }




    static long fib(long n)
    {
        if (memo[n] > -1) return memo[n];

        long rtn = 0;
        if (n <= 1)
        {
            rtn = 1;
        }
        else
        {
            memo[n] = rtn = fib(n - 1) + fib(n - 2);
        }
        return rtn;
    }
}



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

using namespace std;

#define D(x) x
#define REP(i,a,b) for (int i = (a); i < (b); ++i)
#define REPR(i,a,b) for (int i = (b) - 1; i >= (a); --i)
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<vector<int> > VII;

void solve() {
    ll a, b, c;
    cin >> a >> b >> c;
    cout << b +   min(c, a + b + 1) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << setprecision(12) << fixed;

    solve();

	return 0;
}


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

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

    vector<bool> a(26);
    
    for(int i = 0; i < 26; i++){
        a[i] = false;
    }
    
    for(int i = 0; s[i] != 0; i++){
        a[s[i] - 'a'] = true;
    }
    
    int flag = 0;
    for(int i = 0; i < 26; i++){
        if(!a[i]){
            flag = 1;
            char c = i + 'a';
            cout << c;
            break;
        }
    }
    if(!flag) cout << "None";
}

Measured memory_bytes: 512
import java.util.*;

public class Main{

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

		int a = sc.nextInt();
		int b = sc.nextInt();

		if((a % 2 != 0) & (b % 2 != 0)){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.12f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX_N = 1010101;

//組み合わせの余りを求める
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX_N; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

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

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll dx[8] = { 1,-1,0,0,1,1,-1,-1 };
ll dy[8] = { 0,0,1,-1,1,-1,1,-1 };
ll d[110][2];

//long longしか使わない
//素数は1より大きい
//lower_boundは指定したkey以上の要素の一番左のイテレータをかえす
//upper_boundは指定したkeyより大きい要素の一番左のイテレータをかえす
int main() {
	ll k, s;
	ll ans = 0;
	cin >> k >> s;
	rep(i, k + 1) {
		rep(j, k + 1) {
			ll res = i + j;
			if (s - k <= res && res <= s)ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3636
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const long long MAXN=100005,INF=1e9;
long long n,d[MAXN],jl[MAXN];
struct edge
{
	long long v,c;
	edge(){}
	edge(long long vv,long long cc)
	{
		v=vv,c=cc;
	}
};
vector<edge>w[MAXN];
long long ans=0;
void dfs(long long u,long long f)
{
	d[u]=1;
	for(long long i=0;i<int(w[u].size());i++)
	{
		long long v=w[u][i].v;
		long long c=w[u][i].c;
		if(v!=f)
		{
			dfs(v,u);
			ans+=2*d[v]*c;
			d[u]+=d[v];
			jl[u]=max(jl[u],d[v]);
		}
	}
	jl[u]=max(jl[u],n-d[u]);
}
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<n;i++)
	{
		long long u,v,c;
		scanf("%lld %lld %lld",&u,&v,&c);
		w[u].push_back(edge(v,c));
		w[v].push_back(edge(u,c));
	}
	dfs(1,0);
	long long Y=jl[1]<jl[2]?1:2,C=Y^3;
	for(long long i=1;i<=n;i++)
	{
		if(jl[Y]>=jl[i])
		{
			C=Y;
			Y=i;
		}
		else if(jl[C]>jl[i])
		{
			C=i;
		}
	}
	ans=0;
	dfs(Y,0);
	long long Mi=INF;
	for(long long i=0;i<int(w[Y].size());i++)
	{
		long long v=w[Y][i].v;
		long long c=w[Y][i].c;
		if(v==C&&jl[C]==jl[Y])
		{
			Mi=c;
			break;
		}
		else
		{
			Mi=min(Mi,c);
		}
	}
	printf("%lld\n",ans-Mi);
}

Measured memory_bytes: 16128
//kruskal tree
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
#define M 9999
int parent[M],a[M],b[M];
pair<double,int>node[M];
int root(int a){return parent[a]==a?a:parent[a]=root(parent[a]);}
int unite(int a,int b){
	int x=root(a),y=root(b);
	if(x==y)return 0;
	parent[x]=y;
	return 1;
}
int main(){
	int i,j,k,m,n,q;
	double x,y,z,r,t;
	for(;scanf("%d",&n),n;){
		vector<vector<double> >v(n);
		for(q=m=i=0;i<n;i++){
			scanf("%lf%lf%lf%lf",&x,&y,&z,&r),v[i]={x,y,z,r},parent[i]=i;
			for(j=0;j<i;j++){
				for(x=k=0;k<3;k++)x+=(t=v[i][k]-v[j][k])*t;
				x=sqrt(x)-v[i][3]-v[j][3];
				if(x<=0){if(unite(i,j))q++;}
				else a[m]=i,b[m]=j,node[m].first=x,node[m++].second=m;
			}
		}
		sort(node,node+m);
		for(x=i=0;i<m&&q<n-1;i++)if(unite(a[node[i].second],b[node[i].second]))x+=node[i].first,q++;
		printf("%.3f\n",x);
	}
}

Measured memory_bytes: 1300
#!/usr/bin/env python3
#ABC68 C

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

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 6132
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextLong()
    val v = sc.nextLong()
    val b = sc.nextLong()
    val w = sc.nextLong()
    val t = sc.nextLong()
    println(problem2020b(a, v, b, w, t))
}

fun problem2020b(A: Long, V: Long, B: Long, W: Long, t: Long): String {
    var a = A
    var b = B
    var v = V
    var w = W
    if (a < 0 && b >= 0) {
        b = b + Math.abs(a)
        a = 0
    } else if (b < 0 && a >= 0) {
        a = a + Math.abs(b)
        b = 0
    } else if (a < 0 && b < 0) {
        a += Math.pow(10.0, 9.0).toLong()
        b += Math.pow(10.0, 9.0).toLong()
    }
    if (a < b) {
        if (v - w <= 0) {
            return "NO"
        }
        val speed = v - w
        val diff = b - a
        return if (speed * t >= diff) "YES" else "NO"
    } else {
        if (v - w <= 0) return "NO"
        val speed = v - w
        val diff = a - b
        return if (speed * t >= diff)  "YES" else "NO"
    }
}

Measured memory_bytes: 36388
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int A, B, C, D;
    cin >>A >>B >>C >>D;
    if(A+B > C+D)
        cout << "Left\n";
    else if(A+B == C+D)
        cout << "Balanced\n";
    else 
        cout <<"Right\n";

        return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

typedef long long ll;

const int MAX_H=300,MAX_W=300,INF=1e8;

int H,W;
char C[MAX_H][MAX_W+1];
int dp[MAX_H+1][MAX_H+1];
int cost[MAX_H+1][MAX_H+1];

int main(){
	scanf("%d %d",&H,&W);
	REP(i,H){
		scanf("%s",C[i]);
	}
	int ans=0;
	REP(w,W-1){
		memset(dp,0,sizeof(dp));
		memset(cost,0,sizeof(cost));
		FOR(i,1,H+1){
			FOR(j,1,H+1){
				cost[i][j]=cost[i-1][j-1]+(C[i-1][w]==C[j-1][w+1]);
			}
		}
		FOR(i,1,H+1){
			FOR(j,1,H+1){
				dp[i][j]=cost[i][j]+min(dp[i-1][j],dp[i][j-1]);
			}
		}
		ans+=dp[H][H];
	}
	printf("%d\n",ans);
	return 0;
}


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

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    long long h = 0, w = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + 1])
        {
            if (h == 0)
                h = a[i];
            else
            {
                w = a[i];
                break;
            }
            i++;
        }
    }
    cout << h * w << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1e+9;

int main()
{
	int n, m = 0;
	cin >> n;
	map<string, int> blue;
	map<string, int> red;
	for (int i = 0; i < n; i++)
	{
		string card = "";
		cin >> card;
		blue[card]++;
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		string card = "";
		cin >> card;
		red[card]++;
	}
	int ans = 0;
	for(auto itr = blue.begin(); itr != blue.end(); ++itr)
	{
		ans = max(ans, itr->second - red[itr->first]);
	}


	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

r, c, k = map(int, input().split())
v = [[0 for j in range(c)] for i in range(r)]

dp = [[[0 for j in range(c)] for i in range(r)] for k in range(4)]

for i in range(k):
    ri, ci, vi = map(int, input().split())
    v[ri-1][ci-1] = vi


for i in range(r):
    if i > 0:
        for j in range(c):
            for k in range(4):
                dp[0][i][j] = max(dp[0][i][j], dp[k][i-1][j])
    for j in range(c):
        if j > 0:
            for k in range(4):
                dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
        if v[i][j]:
            for k in reversed(range(1, 4)):
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j]+v[i][j])
        

ans = 0

for k in range(4):
    ans = max(ans, dp[k][r-1][c-1])

print(ans)
        


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

#define ll long long
#define mod 1000000007

using namespace std;

ll a[100010],b[100010];

ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
 
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;

        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

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

    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        b[a[i]]++;
    }

    bool flag = false;

    if(n%2 == 0)
    {
        for(int i=1;i<n;i+=2)
        {
            if(b[i] != 2)
                flag = true;
        }

        if(flag)
            cout << 0 << endl;
        else
            cout << power(2,n/2,mod)%mod << endl;
    }
    else
    {
        if(b[0] != 1)
            flag = true;

        for(int i=2;i<n;i+=2)
        {
            if(b[i] != 2)
                flag = true;
        }

        if(flag)
            cout << 0 << endl;
        else
            cout << power(2,n/2,mod)%mod << endl;
    }
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(){
  int a;
  int b;

  cin >> a >> b;

  if (a==1){
    a=14;
  }
  if (b==1){
    b=14;
  }
  if (a>b){
    cout << "Alice";
  }else if (a<b){
    cout << "Bob";
  }else{
    cout<< "Draw";
  }
}

Measured memory_bytes: 256
import java.util.*;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), n=N, m=100000;
		double K = sc.nextDouble();
		double[] cnt = new double[m+1];
		while (n-->0) {
			int b = sc.nextInt(), c = sc.nextInt();
			cnt[b]+=c;
		}
		for (int ans = 1; ans<=m; ans++) {
			if (K<=cnt[ans]) {
				System.out.println(ans);
				System.exit(0);
			}
			K-=cnt[ans];
		}
		sc.close();		
	}

	public static void main(String args[]) {
		solve();
	}

}

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

int main(){
    int n; cin >> n;
    vector<int> h(n);
 
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
 
    
    vector<int> dp(n, INT_MAX);
    
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
 
    
    for(int i = 2; i < n; i++){
       
       
        dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]),
                    dp[i - 1] + abs(h[i] - h[i - 1]));
    }
    
    
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
print "1x1=1\n1x2=2\n1x3=3\n1x4=4\n1x5=5\n1x6=6\n1x7=7\n1x8=8\n1x9=9\n2x1=2\n2x2=4\n2x3=6\n2x4=8\n2x5=10\n2x6=12\n2x7=14\n2x8=16\n2x9=18\n3x1=3\n3x2=6\n3x3=9\n3x4=12\n3x5=15\n3x6=18\n3x7=21\n3x8=24\n3x9=27\n4x1=4\n4x2=8\n4x3=12\n4x4=16\n4x5=20\n4x6=24\n4x7=28\n4x8=32\n4x9=36\n5x1=5\n5x2=10\n5x3=15\n5x4=20\n5x5=25\n5x6=30\n5x7=35\n5x8=40\n5x9=45\n6x1=6\n6x2=12\n6x3=18\n6x4=24\n6x5=30\n6x6=36\n6x7=42\n6x8=48\n6x9=54\n7x1=7\n7x2=14\n7x3=21\n7x4=28\n7x5=35\n7x6=42\n7x7=49\n7x8=56\n7x9=63\n8x1=8\n8x2=16\n8x3=24\n8x4=32\n8x5=40\n8x6=48\n8x7=56\n8x8=64\n8x9=72\n9x1=9\n9x2=18\n9x3=27\n9x4=36\n9x5=45\n9x6=54\n9x7=63\n9x8=72\n9x9=81"


Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
using P = pair<int, int>;
const ll inf =1e9;
const ll linf = 1e18;

struct edge{
    int to;
    int cost;
};
using graph = vector<vector<edge>>;

int main(){
    str n; cin >> n;
    char first_letter = n[0];
    char second_letter = n[1];
    if((first_letter == '9') || (second_letter == '9')){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
/*
解説AC.

*/
#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define iter(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define riter(i, c) for (auto i = (c).rbegin(); i != (c).rend(); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> W(N), S(N), V(N);
    rep(i, 0, N) {
        cin >> W[i] >> S[i] >> V[i];
    }
    vector<int> idx(N);
    rep(i, 0, N) {
        idx[i] = i;
    }
    // sort(all(idx), [&](int i1, int i2) {
    //     return S[i1] + W[i1] < S[i2] + W[i2];
    // });
    sort(all(idx), [&](int i1, int i2) {
        return min(S[i1], S[i2] - W[i1]) > min(S[i2], S[i1] - W[i2]);
    });
    ll max_val = *max_element(all(S)) + *max_element(all(W));
    vector<vector<ll>> dp(N + 1, vector<ll>(max_val + 1, 0));
    rep(i, 1, N + 1) rep(j, 0, max_val + 1) {
        dp[i][j] = dp[i - 1][j];
        if (j - W[idx[i - 1]] >= 0 && j - W[idx[i - 1]] <= S[idx[i - 1]]) {
            chmax(dp[i][j], dp[i - 1][j - W[idx[i - 1]]] + V[idx[i - 1]]);
        }
    }
    ll ans = 0;
    rep(i, 0, max_val + 1) {
        chmax(ans, dp[N][i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 160640
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

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

    double sum=0, rate=380000.0;
    for(int i=0; i<n; i++){
        double money;
        string currency;
        cin >> money >> currency;

        if(currency == "BTC"){
            sum += money*rate;
        }else{
            sum += money;
        }
    }

    printf("%.6f\n", sum);
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>

#define size_t int

using namespace std;

int main(int argc, char const *argv[]) {
  int N, T;
  scanf("%d %d", &N, &T);
  int C = INT_MAX;
  for (size_t i = 0; i < N; i++) {
    int c, t;
    scanf("%d %d", &c, &t);
    if (t <= T && c < C) {
      C = c;
    }
  }
  if (C == INT_MAX) {
    printf("TLE\n");
  } else {
    printf("%d\n", C);
  }
  return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 15 21:08:34 2018

@author: ogura
"""

N, x = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)

cnt = 0
for i in range(len(b)):
    cnt += 1
    x = x - b[i]
    if x < 0:
        break

if x != 0:
    cnt = cnt -1;
    
print(cnt)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		int[][] dp = new int[2][N];
		int[][] table = new int[2][N];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < N; j++) {
				table[i][j] = input.nextInt();
			}
		}
		dp[0][0] = table[0][0];
		for (int i = 1; i < N; i++) {
			dp[0][i] = dp[0][i-1]+table[0][i];
		}
		dp[1][0] = dp[0][0]+table[1][0];
		for (int i = 1; i < N; i++) {
			dp[1][i] = Math.max(dp[1][i-1], dp[0][i])+table[1][i];
		}
		System.out.println(dp[1][N-1]);
	}
}

Measured memory_bytes: 23380
#include <bits/stdc++.h>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
#define co(i) cout<<i<<endl
#define fcout cout<<fixed<<setprecision(10)
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;

int main(){
	string s; cin>>s;
	int a[100001]={};
	FOR(i,0,s.size()){
		a[i]='z'-s[i]+1;
		if(s[i]=='a')a[i]=INF;
	}
	int k; cin>>k;
	FOR(i,0,s.size()){
		if(a[i]<=k){
			s[i]='a';
			k-=a[i];
		}
	}
	s[s.size()-1]=(s[s.size()-1]-'a'+k)%26+'a';
	co(s);
}

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

int main()
{
  char c;
  cin >> c;

  c += 1;

  cout << c << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int DP[1001][1001];
int main(){
	int W,N,C=0;
	while(cin>>W){
		if(!W) break;
		cin>>N;
		int v[1000],w[1000],SUMW=W;
		for(int i=0;i<N;++i) scanf("%d,%d",&v[i],&w[i]);
		for(int i=0;i<=N;++i)for(int j=0;j<=W;++j) DP[i][j]=0;
		for(int i=0;i<N;++i){
			for(int j=0;j<=W;++j){
				if(w[i]>j){//入らない時
					DP[i+1][j]=DP[i][j];
				}else{//入る時
					DP[i+1][j]=max(DP[i][j],DP[i][j-w[i]]+v[i]);
				}
			}
		}
		for(int j=W;j>=0;--j) if(DP[N][W]==DP[N][j])SUMW=j;
		cout<<"Case "<<++C<<":\n";
		cout<<DP[N][W]<<"\n"<<SUMW<<"\n";
	}
	return 0;
}

Measured memory_bytes: 0
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		String[] strs = read(2);
		
		String s = strs[0];
		long k = Long.parseLong(strs[1]);
		
		char c = '1';
		for (int i = 0; i < s.length() && i < k; i++) {
			c = s.charAt(i);
			if (c != '1') {
				break;
			}
		}
		
		System.out.println(c);
	}
	
	private static String[] read(int len) {
		List<String> strList = new ArrayList<>();
		
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			for (int i = 0; i < len; i++) {
				strList.add(br.readLine());
			}
		} catch (IOException e) {
		}
		
		return strList.toArray(new String[0]);
	}
}


Measured memory_bytes: 20820
unittest
{
	assert( [ "3" ].parse.expand.solve == 6 );
	assert( [ "10" ].parse.expand.solve == 3628800 );
	assert( [ "100000" ].parse.expand.solve == 457992974 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	return tuple( n );
}

auto solve( long n )
{
	const MOD = 10 ^^ 9 + 7;
	
	auto ans = 1;
	for( auto i = 1L; i <= n; i++ )
	{
		ans = ( ans * i ) % MOD;
	}
	return ans;
}


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

int main() {
	char str[55];
	int n;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> str[i];
	}

	int cnt = 0;
	for (int i = 0;i < n - 2; i++) {
		if (str[i] == 'A' && str[i + 1] == 'B' && str[i + 2] == 'C') {
			cnt++;
		}
	}

	cout << cnt << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
string S;
map< tuple< int, int, int64, int >, int64 > dp;
int length;
int64 weight;

int64 dfs(int idx, int num, int64 seki, int flag)
{
  if(num - (length - idx) * 9 > 0) return(0);
  if(idx == length) {
    if(seki != weight) return(seki < weight);
    return(flag == 1);
  }
  if(dp.find(make_tuple(idx, num, seki, flag)) != dp.end()) return(dp[make_tuple(idx, num, seki, flag)]);
  int64 ret = 0;
  for(int i = 0; i <= min(num, 9); i++) {
    int nextflag = flag;
    if(flag == 0) {
      if(i < S[idx] - '0')      nextflag = 1;
      else if(i > S[idx] - '0') nextflag = 2;
    }
    ret += dfs(idx + 1, num - i, seki * (i + 1), nextflag);
  }
  return(dp[make_tuple(idx, num, seki, flag)] = ret);
}

int main()
{
  cin >> S;
  length = S.size();
  int sum = accumulate(S.begin(), S.end(), 0) - '0' * S.size();
  if(sum == 0) {
    cout << 0 << endl;
  } else {
    vector< int64 > poyo(sum, 0);
    poyo[0] = 1;
    for(int i = 0; i < length; i++) {
      for(int j = sum - 1; j >= 0; j--) {
        for(int k = j + 1; k <= min(sum - 1, j + 9); k++) {
          poyo[k] += poyo[j];
        }
      }
    }
    weight = 1;
    for(int i = 0; i < S.size(); i++) weight *= (S[i] - '0' + 1);
    cout << accumulate(poyo.begin(), poyo.end(), 0LL) + dfs(0, sum, 1, 0) << endl;
  }
}

Measured memory_bytes: 31216
N = int(input())

for i in range(N):
	sides = list(map(int, input().split()))
	longestSide = max(sides)
	sides.remove(longestSide)
	if (longestSide ** 2) == (sides[0] ** 2 + sides[1] ** 2):
		print('YES')
	else:
		print('NO')

Measured memory_bytes: 7700
#include<iostream>

using namespace std;

int ans[200001];
int a[200001];

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

    for(int i=2;i<=n;i++){
        cin >> a[i];
    }

    for(int i=2;i<=n;i++){
        ans[a[i]]++;
    }

    for(int i=1;i<=n;i++){
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 5180
x,y = map(int,input().split())

mod = 10**9 +7

def fact(n,mod):
   t = 1
   for i in range(1,n+1):
       t = (t * i) % mod
   return t

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod




if (x+y) % 3 == 0 and y <= 2*x and 2*y >= x:
    n = (x+y)//3
    m = x-n
    ans = fact(n,mod) * inv(fact(n-m,mod),mod) * inv(fact(m,mod),mod)
    print(ans % mod)
else:
    print(0)
    exit()
    

Measured memory_bytes: 38480
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 1000000007; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  string s, t;
  cin >> s >> t;

  int N = s.size(), M = t.size();
  vector<vector<int>> dp(N+1, vector<int>(M+1, 0));

  REP(i, N){
    REP(j, M){
      if(s[i] == t[j]) chmax(dp[i+1][j+1], dp[i][j]+1);
      else chmax(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]));
    }
  }

  string ans = "";
  while(N > 0 && M > 0){
    if(dp[N][M] == dp[N-1][M]) N--;
    else if(dp[N][M] == dp[N][M-1]) M--;
    else{
      N--; M--;
      ans += s[N];
    }
  }

  reverse(ALL(ans));
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, l, r) for (int i = l; i <= (int)(r); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    double n;
    cin >> n;
    cout << n * 2 * 3.141592 << endl;
    // printf("%d\n", N);
    return 0;
}

Measured memory_bytes: 3788
#include <iostream>
    #include <vector>
     
    using namespace std;
     
    int main() {
        int n; double d, x;
        cin >> n >> d >> x;
        vector<double> p(n+1, 0), psm(n+2, 0);
        for (int i = 1; i <= n; i++) {
            p[i] = p[i-1] + 0.5/i;
            //psm[i+1] = psm[i] + p[i];
        }
     
        double ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (p[i+1]+p[n-i])/2 * (d + d+x);
            d += 2*x;
        }
        printf("%.20lf\n", ans);
        
        return 0;
    }


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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> h(n);
  for (int i = 0; i < n; i++) cin >> h[n - i - 1];
  int ans = 0;
  int tmp = 0, now = 1000000007;
  for (int i = 0; i < n; i++) {
    if (now <= h[i]) {
      now = h[i];
      tmp++;
      ans = max(ans, tmp);
    } else {
      now = h[i];
      tmp = 0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;

 main()

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

}





































Measured memory_bytes: 3592