akhauriyash/Code-Regression huggingface dataset:
//1.read question_2.read I/O_3.read test cases_4.read constraints(to decide TC of solution)_5.decide method_6.dry run_
//7.code_8.test_9.submit
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define mod 1000000007
#define F first
#define S second
#define _READ freopen("input.txt","r", stdin);
#define pb push_back
#define MP make_pair
#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
    
    _FAST
    lli n,t,i,j,k,ans=0,flag=0,a,b,m,w;
    cin>>n>>w;
    vector<vector<lli>> v(n,vector<lli>(2));
    for(i=0;i<n;i++)
        cin>>v[i][1]>>v[i][0];
        //return 0;
    vector<lli> dp(w+1,0);
    for(i=0;i<n;i++)
    {
        //for(j=0;j<=w-v[i][1];j++)
        for(j=w-v[i][1];j>=0;j--)
        {
            //cout<<j<<","<<j+v[i][1]<<",";
            dp[j+v[i][1]]=max(dp[j+v[i][1]],
                              dp[j]+v[i][0]);
            //cout<<dp[j+v[i][1]]<<"...";
        }
        //cout<<"\n";
    }
    cout<<*max_element(dp.begin(),dp.end());
    return 0;
}


Measured memory_bytes: 1024
/*
 Sarthak Jain
*/
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
int mod=1e9+7;
int min(int a,int b){
  return (a<b)?a:b;
}
int max(int a,int b){
  return (a>b)?a:b;
}
int fp(int a,int b){
  if(b==0) return 1;
  int x=fp(a,b/2);
  x=(x*x)%mod;
  if(b&1) x=(x*a)%mod;
  return x;
}

int solve(int x)
{
  int ans=0;
  while(x!=0)
  {
    ans+=1;
    int y=__builtin_popcount(x);
    x%=y;
  }
  return ans;
}

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

 int n;
 cin>>n;

 string s;
 cin>>s;
 int ct=0;
 for(auto i:s)
  ct+=(i-'0');

 int p=1;
 int y=0;
 int pw[s.size()+1];
 mod=ct+1;
 for(int i=s.size()-1;i>=0;i--)
 {
  if(s[i]=='1')
  {
    y=(y+p)%mod;
  }
  pw[i]=p;
  p=(p*2)%mod;
 }
 //cout<<y<<endl;



 int pw2[s.size()+1];
 int z=0;
 mod=ct-1;
 p=1;
 if(mod!=0)
 for(int i=s.size()-1;i>=0;i--)
 {
  if(s[i]=='1')
  {
    z=(z+p)%mod;
  }
  pw2[i]=p;
  p=(p*2)%mod;
 }
 //cout<<z<<endl;

 int ans;
 for(int i=0;i<s.size();i++)
 {
  if(s[i]=='0')
  {
    int x=(y+pw[i])%(ct+1);
   // cout<<i<<":"<<x<<endl;
    ans=1+solve(x);
  }
  else
  {
    if(ct==1)
    {
      cout<<0<<endl;
      continue;
    }
    int x=(z-pw2[i]+(ct-1))%(ct-1);
    ans=1+solve(x);
  }
  cout<<ans<<endl;
 }


}

Measured memory_bytes: 6884
import scala.io.StdIn._
import scala.collection.mutable.ArrayBuffer
object Main extends App {
  case class Edge(a: Int, b: Int) {
    var color = 0;
  }

  val n = readInt
  val nodes = Array.fill(n + 1)(new ArrayBuffer[Edge]())

  val edges = Array.fill(n - 1){
    val Array(a, b) = readLine.split(" ").map(_.toInt)
    val e = Edge(a, b)
    nodes(a) += e
    nodes(b) += e
    e
  }

  println(nodes.foldLeft(0)((z, n) => Math.max(z, n.size)))

  def bfs(targets: Seq[Int]): Unit = {
    val nexts = targets.flatMap{ i => 
      val (p, c) = nodes(i).partition(_.color != 0)
      val counts: Seq[Int] = (1 to c.size + 1).filter(_ != p.headOption.fold(0)(_.color))
      c.zip(counts).map {case (edge, index) =>
        edge.color = index
        if (edge.a == i) edge.b else edge.a
      }
    }
    if (nexts.nonEmpty) bfs(nexts)
  }

  bfs(Seq(1))

  println(edges.map{_.color}.mkString("\n"))
}

Measured memory_bytes: 112804
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;

