akhauriyash/Code-Regression huggingface dataset:
p = 998244353
n, k = [int(i) for i in input().split(" ")]
n -= 1
a = [[0, 0] for i in range(k)]
for i in range(k):
  a[i] = [int(j) for j in input().split(" ")]
dp = [0] * (n+10)
cum = [0] * (n+10)
dp[0] = 1
cum[0] = 1

for i in range(1, n+1):
  for j in range(k):
    fi = i - a[j][1]
    se = i - a[j][0]
    if se < 0:
      continue
    if fi < 0:
      fi = 0
    if fi == 0:
      dp[i] = (dp[i] + cum[se]) % p
    else:
      dp[i] = (dp[i] + cum[se] - cum[fi-1]) % p
  cum[i] = (cum[i-1] + dp[i]) % p

# print(dp[n] % p)
# print(dp)
# print(cum)
print(dp[n] % p)

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

const char *Conv( int N )
{
int iPos;
static char S[ 50 ];

	if( N == 0 ) return "0";

	iPos = 40;
	S[ iPos ] = '\0';
	while( N != 0 )
	{
		iPos--;
		if( N % 2 == 0 )
			S[ iPos ] = '0';
		else
			S[ iPos ] = '1';

		if( N < 0 && N % 2 != 0 )
		{
			N /= - 2;
			N++;
		}
		else
			N /= - 2;
	}

	return S + iPos;
}

int main()
{
int N;

	cin >> N;

	cout << Conv( N ) << endl;

	return 0;
}





Measured memory_bytes: 256
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50 + 5;
const int MOD = (int)1e9 + 7;

int n;
long long binom[N][N];
long long f[N][N][N];

void solve()
{
    cin >> n;
    binom[0][0] = 1;
    for(int i = 1; i < N; ++ i) {
        binom[i][0] = 1;
        for(int j = 1; j <= i; ++ j) {
            binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % MOD;
        }
    }

    f[0][1][0] = 1;
    for(int i = 0; i < N; ++ i) {
        if (i) {
            for(int j = 0; j + 1 < N; ++ j) {
                for(int k = 0; k + 1 < N; ++ k) {
                    (f[i][j + 1][k + 1] += f[i][j][k]) %= MOD;
                }
            }
        }

        for(int j = 0; j < N; ++ j) {
            for(int k = 0; k < N; ++ k) {
                if (i + j + k >= N) continue;
                if (j == 0 && k == 0) continue;
                for(int w = 0; w <= j; ++ w) {
                    (f[i + j + k][w][0] += f[i][j][k] * binom[i + j + k][j - w] % MOD * binom[i + k + w][k + w] % MOD) %= MOD;
                }
                for(int w = 1; w <= k; ++ w) {
                    (f[i + j + k][0][w] += f[i][j][k] * binom[i + j + k][j + w] % MOD * binom[i + k - w][k - w] % MOD) %= MOD;
                }
            }
        }
    }

    cout << f[n][0][0] << endl;
}

int main()
{
    solve();
    return 0;
}



Measured memory_bytes: 1536
public class AtCoder
{
    public static void Main()
    {
        var input = System.Console.ReadLine();
 
        int answer = 0;
        for (int i = 0; i < input.Length; i++)
        {
            string s = input.Substring(i, 1);
            if ("1".Equals(s))
            {
                answer++;
            }
        }
 
        System.Console.WriteLine(answer);
    }
}

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

int main() {
  int n,q; cin>>n>>q;
  string s; cin>>s;
  vector<int> v(n,0);
  rep(i,n-1){
    v[i+1]=v[i];
    if(s.at(i)=='A'&&s.at(i+1)=='C'){v[i+1]++;}
    //cout<<v[i]<<" ";
  }
  rep(i,q){
    int l,r,ans; cin>>l>>r;
    if(l==1){ans=v[r-1];}
    else{
      ans=v[r-1]-v[l-2];
      if(s.at(l-2)=='A'&&s.at(l-1)=='C'){ans--;}
    }
    cout<<ans<<endl;
  }
}

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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = unordered_set<int32_t>;
using setstr = unordered_set<string>;
using qint = queue<int32_t>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

