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

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

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

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//grobal variable
//------------------------------------------
int N,M;
VI Vec;

//動的計画法で役に立つ関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int N, W; cin>>N>>W;

    VI weight(N), value(N);
    REP(i, N)
    {
        cin >> weight.at(i) >> value.at(i);
    }

    vector<vector<long long> > dp(N+1, vector<long long>(W+1, 0));

    REP(i, N)
    {
        FOR(sum_w, 1, W+1)
        {
            if (sum_w >= weight.at(i)) dp.at(i+1).at(sum_w)=dp.at(i).at(sum_w-weight.at(i)) + value.at(i);
            chmax(dp.at(i+1).at(sum_w),dp.at(i).at(sum_w));
        }
    }
    
    cout << dp.at(N).at(W) << endl;

    return 0;
}



Measured memory_bytes: 80256
import sys

N = int(sys.stdin.readline().rstrip())

maxs = []
mins = []

for _ in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    maxs.append(b)
    mins.append(a)

maxs.sort()
mins.sort()

if N % 2 == 1:
    mid = (N + 1) // 2 - 1
    ans = maxs[mid] - mins[mid] + 1
else:
    mid = N // 2
    ans = (maxs[mid - 1] + maxs[mid] - mins[mid - 1] - mins[mid] + 1)

print(ans)

Measured memory_bytes: 25380
#include <stdio.h>

#define INF 10000000

int main( void ) {
	int i, j, n, m, num[ 2 ][ 100 ], sum[ 2 ], min[ 2 ], diff;

	while ( scanf( "%d %d", &n, &m ), n ) {
		sum[ 0 ] = sum[ 1 ] = 0;
		for ( i = 0; i < n; i++ ) {
			scanf( "%d", num[ 0 ] + i );
			sum[ 0 ] += num[ 0 ][ i ];
		}
		for ( i = 0; i < m; i++ ) {
			scanf( "%d", num[ 1 ] + i );
			sum[ 1 ] += num[ 1 ][ i ];
		}

		if ( sum[ 0 ] + sum[ 1 ] & 1 ) {
			puts( "-1" );
			continue;
		}

		diff = ( sum[ 0 ] - sum[ 1 ] ) / 2;
		min[ 0 ] = min[ 1 ] = INF;
		for ( i = 0; i < n; i++ )
			for ( j = 0; j < m; j++ )
				if ( num[ 0 ][ i ] - num[ 1 ][ j ] == diff )
					if ( num[ 0 ][ i ] + num[ 1 ][ j ] < min[ 0 ] + min[ 1 ] ) {
						min[ 0 ] = num[ 0 ][ i ];
						min[ 1 ] = num[ 1 ][ j ];
					}

		if ( min[ 0 ] == INF )
			puts( "-1" );
		else
			printf( "%d %d\n", min[ 0 ], min[ 1 ] );
	}

	return 0;
}

Measured memory_bytes: 612
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>
#include <cstring>
#include <iterator>
#include <map>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define eb emplace_back
#define el '\n'
typedef  long long  ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<bool> vb;


const int mod=1000000007;
//const int mod=998244353;



int main()
{   ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll t,n,m,k,q,x,a,b,c,d,y,l,r;
    cin >> n;
    ll dp[1<<n];
    memset(dp,0,sizeof(dp));
    int v[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> v[i][j];
        }
    }
    for(int i=0; i<n; i++){
        if(v[0][i]){
            dp[(1<<i)]=1;
        }
    }
    for(int i=1,cnt; i<(1<<n); i++){
        cnt=__builtin_popcount(i);
        if(dp[i]!=0){
            for(int j=0; j<n; j++){
                if(!((i>>j)&1)&&v[cnt][j]){
                    dp[i^(1<<j)]+=dp[i];
                    dp[i^(1<<j)]%=mod;
                }
            }
        }
    }
    cout << dp[(1<<n)-1] << el;

    return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll num = 100;
    ll day = 0;
    ll x; cin >> x;
    while (num < x) {
        day++;
        num = (ll)((double)num * 1.01);
    }
    cout << day << endl;
    return 0;
}

Measured memory_bytes: 3624
class Node_information():
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.depth = 0
        self.type = ""
        self.child = list()

def get_tree_id_child_and_parent(tree_id, tree_k, tree_information, node_information):
    for j in range(tree_k):
        tree_information[tree_id].child.append(node_information[j+2])
        tree_information[node_information[j+2]].parent = tree_id

def get_tree_id_type(number_of_child):
    if number_of_child == 0:
        return "leaf"
    else:
        return "internal node"