int main(){
    int a,b;
    cin >> a >> b;
    if(b%a == 0) cout << a+b << endl;
    else cout << b-a << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod=1e9+7;

int main(){
    int n=0, w=0, s=0, e=0;
    string S;
    cin >> S;
    for(int i=0; i<S.size(); i++){
        if(S[S.size()-1]=='N'){
            n++;
            S.pop_back();
        }
        if(S[S.size()-1]=='W'){
            w++;
            S.pop_back();
        }
        if(S[S.size()-1]=='E'){
            e++;
            S.pop_back();
        }
        if(S[S.size()-1]=='S'){
            s++;
            S.pop_back();
        }
    }

    if((n>0 && s==0) | (e>0 && w==0) | (n==0 && s>0) | (e==0 && w>0)) cout << "No";
    else cout << "Yes";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5 + 10;
int main() {
  long long N;
  cin >> N;
  for (long long a = 1; a <= 3500ll; a++) {
    for (long long b = a; b <= 3500ll; b++) {
      long long X = N * a * b;
      long long Y = 4ll * a * b - (N * a + N * b);
      if (Y > 0ll && X % Y == 0) {
        cout << a << ' '<< b << ' ' <<  X / Y;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()


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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
	int ans = 0;
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
			ans = max(ans, abs(a[i]-a[j]));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime MOD
    mint inv() const { return pow(MOD-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination MOD prime
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < MOD);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
    mint p(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[n-k];
    }
}; //comb(10000007);
// comb(5, 2) → 10, comb.p(5, 2) → 20
// comb.fact[4] → 24, 2のN乗 → mint(2).pow(N)

int main() {
    // 包除原理
    int N;
    cin >> N;
    mint ans = mint(10).pow(N);
    ans -= mint(9).pow(N) * 2;
    ans += mint(8).pow(N);
    cout << ans << '\n';
    return 0;
    // ll, 0, -, 1i, for s&g, debug
}

Measured memory_bytes: 3644
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<int,int> P;
ll longinf=1ll<<60;
int inf=1<<29;

ll N;
ll K;
ll x[100002];
ll s[100002];



int main(){
      cin>>N>>K;
      rep0(i,N) cin>>x[i];
      ll ans=longinf;
      rep0(i,N-K+1){
            s[i]=x[i+K-1]-x[i];
      }
      rep0(i,N-K+1){
            ans=min(ans,s[i] + min(abs(x[i+K-1]),abs(x[i]))); 
      }
      cout<<ans<<endl;

      return 0;
}

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

int main() {
  int N=0, K=0;
  cin >> N >> K;
  long long ans = K;
  rep(n, N-1){
    ans *= (K-1);
  }
  cout << ans << endl;
}

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

using namespace std;

const int inf = 1e9;

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

    int n, k, s;
    cin >> n >> k >> s;
    for (int i = 0; i < n; ++i) {
        if (i < k) {
            cout << s << " ";
        } else {
            cout << (s == inf ? s - 1 : s + 1) << " ";
        }
    }
    cout << "\n";
}


Measured memory_bytes: 1280
import sys
input = lambda : sys.stdin.readline().rstrip()

x = int(input())

if 400 <= x <= 599:
    out = 8
elif 600 <= x <= 799:
    out = 7
elif 800 <= x <= 999:
    out = 6
elif 1000 <= x <= 1199:
    out = 5
elif 1200 <= x <= 1399:
    out = 4
elif 1400 <= x <= 1599:
    out = 3
elif 1600 <= x <= 1799:
    out = 2
elif 1800 <= x <= 1999:
    out = 1

print(out)

Measured memory_bytes: 64380
N = int(input())
CSF = [list(map(int, input().split())) for _ in range(N - 1)]
for n in range(N - 1):
  t = 0
  for i in range(n, N - 1):
    if t < CSF[i][1]:
      t = CSF[i][1]
    elif not (t % CSF[i][2] == 0):
      t += CSF[i][2] - (t % CSF[i][2])
    t += CSF[i][0]
  print(t)
print(0)

Measured memory_bytes: 3188
h,w,k=map(int,input().split())
C=[list(input().strip()) for _ in range(h)]
ans=0
for i in range(1<<h):
    for j in range(1<<w):
        cnt=0
        for x in range(h):
            if (i>>x)&1==1:
                continue
            for y in range(w):
                if (j>>y)&1==1:
                    continue
                cnt+=int(C[x][y]=='#')
        if cnt==k:
            ans+=1
print(ans)

Measured memory_bytes: 68468
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=998244353,N=2e7+5;
int n,a,b,ans,fac[N],inv[N];

int fpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
	return res;
}

int C(int n,int m){
	if(m<0||n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int calc(int x,int y){
	if(y<=x-1) return 0;
	return (C(x+y,x)-C(x+y,x-1)+mod)%mod;
}

signed main(){
	read(n);read(a);read(b);
	if(!b){
		write(1);
		return 0;
	}
	fac[0]=1;
	for(int i=1;i<=n+n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n+n]=fpow(fac[n+n],mod-2);
	for(int i=n+n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; 
	for(int i=0;i<=n-b;i++){
		int num=calc(i,b-1);
		if(i+b==n){
			if(a==i) ans=(ans+num)%mod;
		}
		else{
			int x=n-b-i-1,y=a-i;
			ans=(ans+num*C(x+y,y)%mod)%mod;
		}
	}
	write(ans);
}

Measured memory_bytes: 312704
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
namespace ABC177
{
    class Program
    {
        static void Main(string[] args)
        {
            var DTS = Console.ReadLine().Split().Select(double.Parse).ToArray();
            if (Math.Ceiling(DTS[0] / DTS[2]) <= DTS[1]) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 28232
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define MAX 1000001
#define mod 1000000007
#define pie 3.14159265358979323846
void solve()
{
	int n,i,ans=0;
	cin>>n;
	int h[n];
	for(i=0;i<n;i++)
	cin>>h[i];
	for(i=1;i<n;i++){
		if(h[i-1]>h[i])
		ans+=(h[i-1]-h[i]);
	}
	ans+=h[n-1];
	cout<<ans;
}
int main()
{ 
    cool;
    int t;
    //cin>>t;
    t=1;
    while(t--){
    	solve();
	}
    return 0;
}


Measured memory_bytes: 256
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
    let x: usize = read();
    let ans = (x / 500) * 1000 + ((x % 500) / 5) * 5;
    println!("{}", ans);
}


Measured memory_bytes: 4352
import java.util.*;
import java.math.*;
import java.awt.geom.*;
import java.io.*;
   
   
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n == 0) break;
			int[] a = new int[n];
			int[] b = new int[n];
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				
			}
			for(int i = 0; i < n; i++) {
				b[i] = sc.nextInt();
			}
			Arrays.sort(a);
			Arrays.sort(b);
			int[] a2 = new int[n];
			int[] b2 = new int[n];
			for(int i = 0; i < n; i++) {
				a2[n - i - 1] = a[i];
				b2[n - i - 1] = b[i];
			}
			a = a2;
			b = b2;
			int ans = -1;
			for(int k = 0; k < n/2; k++) {
				if(a[k*2] > b[k]) {
					ans = k*2+1;
					break;
				}
			}
			if(ans == -1) {
				System.out.println("NA");
			}
			else {
				System.out.println(ans);
			}
		}
		
		
		
	}
	
}

Measured memory_bytes: 290848
#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 ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define PAI 3.141592653589
typedef long long ll;

using namespace std;

int main() 
{
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    int s[n];
    double sum = 0;
    REP(i, n)
    {
      cin >> s[i];
      sum += s[i];
    }
    double av = 0;
    av = sum / n;

    double hensa = 0;
    REP(i, n) {
      hensa += (s[i] - av) * (s[i] - av);
    }

    cout << fixed << setprecision(8) << sqrt(hensa / n) << "\n";
  }
}



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

#pragma GCC optimize "O3"
#define rep(i,a,n) for(int i=a; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
const ll powll = 1LL<<1;

int main(void){
    int n,mw; cin >> n >> mw;
    int v[n],w[n];
    rep(i,0,n){
        cin >> v[i] >> w[i];
    }
    int dp[n+1][mw+1];
    rep(i,0,mw+1){
        dp[0][i] = 0;
    }
    rep(i,0,n){
        rep(j,0,mw+1){
            if(j-w[i] >= 0){
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
            }else{
                dp[i+1][j] = dp[i][j];
            }
        }
    }
    // rep(i,0,n+1){
    //     rep(j,0,mw+1){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    cout <<dp[n][mw] << "\n";
}


Measured memory_bytes: 7040
#include <stdio.h>
#define N 100000

typedef struct{
  int p,r,l;
}Node;

Node T[N];

int depth(int);
int degree(int);

int main()
{
  int n,i,j,id,d,c,k;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].p = -1;
    T[i].r = -1;
    T[i].l = -1;
  }
  
  for(i=0;i<n;i++){
    scanf("%d %d",&id,&d);
    for(j=0;j<d;j++){
      scanf("%d",&c);
      T[c].p = id;
      if(j==0){
	T[id].l = c;
      }
      else{
	T[k].r = c;
      }
      k = c;
    }
  }
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, depth = %d, ",i,T[i].p,depth(i));
    if(T[i].p==-1){
      printf("root, [");
    }
    else if(T[i].l==-1){
      printf("leaf, [");
    }
    else {
      printf("internal node, [");
    }
    degree(T[i].l);
    printf("]\n");
  }
  return 0;
}