vector<ll> divisor(ll n)
{
    vector<ll> ret;
    for (std::int64_t i = 1; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(ALL(ret));
    return ret;
}

void Main()
{
    ll n;
    cin >> n;
    vll div = divisor(n);

    auto itr = lower_bound(ALL(div), sqrt(n) - 0.5);
    ll val = *itr;

    ll val2 = n / val;
    cout << val + val2 - 2 << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


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

int n, m, q;
int a[50], b[50], c[50], d[50];
int A[10], ans;

void dfs(int dep, int pre) {
    if (dep == n) {
        int sum = 0;
        for (int i = 0; i < q; i++) 
        	if (A[b[i]] - A[a[i]] == c[i]) sum += d[i];
        ans = max(ans, sum);
        return;
    }
    for (int i = pre; i <= m; i++) {
        A[dep] = i;
        dfs(dep + 1, i);
    }
}

int main() {
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i], --b[i];
    }
    dfs(0, 1);
    cout << ans << "\n";
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define For1(i, n) for(int i = 1; i <= (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n, k);
    Cins(int, n, a);
    vc<int> posa(n);
    For(i, n) posa[i] = max(a[i], 0);
    Cusum(ll, a, sa);
    Cusum(ll, posa, sposa);
    
    ll ans = 0;
    For(i, n-k+1){
        // printf("%d : %lld + %lld + %lld\n", i, sposa[i]-sposa[0], max(sa[i+k]-sa[i], 0ll), sposa[n]-sposa[i+k]);
        Maxi(ans, sposa[i]-sposa[0] + max(sa[i+k]-sa[i], 0ll) + sposa[n]-sposa[i+k]);
    }
    Cout(ans);
}




Measured memory_bytes: 2560
import java.io.*;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;

public class Main
{
    public static void main(String argvs[])
    {
        try{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String[] strLine = in.readLine().split(" ");
            System.out.println(solve(Integer.parseInt(strLine[0]),Integer.parseInt(strLine[1])));

        }catch(IOException e)
            {
                System.out.println(e);
                System.exit(0);
            }
    }
    private static int solve(int X,int A)
    {
        if(X<A)
            return 0;
        else
            return 10;

    }
}


Measured memory_bytes: 21076
N=int(input())
res = 0
for k in range(1,N+1):
    c = 0
    for i in range(1,k+1):
        if k%i == 0:
            c += 1
        else:
            pass
    if k%2 == 1 and c == 8:
        res += 1
    else:
        pass
print(res)


Measured memory_bytes: 2940
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n,k,a[100010],rt;
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if (a[i]==1)
		{
			rt=i;
		} 
	}
	k--;
	int ans=1e9;
	for (int i=0;i<rt;i++)
	{
		int now=1;
		if (rt-i>1)
		{
			now+=(rt-i-2)/k+1;
		}
		if (rt+(k-i)<n)
		{
			now+=(n-rt-(k-i)-1)/k+1;
		}
		ans=min(ans,now);
	}
	/*
	if (rt>1)
	{
		ans+=(rt-2)/k+1;
	}
	if (rt<n)
	{
		ans+=(n-rt-1)/k+1;
	}
	*/
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
long long fac(ll a) {
 long long ans=1;
 while(a>=1){
 ans*=2;
 ans%=1000000007;
   a--;
     ;
    }
    return ans;
     }


int main() {
ll N;
  cin >>N;
  vl a(N);
  rep(i,N) {
cin >>a.at(i);
  }
  sort(all(a));
  
  
  
  if(N%2!=0) {
    vl vec(N);
    vec.at(0)=0;
    repl(i,1,(N-1)/2+1) {
      vec.at(2*i-1)=2*i;
      vec.at(2*i)=2*i;
    }
    bool ans=true;
    rep(i,N) {
      if(a.at(i)!=vec.at(i)) {
ans=false;
        break;
      }
    }
    
    if(!ans) {
cout<<0<<endl;
    }
    else {
      cout<<fac(N/2)<<endl;
                }
  }
  
  
  
  
  else if(N%2==0) {
    vl veec(N);
   
    repl(i,0,(N)/2) {
      veec.at(2*i)=2*i+1;
      veec.at(2*i+1)=2*i+1;
    }
    bool ans=true;
    rep(i,N) {
      if(a.at(i)!=veec.at(i)) {
ans=false;
        break;
      }
    }
    
    if(!ans) {
cout<<0<<endl;
      
      
    }
    else {
      cout<<fac(N/2)<<endl;
                }
  }
  
  
  
  
}
      
 

Measured memory_bytes: 1792
import itertools,sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]

s = S()
n = len(s)
for i in range(n):
    if s[i] != s[n-1-i]:
        print("No")
        exit()