def depth_search(tree_information, now_depth, now_id):
    tree_information[now_id].depth = now_depth
    for i in range(len(tree_information[now_id].child)):
        depth_search(tree_information, now_depth+1,tree_information[now_id].child[i])
    
def print_tree_information(tree_information, N):
    for i in range(N):
        print("node {}: parent = {}, depth = {}, {}, [".format(tree_information[i].id,tree_information[i].parent,tree_information[i].depth,tree_information[i].type),end="")
        for j in range(len(tree_information[i].child)):
            if j != len(tree_information[i].child) - 1:
                print("{},".format(tree_information[i].child[j]),end=" ")
            else: 
                print("{}".format(tree_information[i].child[j]),end="")
        print("]")


def main():
    N = int(input())
    tree_information = list()
    for i in range(N):
        tree_information.append(Node_information())
    for i in range(N):
        node_information = [int(i) for i in input().split()]
        tree_id = node_information[0]
        tree_k = node_information[1]
        tree_information[tree_id].id = node_information[0]
        get_tree_id_child_and_parent(tree_id, tree_k, tree_information, node_information)
        tree_information[tree_id].type = get_tree_id_type(len(tree_information[tree_id].child))
    for i in range(N):
        if tree_information[i].parent == -1:
            tree_information[i].type = "root"
            depth_search(tree_information,0,i)
    print_tree_information(tree_information, N)

if __name__ == "__main__":
    main()


Measured memory_bytes: 40176
#include <stdio.h>
int main() {
    int A1, A2, A3;
    scanf("%d %d %d", & A1, & A2, & A3);
  if (A1 + A2 + A3 >= 22)
  {printf("bust");}
  else{
      printf("win");
  }
  return 0;
}



Measured memory_bytes: 2148
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>

using namespace std;
typedef long long ll;

int main() {
	int N; cin >> N;
	vector<ll> H(N);
	for (int i = 0; i < N; i++) cin >> H[i];
	int ans = 0,cnt=0;
	for (int i = 0; i < N-1; i++) {
		if (H[i] >= H[i + 1]) cnt++;
		else cnt = 0;
		ans = max(ans, cnt);
	}
	cout << ans << endl;
}


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

double getP(const std::vector<double> &probabilities) {
  std::vector<double> dp_faceside(probabilities.size() + 1, 0.0);
  dp_faceside[0] = 1.0;

  for (const auto &prob : probabilities) {
    double total = 0;
    for (int i = static_cast<int>(dp_faceside.size()) - 1; i >= 1; --i) {
      dp_faceside[i] = dp_faceside[i] * (1.0-prob) + dp_faceside[i - 1] * prob;
      total += dp_faceside[i];
    }
    dp_faceside[0] *= (1.0 - prob);
    total += dp_faceside[0];
  }
  
  double result = 0.0;
  int border = (static_cast<int>(probabilities.size()) + 1) / 2;
  for (int i = static_cast<int>(dp_faceside.size()) - 1; i >= border; --i) {
    result += dp_faceside[i];
  }
  return result;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<double> probs(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> probs[i];
  }
  std::cout << std::fixed << std::setprecision(10) << getP(probs) << std::endl;
  return 0;
}


Measured memory_bytes: 256
import sys
import os
import math
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
#大きいものから取り出したいので-1倍してqueueに入れる

Q = []
for a in A:
    heapq.heappush(Q,-a)

for i in range(M):
    first = -heapq.heappop(Q)
    first = first//2
    heapq.heappush(Q,-first)

