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

using namespace std;


typedef long long LL;


const int N = 3010;


inline LL power(LL a, LL n, LL mod)
{
	LL Ans = 1;
	while (n)
	{
		if (n & 1) Ans = Ans * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return Ans;
}


int mod;


LL x[N], y[N];

LL num[N];


void Lagrange(int n)
{
	static LL tmp1[N], tmp2[N], tmp3[N];
	memset(tmp1, 0, sizeof(tmp1));
	memset(tmp2, 0, sizeof(tmp2));
	
	tmp1[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		tmp2[0] = (mod - x[i] * tmp1[0] % mod) % mod;
		for (int j = 1; j <= i; j++)
			tmp2[j] = (tmp1[j-1] + mod - x[i] * tmp1[j] % mod) % mod;
		for (int j = 0; j <= i; j++) tmp1[j] = tmp2[j];
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= n; j++) tmp2[j] = tmp1[j];
		for (int j = n; j >= 1; j--)
		{	tmp3[j-1] = tmp2[j];
			tmp2[j-1] = (tmp2[j-1] + tmp2[j] * x[i] % mod) % mod;
		}
		
		LL pro = 1; 
		for (int j = 1; j <= n; j++)
			if (i != j) pro = pro * ((x[i] - x[j] + mod) % mod) % mod;
		LL inv = power(pro, mod-2, mod) * y[i] % mod;
		
		for (int j = 0; j < n; j++)
			num[j] = (num[j] + tmp3[j] * inv % mod) % mod;
	}
}


int main()
{
	scanf("%d", &mod);
	
	for (int i = 1; i <= mod; i++)
		scanf("%lld", &y[i]), x[i] = i-1;
	
	Lagrange(mod);
	
	for (int i = 0; i < mod; i++)
		printf("%lld ", num[i]);
	puts("");
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  int score = 0;
  int groups = 0;
  REP(i,n-1){
    if(s[i] == s[i+1]){
      score++;
    }else{
      groups++;
    }
  }
  groups++;
  
  if(groups%2 == 1){
    int limit_ = groups/2;
    score += 2*min(limit_, k);
  }else{
    int limit_ = groups/2;
    if(limit_ <= k){
      score += 2*limit_ - 1;
    }else{
      score += 2*k;
    }
  }
  cout<<score<<endl;
  return 0; 
}

Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const int N = 1e5+10;

//head

int n;
int h[N];
int dp[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	rep(i, n) cin >> h[i];
	fill(dp+1, dp+n, INT_MAX);
	rep(i, n-1) {
		dp[i+2] = dp[i] + abs(h[i+2]-h[i]);
		chmin(dp[i+1], dp[i] + abs(h[i+1]-h[i]));
	}
	cout << dp[n-1] << endl;
}

Measured memory_bytes: 4372
import math
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

p = [0] * 3
Max = 0
for i in range(3) :
    for j in range(n) :
        p[i] += abs(x[j] - y[j]) ** (i+1)
        if abs(x[j] - y[j]) > Max :
            Max = abs(x[j] - y[j])
            
    print('{:.5f}'.format(p[i] ** (1/(i+1))))
print('{:.5f}'.format(Max))
            



Measured memory_bytes: 5700
#include <bits/stdc++.h>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    string s,t;
    cin>>s>>t;
    int ans=0;
    for (size_t i = 0; i < s.size(); i++)
    {
        if(s[i]!=t[i])
        ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3848
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    bool war = false;
    int n,m,X,Y;
    cin >> n >> m >> X >> Y;
    vector<int> x(n);
    REP(i, n) cin >> x[i];
    x.push_back(X);
    vector<int> y(m);
    REP(i, m) cin >> y[i];
    y.push_back(Y);
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    if (x[x.size()-1] < y[0]) cout << "No War" << endl;
    else cout << "War" << endl;
    

    //cout << ans << endl;
}

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

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define read()          freopen("in.txt","r",stdin)
#define write()         freopen("out.txt","w",stdout)
#define sf(n)           scanf("%d",&n)
#define sfd(n)          scanf("%lf",&n)
#define sl(x)           scanf("%I64d",&x)
#define sfl(n)          scanf("%lld", &n)
#define sfc(n)          scanf(" %c",&n)
#define sful(n)         scanf("%llu",&n)
#define ull             unsigned long long
#define endll           pf("\n")
#define pf              printf
#define PI              acos(-1.0)
#define eps             1e-12
#define mem(a,b)        memset(a,b,sizeof(a))
#define pb              push_back
#define xx              first
#define yy              second
#define pii             pair<int, int>
#define pll             pair<ll, ll>
#define MP make_pair
#define ll              long long
#define uniq(a)      a.erase(unique(a.begin(), a.end()), a.end())
#define cnd tree[idx]
#define lnd tree[idx<<1]
#define rnd tree[(idx<<1)+1]
#define lndp (idx<<1),(b),((b+e)>>1)
#define rndp ((idx<<1)+1),(((b+e)>>1)+1),(e)
#define inf 1999999999
#define MOD  1000000007
#define mod1 1000000009
#define var    int i,j,c=0,t,l,r,mid,z=0,k,x,y
#define aloc(n,t) ((t*)malloc((n)*sizeof(t)))