int depth(int x)
{
  if(T[x].p==-1){
    return 0;
  }
  else {
    return 1+depth(T[x].p);
  }
}


int degree(int y)
{
  if(y==-1){
    return 0;
  }
  
  else {
    if(T[y].r==-1){
      printf("%d",y);
    }
    else{
      printf("%d, ",y);
      degree(T[y].r);
    }
  }
}

Measured memory_bytes: 1784
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  double a,b,x;
  cin >> a >> b >> x;
  if(x<=a*a*b/2) {
    cout << fixed << setprecision(10) << atan((a*b*b)/(2*x))*180/pi << endl;
  }
  else {
    cout << fixed << setprecision(10) << atan((2*a*a*b-2*x)/(a*a*a))*180/pi << endl;
  }
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main{
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		int i = 1;
		while(true) {
			int x = sc.nextInt();
			if(x == 0) break;
				System.out.println("Case " + i + ":" + " " + x);
				i++;
		}
	}

}


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

int main() {
    ll N; cin >> N;
    string s = "";
    while (N != 0) {
        --N;
        ll x = N % 26;
        char c = 'a' + x;
        s += c;
        N /= 26;
    }
    reverse(s.begin(), s.end());
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define mems(a,x) memset(a,x,sizeof(a))
#define first fi
#define second se
using namespace std;
typedef long long ll;
const int mod=998244353,N=3005;
int n,x,c[N][N];
ll dp[N][N<<1];
ll C(ll n,ll m)
{
    if(m==0||n==m) return 1;
    if(m==1) return n;
    if(c[n][m]) return c[n][m];
    return c[n][m]=(C(n-1,m-1)+C(n-1,m))%mod;
}
ll solve(int m)
{
    ll ans=0;
    for(int i=0;i<x;i++) (ans+=dp[m][i])%=mod;
    for(int i=x+1;i<=2*m;i+=2)
    {
        int t=max(0,m-(i-(x-1))),s=i-2*(m-t);
        if(t>=0&&s>=0)
            (ans+=dp[t][s])%=mod;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&x);
    dp[0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=i;j<=i*2;j++)
    {
        (dp[i+1][j+1]+=dp[i][j])%=mod;
        (dp[i+1][j+2]+=dp[i][j])%=mod;
    }
    ll ans=0;
    for(int i=0;i<=n;i++)
        ans=(ans+C(n,i)*solve(i))%mod;
    printf("%lld\n",ans);
}


Measured memory_bytes: 174848
#!/usr/bin/env python3
n, k, c = map(int, input().split())
s = input()

left = [0] * (n + 2)
t = 0
while t < n:
    if s[t] == "o":
        left[t + 1] = 1
        t += c
    t += 1
for i in range(n + 1):
    left[i + 1] += left[i]

right = [0] * (n + 2)
t = n - 1
while t >= 0:
    if s[t] == "o":
        right[t + 1] = 1
        t -= c
    t -= 1
for i in range(n + 1)[::-1]:
    right[i] += right[i + 1]

for i in range(1, n + 1):
    if left[i - 1] + right[i + 1] < k:
        print(i)


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

int main(void)
{
	int a,b;

	cin >> a;
	cin >> b;

	if (a>b) {
		cout << "a > b" << endl;
	}
	else if (a<b) {
		cout << "a < b" << endl;
	}
	else {
		cout << "a == b" << endl;
	}

	return 0;
}



Measured memory_bytes: 3104
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#include<random>
#include<cassert>
//This code is written by Itst
using namespace std;

int w[107] , val[107] , dp[107][307];
int N , W , allW;

int main(){
	cin >> N >> W;
	for(int i = 1 ; i <= N ; ++i)
		cin >> w[i] >> val[i];
	allW = w[1];
	for(int i = 1 ; i <= N ; ++i) w[i] -= allW;
	for(int i = 1 ; i <= N ; ++i)
		for(int j = N ; j ; --j)
			for(int k = 3 * N ; k >= w[i] ; --k)
				dp[j][k] = max(dp[j][k] , dp[j - 1][k - w[i]] + val[i]);
	int ans = 0;
	for(int i = 1 ; i <= N ; ++i){
		int cur = W - allW * i;
		if(cur < 0) break;
		ans = max(ans , dp[i][min(cur , 3 * N)]);
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;

ll N,M;

vector<ll> A;

ll combination(int n, int m){
	ll ans = 1;
	for(ll i=0;i<m;i++){
		ans *= n-i;
		ans /= i+1;
	}
	return ans;
}


void solve(){
	vector<ll> m;
	ll x=0;

	for(int i=0;i<=N;i++){
		x += A[i];
		m.push_back(x%M);
	}

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

	ll ans=0; ll cur;

	int count=0;
	for(int i=0;i<m.size();i++){
		cur = m[i];
		count++;
		if(cur!=m[i+1] || i+1==m.size()){
			ans += combination(count,2);
			count = 0;
		}
	}

	cout << ans << endl;


}


int main(){
	cin >> N >> M;
	A.resize(N+1);
	A[0]=0;
	for(int i=1;i<=N;i++){
		cin >> A[i];
	}
	solve();
	return 0;
}

Measured memory_bytes: 2296
#include <iostream>
using namespace std;
int main()
{
    unsigned long long a,b;
    cin >> a >> b;
    if(a % 2 == 0 || b % 2 == 0)
    {
        cout << "Even\n";
    }
    else
    {
        cout << "Odd\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}


int main(){
	const int intmax = 300001;
	bool isprime[intmax];
	REP(i,intmax) isprime[i] = true;
	for(int i=6;i*i<=intmax;i+=7){
		for(int j=i+7;j<intmax;j+=7){
			if(j%i==0) isprime[j] = false;
			if((j+2)%i==0) isprime[j+2] = false;
		}
	}
	for(int i=8;i*i<=intmax;i+=7){
		for(int j=i+7;j<intmax;j+=7){
			if(j%i==0) isprime[j] = false;
			if((j+5)%i==0) isprime[j+5] = false;
		}
	}
	while(1){
		ll int n;
		cin >> n;
		vi ans;
		if(n==1) break;
		FOR(i,6,intmax){
			if(i%7!=1&&i%7!=6) continue;
			if(isprime[i]&&n%i==0) ans.pb(i);
		}
		cout << n << ": ";
		REP(i,ans.size()){
			cout << ans[i];
			if(i!=ans.size()-1) cout <<" ";
		}
		cout << endl;
	}
}

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

using namespace std;

#define sqr(x) ((x)*(x))
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define RE(i, n) FOR(i,1,n)
#define REP(i,n) FOR(i, 0, (int)(n)-1)
#define all(x) (x).begin(), (x).end()
#define fst first
#define snd second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef tuple<int,int,int> iii;

string to_string(string s) {
    return '"' + s + '"';
}
    
string to_string(const char* s) {
    return to_string((string) s);
}
    
string to_string(bool b) {
    return (b ? "true" : "false");
}
    
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
    
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

void fastIO() {
    cin.sync_with_stdio(false);
    cin.tie(0);
}

template<typename T>
vector<T> make_unique(vector<T> v) {
    sort(all(v));
    return v.resize(unique(all(v)) - v.begin());
}

int nxt() {
    int x;
    cin >> x;
    return x;
}


int XMOV[4] = {0, 0, 1, -1};
int YMOV[4] = {1, -1, 0, 0};

//#############################
const int MAXN = 1000005;
vector<vector<int>> a;
int n,m,x;
ll ans;
bool mark[13];

bool check(vector<ll> &v) {
    for(int i = 0; i < v.size(); i++)
        if (v[i] < x )
            return false;
    
    return true;
}

int main() {
    n = nxt(), m = nxt(), x = nxt();
    a = vector<vector<int>>(n, vector<int>(m+1, 0));
    for(int i = 0; i < n; i++){
        for (int j = 0; j < m+1; j++){
            cin >> a[i][j];
        }
    }
    memset(mark, 0, sizeof(mark));
    ans = 0x3f3f3f3f;
    for(int bitmask = 0; bitmask < (1 << n); bitmask++){
        vector<ll> skills(m, 0);
        ll sum = 0;
        for(int bit = 0; bit < n; bit++){
            if ((1 << bit) & bitmask){
                for(int i = 0;i < m; i++){
                    skills[i]+= a[bit][i+1];
                    // cout << a[bit][0] << endl;
                }
                sum += a[bit][0];
            }
        }
        if (check(skills)){
            // cout << "x: " << x << " " << to_string(skills) << " " << sum << " " << bitset<3>(bitmask) << endl;
            ans = min(ans, sum);
        }
    }
    cout << (ans == 0x3f3f3f3f? -1 : ans) << endl;
    return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
int n,m;
std::vector<std::vector<std::pair<int,int>>> hen; // ver : cost
std::vector<std::vector<int>> seen; //辺i-jの使用回数

void dijkstra(int start){
    std::vector<int> past(n, n + 5);
    std::vector<int> dist(n,1000000000);
    using T = std::pair<int, int>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> que;
    que.push({0,start});
    dist[start] = 0;
    while(que.size()){
        auto cur = que.top();
        que.pop();
        for(auto i : hen[cur.second]){

            if(dist[cur.second] + i.second < dist[i.first]){
                dist[i.first] = cur.first + i.second;
                seen[i.first][past[i.first]]--;
                seen[past[i.first]][i.first]--;
                seen[i.first][cur.second]++;
                seen[cur.second][i.first]++;
                que.push({dist[i.first],i.first});
                past[i.first] = cur.second;
            }
        }
    }
}


int main()
{
    std::cin >> n >> m;
    hen.resize(n);
    seen.resize(n + 10,std::vector<int>(n + 10,-1000000000));
    for(int i = 0; i < m; i++){
        int a,b,c;
        std::cin >> a >> b >> c;
        a--; b--;
        hen[a].push_back({b,c});
        hen[b].push_back({a,c});
        seen[a][b] = 0;
        seen[b][a] = 0;
    }


    for(int i = 0; i < n; i++)dijkstra(i);
    int cnt = 0;


    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(seen[i][j] == 0)cnt++;
        }
    }

    std::cout << cnt << std::endl;

}


Measured memory_bytes: 384
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream> 

using namespace std;
typedef long long int ll;
typedef long double ld;

//repetition
#define REP(i,n)  for(ll i=0;i<n;i++)

unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
 
unsigned binarySearch(ll target, ll max, ll min) {
  while((max - min) > 1) {
      if((max + min)/2 > target) {
        max = (max + min)/2;
        min = min;
      } else {
        max = max;
        min = (max + min)/2;
      }
    }
}

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}

ll r,s,p;

ll calc(ll total, string sc) {
  if (sc == "p") {
    total = total + s;
  } else if(sc == "r") {
    total = total + p;
  } else if (sc == "s") {
    total = total + r;
  }
  return total;
}


int main() {
  ll n,k;
  cin >> n >> k;
  cin >> r >> s >> p;
  vector<string> v(k, "");
  vector<bool> vb(k, false);

  ll total = 0;

  REP(i, n) {
    char c;
    cin >> c;
    string sc{c};

    if(v.at(i%k) == sc) {
      if(vb.at(i%k)) {
        total = calc(total, sc);
        vb.at(i%k) = false;
      } else {
        vb.at(i%k) = true;
      }
    } else {
      total = calc(total, sc);
      vb.at(i%k) = false;
    }
    v.at(i%k) = sc;
  }

  cout << total << endl;
}


Measured memory_bytes: 5120
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
int a,b,c,d;
while(~scanf("%d%d%d",&a,&b,&c))
{
    if(a==b&&a!=c&&b!=c)
        printf("Yes\n");
    else if(a==c&&a!=b&&c!=b)
         printf("Yes\n");
    else if(b==c&&b!=a&&a!=c)
         printf("Yes\n");
    else
        printf("No\n");
}

}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int b[n-1];
  int i;
  for(i=0;i<n-1;i++){
    cin >> b[i];
  }
  int ans = b[0];
  for(i=1;i<n-1;i++){
    ans += min(b[i],b[i-1]);
  }
  ans += b[n-2];
  cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int main() {
  int n,m,ans; cin>>n;
  map<string,int> a;
  rep(i,n){
    string s; cin>>s; a[s]++;
  }
  cin>>m;
  rep(i,m){
    string s; cin>>s; a[s]--;
  }
  for(auto x:a) ans=max(ans,x.second);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
from math import factorial
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
a=0
b=0
for i in range(n-1):
  A=0
  B=0
  for j in range(i+1,n):
    if p[i]>p[j]:
      A+=1
    if q[i]>q[j]:
      B+=1
  a+=factorial(n-i-1)*A
  b+=factorial(n-i-1)*B
  
print(abs(a-b))

Measured memory_bytes: 9196
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
int main(){
   int a,b,c;
   cin >> a >> b >> c;
   cout << max(c-a+b,0) <<endl;
}

Measured memory_bytes: 256
#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(unused_variables)]
#![allow(dead_code)]

use itertools::Itertools;
use proconio::input;
use proconio::marker::{Chars, Usize1};

#[allow(unused_macros)]
#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    //($arg:expr) => (println!("{:?}",$arg));
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
}
#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}

macro_rules! echo {
    ($($a:expr),*) => {
          $(println!("{}",$a))*
      }
}

use std::cmp::*;
use std::collections::*;
use std::ops::{Add, Div, Mul, Sub};

#[allow(dead_code)]
static INF_I64: i64 = 92233720368547758;
#[allow(dead_code)]
static INF_I32: i32 = 21474836;
#[allow(dead_code)]
static INF_USIZE: usize = 18446744073709551;
#[allow(dead_code)]
static M_O_D: usize = 1000000007;
#[allow(dead_code)]
static PAI: f64 = 3.1415926535897932;

trait IteratorExt: Iterator {
    fn toVec(self) -> Vec<Self::Item>;
}

impl<T: Iterator> IteratorExt for T {
    fn toVec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

trait CharExt {
    fn toNum(&self) -> usize;
    fn toAlphabetIndex(&self) -> usize;
    fn toNumIndex(&self) -> usize;
}
impl CharExt for char {
    fn toNum(&self) -> usize {
        return *self as usize;
    }
    fn toAlphabetIndex(&self) -> usize {
        return self.toNum() - 'a' as usize;
    }
    fn toNumIndex(&self) -> usize {
        return self.toNum() - '0' as usize;
    }
}

trait VectorExt {
    fn joinToString(&self, s: &str) -> String;
}
impl<T: ToString> VectorExt for Vec<T> {
    fn joinToString(&self, s: &str) -> String {
        return self
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(s);
    }
}

trait StringExt {
    fn get_reverse(&self) -> String;
}
impl StringExt for String {
    fn get_reverse(&self) -> String {
        self.chars().rev().collect::<String>()
    }
}

trait UsizeExt {
    fn pow(&self, n: usize) -> usize;
}
impl UsizeExt for usize {
    fn pow(&self, n: usize) -> usize {
        return ((*self as u64).pow(n as u32)) as usize;
    }
}

fn main() {
    input! {
       a: usize,
    }

    let mut ans: usize = 0;
    ans = a + a * a + a * a * a;

    echo!(ans);
}


Measured memory_bytes: 2156
S = list(map(str, input().rstrip()))

ans = [0]*(len(S)+1)

for i, s in enumerate(S):
    if s=="<":
        ans[i+1] = max(ans[i+1], ans[i]+1)

ans = ans[::-1]
S = S[::-1]

for i, s in enumerate(S):
    if s==">":
        ans[i+1] = max(ans[i+1], ans[i]+1)

print(sum(ans))

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

using namespace std;

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

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

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


Measured memory_bytes: 3576
A, B, C, D = map(int,input().split())
ans = 0
x1c = B // C
x1d = B // D
x2c = (A-1) // C
x2d = (A-1) // D
def gcd(x,y):
    if x < y:
        z = x
        x = y
        y = z
    while y != 0:
        x, y = y, x%y
    return x
g = gcd(C,D)
l = (C*D) // g
x1cd = B // l
x2cd = (A-1) // l
ans_B = B - (x1c+x1d-x1cd)
ans_A = (A-1) - (x2c+x2d-x2cd)
ans = ans_B - ans_A
ans = int(ans)
print(ans)

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

using namespace std;

int main()
{
    while (true) {
        int64_t a, b;
        char op;
        cin >> a >> op >> b;
        if (op == '?') break;
        switch (op) {
        case '+':
            cout << a + b << endl;
            break;
        case '-':
            cout << a - b << endl;
            break;
        case '*':
            cout << a * b << endl;
            break;
        case '/':
            cout << a / b << endl;
            break;
        default:
            break;
        }
    }
    
    return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,a[N],k;
int cal(int m)
{
	int s=0;
	for(int i=1;i<=n;i++)
	{
		s+=(a[i]+m-1)/m-1;
		if(s>k)
			return 0;
	}
	return 1;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=0,r=1e9;
	while(r-l>1)
	{
		int m=l+r>>1;
		if(cal(m))
			r=m;
		else
			l=m;
	}
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 4540
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
template <typename T> 
struct SegmentTree {
  
  int n;
  vector<T> node;
  T e;

  T f(T a, T b) {return max(a, b);}
  void g(T &a, T b) {a = b;}

  SegmentTree (int sz, T init = 0) {
    n = 1; e = init; while (n < sz) n <<= 1;
    node.assign(2*n, init);
    for (int i = n - 2; i >= 0; i--) node[i] = f(node[2*i+1], node[2*i+2]);
  }

  void update(int k, T x) {
    k += (n - 1);
    g(node[k], x);
    while (k > 0) {
      k = (k - 1) >> 1;
      node[k] = f(node[2*k+1], node[2*k+2]);
    } 
  }

  T query(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (r <= a || b <= l) return e;
    if (a <= l && r <= b) return node[k];
    T vl = query(a, b, 2*k+1, l, (l+r)/2);
    T vr = query(a, b, 2*k+2, (l+r)/2, r);
    return f(vl, vr);
  }

  T getvalue(int k) {
    return query(k,k+1);
  }
  
  template <typename F> 
  int find (int a, int b, T x, F &ok, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (!ok(node[k]) || r <= a || b <= l) return b;
    if (k >= n - 1) return k - n + 1;
    int vl = find(a, b, x, ok, 2*k+1, l, (l + r)/2);
    if (vl != b) return vl;
    return find(a, b, x, ok, 2*k+2, (l + r)/2, r);
  }
 
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  SegmentTree<int> seg(n);
  rep(i,n) {
    int a;
    cin >> a;
    seg.update(i, a);
  }
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, v;
      cin >> x >> v; x--;
      seg.update(x, v);
    } else if (t == 2) {
      int l, r;
      cin >> l >> r; l--;
      
      cout << seg.query(l, r) << "\n";
    } else {
      int x, v;
      cin >> x >> v; x--;
      auto ok = [&](int a) {return a >= v;};
      cout << seg.find(x, n, v, ok) + 1 << "\n";
    }
  }
  return 0; 
}


Measured memory_bytes: 5328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n+1); i++)
int f(int i){
    if(i%2==0){
        return i/2;
    }else{
        return i*3+1;
    }
}
int main() {
    string S;
    cin>>S;
    int a=S.size();
    int ans=0;
    int b=0;
    rep(i,a){
        if(S[i]=='A'||S[i]=='T'||S[i]=='C'||S[i]=='G'){
            b++;
        }
        else{
            if(ans<b){
                ans=b;
            }
            b=0;
        }
    }
  if(ans<b){
    ans=b;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_set>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x,y,z,k;
  cin>>x>>y>>z>>k;
  vector<ll>a(x+1),b(y+1),c(z+1);
  rep(i,x)cin>>a[i];
  rep(i,y)cin>>b[i];
  rep(i,z)cin>>c[i];
  a[x]=(-(ll)1e17);
  b[y]=(-(ll)1e17);
  c[z]=(-(ll)1e17);
  sort(all(a),greater<ll>());
  sort(all(b),greater<ll>());
  sort(all(c),greater<ll>());
  priority_queue<pair<ll,int>>q;
  unordered_set<int> ma;
  q.push({a[0]+b[0]+c[0],0});
  rep(i,k)
  {
    auto tq=q.top();q.pop();
    if(ma.count(tq.second)){i--;continue;}
    ma.insert(tq.second);
    int x[3]={tq.second&1023,tq.second>>10&1023,tq.second>>20&1023};
    rep(j,3)
    {
      x[j]++;
      q.push({a[x[2]]+b[x[1]]+c[x[0]],tq.second+(1<<(10*j))});
      x[j]--;
    }
    cout<<tq.first<<"\n";
  }
  cout<<flush;
  return 0;

}


Measured memory_bytes: 640
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;
const int MOD = 1000000007;

int main() {
	ll N, A, B;
	cin >> N >> A >> B;
	vector<ll> X(N);
	REP(i, N) {
		cin >> X[i];
	}

	ll ans = 0;
	REP(i, N - 1) {
		ans += min((X[i + 1] - X[i])*A, B);
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char num[4];
    int a[4];
    scanf("%s",num);
    for(int i = 0;i<4;i++){
        a[i] = num[i]-'0';
    }
    if(a[0]+a[1]+a[2]+a[3] == 7)
        printf("%d+%d+%d+%d=7\n",a[0],a[1],a[2],a[3]);
    else if(a[0]+a[1]+a[2]-a[3] == 7)
        printf("%d+%d+%d-%d=7\n",a[0],a[1],a[2],a[3]);
    else if(a[0]+a[1]-a[2]-a[3] == 7)
        printf("%d+%d-%d-%d=7\n",a[0],a[1],a[2],a[3]);
    else if(a[0]+a[1]-a[2]+a[3] == 7)
        printf("%d+%d-%d+%d=7\n",a[0],a[1],a[2],a[3]);
    else if(a[0]-a[1]+a[2]+a[3] == 7)
        printf("%d-%d+%d+%d=7\n",a[0],a[1],a[2],a[3]);
    else if(a[0]-a[1]+a[2]-a[3] == 7)
        printf("%d-%d+%d-%d=7\n",a[0],a[1],a[2],a[3]);
    else if(a[0]-a[1]-a[2]+a[3] == 7)
        printf("%d-%d-%d+%d=7\n",a[0],a[1],a[2],a[3]);
    return 0;
}


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

stack<int>S;
int n, a, b, g[105], w;
vector<int>x[105];

void dfs() {
	for (int j = 0; j < x[S.top()].size(); j++) {
		if (g[x[S.top()][j]] == 0) {
			g[x[S.top()][j]] = 1;
			S.push(x[S.top()][j]);
			w = max(w, (int)S.size());
			dfs();
		}
	}
	g[S.top()] = 0;
	S.pop();
}

int main() {
	while (true) {
		w = 0;
		for (int i = 0; i < 105; i++) {
			x[i].clear();
		}
		cin >> n;
		if (n == 0) { break; }
		for (int i = 0; i < n; i++) {
			cin >> a >> b;
			x[a].push_back(b);
			x[b].push_back(a);
		}
		for (int i = 1; i <= 100; i++) {
			S.push(i);
			g[i] = 1;
			dfs();
			g[i] = 0;
			if (S.size() >= 1) {
				S.pop();
			}
		}
		cout << w << endl;
	}
}

Measured memory_bytes: 3096
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int top, S[1000];

void push(int x){
   S[++top] = x;
}

int pop(){
   top--;
   return S[top+1];
}

int main(){
   int a, b;
   top = 0;
   char s[100];

   while(scanf("%s", s) != EOF){
      // cout << s << endl;
      if(s[0]=='+'){
         a = pop();
         b = pop();
         push(a+b);
      } else if (s[0]=='-'){
         a = pop();
         b = pop();
         push(b-a);
      } else if (s[0]=='*'){
         a = pop();
         b = pop();
         push(a*b);
      } else {
         push(atoi(s));
      }
   }
   printf("%d\n", pop());

   return 0;
}



Measured memory_bytes: 3212
import Foundation

let input = readLine()!.components(separatedBy: " ").map{ Int($0)! }
let L = input[0]
let R = input[1]
let d = input[2]
var count = 0

for i in L...R {
    if i % d == 0{
        count += 1
    }
}

print(count)

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

int main() {
  int N;
  cin >> N;
  int ichi = N % 10;
  if (ichi == 3) {
    cout << "bon" << endl;
  } else if (ichi == 0 || ichi == 1 || ichi == 6 || ichi == 8) {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }
  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdtr1c++.h>
using namespace std;
#define INP "solve"
#define OUT "solve"
const int QQ = 3e5 + 10;
const int maxN = 3e5 + 10;
const int maxM = 3e5 + 10;
const int oo = 1e9;
const int module = 1e9 + 7;
const long double du = 1e-9;

void doc() {
    freopen(INP ".inp","r",stdin);
    freopen(OUT ".out","w",stdout);
}

vector <int> a[26];
int Next(int c, int pos) {
    if ((int)a[c].size() == 0) return -1;
    auto VT = lower_bound(a[c].begin(), a[c].end(), pos + 1);
    if (VT == a[c].end()) return *a[c].begin();
    return *VT;
}
long long Check(string S, string T) {
    int L = -1;
    int n = (int)S.size();
    long long Res = 0;
    for (int i = 0; i < n; i++) a[S[i] - 'a'].push_back(i);
    for (char c : T) {
        int newL = Next(c - 'a', L);
        if (newL == -1) return -1;
        if (newL <= L) Res += n;
        L = newL;
    }
    Res += L + 1;
    return Res;
}
void solve() {
    string s, t;
    cin >> s >> t;
    cout << Check(s, t);
}
int main(int argc,char *argv[]) {
    //srand(time(nullptr));
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    //doc();
    solve();
}


Measured memory_bytes: 1232
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

int main() {
  size_t H, W;
  std::cin >> H >> W;
  char c[55][55];
  for (size_t i = 0; i < H; i++) {
    for (size_t j = 0; j < W; j++) {
      std::cin >> c[i][j];
    }
  }

  for (size_t i = 0; i < H; i++) {
    for (size_t j = 0; j < W; j++) {
      if (c[i][j] == '#') {
        const int dx[] = {-1, 0, 0, 1};
        const int dy[] = {0, 1, -1, 0};

        bool flag = false;
        for (size_t t = 0; t < 4; t++) {
          int ny = i + dy[t], nx = j + dx[t];
          if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
          if (c[ny][nx] == '#') {
            flag = true;
            break;
          }
        }

        if (!flag) {
          std::cout << "No" << std::endl;
          return 0;
        }
      }
    }
  }

  std::cout << "Yes" << std::endl;
  return 0;
}


Measured memory_bytes: 256
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a // gcd(a, b) * b

n = int(input())
ans = 1
for i in range(n):
    ans = lcm(ans, int(input()))
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 2e9;

void merge(int& count, vector<int>& A, int left, int mid, int right)
{
    vector<int> L(A.begin() + left, A.begin() + mid);
    vector<int> R(A.begin() + mid, A.begin() + right);
    L.push_back(INF);
    R.push_back(INF);
    int i = 0;
    int j = 0;
    for (int k = left; k < right; ++ k) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            ++i;
        }
        else {
            A[k] = R[j];
            ++j;
        }
    }
    count += (right - left);

}

void mergeSort(int& count, vector<int>& A, int left, int right) 
{
    if (left + 1 < right) {
        const int mid = (left + right) / 2;
        mergeSort(count, A, left, mid);
        mergeSort(count, A, mid, right);
        merge(count, A, left, mid, right);
    }
}


int main() {
    int n;
    cin >> n;
    vector<int> S(n);
    for (auto& s : S) {
        cin >> s;
    }

    int count = 0;
    mergeSort(count, S, 0, n);
    for (int i = 0; i < S.size() - 1; ++i) {
        cout << S[i] << " ";
    }
    cout << S.back() << endl;
    cout << count << endl;

}


Measured memory_bytes: 8576