print(-sum(Q))

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int n;
    cin >>n;
    rep(q,n)
    {
        int r,t;
        cin >>r >>t;

        vector<int> ans;

        if(r%100==0)
        {
            if(t%30==0)
            {
                //?¨???¬??????
                ans.pb((t/30)*5 + r/100);
            }
            else
            {
                //?????§??????
                ans.pb((t/30)*5 + r/100);
                ans.pb((t/30+1)*5 + r/100);
            }
        }
        else
        {
            if(t%30==0)
            {
                //????????????
                ans.pb((t/30)*5 + r/100);
                ans.pb((t/30)*5 + r/100+1);
            }
            else
            {
                //??????????????´
                ans.pb((t/30)*5 + r/100);
                ans.pb((t/30)*5 + r/100+1);
                ans.pb((t/30+1)*5 + r/100);
                ans.pb((t/30+1)*5 + r/100+1);
            }
        }


        rep(i,ans.size())
        {
            if(i) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

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

using ll = long long;

template<typename T>
T gcd(T a, T b)
{
	if (a < b)	return gcd(b, a);
	T r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

template<typename T>
T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

template<typename T>
T ext_gcd(T a, T b, T& x, T& y)
{
	x = 1;
	y = 0;
	T x0 = 0, y0 = 1;
	while (b != 0)
	{
		T q = a / b;
		a -= q * b;
		swap(a, b);
		x -= q * x0;
		swap(x, x0);
		y -= q * y0;
		swap(y, y0);
	}
	return a;
}

template<typename T>
T inv_mod(T a, T mod)
{
	T t1, t2;
	ext_gcd(a, mod, t1, t2);
	t1 %= mod;
	if (t1 < 0)		t1 += mod;
	return t1;
}

template<typename T>
T combination_large(T n, T k, T mod)
{
	if (n < k || n < 0 || k < 0)	return 0;
	vector<T> inv(n + 1, 1), fact(n + 1, 1), fact_inv(n + 1, 1);
	for (T i = 2; i <= n; ++i)
	{
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fact[i] = (fact[i - 1] * i) % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

template<typename T>
T combination(T n, T k, T mod = 1)
{
	vector<vector<T>> table(n + 1, vector<T>(k + 1, 1));
	for (T i = 1; i <= n; ++i)
	{
		table[i][0] = 1;
		for (T j = 1; j <= n; ++j)
		{
			table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;
		}
	}
}


int main(int, char**)
{
	std::string S;
	std::cin >> S;
	std::string T;
	std::cin >> T;

	cout << T << S << endl;

	return 0;
}


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

signed main() {
	ll K, A, B; cin >> K >> A >> B;
	if (B - A <= 2)cout << K + 1 << endl;
	else {
		if (K <= A - 1)cout << K + 1 << endl;
		else {
			K -= A - 1;
			ll ans = A;
			ans += K / 2 * (B - A);
			if (K % 2 == 1)ans++;
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
  int N;
  cin >> N;
  int arr[N];
  for (int i = 0; i < N; i++) {
    cin >> arr[i];
  }
  sort(&arr[0], &arr[N]);
  cout << arr[N / 2] - arr[N / 2 - 1];
  return 0;
}

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

int main() {
  ll n;
  cin >> n;
  ll ans = 1e18;
  for (ll i = 1; i*i <= n; i++) {
    if (n % i != 0) continue;
    ans = min(i+n/i-2, ans);
  }
  cout << ans << endl;
  return 0;
}


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

def solve():
    N = int(input())
    D = list(map(int, input().split()))
    D.sort()

    """
    1 4 4 | 6 7 9　OK

    1 4 4 | 4 7 9　だめ

    1 2 3 | 3 7 9  だめ
    """

    if D[int(N//2)-1] == D[int(N//2)]:
        print(0)
        return
    
    ans = D[int(N//2)] - D[int(N//2)-1]

    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 14428
a,b=map(int,input().split())
d=".#"*(a-1)
s=".#"*(b-1)
print(100,100)
for i in range(100):
    if i<50:
        if i%2==0:
            if len(d)>0:
                if len(d)>99:
                    print(d[:100])
                    d=d[100:]
                else:
                    print(d+"#"*(100-len(d)))
                    d=""
            else:
                print("#"*100)
        else:
            print("#"*100)
    else:
        if i%2==1:
            if len(s)>0:
                if len(s)>99:
                    print(s[:100])
                    s=s[100:]
                else:
                    print(s+"."*(100-len(s)))
                    s=""
            else:
                print("."*100)
        else:
            print("."*100)

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

const int maxn = 200005;
const int maxd = 29;

int n, t;
int a[maxn], x[maxn], res[maxn];

signed main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) 
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i)
		x[i] = x[n - i + 1] = a[i] ^ a[n - i + 1];
	for (int i = 1; i <= n / 2; ++i)
		t ^= x[i];
	for (int i = 1; i <= n / 2; ++i) {
		t ^= x[i] ^ x[i - 1];
		res[i] = t ^ a[n - i + 1];
		res[n - i + 1] = x[i] ^ res[i];
	}
	for (int i = 1; i <= n; ++i)
		printf("%d ", res[i]);
	printf("\n");
}


Measured memory_bytes: 5992
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<string>
#include<cassert>
using namespace std;
#define N 4
#define N2 16
#define LIMIT 100

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char dir[4] = {'r', 'u', 'l', 'd'};
int MDT[N2][N2];

struct Puzzle { int f[N2], space, MD; };

Puzzle state;
int limit;
int path[LIMIT];

int getAllMD(Puzzle pz) {
  int sum = 0;
  for ( int i = 0; i < N2; i++ ) {
    if ( pz.f[i] == N2 ) continue;
    sum += MDT[i][pz.f[i] - 1];
  }
  return sum;
}

bool isSolved() {
  for ( int i = 0; i < N2; i++ ) if ( state.f[i] != i + 1 ) return false;
  return true;
}


bool dfs(int depth, int prev) {
  if ( state.MD == 0 ) return true;
  if ( depth + state.MD > limit ) return false;

  int sx = state.space / N;
  int sy = state.space % N;
  Puzzle tmp;

  for ( int r = 0; r < 4; r++ ) {
    int tx = sx + dx[r];
    int ty = sy + dy[r];
    if ( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
    if ( max(prev, r)-min(prev, r) == 2 ) continue;
    tmp = state;
    state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];
    state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];
    swap(state.f[tx * N + ty], state.f[sx * N + sy]);
    state.space = tx * N + ty;
    if ( dfs(depth + 1, r) ) { path[depth] = r; return true; }
    state = tmp;
  }

  return false;
}

string iterative_deepening(Puzzle in) {
  in.MD = getAllMD(in);

  for ( limit = in.MD; limit <= LIMIT; limit++ ) {
    state = in;
    if ( dfs(0, -100) ) {
      string ans = "";
      for ( int i = 0; i < limit; i++ ) ans += dir[path[i]];
      return ans;
    }
  }

  return "unsolvable";
}

int main() {
  for ( int i = 0; i < N2; i++ )
    for ( int j = 0; j < N2; j++ )
      MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);

  Puzzle in;

  for ( int i = 0; i < N2; i++ ) {
    cin >> in.f[i];
    if ( in.f[i] == 0 ) {
      in.f[i] = N2;
      in.space = i;
    }
  }
  string ans = iterative_deepening(in);
  cout << ans.size() << endl;

  return 0;
}


Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long ll;
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;}

int main(){
   int a,b;
   cin >> a >> b;
   int sum=0;
   if(b==1){
      cout << 0 << endl;
      return 0;
   }
   for(int i=1;;i++){
     sum+=a;
     if(sum>=b){
        cout << i << endl;
        return 0;
     }
     sum--;
   }
   return 0;
}

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

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int m, n;
  cin >> m >> n;
  vector<int> dp(m+1, 1e9);
  dp[0] = 0;
  vector<int> a(n),b(n);
  for (int j = 0; j < n; j++) cin >> a[j] >> b[j];

  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < n; j++) {
      dp[i] = min(dp[i], dp[max(i-a[j],0)]+b[j]);
    }
  }
  cout << dp[m] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ip pair<int, int>

using namespace std;
int n,m;
vector<pair<int, int>>v;
bool comp(const ip a, const ip b)
{
	return a.second*1.0/a.first>b.second*1.0/b.first;
}

bool check(int p)
{
    int c = 0, k=0;
    for(int i=0;i<n;i++)
    {
        
        int x = m-c;
        if(v[i].second <=x)
        {
            c+=v[i].second;
            k+=v[i].second * v[i].first;
        }
        else{
            c+=x;
            k+=x*v[i].first;
        }
        if(c>=m)
            break;
    }

    if(k<=p)
        return 1;
    return 0;
}

signed main()
{
	
	cin>>n>>m;
	int a[n], b[n];
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
		v.push_back(make_pair(a[i], b[i]));
	}
	sort(v.begin(), v.end());
	//for(int i=0;i<n;i++)
	//cout<<v[i].first<<" "<<v[i].second<<endl;
    int s = 0, e = (m *v[n-1].first);
    int ans = 0;

    while(s<=e)
    {
        int mid = (s+e)/2;
        //cout<<s<<" "<<mid<<" "<<e<<endl;
        if(check(mid))
        {
            ans = mid;
            e = mid-1;
        }
        else
            s=mid+1;
    }

	cout<<ans<<endl;
}

Measured memory_bytes: 3444
import numpy as np

N,D = list(map(int,input().split()))

X = []

for i in range(N):
    X.append(list(map(int,input().split())))
count=0
for i in range(N-1):
    for j in range(i+1,N):
        s = np.linalg.norm(np.array(X[i])-np.array(X[j]))
        if s==int(s):
            count+=1

print(count)

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

struct UnionFind {
    vector<int> d;
    UnionFind(int n) : d(n, -1) {}
    void unite(int a, int b) {
        a = root(a);
        b = root(b);
        if (a != b) {
            if (size(a) > size(b)) swap(a, b);
            d[b] += d[a];
            d[a] = b;
        }
    }
    int root(int a) {
        if (d[a] < 0) return a;
        return d[a] = root(d[a]);
    }
    int size(int a) {
        return -d[root(a)];
    }
};

signed main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> E(M);
    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        E[i] = {a, b};
    }
    int ans = 0;
    rep(i, 0, M) {
        UnionFind uf(N);
        rep(j, 0, M) {
            if (i == j) continue;
            int a, b;
            tie(a, b) = E[j];
            uf.unite(a, b);
        }
        if (uf.size(0) != N) {
            ans++;
        }
    }
    cout << ans << endl;
}




Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);