//int dx[8]={0,0,1,1,-1,-1,1,-1};  //8 direction
//int dy[8]={1,-1,1,-1,1,-1,0,0};
//int dx[4]={1,-1,0,0};  //4 direction
//int dy[4]={0,0,1,-1};

ll n,m,a[200005];
vector<ll> v[100005],g[100005];
int main()
{
    ll k;
    sfl(n);sfl(m);
    for(int i=1;i<=n;i++)sfl(a[i]);
    for(int i=1;i<=m;i++)
    {
        ll x,y;
        sfl(x);sfl(y);
        v[x].pb(y);
        v[y].pb(x);
    }
    ll ans =0;
    for(int i=1;i<=n;i++)
    {
        ll c =0;
        for(int j=0;j<v[i].size();j++)
        {
            c=max(c,a[v[i][j]]);
        }

        if(a[i]>c)
        {
            ans++;
        }
    }
    pf("%lld\n",ans);
}


Measured memory_bytes: 12764
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int age = sc.nextInt();
    if(age == 3 || age == 5 || age == 7){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
  }
}

Measured memory_bytes: 21716
from math import ceil

n, a, b = map(int, input().split())
hs = [int(input()) for _ in range(n)]


def defeatable(k):
    hb = [max([h - k * b, 0]) for h in hs]
    n_attack = sum([ceil(h / (a - b)) for h in hb])
    return n_attack <= k


l, r = 0, ceil(max(hs) / b)

while r - l > 1:
    m = (l + r) // 2

    if defeatable(m):
        r = m
    else:
        l = m

print(r)



Measured memory_bytes: 15140
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  int N;
  char S[101];
  int res=0;
  cin >> N>>S;

  int num=0;
  rep(i,N){
    if(S[i]=='I') {
      num++;
      res = max(res, num);
    }
    if(S[i]=='D'){
      num--;
      res = max(res, num);
    }
  }

  cout << res << endl;
}


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

using namespace std;

const int INF = 1145141919;

int main() {
    int a, b, m;
    cin >> a >> b >> m;

    int mina = INF, minb = INF;
    vector<int> p(a);
    for (int i = 0; i < a; i++) {
        cin >> p[i];
        mina = min(mina, p[i]);
    }
    vector<int> q(b);
    for (int i = 0; i < b; i++) {
        cin >> q[i];
        minb = min(minb, q[i]);
    }

    int ret = mina + minb;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        ret = min(ret, p[x - 1] + q[y - 1] - c);
    }
    cout << ret << endl;
    return 0;
}

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

ll inf=9223372036854775806;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n;
	cin>>n;
	if (n==22){
		cout<<"Christmas Eve Eve Eve";
	}
	else if (n==23){
		cout<<"Christmas Eve Eve";
	}
	else if (n==24){
		cout<<"Christmas Eve";
	}
	else {
		cout<<"Christmas";
	}
	return 0;
}

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