for i in range((n-1)//2):
    if s[i] != s[(n-1)//2-1-i]:
        print("No")
        exit()
for i in range((n+3//2),n):
    if s[i] != s[n-1-i]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 6568
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader reader = new BufferedReader(isr);
		String string;
		int n;
		
		boolean[] primes = new boolean[10001];
		primes[0] = primes[1] = false;
		for(int i = 2; i < 10000; i++){
			boolean judge = true;
			for(int j = 2; j <= Math.sqrt(i); j++){
				if(i % j == 0){
					judge = false;
					break;
				}
			}
			if(judge) primes[i] = true;
			else      primes[i] = false;
		}
		
		while(!(string = reader.readLine()).equals("0")){
			n = Integer.parseInt(string);
			
			for(int i = n; i > 0; i--){
				if(primes[i] && primes[i - 2]){
					System.out.println(i - 2 + " " + i);
					break;
				}
			}
		}
		reader.close();
	}
}

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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

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

int main()
{
    
    ll x,y,sum=0;
    cin >> x >> y;
    for(int i=0;;i++){
        ll tmp=x*pow(2,i);
        if(tmp > y)break;
        sum++;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
using namespace std;
const int MAX=1e9+7;
int n,x1,x2,x,ans,ansa[100010],ansb[100010],Min,a[100010],tota,b[100010],totb,tot,sum,suma,sumb,Max;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	scanf("%d%d",&x1,&x2);
	Max=max(x1,x2);
	Min=min(x1,x2);
	for(int i=3;i<=n;i++){
		scanf("%d",&x);
		if(x<Min){
			if(Min>0){
				tota++;
				a[tota]=Min;
			}
			else{
				totb++;
				b[totb]=Min;
			}
			Min=x;
		}
		else if(x>Max){
			if(Max>0){
				tota++;
				a[tota]=Max;
			}
			else{
				totb++;
				b[totb]=Max;
			}
			Max=x;
		}
		else{
			if(x>0){
				tota++;
				a[tota]=x;
			}
			else{
				totb++;
				b[totb]=x;
			}
		}
	}
	suma=Max;
	sumb=Min;
	for(int i=1;i<=tota;i++){
		sum++;
		ansa[sum]=sumb;
		ansb[sum]=a[i];
		sumb-=a[i];
	}
	for(int i=1;i<=totb;i++){
		sum++;
		ansa[sum]=suma;
		ansb[sum]=b[i];
		suma-=b[i];
	}
	sum++;
	ansa[sum]=suma;
	ansb[sum]=sumb;
	ans=suma-sumb;
	printf("%d\n",ans);
	for(int i=1;i<=sum;i++){
		printf("%d %d\n",ansa[i],ansb[i]);
	}
	return 0;
}

Measured memory_bytes: 3072
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }

    public void solve() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        boolean[] a = new boolean[n];
        boolean[] b = new boolean[n];
        for (int i = 0; i < m; ++i) {
            int u = in.nextInt() - 1, v = in.nextInt() - 1;
            if (u == 0) {
                a[v] = true;
            }
            if (v == n - 1) {
                b[u] = true;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (a[i] && b[i]) {
                System.out.println("POSSIBLE");
                return;
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}

Measured memory_bytes: 93696
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (300006)
ll n, m;
bool have[702][702];
vector<int> v[706];
int colour[702];
bool notbi;
vector<pi> sz;
void dfs(ll x, ll c) {
	if(colour[x]) {
		notbi |= (colour[x] != c);
		return;
	}
	colour[x]=c;
	if(colour[x]==1) sz.back().f ++;
	else sz.back().s ++;
	for(auto i:v[x]) {
		dfs(i, 3-c);
	}
}
ll dp[706];
ll nc2(ll x) {
	return x*(x-1)/2;
}
int main()
{
	FAST
	cin>>n>>m;
	FOR(i,0,m-1) { ll a, b; cin>>a>>b; have[a][b]=1, have[b][a]=1; }
	FOR(i,1,n) FOR(j,1,n) if(!have[i][j]&&i!=j) v[i].pb(j);
	FOR(i,1,n) if(colour[i] == 0) {
		sz.pb(pi(0,0));
		dfs(i, 1);
	}
	if(notbi) { cout<<"-1\n"; return 0; }
	FOR(i,0,705) dp[i]=-2;
	dp[0]=-1;
	for(ll i=0;i<sz.size();++i) { 
		DEC(j,n,0) {
			if(j>=sz[i].f&&dp[j-sz[i].f]==i-1) dp[j]=i;
			if(j>=sz[i].s&&dp[j-sz[i].s]==i-1) dp[j]=i;
		}
	}
	ll ans=LLINF;
	FOR(i,0,n) {
		if(dp[i] == siz(sz)-1) {
			ans = min(ans, nc2(i) + nc2(n-i));
		}
	} assert(ans^LLINF);
	cout<<ans<<'\n';
}


Measured memory_bytes: 3072
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <fstream>
#include <sstream>
#include <math.h>
#include <queue>
#include <stack>
#include <math.h>
#include <string.h>


using namespace std;


int main(){
    int n;
    cin>>n;
    string h[6];
    for(int i=0; i<n; i++){
        double hight;
        cin>>hight;
        if(hight<165.0)h[0]+='*';
        else if(hight<170.0)h[1]+='*';
        else if(hight<175.0)h[2]+='*';
        else if(hight<180.0)h[3]+='*';
        else if(hight<185.0)h[4]+='*';
        else h[5]+='*';
        
    }
    
    for(int i=0; i<6; i++){
        cout<<i+1<<":" <<h[i]<<endl;
    }
}

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

int main(){
  long N;cin>>N;
  if(floor(N/1.08)==N/1.08)cout<<floor(N/1.08)<<endl;
  else if(floor((N+1)/1.08)!=floor(N/1.08)){
    if(floor(N/1.08)==N/1.08)cout<<floor(N/1.08)<<endl;
    else if(floor((N+1)/1.08)==(N+1)/1.08)cout<<":("<<endl;
    else cout<<floor((N+1)/1.08)<<endl;
  }
  else cout<<":("<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int k = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        boolean fl = false;
        for (int i = a; i <= b; i++) {
            if (i % k == 0) {
                fl = true;
            }
        }

        System.out.println(fl ? "OK" : "NG");

        sc.close();
    }
}

Measured memory_bytes: 35752
#include <iostream>
#include <map>
#include <vector>

using namespace std;
using ll = long long;

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

vector<ll> primes, cubes;

void precalc() {
    bool isp[100010];
    fill(isp, isp + 100010, true);

    for (ll i = 2; i * i < 1e10; ++i) {
        if (!isp[i]) continue;
        primes.push_back(i);
        for (ll j = 2; i * j <= 100000; ++j) isp[i * j] = false;
    }

    for (ll p : primes) {
        if (p * p * p > 1e10) break;
        cubes.push_back(p * p * p);
    }
}

ll delcube(ll n) {
    for (ll c : cubes) {
        while (n % c == 0) n /= c;
    }
    return n;
}

ll anticube(ll n) {
    ll ret = 1;

    for (ll p : primes) {
        if (p * p > n) break;
        if (n % p > 0) continue;

        int c = 0;
        while (n % p == 0) {
            n /= p;
            ++c;
        }
        ret *= mypow(p, 3 - c);
    }

    ret *= mypow(n, 2);
    return ret;
}

int main() {
    precalc();

    int N;
    cin >> N;

    map<ll, int> cnt;
    for (int i = 0; i < N; ++i) {
        ll s;
        cin >> s;
        s = delcube(s);
        if (cnt.count(s) == 0) cnt[s] = 0;
        ++cnt[s];
    }

    int ans = 0;
    for (auto p : cnt) {
        if (p.second == 0) continue;
        if (p.first == 1) {
            ++ans;
            continue;
        }

        ll opp = anticube(p.first);
        if (cnt.count(opp)) {
            ans += max(cnt[p.first], cnt[opp]);
            cnt[p.first] = cnt[opp] = 0;
        } else {
            ans += cnt[p.first];
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6656
from itertools import accumulate
n,q = map(int,input().split())
s = input()
L = [0]*n

for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        L[i] = 0
        L[i+1] = 1

LL = list(accumulate(L))
for i in range(q):
    l,r = map(int,input().split())
    print(LL[r-1]-LL[l-1])


Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;


int main(){
    int n;  cin >> n;
    map<int, int> key;
    for(int i=0; i<n; i++){
        int x;  cin >> x;
        key[x] += 1;
    }
    ll ans=0;
    for(auto x: key)
        ans += x.second-1;
    cout << n - (ans + ans%2) << endl;
}



Measured memory_bytes: 4992
#include <cstdio>

int main()
{
    long long W, H, x, y;
    scanf("%lld %lld %lld %lld", &W, &H, &x, &y);

    printf("%lf ", (H * W) / 2.0);
    if (2 * x == W && 2 * y == H) {
        printf("1\n");
    } else {
        printf("0\n");
    }

    return 0;
}


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

using namespace std;

class UF {
  int sz, mxsz;
  vector<int> rank, p, ssz;
public:
    UF(int n) {
      	sz = n;
        p = vector<int>(n);
        rank = vector<int>(n, 0);
        ssz = vector<int>(n, 1);
        for(int i = 0; i < n; i++) p[i] = i;
        mxsz = 1;
    }
  int par(int x) {
  	return p[x] == x ? x : p[x] = par(p[x]);
  }
  bool IsSameSet(int x, int y) {
    return par(x) == par(y);
  }
  void merge(int x, int y) {
  	int a = par(x), b = par(y);
    if(a != b) {
    	if(rank[a] > rank[b]) {
        	p[b] = a;
          ssz[a] += ssz[b];
          mxsz = max(mxsz, ssz[a]);
        }
      else {
      	p[a] = b;
        ssz[b] += ssz[a];
        mxsz = max(mxsz, ssz[b]);
        if(rank[a] == rank[b]) rank[b]++;
      }
    }
  }
  int maxsize() {
  	return mxsz;
  }
};

int main() {
	int n, x, y, m;
    cin >> n >> m;
    UF set(n);
    for(int i = 0; i < m; i++) {
  	    cin >> x >> y;
  	    x--, y--;
        set.merge(x, y);
    }
  	cout << set.maxsize();
	return 0;
}

Measured memory_bytes: 5604
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int[] x=new int[n];
		int[] y=new int[n];
		double sum=0;
		for(int i=0;i<n;i++) {
			x[i]=sc.nextInt();
			y[i]=sc.nextInt();
		}
		String s="";
		for(int i=1;i<=n;i++)s+=String.valueOf(i);
		List<String> res=new ArrayList<>();
		res=permutation(s,"",res);
		for(int i=0;i<res.size();i++) {
			for(int j=0;j<n-1;j++) {
				int buff1=Integer.parseInt(res.get(i).toString().substring(j, j+1))-1;
				int buff2=Integer.parseInt(res.get(i).toString().substring(j+1, j+2))-1;
				sum+=Math.sqrt(Math.pow(x[buff1]-x[buff2], 2)+Math.pow(y[buff1]-y[buff2], 2));
			}
		}
		System.out.println(sum/res.size());
	}
	public static List<String> permutation(String q, String ans, List<String> res){
        // Base Case
        if(q.length() <= 1) {
            res.add(ans+q);
        }
        // General Case
        else {
            for (int i = 0; i < q.length(); i++) {
                permutation(q.substring(0, i) + q.substring(i + 1),
                        ans + q.charAt(i), res);
            }
        }
		return res;
    }
}



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

#define inf 1e9+7
typedef long long ll;

void solve(int n,const vector<ll> &a){
    for(int i=0;i<n;i++){
        int sub=i+1;
        cout << "node " << sub << ":";
        cout << " key = " << a[i] << ",";
        if(i)cout << " parent key = " << a[sub/2-1] << ",";
        if(sub*2-1 < n)cout << " left key = " << a[sub*2-1] << ",";
        if(sub*2 < n)cout << " right key = " << a[sub*2] << ",";
        cout << " \n";
    }
}

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

    int n;
    cin >> n;
    vector<ll> a(n,inf);
    for(int i=0;i<n;i++)cin >> a[i];
    solve(n, a);
    return 0;
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
using namespace std;
int main(){
	ll n,mi=0;
	cin>>n;
	vector<ll> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	ll sum = a[0];
	for(int i=1;i<n;i++){
		if(sum * 2 < a[i]) mi = i;
		sum += a[i];
	}
	cout<<n-mi<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define NIL -1
static const int INFTY=(1<<21);
int color[102];
int d[102][102];
int n,di,sum=0;
vector<int> searched;
void count(int start){
    int min=INFTY,minp,a,b,c;
    color[start]=2;
    searched.push_back(start);
    for(int i=0;i<n;i++){
        a=d[start][i];
        if(a!=NIL&&color[i]==0) color[i]++;
    }
    for(int i=0;i<searched.size();i++){
        b=searched[i];
        for(int j=0;j<n;j++){
            c=d[b][j];
            if(color[j]==1&&c<min&&c!=NIL){
                min=c; 
                minp=j;
                }
        }
    }
    if(min!=INFTY){
            sum+=min;
            count(minp);
    }

}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]=NIL;
            cin>>di;
            d[i][j]=di;
        }
        color[i]=0;
    }
    count(0);
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
#define YY "YES\n"
#define NN "NO\n"
#define f first
#define s second
#define LL long long
using namespace std;

LL n,m;
char c;
int main(){
	scanf("%d %c %d",&n,&c,&m);
	if (c=='+'){
		cout<<n+m<<"\n";
	}
	else cout<<n-m<<"\n";
	
}

Measured memory_bytes: 3672
N, K = map(int, input().split())

def solve():
  if( (N-1)*(N-2)//2 < K ):
    print('-1')
    return
  print(N-1 + (N-1)*(N-2)//2 - K)
  for i in range(2, N+1):
    print('1', i)
  n = (N-1)*(N-2)//2 - K
  count = 0
  s = 2
  f = 3
  while (count<n):
    print(s, f)
    f+=1
    count+=1
    if(N<f):
      s+=1
      f=s+1

solve()
  

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

using namespace std;
typedef long long ll;

#define ZERO_IQ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x, y) cerr << (#x) << " " << (#y) <<" is " << (x) <<" "<< (y) << endl
#define debug2(x, y, z) cerr << (#x) << " " <<(#y) << " " << (#z) << " is " << (x) << " " << (y) << " " << (z) << endl
#define watch(x) cerr << (#x) << " is " << (x) << endl
const ll mod = 1e9 + 7;
vector<ll> fact(2004), inv(2004);

ll fp(ll base, ll exp) {
    if (exp == 0)
        return 1;
    ll ans = fp(base, exp / 2);
    ans = (ans * ans) % mod;
    if (exp % 2 != 0)
        ans = (ans * (base % mod)) % mod;
    return ans;
}

void calcFacAndInv(ll n) {
    fact[0] = inv[0] = 1;
    for (ll i = 1; i <= n; i++) {
        fact[i] = (i * fact[i - 1]) % mod;
        inv[i] = fp(fact[i], mod - 2);
    }
}

ll ncr(ll n, ll r) {
    if(n<r)return 0;
    return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}

int main() {
    ll n, k;
    cin >> n >> k;
    calcFacAndInv(2003);
    for (int i = 1; i <= k; ++i) {
        cout << 1LL*((ncr(n - k + 1, i) * ncr(k - 1, i - 1)) % mod) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include<math.h>
#include<bitset>
using namespace std;

int main() {
	int n; cin >> n;
	int a[n+2];
	a[0] = 0; a[n + 1] = 0;
	for (int i = 1; i <= n; i++)cin >> a[i];
	int sum = 0;
	for (int i = 1; i <= n + 1; i++)sum += abs(a[i] - a[i - 1]);
	for (int i = 1; i <= n; i++) {
		cout << sum + abs(a[i - 1] - a[i + 1]) - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) << endl;
	}
}

Measured memory_bytes: 3968
N = int(input())
H = list(map(int,input().split()))
A = [0]*N
t = 0

def water(l,r,t,A):
    t += 1
    for i in range(r-l+1):
        A[l+i] += 1
    return t,A

yet = True
lowest = 0  #最小の値

while yet:
    water_place = []
    last_need = False    #直前は水が必要だったか
    start = 0
    end = 0
    for i in range(N):
        if last_need == False and A[i] < H[i]:
            start = i
            last_need = True
        elif last_need == True and A[i] >= H[i]:
            end = i-1
            last_need = False
            water_place.append([start,end])
        
        if i == N - 1 and A[i] < H[i]:
            end = i
            water_place.append([start,end])

    for l,r in water_place:
        t,A = water(l,r,t,A)
    if A == H:
        print(t)
        yet = False

Measured memory_bytes: 3064
#include <cassert>
#include <climits>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct state {
	int x, y, d, dist;
	state(int x, int y, int d, int dist):x(x), y(y), d(d), dist(dist){}

	bool operator>(const state& s) const {
		return dist > s.dist;
	}
};

#define X first
#define Y second
typedef pair<int, int> P;

const int MAX = 30;
const int EAST = 0, SOUTH = 1, WEST = 2,  NORTH = 3;
const int STRAIGHT = 0, RIGHT = 1, BACK = 2, LEFT = 3, HALT = 4;
const P dir[4] = {P(1, 0), P(0, 1), P(-1, 0), P(0, -1)};

int w, h;
int s[MAX][MAX];
int cost[4];

P turn(int d, int ori) {
	switch(ori) {
	case STRAIGHT: return dir[d]; break;
	case RIGHT: return  P(-dir[d].Y, dir[d].X); break;
	case BACK: return P(-dir[d].X, -dir[d].Y); break;
	case LEFT: return P(dir[d].Y, -dir[d].X); break;
	}
	assert(false);
}

int dijkstra() {
	vector<vector<vector<int> > > dist(h, vector<vector<int> >(w, vector<int>(4, INT_MAX)));
	priority_queue<state, vector<state>, greater<state> > que;
	que.push(state(0, 0, EAST, 0));
	dist[0][0][EAST] = 0;

	while(!que.empty()) {
		const state sta = que.top();
		que.pop();

		if(dist[sta.y][sta.x][sta.d] < sta.dist)
			continue;

		if(sta.x == w - 1 && sta.y == h - 1)
			return sta.dist;

		for(int ori = 0; ori < 4; ++ori) {
			const P forward = turn(sta.d, ori);
			const int nx = sta.x + forward.X, ny = sta.y + forward.Y;
			if(nx < 0 || ny < 0 || nx >= w || ny >= h)
				continue;

			const int nd = (sta.d + ori) % 4, nc = sta.dist + (ori == s[sta.y][sta.x] ? 0 : cost[ori]);
			if(dist[ny][nx][nd] > nc) {
				dist[ny][nx][nd] = nc;
				que.push(state(nx, ny, nd, nc));
			}
		}
	}

	assert(false);
	return 0;
}

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

	while(cin >> w >> h, w) {
		for(int i = 0; i < h; ++i)
			for(int j = 0; j < w; ++j)
				cin >> s[i][j];

		for(int i = 0; i < 4; ++i)
			cin >> cost[i];

		cout << dijkstra() << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1388
#include <cstdio>

int main(){
    int m, n, total = 0, num = 0, row = 0;
    while( scanf("%d,%d\n", &m, &n) != EOF ){
        total += m * n; // 販売金額の合計に加算
        num += n;       // 販売の数量の数に加算
        row++;          // 入力の行数を増やす
    }
    int ans = (int)(num / (double)row + 0.5); // 販売数量の平均(四捨五入する)
    printf("%d\n%d\n", total, ans );
}

Measured memory_bytes: 1024
N = int(input())
X = list(map(int, input().split()))
Y = X.copy()
Y.sort()
if N % 2 == 1:
    Bmin = Y[N // 2 - 1]
    Bmid = Y[N // 2]
    Bmax = Y[N // 2 + 1]
    for i in X:
        if i < Bmid:
            print((Bmid + Bmax) / 2)
        elif i > Bmid:
            print((Bmid + Bmin) / 2)
        else:
            print(Bmid)
else:
    Bmin = Y[N // 2 - 1]
    Bmax = Y[N // 2]
    for i in X:
        if i <= Bmin:
            print(Bmax)
        elif i >= Bmax:
            print(Bmin)

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


void solve(long long N, std::vector<long long> a)
{
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans ^= a[i];
    }
    
    for (int i = 0; i < N; i++) {
        cout << (ans^a[i]);
        if (i != N -1) cout << " ";
    }
    cout << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 4816
#include<cmath>
#include<iostream>
using namespace std;
const int MAXN = 51;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
inline int dist(int x1, int y1, int x2, int y2) {
	return abs(x1-x2) + abs(y1-y2);
}
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> a[i] >> b[i];
	}
	for (int j = 1; j <= M; j++) {
		cin >> c[j] >> d[j];
	}
	for (int i = 1; i <= N; i++) {
		int min_dist = dist(a[i], b[i], c[1], d[1]);
		int id = 1;
		for (int j = 2; j <= M; j++) {
			int cur_dist = dist(a[i], b[i], c[j], d[j]);
			if (cur_dist < min_dist) {
				min_dist = cur_dist;
				id = j;
			}
		}
		cout << id << endl;
	}
	return 0;
}

Measured memory_bytes: 892
#include<iostream>
using namespace std;
int main(void){
    int d,n;
    cin>>d>>n;
    if(n==100){
        if(d==0){
        cout<<n+1;
    }else if(d==1){
        cout<<100*(n+1);
    }else if(d==2){
        cout<<10000*(n+1);
    }
    }else{
    if(d==0){
        cout<<n;
    }else if(d==1){
        cout<<100*n;
    }else if(d==2){
        cout<<10000*n;
    }
    }
}

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

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] a = new int[n];
		int[] count = new int[n+1];
		
		for(int i=1;i<n;i++) {
			a[i] = scan.nextInt();
			count[a[i]]++;
		}
		
		for(int i=1;i<n+1;i++) {
			System.out.println(count[i]);
		}

	}

}


Measured memory_bytes: 61936
#include <bits/stdc++.h>
using namespace std;
#define INF INT_MAX/3

int main(){
    int N,M,R;cin >> N >> M >> R;
    vector<int> vis;
    vector<vector<int> >dist(N);
    for(int i = 0 ; i < R ; i++){
        int r;cin >> r;r--;
        vis.push_back(r);
    }
    for(int i = 0 ; i < N ; i++){
        dist[i].resize(N);
        for(int j = 0; j < N ; j++){
            if(i == j)dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }
    for(int i = 0; i < M ; i++){
        int u,v,cost;
        cin >> u >> v >> cost;u--;v--;
        dist[u][v] = cost;
        dist[v][u] = cost;
    }
    //warshall_floyd
    
    for(int k = 0 ; k < N ; k++){
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                dist[i][j] = min(dist[i][j],dist[k][j]+dist[i][k]);
            }
        }
    }
    int res = INF;

    sort(vis.begin(), vis.end());
    do {
        int tmp = 0;
        for (int i = 1; i < vis.size(); ++i) tmp += dist[vis[i]][vis[i-1]];
        res = min(res, tmp);
    } while (next_permutation(vis.begin(), vis.end()));
    

    cout << res << endl;

    return 0;
}


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

#define llint long long

const double LONG_ANGULER = 360.0 / (60.0 * 12.0);
const double SHORT_ANGULER = 360.0 / (60.0);

signed main() {
	double a, b, h, m;
	cin >> a >> b >> h >> m;
	double minite = h * 60.0 + m;
	double longAngle = minite * LONG_ANGULER;
	double shortAngle = minite * SHORT_ANGULER;
	double difAngle = abs(longAngle - shortAngle);
	double ans = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(difAngle / 180.0 * M_PI));
	cout << fixed << setprecision(20) << ans << endl;
}

Measured memory_bytes: 4216
import java.util.Scanner;

public class Main {
	public static Scanner sc;
	
	public static void main(String[] args) {
		//宣言
		int N=0;
		int A[]= new int[300];
		sc = new Scanner(System.in);
		int count=0;
		//入力
		N= sc.nextInt();
		for(int i=0;i<N;i++) {
			A[i]=sc.nextInt();
		}
		//出力
		for(int j=0;j<N;j++) {
			for(int i=N-1;i>=j+1;i--) {
				if(A[i]<A[i-1]) {
					int w = A[i];
					A[i]=A[i-1];
					A[i-1]=w;
					count++;
				}
			}	
		}
		for(int i=0;i<N;i++) {
			if(i>=0 &&i<N-1) {
				System.out.print(A[i]+" ");
			}else if(i==N-1) {
				System.out.println(A[i]);
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 26264
#include <stdio.h>
#include <math.h>
#define N 10000
int isPrime(int);

int main() {
  int i,n,num[N],cnt=0;
  scanf("%d",&n);
  for (i = 0; i < n; i++) {
  scanf("%d",&num[i]);
  }
  for (i = 0; i < n; i++) {
    if (isPrime(num[i]) == 1) cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}

int isPrime(int n){
  int i;
  if (n == 2) return 1;
  if (n%2 == 0 || n < 2) return 0;
  for (i = 3; i <= sqrt(n); i+=2) {
    if (n%i == 0) return 0;
  }
  return 1;
}



Measured memory_bytes: 2048
def dfs(i,sall):
    if i == lenS:
        return (sall)
        #return sum(map(int,(s[0]+sall).split("+")))
    return dfs(i + 1,sall+"+"+s[i])+"+"+dfs(i + 1,sall+s[i])

s = input()
lenS = len(s)
print(sum(map(int,dfs(1,s[0]).split("+"))))

Measured memory_bytes: 9104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,W;
int w[100+10],v[100+10];
ll dp[100+10][100000+10];
int main()
{
    cin>>n>>W;
    for(int i=0;i<n;i++)    cin>>w[i]>>v[i];
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<=W;j++)
        {
            if(j<w[i])  dp[i][j]=dp[i+1][j];
            else    dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
        }
    }
    cout<<dp[0][W];
    return 0;
}

Measured memory_bytes: 80128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ll x, k, d, ans = -1;
  cin >> x >> k >> d;
  x = abs(x);

  if (d < ceil((double)x / k)) {
    ans = x - k * d;
    cout << ans << endl;
    return 0;
  }

  ll t1 = abs(x - d * floor(x / d));
  ll t2 = min(abs(x - d * (floor(x / d) + 1)), abs(x - d * (floor(x / d) - 1)));

  if ((abs((ll)floor(x / d))) % 2 == k % 2 || floor(x / d) + 1 > k)
    ans = t1;
  else
    ans = t2;

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>

int		main()
{
	int		a;
	int		b;

	scanf("%d %d\n", &a, &b);
	if (a <= b)
	{
		while (b)
		{
			printf("%d", a);
			b--;
		}
	}
	else
	{
		while (a)
		{
			printf("%d", b);
			a--;
		}
	}
	printf("\n");
	return (0);
}


Measured memory_bytes: 128
from statistics import mean, median,variance,stdev
import sys
import math
import fractions

def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

x = ip()                              #入力整数1つ
#x,y= (int(i) for i in input().split())      #入力整数横2つ
#x,y,z = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#x = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列

#jの変数はしようできないので注意
a = []
a.append(x)
num =1
while True:
    num+=1
    if x%2:
        x = (3*x)+1
    else: x//=2
    if x in a:
        print(num)
        exit(0)
    a.append(x)

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

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

long long t;
  if(n==1)cout << k << endl;
  else{
    t=k;
  for(int i=1;i<n;i++){
    t*=k-1;
  }
    cout << t << endl;
  }

}

Measured memory_bytes: 3600
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <string>
#include <queue>
#include <vector>
using namespace std;

int NIL = -1;

struct Node {
	int parent;
	int left;
	int right;
};

Node T[100000];
int n, D[100000];

void print(int u) {
	cout << "node " << u << ": ";
	cout << "parent = " << T[u].parent << ", ";
	cout << "depth = " << D[u] << ", ";

	if (T[u].parent == NIL) cout << "root, ";
	else if (T[u].left == NIL) cout << "leaf, ";
	else cout << "internal node, ";

	cout << "[";
	for (int i = 0, c = T[u].left; c != NIL; i++, c = T[c].right) {
		if (i) cout << ", "; 
		cout << c;
	}

	cout << "]" << endl;
}

void rec(int u, int p) {
	D[u] = p;
	if (T[u].right != NIL) rec(T[u].right, p);
	if (T[u].left != NIL) rec(T[u].left, p + 1);
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++) T[i].parent = T[i].left = T[i].right = NIL;

	int id, k, c, l = 0;
	for (int i = 0; i < n; i++) {
		cin >> id >> k;

		for (int j = 0; j < k; j++) {
			cin >> c;
			if (j == 0) {
				T[id].left = c;
			}
			else {
				T[l].right = c;
			}

			l = c;
			T[c].parent = id;
		}
	}

	int r;
	for (int i = 0; i < n; i++)
		if (T[i].parent == NIL) r = i;

	rec(r, 0);

	for (int i = 0; i < n; i++) print(i);
}



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

int main() {
	int c[3][3];
	bool flag=true;
	for(int i = 0;i<3;i++)
		for(int j = 0;j<3;j++)
			cin >> c[i][j];
	
	for(int i = 0;i<3;i++){
		c[i][1] -= c[i][0];
		c[i][2] -= c[i][0];
		c[i][0] -= c[i][0];
	}
	for(int i = 0;i<3;i++){
		if(c[0][i] != c[1][i] || c[1][i] != c[2][i])
			flag=false;
	}
	if(flag)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

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

using namespace std;

#define FOR(i,k,n) for(int i=k;i<n;i++)
#define FORR(i,k,n) for(int i=k;i<=n;i++)
#define scan(a) scanf("%d",&a)
#define scann(a,b) scanf("%d%d",&a,&b)
#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define mst(a,n)  memset(a,n,sizeof(a))
#define ll long long
#define N 10
#define mod 1000000007
#define INF 0x3f3f3f3f

const double eps=1e-8;
const double pi=acos(-1.0);

int n,m;
vector<int> g[N];
int vis[N];
int ans;

void Dfs(int u)
{
    int j=1;
    for(;j<=n;j++)
    {
        if(!vis[j]) break;
    }
    if(j>n)
    {
        ans++;
        return ;
    }
    for(int i=0;i<g[u].size();i++)
    {
        if(!vis[g[u][i]])
        {
            vis[g[u][i]]=1;
            Dfs(g[u][i]);
            vis[g[u][i]]=0;
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    scann(n,m);
    int u,v;
    for(int i=0;i<m;i++)
    {
        scann(u,v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vis[1]=1;
    Dfs(1);
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
/// You just can't beat the person who never gives up
/// ICPC next year

///#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6+5 ;

int n ;
string str ;
priority_queue<pair<int,pair<int,int>>> neg ;
priority_queue<pair<int,int>> pos ;
int main(){
    cin >> n ;
    for(int i=0;i<n;++i){
        cin >> str ;
        int o = 0 ,need = 0 ;
        for(char ch:str){
            if(ch=='(') ++o ;
            else --o ;
            need = min(need,o);
        }
        if(o>=0) pos.push({need,o});
        else neg.push({-need+o,{-need,o}});
    }
    int cur = 0 ;
    while(pos.size()){
        int need = -pos.top().first ;
        int add = pos.top().second ;
        pos.pop();
        if(need>cur) return cout << "No",0 ;
        cur += add ;
    }
    while(neg.size()){
        int need = neg.top().second.first ;
        int add = neg.top().second.second ;
        neg.pop();
        if(need>cur) return cout << "No",0 ;
        cur += add ;
    }
    puts(cur?"No":"Yes");
    return 0;
}


Measured memory_bytes: 13040
import java.util.Arrays;
import java.util.Scanner;

public class Main {

		public static void main(String[] args) {
			int []ThreeNumbers;
			ThreeNumbers = new int[3];

			Scanner scan = new Scanner(System.in);
			for (int i = 0; i < 3; i++) {
				ThreeNumbers[i] = scan.nextInt();
			}

			Arrays.sort(ThreeNumbers);
		System.out.println(ThreeNumbers[0] + " " + ThreeNumbers[1] + " " + ThreeNumbers[2]);

	}

}

Measured memory_bytes: 26188
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define F0(i,n) for (int i = 0; i < n; i++)
#define F1(i,n) for (int i = 1; i <= n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const double eps = 1e-10;
const int inf = 1000000009;
int i, j, k, m, n, l;
int ans;

int main() {
	//freopen("x.in", "r", stdin);
	cin >> n;
	string s, t;
	cin >> s >> t;

	for (int i = n; i >= 0; i--)
	if (t.substr(0, i) == s.substr(n - i)) {
		cout << 2 * n - i << endl;
		break;
	}

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
#define fst first
#define snd second
using ll = long long;
using I = pair<int, int>;

int main() {
  ll N, Y;
  while (cin >> N >> Y) {
    ll t = Y / 1000 - N;
    ll ax = -1, ay = -1, az = -1;
    ll mk = -2 * t / 9;
    for (ll dk = -5; dk <= 5; dk++) {
      ll k = mk + dk;
      ll x = 4 * k + t;
      ll y = -9 * k - 2 * t;
      if (x >= 0 && y >= 0 && x + y <= N) {
        ax = x;
        ay = y;
        az = N - x - y;
      }
    }
    cout << ax << " " << ay << " " << az << endl;
  }
  return 0;
}


Measured memory_bytes: 256