ll mod_pow(ll x, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x % mod;
		x = x * x % mod; n >>= 1;
	}
	return res;
}
struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n % mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a * a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}


void solve() {
	int n; cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			ans += j;
		}
	}
	cout << ans << "\n";
}



signed main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)
	solve();
		return 0;
}


Measured memory_bytes: 20024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ai = a[n-1];
    int aj;
    double m = 1000000000.0;
    for (int i = 0; i < n - 1; i++)
    {
        if (abs(ai/2.0-a[i]) < m) {
            aj = a[i];
            m = ai/2.0-a[i];
        }
    }
    cout << ai << " " << aj << endl;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
//const ll mod=1e9+7;
const ll mod=998244353;
const ll inf=1LL<<61;

ll mpow(ll x, ll n) {
  ll ans=1;
  while(n>0) {
    if(n&1) {
      ans=ans*x%mod;
    }
    x=x*x%mod;
    n>>=1;
  }
  return ans;
}

int main() {
  ll n,s;
  cin >> n >> s;
  vec a(n);
  for(ll i=0;i<n;i++) cin >> a[i];
  mat dp(n+1,vec(s+1));
  dp[0][0]=1;
  for(ll i=0;i<n;i++) {
    for(ll j=s;j>=0;j--) {
      (dp[i+1][j]+=dp[i][j]*2)%=mod;
      if(j-a[i]>=0) {
        (dp[i+1][j]+=dp[i][j-a[i]])%=mod;
      }
    }
  }
  cout << dp[n][s] << endl;
}