int main() {
	int m, t, p, r;
	while (cin >> m >> t >> p >> r) {
		if (m == 0) break;
		vector<pair<int, int>> cnt(55);
		for (int i = 0; i < t; i++) {
			cnt[i] = make_pair(0, i);
		}
		int time[55] = {};
		int pena[55][20] = {};
		for (int i = 0; i < r; i++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			b--;
			if (d == 0) {
				time[b] += a + 20 * pena[b][c];
				cnt[b].first++;
			}
			else {
				pena[b][c]++;
			}
		}
		sort(cnt.begin(), cnt.end());
		reverse(cnt.begin(), cnt.end());
		vector<vector<pair<int,int>>> ac(15);
		for (int i = 0; i < t; i++) {
			ac[cnt[i].first].push_back(make_pair(time[cnt[i].second],-cnt[i].second));
		}
		bool win = true;
		for (int i = p; i >= 0; i--) {
			if (ac[i].empty()) continue;
			sort(ac[i].begin(), ac[i].end());
			if (!win) cout << ",";
			if (win) win = false;
			cout << -ac[i][0].second +1;
			
			for (int j = 1; j < ac[i].size(); j++) {
				if (ac[i][j - 1].first == ac[i][j].first) {
					cout << "=";
				}
				else cout << ",";
				cout << -ac[i][j].second + 1;
			}
		}
		cout << endl;
	}
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin>>N;
  N = N % 10;
  if(N==2||N==4||N==5||N==7||N==9){
    cout<<"hon"<<endl;
  }else if(N==0||N==1||N==6||N==8){
    cout<<"pon"<<endl;
  }else if(N==3){
    cout<<"bon"<<endl;
  }  
}



Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) throws Exception {
        final Scanner scan = new Scanner(System.in);
        String str1 = scan.next();
        String str2 = scan.next(); 
        scan.close();

        if (str1.equals(str2.substring(0, str2.length()-1))) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

        
    }
}


Measured memory_bytes: 35484
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m;
const int maxn = 505;
int a[maxn][maxn];
typedef pair<int,int> pii;
#define f first
#define s second
int main(int argc, char const *argv[])
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n; ++i)
	{
		for(int j = 1;j <= m; ++j)
		{
			scanf("%d",&a[i][j]);
		}
	}
	vector<pii> vv;
	vector< pair<pii,pii> > v;
	for(int i = 1;i <= n; ++i)
	{
		if(i & 1)
		{
			for(int j = 1;j <= m; ++j)
			{
				vv.push_back({i,j});
			}
		}
		else
		{
			for(int j = m;j >= 1; --j)
			{
				vv.push_back({i,j});
			}
		}
	}
	for(int i = 1;i < vv.size(); ++i)
	{
		if(a[vv[i - 1].f][vv[i - 1].s] & 1)
		{
			v.push_back({vv[i - 1],vv[i]});
			++a[vv[i].f][vv[i].s];
		}
	}
	printf("%d\n",v.size());
	for(auto x : v)
	{
		printf("%d %d %d %d\n",x.f.f,x.f.s,x.s.f,x.s.s);
	}
	return 0;
}

Measured memory_bytes: 7152
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();

        String zenhan = s.substring(0, k-1);
        String komozi = s.substring(k-1 , k).toLowerCase();
        String kouhan = s.substring(k);

        System.out.println(zenhan + komozi + kouhan);





    }
}

Measured memory_bytes: 21204
from collections import defaultdict

MOD = 10 ** 9 + 7

N = int(input())


"""dp = dict()
for c1 in "ACGT":
    for c2 in "ACGT":
        for c3 in "ACGT":
            for c4 in "ACGT":
                s = c1 + c2 + c3 + c4
                if s[0:3] in ("AGC", "ACG", "GAC"):
                    continue
                if s[1:4] in ("AGC", "ACG", "GAC"):
                    continue
                if s in ("AGGC", "AGTC", "ATGC"):
                    continue

                dp[s] = 1"""

dp = {"TTT": 1}
for _ in range(N):
    new_dp = defaultdict(int)
    for s, count in dp.items():
        new_dp[s[1:] + 'A'] += count
        new_dp[s[1:] + 'T'] += count
        if s[1:] != "AC":
            new_dp[s[1:] + 'G'] += count
        if s not in ("AGG", "AGT", "ATG") and s[1:] not in ("AG", "GA"):
            new_dp[s[1:] + 'C'] += count

    dp = dict()
    for k, v in new_dp.items():
        dp[k] = v % MOD

print(sum(dp.values()) % MOD)