Measured memory_bytes: 73748
#include<stdio.h>
int main()
{
char str[4];
scanf("%s",str);
if(str[1]==82)
{
str[1]=66;
}
else if(str[1]==66)
{
str[1]=82;
}
for(int i=0;i<3;i++)
{
printf("%c",str[i]);
}
return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
long long  n,a[100005],ans=0;
 main (){
     std::cin>>n;
     for(long long  i=1;i<=n;i++){
        std::cin>>a[i];
     }
     for (int i=1;i<=n;i++){
        ans+= (i%2==1) ? a[i]:-a[i];
     }
     std::cout<<ans<<" ";
     for (int i=1;i<=n-1;i++){
        ans=a[i]*2-ans;
        std::cout<<ans<<" ";
     }
 }


Measured memory_bytes: 2048
n,m=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lst=prime_factorize(m)
if m!=1:
    li=[1]
else:
    li=[0]
for i in range(1,len(lst)):
    if lst[i]==lst[i-1]:
        li[-1]+=1
    else:
        li.append(1)
ans=1
for u in li:
    a=n-1+u
    x=cmb(a,u)%mod
    ans=(ans*x)%mod
print(ans)

Measured memory_bytes: 3572
/*
                                Shahriar Hasan
                          "University of Chittagong"
                                CSE 18 Batch
*/
#include <bits/stdc++.h>
using namespace std;

#define nln puts("")                    // newline
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))    //max/min from 3 input

#define even(x) x%2==0                  //even odd
#define odd(x) x%2!=0

#define PI acos(-1)                     // constant + math
#define lcm(a,b) (a*b/gcd(a,b))

#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)          // algorithm habijabi
#define srt(a,n) sort(a,a+n)
#define srtt sort(a.begin(),a.end())
#define cnt(x) count(a,a+n,x)
#define F first
#define S second
#define all(p) p.begin(),p.end()

#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(ull i=1;i<=n;i++)         //loop
#define forr(i,n) for(int i=n-1;i>=0;i--)
#define mem(a,b) memset(a, b, sizeof(a))
#define fill(a,b) fill(a.begin(),a.end(),b)
#define fill_n(a,n,b) fill_n(a.begin(),n,b)
                        //input
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define print0(a) for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
#define print1(a) for(int i=1;i<=a.size();i++)cout<<a[i]<<endl;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ll> vl;
typedef pair<int,int> pii;           // datatype
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;



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

ull power(int a,int n)              // to the power
{ll multi=1;for(int i=1;i<=n;i++)multi=multi*a; return multi;}
bool isPrime(ull n)                 // prime number check
{if(n==2 | n==3)return true;else{ull m=power(2,n-1);if(m%n==1 && n%2==1)return true;else return false;}}
vi getdiv(ll n){vi div;int i;
    for(i=1;i*i<n;i++)
    {if(n%i==0){div.pb(i);div.pb(n/i);}}if(i*i==n)div.pb(i);            // divisor nirnoy kora
    //sort(div.begin(),div.end());
    return div;}
bool isPalindrome(int n){int num=n,sum=0,mod;
    while(n){mod=n%10;n=n/10;sum=sum*10+mod;}
    if(sum==num)return true;else return false;}


int main()
{
    long long n;
    optimize()
    cin >> n;
    vi v;
    int root=sqrt(1.0*n);
    //cout << root << endl;
    for1(i,root+1)
    {
        if(n%i==0)v.pb(i);
    }
    int ans=*(max_element(all(v)));
    if(v.empty())cout << n-1 << endl;
    else
        cout << ans+n/ans-2 << endl;
    return 0;
}



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

using namespace std;

void Main() {
    string S;
    cin >> S;

    int nbConn = 1;
    char prev;
    for (int i = 0; i < S.size(); ++i) {
        if (i == 0) {
            prev = S[i];
            continue;
        }
        char curr = S[i];
        if (prev != curr) {
            ++nbConn;
        }
        prev = curr;
    }
    cout << (nbConn - 1) << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int n,c,k;
    int t;
    Scd3(n,c,k);

    priority_queue<int,vector<int>,greater<int>> q;
    Rep(i,n){
        Scd(t);
        q.push(t);
    }

    int cnt = 0;
    int ans = 0;
    while( !q.empty() ){
        if( !cnt ){
            t = q.top();
            cnt++;
            q.pop();
        }else{
            if( t + k >= q.top() ){
                cnt++;
                q.pop();
            }
            else{
                cnt = 0;
                ans++;
            }
        }
        if( cnt == c ){
            cnt = 0;
            ans++;
        }
    }

    if( cnt ) ans++;
    printf ("%d\n", ans);
    return 0;
}



Measured memory_bytes: 892
#include <cstdio>
#include <cstdlib>
#define FIELD_SIZE 21

int main () {
  while ( 1 ) {
    int n;
    scanf( "%d", &n );
    if ( !n ) { return EXIT_SUCCESS; }
    
    int field[ FIELD_SIZE ][ FIELD_SIZE ] = {0};
    for ( int i = 0; i < n; i++ ) {
      int x, y;
      scanf( "%d%d", &x, &y );
      field[ y ][ x ] = 1;
    }

    int m;
    char dir[ 2 ];
    int len;
    int px = 10, py = 10;
    int get_num = 0;
    scanf( "%d", &m );
    if ( field[ py ][ px ] ) {
      get_num++;
      field[ py ][ px ] = 0;
    }

    for ( int i = 0; i < m; i++ ) {
      scanf( "%s%d", dir, &len );
      for ( int j = 0; j < len; j++ ) {
          switch ( dir[ 0 ] ) {
            case 'W':
            px--;
            break;
          case 'S':
            py--;
            break;
          case 'E':
            px++;
            break;
          case 'N':
            py++;
            break;
        }
//        printf( "%d, %d: %d\n", px, py, field[ py ][ px ] );
        if ( field[ py ][ px ] ) {
          get_num++;
          field[ py ][ px ] = 0;
        }
      }
    }
    
    puts( get_num == n ? "Yes" : "No" );
  }
}

Measured memory_bytes: 1012
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key, find_by_order

#define ll long long
#define pi pair<int, int>
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int mxn = 1e6 + 5;
const ll MOD =  1e9 + 7;
int arr[mxn];
int n, m, k, q;
string s, t;

void solve(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            ans += arr[i - 1] - arr[i];
            arr[i] = arr[i - 1];
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}


Measured memory_bytes: 4364
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000009;
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a, b;
  long long c, d;
  long long lcm;
  long long ans;

  cin >> a >> b >> c >> d;
  
  ans = b - a;
  lcm = (c / __gcd(c, d)) * d;

  ans -= (((b / c) + (b / d)) - (b / lcm)) - (((a / c) + (a / d)) - (a / lcm));
  
  if(a % c != 0 && a % d != 0)ans++;
  cout << ans << endl;
  return 0;
}




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

int main(){
	string str;
	cin>>str;
	int ans;
	if(str=="SSS")ans=0;
	else if(str=="SSR")ans=1;
	else if(str=="SRS")ans=1;
	else if(str=="RSS")ans=1;
	else if(str=="RRS")ans=2;
	else if(str=="RSR")ans=1;
	else if(str=="SRR")ans=2;
	else ans=3;
	cout<<ans<<endl;
	return 0; 
}