Measured memory_bytes: 3316
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[5];
int main()
{
	cin>>a[1]>>a[2]>>a[3];
	sort(a+1,a+4);
	cout<<a[1]+a[2]<<endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
st = []
for _ in range(n):
    a = input().split()
    a[1] = int(a[1])
    st.append(a)
x = input()

res = 0
s = False
for i in st:
    if i[0] == x:
        s = True
    elif s:
        res += i[1]

print(res)

Measured memory_bytes: 3064
import sys

N = int(input())
sum = 0

for i in range(1, N+1):
    if (N-i) % i == 0:
        m = int((N-i) / i)
        if(m <= i):
            print(sum)
            sys.exit()
        
        sum += m
    if((N-i)/i < i):
        print(sum)
        sys.exit()

Measured memory_bytes: 3060
#include <stdio.h>
int main(void)
{int num;
scanf("%d",&num);
int N=num;
int dig;
int sum=0;
while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
}
if(N%sum == 0){
    printf("Yes");}
else{
    printf("No");}
return 0;

    
    
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
// Use cout.flush() for interactive problems.
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int main()
{
    she_told_me_dont_worry
    int n, h, w;
    cin>>n>>h>>w;
    int i;
    int ans = 0;
    FOR0(i, n)
    {
        int a, b;
        cin>>a>>b;
        if(a>=h&&b>=w) ans++;
    }
    cout<<ans;
}

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

#define F first
#define S second
#define endl "\n"
#define ll long long
#define ii pair<int, int>

using namespace std;

ll arr[200100];

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

    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> arr[i];

    for(int i = 1; i < n; i++)
        arr[i] += arr[i - 1];

    ll mini = (ll)(1e18);

    for(int i = 0; i < n - 1; i++)
    {
        ll temp = arr[n - 1] - 2 * arr[i];

        if(temp < 0)
            temp *= -1;

        mini = min(mini, temp);
    }

    cout << mini;
}


Measured memory_bytes: 1792
public class Main {
	public static void main(String args[]) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();

		int result = 0;
		for (int i=0; i <= N ;i++) {
			if (i+K <= N) {
				result++;
			}
		}

		System.out.println(result);
	}
}

Measured memory_bytes: 21844
package main

import (
	"fmt"
	"strings"
)