Measured memory_bytes: 3592
//ABC177_A
 
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		int D = sc.nextInt();
		int T = sc.nextInt();
		int S = sc.nextInt();
 
      	double ret = (double)D / (double)S;
      
		if(ret <= T){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		sc.close();
	}
}

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

class Main{
	public void run(){
		int n = ni();
		int k = ni();
		int ans = k;
		for(int i=1;i<n;i++)ans *= k - 1;
		out.println(ans);
	}

	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().run();
		out.flush();
	}

	public Main(){
	}

	int ni(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;	}

	long nl(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}

	double nd(){
		return Double.parseDouble(next());
	}

	String next(){
		int c;
		while(!isAlNum(c = read()));
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	String nextLine(){
		int c;
		while(!isAlNumOrSpace(c = read()));
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNumOrSpace(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
	private static boolean isAlNumOrSpace(int c){
		return isAlNum(c) || c == ' ' || c == '\t';
	}
	void debug(Object... os){
		out.println(Arrays.deepToString(os));
	}
}

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

int main() {
	
	string s;
	cin >> s;
	
	int ans = 0;
	int cnt = 0;
	rep(i, 10){
		if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T'){
			cnt++;
		}else{
			ans = max(ans, cnt);
			cnt = 0;
		}
	}
	ans = max(ans, cnt);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 764
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m,x=INTM()
    ca=[]
    for i in range(n):
        ca.append(LIST())
    inf=10**9
    ans=inf
    for i in range(2**n):
        bag=[]
        for j in range(n):
            if ((i>>j)&1):
                bag.append(ca[j])
        ms=[0]*(m+1)
        for k in bag:
            for l in range(1,m+1):
                ms[l]+=k[l]
        ms=ms[1:]
        flg=1
        #print(bag,ms)
        for j in range(m):
            if ms[j]<x:
                flg=0
        if flg==1:
            cost=0
            for k in bag:
                cost+=k[0]
            ans=min(ans,cost)
    
    if ans==inf:
        print(-1)
    else:
        print(ans)
    
    
if __name__ == '__main__':
    do()

Measured memory_bytes: 9264
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a, b, c, d;
  cin >> a;
  b = "Sunny"; c = "Cloudy"; d = "Rainy";
  if (a == b){
    cout << c << endl;
  }
  else if (a == c) {
      cout << d << endl;
  }
  else{
      cout << b << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
	main()
    {
      int d,t,s,x,y;
      	scanf("%d",&d);
      	scanf("%d",&t);
      	scanf("%d",&s);
      x=s*t;
      y=d-x;
      if(y<=0){
        printf("Yes");
      }
      else{
        printf("No");
      }
    }
    

Measured memory_bytes: 2148
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

void mod( ll &n, ll m=MOD ){ n%=m,n+=m,n%=m; }

const int MAXN = 1e5+5;
const ll INF = 1e12;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main() 
{
    fastio();

    ll n,cap;
    cin>>n>>cap;
    ll weight[n],val[n];
    ll val_sum = 0;
    for(int i=0;i<n;i++) cin>>weight[i]>>val[i],val_sum+=val[i];
    ll dp[n+1][val_sum+1];
    for(int i=0;i<n+1;i++)
    {
        for(int j=0;j<=val_sum;j++)
        {
            dp[i][j] = INF;
        }
    }
    //dp[i][j] = min weight with index till i and val j
    dp[0][0] = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=val_sum;j++)
        {
            dp[i+1][j] = dp[i][j];
            if( j-val[i] >= 0 )
                min_self( dp[i+1][j], weight[i] + dp[i][j-val[i]] );
        }
    }
    ll ans = 0;
    for(int j=val_sum;j>=0;j--)
    {
        if( dp[n][j] <= cap )
        {
            ans = j;
            break;
        }
    }
    cout<<ans,nl;
    return 0;
}

Measured memory_bytes: 79104
class MyClass():
    def main(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())
        
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        w = self.rec(m,self.A)
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 1:
            r1 = False
        else:
            r1 = self.rec(m,A[1:])

        m_new = m - A[0]
        if m_new == 0:
            r2 = True
        elif len(A) > 1 and min(A[1:]) <= m_new <= sum(A[1:]):
            r2 = self.rec(m_new,A[1:])
        else:
            r2 = False

        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Measured memory_bytes: 6404
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  string S,T,U;
  int A,B,count=0;;
  cin >> S >> T >> A >> B >> U;
  if(U.size()<=S.size()&&S.size()<=T.size()){
    for(int i=0;i<U.size();i++){
      if(U.at(i)==S.at(i))count++;
      if(U.at(i)==T.at(i))count--;
    }
  }
  else if(U.size()==S.size()) count++;
  else count--;
    
  if(0<count) cout << A-1 << " " << B << endl;
  else if(count<0) cout << A << " " << B-1 << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

bingos = []
for _ in range(3):
   bingo = [int(i) for i in input().split()]
   bingos.append(bingo)
  
N = int(input())

for i in range(N):
    n = int(input())
    for y in range(3):
        for x in range(3):
            if bingos[y][x] == n:
                bingos[y][x] = None

y_cnt = [0] * 3
x_cnt = [0] * 3
result = False
for y in range(3):
    for x in range(3):
        if bingos[y][x] is None:
            x_cnt[y] += 1
            y_cnt[x] += 1

if 3 in y_cnt or 3 in x_cnt:
    print('Yes')
elif bingos[0][0] is None and bingos[1][1] is None and bingos[2][2] is None:
    print('Yes')
elif bingos[0][2] is None and bingos[1][1] is None and bingos[2][0] is None:
    print('Yes')
else:
    print('No')

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

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    for(int i = 0; i < n - i - 2; i++){
        if(s[i] != s[n - i - 2]){
            cout << -1 << endl;
            return 0;
        }
    }
    if(s[0] == '0' || s[n - 1] == '1'){
        cout << -1 << endl;
        return 0;
    }
    int rootl = (n + 1) / 2 - 1, rooth = (n + 1) / 2 - 1;
    if(n % 2 == 0){
        cout << rooth + 1 << " " << rooth + 2 << endl;
        if(s[(n + 1) / 2 - 1] == '1') rooth = rooth + 1;
    }
    for(int i = (n + 1) / 2 - 2; i >= 0; i--){
        cout << i + 1 << " " << rootl + 1 << endl;
        cout << rooth + 1 << " " << n - i << endl;
        if(s[i] == '1'){
            rootl = i;
            rooth = n - i - 1;
        }
    }
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INF 10000000000
#define mod 1000000007
typedef long long int ll;
int u(const void *a, const void *b){
    return *(ll*)a-*(ll*)b;
}
int d(const void *a, const void *b){
    return *(ll*)b-*(ll*)a;
}
int min(int a,int b){
  if(a>b)return b;
  return a;
}
int max(int a,int b){
  if(a>b)return a;
  return b;
}
int gcd(int a,int b){
  if(!b)return a;
  return gcd(b,a%b);
}
int kt(ll a){
  int sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
int ks(ll a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
int main(void){
  int n;
  scanf("%d",&n);
  int a[n][2];
  FOR(n){
    scanf("%d",&a[i][0]);
    a[i][1]=i+1;
  }
  qsort(a,n,sizeof(int)*2,u);
  FOR(n)PRN(a[i][1]);
  return 0;
}


Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define rg register
#define ll long long
#define LDB long double
#define ull unsigned long long
#define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt)
#define go(i,x,a) for(rg int i=a;i<x;i++)
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
using namespace std;

int n;

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

int main(){
	n=rd(); int fl=0;
	go(i,n+1,1){
		if(rd()%2 == 1){
			fl=1; break;
		}
	}
	if(fl) printf("first");
	else printf("second");
	return 0;
}//Faze


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

int main(){
  int a, b, c, d;
  cin>>a>>b>>c>>d;
  if(a+b<c+d)cout<<"Right"<<endl;
  else if(a+b==c+d)cout<<"Balanced"<<endl;
  else cout<<"Left"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}
char a[55][55];
int dx[] = {1,0,-1,0,1,1,-1,-1};
int dy[] = {0,1,0,-1,1,-1,-1,1};
int main()
{
	dhoom;
	int h , w;
	cin >> h >> w;
	for(int i = 1 ; i <= h ; i++)
		for(int j = 1 ; j <= w ; j++)	
			cin >> a[i][j];
	for(int i = 1; i <= h ; i++)
	{
		for(int j = 1 ; j <= w ; j++)
		{
			int cnt = 0;
			if(a[i][j] == '.')
			{
				for(int k = 0 ; k < 8 ; k++){
					if(a[i+dx[k]][j+dy[k]] == '#')
						cnt++;
				}
				cout << cnt;
			}
			else 
				cout << a[i][j];
			
		}
		cout << endl;
	}
	
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
s = [(0, n)]
ans = 0
while s:
    l, r = s.pop()
    if l == r:
        continue
    m = min(a[l:r])
    ans += m
    for i in range(l, r):
        a[i] -= m
    for i in range(l, r):
        if a[i] == 0:
            s.append((l, i))
            s.append((i + 1, r))
            break
print(ans)

Measured memory_bytes: 3064