func main() {
	var n, k int
	var s string
	fmt.Scan(&n, &k, &s)

	for i := 0; i < n; i++ {
		if i+1 == k {
			fmt.Printf(strings.ToLower(string(s[i])))
		} else {
			fmt.Printf(string(s[i]))
		}
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
    
int main(){
    int n;
    cin >> n;
    int cnt = 0;
    while(cnt*(cnt+1)/2 < n){
        cnt ++;
    }
    int rev = cnt*(cnt+1)/2 - n;
    for(int i=1; i<=cnt; i++){
        if(i != rev){
            cout << i << endl;
        }
    }
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

int main()
{	
	int a, b, c;
	cin >> a >> b >> c;

	cout << (a + b >= c ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i<b; i++)
#define rep(i, n) FOR(i, 0, n)
#define rFOR(i, a, b) for(int i = a;i >= b; i--)
#define rrep(i, a) rFOR(i, a, 0)
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<char> vc;
typedef vector<vc> vvc;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ld PI = acos(-1);
const ll INF = 1e18;
struct edge{ll to, cost;};

template <typename T>
bool chmax(T &a, const T &b) {
    if (a < b) {
      a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T &b) {
    if (a > b) {
      a = b;
      return true;
    }
    return false;
}

class UnionFind {
public:
    vector<int> par;
    vector<int> rnk;
    vector<ll> siz;
    UnionFind(int N): par(N), rnk(N), siz(N){
        for(int i = 0; i < N; i++){
            par[i] = i, rnk[i] = 0, siz[i] = 1;
        }
    }
    //根
    int find(int x){
        if(par[x] ==x )return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y){
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return;
        if(rnk[rx] < rnk[ry]){
            par[rx] = ry;
            siz[ry] += siz[rx];
            siz[rx] = 0;
        }
        else{
            par[ry] = rx;
            siz[rx] += siz[ry];
            siz[ry] = 0;
            if(rnk[rx] == rnk[ry]){
                rnk[rx]++;
            }
        }
    }
    //集合が同じか
    bool same(int x, int y){
        return find(x) == find(y);
    }
    //集合の大きさ
    int size(int x){
        return siz[find(x)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin >> N >> Q;
    UnionFind st(N+1);
    rep(i,Q){
        int t,u,v;
        cin >> t >> u >> v;
        if(t==0){
            st.unite(u,v);
        }
        else{
            cout << st.same(u,v) << '\n';
        }
    }
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 6320
a, b, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
prices = []
prices.append(min(a)+min(b))
for i in range(m):
    ticket = list(map(int, input().split()))
    prices.append(a[ticket[0]-1]+b[ticket[1]-1]-ticket[2])
print(min(prices))


Measured memory_bytes: 18736
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
    
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    List<BigInteger> dp = new ArrayList<BigInteger>();
    Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
    int n = sc.nextInt();
    int m = sc.nextInt();
    for(int i=1; i<=m; i++) {
      int a = sc.nextInt();
      switch (a) {
        case 1:
          mp.put(a, 2);
          break;
        case 2:
        case 3:
        case 5:
          mp.put(a, 5);
          break;
        case 4:
          mp.put(a, 4);
          break;
        case 6:
        case 9:
          mp.put(a, 6);
          break;
        case 7:
          mp.put(a, 3);
          break;
        case 8:
          mp.put(a, 7);
          break;

      }
    }
    
    for(int i=0; i<=n+10; i++) {
      dp.add(BigInteger.valueOf(0L));
    }
    
    BigInteger ten = BigInteger.valueOf(10);
    for(int i=0; i<n; i++) {
      if (i != 0 && dp.get(i).equals(BigInteger.valueOf(0L))) continue;
      for(Map.Entry<Integer,Integer> entry : mp.entrySet()) {
        int pos = i + entry.getValue();
        BigInteger tmp = dp.get(pos);
        BigInteger now = dp.get(i).multiply(ten).add(BigInteger.valueOf(entry.getKey()));
        if (now.compareTo(tmp) > 0) {
          dp.set(pos, now);
        }
      }
    }
    System.out.println(dp.get(n));
  }
}


Measured memory_bytes: 102504
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int N;
	cin >> N;
	for(int i=0; i<=N/4; ++i){
		if((N-4*i)%7==0){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}


Measured memory_bytes: 3604
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N = int(input())
    A = set(li_input())

    if len(A) % 2 == 0:
        print(len(A) - 1)
    else:
        print(len(A))

    



main()


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

int main(){
	int H, W, ansH, ansW;
	bool changeFlag = false;
	cin >> H >> W;
	ansH = H;
	ansW = W;

	char **array = new char*[H];

	for(int height = 0; height < H; height++){
		array[height] = new char[W];
		for(int width = 0; width < W; width++){
			cin >> array[height][width];
		}
	}

	do{
		changeFlag = false;
		for(int height = 0; height < H; height++){
			bool blankFlag = true;
			for(int width = 0; width < W; width++){
				if(array[height][width] != '.')
					blankFlag = false;
			}

			if(blankFlag && height < ansH-1){
				for(int width = 0; width < W; width++){
					array[height][width] = array[height+1][width];
					array[height+1][width] = '.';
				}
				changeFlag = true;
			}else if(blankFlag && height == ansH-1){
				changeFlag = true;
			}
		}
		if(changeFlag)
			ansH--;
	}while(changeFlag);

	do{
		changeFlag = false;
		for(int width = 0; width < W; width++){
			bool blankFlag = true;
			for(int height = 0; height < ansH; height++){
				if(array[height][width] != '.')
					blankFlag = false;
			}

			if(blankFlag && width < ansW-1){
				for(int height = 0; height < ansH; height++){
					array[height][width] = array[height][width+1];
					array[height][width+1] = '.';
				}
				changeFlag = true;
			}else if(blankFlag && width == ansW-1){
				changeFlag = true;
			}
		}
		if(changeFlag) ansW--;
	}while(changeFlag);

	for(int height = 0; height < ansH; height++){
		for(int width = 0; width < ansW; width++){
			cout << array[height][width];
		}
		cout << '\n';

		delete[] array[height];
	}
	delete[] array;

	return 0;
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
typedef vector < vector<ll> > Mat;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  int X, Y, Z; cin >> X >> Y >> Z;
  swap(X, Y);
  swap(X, Z);
  printf("%d %d %d\n", X, Y, Z);


  return 0;
}


Measured memory_bytes: 3704
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String s = sc.next();
		
		if (N >= 3200) {
			System.out.println(s);
		} else {
			System.out.println("red");
		}

	}	
}




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

struct edge{long long to, cost;};
vector<edge> graph[100010];
long long depth[100010];

void dfs(long long now, long long prev, long long dist){
  depth[now] = dist;
  for(auto &e : graph[now]){
    if(e.to != prev){
      dfs(e.to, now, dist+e.cost);
    }
  }
}

int main(){
  long long n,q,k,a,b,c,x,y;
  cin >> n;
  for(int i=0;i<n-1;i++){
    cin >> a >> b >> c;
    a--; b--;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }
  cin >> q >> k;
  k--;
  dfs(k, -1, 0);
  for(int i=0;i<q;i++){
    cin >> x >> y;
    x--; y--;
    cout << depth[x]+depth[y] << endl;
  }
  return 0;
}


Measured memory_bytes: 14336
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }


int main(){
    int N;

    cin>>N;
    int m =0;
    int r=0;
    rep(i, N){
        int a;
        cin>>a;
        if(a>=m){
            ++r;
            m = a;
        }
    }

    cout<<r<<endl;
    return 0;
    

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int a, b;
  cin >> a >> b;
  int num = b - a;
  int ans = num * (num + 1) / 2 - b;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import Counter
N=int(input())
C = input()
p = Counter(C)["R"]
if p == 0 or p == N:
  print(0)
  exit()
r = 0
w = 0

for i,c in enumerate(C):
  if i < p:
    if c == "W":
      w += 1
  else:
    if c == "R":
      r += 1
print(max(r,w))

Measured memory_bytes: 68940
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author champon
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 9e18
#define ceill(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
ll mod = 1e9+7;
void ans(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void ans2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){a=b; return true;} return false; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill((T*)array, (T*)(array+N), val);}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

class debug
{
public:
    template<typename T> void vdeb(T vec);
    template<typename T1, typename T2> void adeb(T1 *arr, T2 n);
    template<typename T> void mdeb(T mp);
};

#endif //INCLUDE_DEBUG_HPP

template<typename T> void debug::vdeb(T vec)
{
    cout << "#vector set debug" << endl;
    for(auto vv : vec) cout << vv << " ";
    cout << endl;
}

template<typename T1, typename T2> void debug::adeb(T1 *arr, T2 n)
{
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}

template<typename T> void debug::mdeb(T mp)
{
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
debug dbg;

class DLuckyPIN {
public:
	void solve(std::istream& in, std::ostream& out)
	{
	    int n;
	    string s;
	    in >> n >> s;

	    int res = 0;
	    for(int i=0; i<10; i++){
	        for(int j=0; j<10; j++){
	            for(int k=0; k<10; k++){
	                int bit = 0;
	                for(int x=0; x<n; x++){
                        if(bit & 1<<2 && s[x] == k+'0'){
                            res++;
                            break;
                        }
                        else if(bit & 1<<1 && s[x] == j+'0') bit |= 1<<2;
                        else if(bit == 0 && s[x] == i+'0') bit |= 1<<1;
	                }
	            }
	        }
	    }

	    out << res << endl;
	}
};


int main() {
	DLuckyPIN solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
/* {{{ */
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */

use num_bigint::{BigInt, ToBigInt};
use num_traits::One;

fn main() {
    input! {
        n: usize,
        a: [u64;n]
    }
    if a.iter().any(|v| *v == 0) {
        println!("0");
        return;
    }
    let limit = 10u64.pow(18).to_bigint().unwrap();
    let mut res: BigInt = One::one();
    for i in 0..n {
        res *= a[i];
        if res > limit {
            println!("-1");
            return;
        }
    }
    println!("{}", res);
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 5176
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define N 22
#define MAX 1000000007
#define int long long
using namespace std;
int n,m,K,Map[N][N],dp[2][1<<N],ans;
int lowbit(int x){
	return x&(-x);
}
signed main(){
	int x,y,z;
	scanf("%lld%lld%lld",&n,&m,&K);n--;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			Map[i][j]=-1;
		}
	}
	for(int i=1;i<=K;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		Map[x][y]=z;
	}
	int cur=1,fin=0,All=(1<<n)-1;
	dp[cur][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			int now=(1<<(j-1));
			swap(cur,fin);
			for(int s=0;s<=All;s++) dp[cur][s]=0;
			for(int s=0;s<=All;s++){
				if(Map[i][j]!=1 && !(s&now)){
					dp[cur][s]=(dp[cur][s]+dp[fin][s])%MAX;
				}
				if(Map[i][j]!=0){
					int x;
					if(s&now) x=s;
					else{
						int t=All-(now<<1)+1;
						t=s&t;
						t=lowbit(t);
						if(!t) x=s|now;
						else x=(s+now-t);
					}
					dp[cur][x]=(dp[cur][x]+dp[fin][s])%MAX;
				}
			}
		}
	}
	for(int i=0;i<=All;i++){
		ans=(ans+dp[cur][i])%MAX;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 12000
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int main(){
    int n,m,a[N],ans;
    while(true){
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)return 0;
        ans=0;
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        sort(a,a+n);
        reverse(a,a+n);
        for(int i=0;i<n;i++)if((i+1)%m!=0)ans+=a[i];
        printf("%d\n",ans);
    }
}


Measured memory_bytes: 2712
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
        int array[3];

        cin >> array[0] >> array[1] >> array[2];

        sort( array, array+3 );

        cout << array[0] << " " << array[1] << " " << array[2] << endl;

return 0;
}



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

#define ll long long
#define INF 99999999
#define rep(i,n) for(int i=0,temp=(int)(n);i<temp;++i) 
#define repi(i,start,end) for(int i=start,temp=(int)(end);i<end;++i)
#define rfor(v,x) for(const auto& x : v) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort(v, v+n)
#define vsort(v) sort(v.begin(), v.end())
#define vfsort(v,lambda) sort(v.begin(),v.end(),lambda)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vin(v) rep(i,v.size()) {cin >> v[i];}
//最終奥義
//#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//(lambda (x y) (< x y)) => [](int x, int y) -> int { return x<y; }

signed main(void){
  int k,x;cin >> k >> x;
  for(int i=x-k+1;i<x+k;i++)
    cout << i << " ";
  cout << endl;

}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

#define PT pair<ll,ll>

unordered_map<ll, ll> MP;
//map<ll, ll> MP;
priority_queue<PT> PQ;

inline void keisan(ll n, ll k) {
	if (k > MP[n]) {
		MP[n] = k;
		PQ.push(mp(k, n));
	}
}

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


	int T;
	cin >> T;

	rep(t, T) {
		ll N, A, B, C, D;
		cin >> N >> A >> B >> C >> D;

		MP.clear();
		PQ = priority_queue<PT>();
		MP[N] = 1e18;
		PQ.push(mp(ll(1e18), N));
		ll owa = 0;
		ll are = ll(1e13) / D;

		while (PQ.size()) {
			auto p = PQ.top();
			PQ.pop();

			ll n = p.second;
			ll k = p.first;
			if (k <= owa) break;

			if (MP[n] != k) continue;
			if (n == 1) break;

			if (n <= are) {
				ll tmp = k - (n - 1) * D;
				if (tmp > owa) {
					owa = tmp;
				}
			}

			ll k2 = k - A;
			if (n & 1) {
				keisan(n >> 1, k2 - D);
				keisan((n >> 1) + 1, k2 - D);
			}
			else {
				keisan(n / 2, k2);
			}

			k2 = k - B;
			int r = n % 3;
			if (r <= 1) {
				keisan(n / 3, k2 - D * r);
			}
			else {
				keisan(n / 3 + 1, k2 - D);
			}

			k2 = k - C;
			r = n % 5;
			if (r <= 2) {
				keisan(n / 5, k2 - D * r);
			}
			else {
				keisan(n / 5 + 1, k2 - D * (5 - r));
			}

		}
		co(ll(1e18) - max(MP[1], owa) + D);
	}

	Would you please return 0;
}

Measured memory_bytes: 4072
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, M = read_values()
    S = input().strip()[::-1]
    P = []
    t = 0
    tmp = 1
    for s in S[1:]:
        if s == "0":
            t = tmp
        
        tmp += 1
        if tmp > M:
            if t == 0:
                print(-1)
                return

            P.append(str(t))
            tmp -= t 
            t = 0
    
    if t != 0:
        P.append(str(t))
    print(" ".join(P[::-1]))


if __name__ == "__main__":
    main()


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

/*{
  }*/

using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int,int>;

signed main() {
  int k, x;
  cin >> k >> x;

  if(k*500 >= x) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}



Measured memory_bytes: 256
import numpy as np

N  = int(input())

AB = []
time = 0

for _ in range(N):
    AB.append(list(map(int, input().split())))

AB = np.array(AB)

sorted_AB = AB[AB[:,1].argsort(), :]

for i in range(N):
    time += sorted_AB[i,0]

    if time > sorted_AB[i,1]:
        print('No')
        exit()

print('Yes')

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

int main(void) {
  int a,b,c;
  cin >> a >> b >> c;

  int ans=max(10*a+b+c, max(a+10*b+c, a+b+10*c));
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
inputs = list(map(int,input().split()))
for i in range(1, N):
	inputs[i] += inputs[i-1]
ans = inputs[K-1]
for i in range(0, N-K):
    ans = max([ans, inputs[i+K]-inputs[i]])
print((ans+K)/2)

Measured memory_bytes: 25060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define fin(ar,k,n) for(int i=k;i<n;i++) cin>>ar[i]
#define fout(ar,k,n) for(int i=k;i<n;i++) cout<<ar[i]<<' '
#define all(z) z.begin(),z.end()
#define mcc ((int)1e9+7)
#define mcf 998244353
#define mi map<int,int>
#define mem(a,n) memset(a,n,sizeof(a))
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> fst;

const int N=1e5+7;
ll dp[N],n,w;
ll minl(ll a,ll b) {return (a<b)? a:b;}


void solve()
{
	mem(dp,0x3f);
    cin>>n>>w;
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int wt,val;
		cin>>wt>>val;
		for (int j=100000-val;j>=0;--j)
		{
			dp[j+val]=minl(dp[j]+wt,dp[j+val]);
		}			
	}
	for (int i=100000; i>=0;--i)
	{
		if(dp[i]<=w)
		{
			cout<<i<<endl;
			break;
		}
	}
	
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,0,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

int main(){
  int M,D,ans=0,t;
  cin>>M>>D;
  if(D<=9) t=D;
  else t=9;
  
  FOR(i,1,M+1){
    FOR(j,2,t+1){
      if(i%j==0){
        if(i/j>=2){
          if(10*(i/j)+j<=D) ans++;
        }
      }
    }
  }
  
  if(M<=3) ans=0;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}

			var N = inputArray[0];

			var manList = new List<TestedMan>();

			for (int i = 0; i < N; i++) {
				var newMan = new TestedMan();
				manList.Add(newMan);
			}

			var ans = 0;


			for (int i = 0; i < Math.Pow(2,N); i++) {
				var katei = new bool[N];

				for (int j = 0; j < N; j++) {
					var x 	= (i >> j) & 1;
					katei[j] = (x == 1);

				}

				var result = true;

				for (int k = 0; k < N; k++) {
					var man = manList[k];

					//仮定配列の正直/不親切と証言の判定結果が矛盾しているかどうか
					if (katei[k]!=man.hantei(katei)) {
						result = false;
						break;
					}
				}


				if (result) {
					ans = Math.Max(ans, katei.Count(x => x));
				}

			}

			//答えの出力
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
	public class TestedMan {

		/// <summary>
		/// 何人の証言をするか
		/// </summary>
		public int ninsu { get; set; }

		public Dictionary<int, bool> _shougenDic;

		public TestedMan() {
			_shougenDic = new Dictionary<int, bool>();
			ninsu = (int)retreiveLongArray()[0];

			for (int i = 0; i < ninsu; i++) {

				var shougen = retreiveLongArray();
				var target = (int)shougen[0];
				var result = (int)shougen[1];

				_shougenDic.Add(target,result==1) ;
			}

		}

		/// <summary>
		/// 与えられた正直/不親切の配列と、この人の証言が矛盾しているか確認する
		/// </summary>
		/// <param name="katei"></param>
		/// <returns></returns>
		public bool hantei(bool[] katei) {

			foreach (var shogen in _shougenDic) {
				var i = shogen.Key;
				if (katei[i - 1] != shogen.Value) {
					return false;
				}
			}

			return true;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 13408
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  string n;
  cin >> n;
  string ans;
  rep(i, n.size()) {
    if(n[i] == '1') ans.push_back('9');
    else if(n[i] == '9') ans.push_back('1');
    else ans.push_back(n[i]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384