akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main(){
  int length,data[100];
  int i,j,minj,datai,count=0;

  
  //input
  scanf("%d",&length);
  
  for(i=0;i<length;i++){
    scanf("%d",&data[i]);
  }
  
  
  for(i=0;i<length;i++){
    minj=i;
    
    for(j=i;j<length;j++){
      if(data[j] < data[minj]){
	minj=j;
      }
    }
    
    if(data[i]!=data[minj]){
      datai=data[i];
      data[i]=data[minj];
      data[minj]=datai;
      count++;
    }
  }
  
  
  //output
  for(i=0;i<length;i++){
    if(i+1==length){
      printf("%d",data[i]);
    }
    else{
      printf("%d ",data[i]);
    }
  } 
  printf("\n%d\n",count);

  
  return 0;
}



Measured memory_bytes: 2104
#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))

int main(void) {
	int N,W; // seguindo o padrão de N(n) e W(n)
	scanf("%d%d",&N,&W);
	long long int w[N],v[N];
	for(int i=0;i<N;i++){
		scanf("%lld%lld",&w[i],&v[i]);
	}
	long long int vc[N+1][W+1];
	for(int i=0;i<=W;i++) vc[0][i] = 0;
	for(int i=0;i<N;i++){
		for(int j=0;j<=W;j++){
			if(j<w[i]) vc[i+1][j] = vc[i][j];
			else vc[i+1][j] = max(vc[i][j],vc[i][j-w[i]]+v[i]);
		}
	}
	printf("%lld",vc[N][W]);
	return 0;
}

Measured memory_bytes: 79104
use input::Input;

fn main() {
    let mut input = Input::default();

    let n: u32 = input.parse();
    let n = n % 10;

    if n == 2 || n == 4 || n == 5 || n == 7 || n == 9 {
        println!("hon");
    } else if n == 0 || n == 1 || n == 6 || n == 8 {
        println!("pon");
    } else {
        println!("bon");
    }
}

#[allow(dead_code)]
pub mod input {
    #[derive(Default)]
    pub struct Input(Vec<String>);

    impl Input {
        pub fn read_line(&mut self) -> String {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).ok().expect("read error");
            s
        }
        pub fn parse<T: std::str::FromStr>(&mut self) -> T {
            let x = if let Some(x) = self.0.pop() {
                x
            } else {
                let s = self.read_line();
                self.0 = s.split_whitespace().map(String::from).rev().collect();
                self.0.pop().expect("reached EOF")
            };
            x.parse().ok().expect("parse error")
        }
    }
}


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

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    long long N;
    cin >> N;
    int ans = 0;
    for (int c=1;c<N;c++){
      const auto &pf = prime_factorize(N-c);
      long long res = 1;
      for (auto p : pf) res *= p.second + 1;
      ans += res;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
li read(){
	li x = 0,y = 1;
	char c;
	c = gc;
	while(!isdigit(c)){
		if(c == '-') y = -1;
		c = gc;
	}
	while(isdigit(c)){
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = gc;
	}
	return x * y;
}
void print(li q){
	if(q < 0){
		pc('-');
		q = -q;
	}
	if(q >= 10) print(q / 10);
	pc(q % 10 + '0');
}
li n,c;
li a[100010],b[100010],as;
li mx1[100010],mx2[100010];
int main(){
	int i,j;
	n = read();
	c = read();
	for(i = 1;i <= n;++i){
		a[i] = read();
		b[i] = read();
	}
	li nw = 0;
	for(i = 1;i <= n;++i){
		nw += b[i] - (a[i] - a[i - 1]);
		mx1[i] = max(mx1[i - 1],nw);
		as = max(as,mx1[i]);
	}
	a[n + 1] = c;nw = 0;
	for(i = n;i;--i){
		nw += b[i] - (a[i + 1] - a[i]);
		mx2[i] = max(mx2[i + 1],nw);
		as = max(as,mx2[i]);
	}
	for(i = 1;i < n;++i) as = max(as,mx1[i] + mx2[i + 1] - a[i]);
	for(i = 2;i <= n;++i) as = max(as,mx1[i - 1] + mx2[i] - (c - a[i]));
	print(as);
	return 0;
}

Measured memory_bytes: 3328
// template {{{

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

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = std::uint32_t;
using ll = std::int64_t;
using ull = std::uint64_t;
using ld = long double;

template<typename T, size_t H, size_t W>
using matrix = std::array<std::array<T, W>, H>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(all(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(all(c)); }

template<typename T>
inline void unique(T &c){ std::sort(c); c.erase(std::unique(all(c)), std::end(c)); }

// }}}

int n, m;
int g[100][100];

int dfs(int p, vector<int> &v)
{
	if (p == n){
		if (v.size() <= 1) return 0;
		int res = 0;
		rep(i, v.size()){
			int mn = INF;
			rep(j, v.size()){
				if (i == j) continue;
				chmin(mn, g[v[i]][v[j]]);
			}
			res += mn;
		}
		return res;
	}
	
	bool f = true;
	rep(i, v.size()){
		if (g[p][v[i]] == 0) f = false;
	}
	int res = 0;
	if (f){
		v.pb(p);
		chmax(res, dfs(p + 1, v));
		v.pop_back();
	}
	chmax(res, dfs(p + 1, v));
	return res;
}

int main()
{
	cin >> n >> m;
	rep(i, m){
		int u, v, f;
		cin >> u >> v >> f, u--, v--;
		g[u][v] = f;
		g[v][u] = f;
	}
	vector<int> v;
	cout << dfs(0, v) << endl;
}

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

int main()
{
 int N,cnt=0,res=0,i,j;
 cin>>N;
  if(N==1) cout<<0<<endl;
  else {
   for(i=3;i<=N;i+=2)
   { //cout<<i<<": ";
       cnt=0;
       for(j=2;j<i;j++)
           {
              // cout<<j<<": ";
               if(i%j==0)
                {
                    cnt++;
                   // cout<<cnt<<endl;
                }
           }
           cnt+=2;
           if(cnt==8) res++;

    }
     cout<<res<<endl;
  }





    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
ll dp[10001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,M;
    cin>>N>>M;
    int A[M];
    rep(i,0,M) cin>>A[i];
    sort(A,A+M);
    reverse(A,A+M);
    int a[10]={0,2,5,5,4,5,6,3,7,6};
    rep(i,1,N+1){
        ll m=0;
        bool t=false;
        rep(j,0,M){
            if(a[A[j]]<=i){
                m=max(m,dp[i-a[A[j]]]);
                if(a[A[j]]==i) t=true;
            }
        }
        if(m==0){
            if(t) dp[i]=1;
        }
        else{
            dp[i]=m+1;
        }
    }
    while(dp[N]>1){
        rep(i,0,M){
            if(N>=a[A[i]]&&dp[N]==dp[N-a[A[i]]]+1){
                N-=a[A[i]];
                cout <<A[i];
                break;
            }
        }
    }
    rep(i,0,M){
        if(N==a[A[i]]){
            cout<<A[i];
            break;
        }
    }
    cout<<"\n";
}

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

int main() {
  int N, M; cin >> N >> M;
  cout << N*(N-1)/2 + M*(M-1)/2 << endl;
  return 0;
}


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

#define ll long long

ll abc (ll x) {
  if (x < 0) {
    return -1 * x;  
  }  
  return x;
}

int main () {
  ll n;
  cin >> n;
  bool ok = false;
  bool fail = false;
  ll x[n], y[n];
  ll xx[n], yy[n];
  for (ll i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    xx[i] = x[i] + 1000000000;
    yy[i] = y[i] + 1000000000;
    if (i == 0 && xx[i] % 2 == yy[i] % 2) {
      ok = true;    
    }  
    if (ok && xx[i]% 2 != yy[i] % 2) {
      fail = true;    
    }
    if (!ok && xx[i] % 2 == yy[i] % 2) {
      fail = true;  
    }
  }  
  if (fail) {
    cout << "-1" << endl;  
    return 0;
  }
  ll m;
  m = 39;
  if (ok) {
    m++;  
  }
  ll two[m];
  for (ll i = 0; i < m; i++) {
    if (i == 0) {
      two[m - i - 1] = 1;  
      cout << m << endl;
    }    
    else {
      if (i == 1 && m == 40) {
        two[m - i - 1] = 1;  
      }
      else {
        two[m - i - 1] = two[m - i] * 2;  
      }
    }
  }
  for (ll i = 0; i < m; i++) {
    if (i != m - 1) {
      cout << two[i] << " ";  
    }  
    else {
      cout << two[i] << endl;  
    }
  }
  for (ll i = 0; i < n; i++) {
    // x, yについて求める.
    for (ll j = 0; j < m; j++) {
      // まずx, yにどっちが大きいかを調べる
      if (abc(x[i]) > abc(y[i])) {
        if (x[i] > 0) {
          x[i] = x[i] - two[j];
          cout << "R";  
        }  
        else {
          x[i] = x[i] + two[j];  
          cout << "L";
        }
      } 
      else {
        if (y[i] > 0) {
          y[i] = y[i] - two[j];
          cout << "U";  
        }    
        else {
          y[i] = y[i] + two[j];
          cout << "D";  
        }
      }         
    }   
    cout << endl;
  }

}

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

typedef long long ll;

#define REP(i, n) for(int i=0; i<(n); i++)
#define REPS(i, n) for(int i=0; i<=(n); i++)
#define FOR(i, a, b) for(int i=a; i<(b); i++)
#define FORS(i, a, b) for(int i=a; i<=(b); i++)
// for container x
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#pragma endregion

int main(){
    vector<int> x(5);
    REP(i, 5) cin >> x[i];
    REP(i, 5) {
        if (x[i] == 0) {
            cout << (i+1);
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3612
require 'pp'

###################

# inputType = :singleLine
inputType = :l2Lines
# inputType = :nLines
  
def main(query)
  n = query[0]
  as = tois(query[1].split(" "))

  e = 0
  s = 0
  as.each { | t |
    if (t >= e) then
      e = t
    else
      s = s + e - t
    end
  }
  return [s]
end

###################

TEST=false

def tois(l)
  l.map { | x | x.to_i}
end

def ppp(msg, val)
  if (TEST) then
    print msg
    pp val
  end
end

target = nil
if (ARGV.size == 0) then
  f = STDIN
end
if (ARGV.size > 0) then
  f = open(ARGV[0])
end
if (ARGV.size > 1) then
  target = ARGV[1].to_i
end

t = 1
ng = []
while true
  query = []
  if (inputType == :singleLine) then
    a = f.gets
    if ! a then
      exit
    end
    a.chomp!
    query.push a
  elsif (inputType == :l2Lines) then
    a = f.gets
    if ! a then
      exit
    end
    a.chomp!
    query.push a
    b = f.gets.chomp
    query.push b
  elsif (inputType == :l3Lines) then
    a = f.gets
    if ! a then
      exit
    end
    a.chomp!
    query.push a
    b = f.gets.chomp
    query.push b
    c = f.gets.chomp
    query.push c
  elsif (inputType == :nLines) then
    a = f.gets
    if ! a then
      exit
    end
    a.chomp!
    query.push a    

    n = a.split(" ")[2].to_i

    query = n.times { | i |
      query.push f.gets.chomp
    }    
  end
  
  aa = f.gets
  if ! aa then
    r = main(query) 
    r.each { | x | puts x }
    exit
  elsif ( aa.chomp == "---") then
    oks = []
    while true
      s = f.gets.chomp
      if (s == "===") then
        break
      end
      oks.push s
    end

    if (target == nil || t == target) then
      if target then
        TEST = true
      end

      puts "--- " + t.to_s + " ---"
      r = main(query)    

      if r.join('\n') == oks.join('\n') then
        puts "RESULT:"
        r.each { | x | puts x }
        puts "OK"
      else
        puts "RESULT:NG"
        r.each { | x | puts x }
        puts "NG!!!!!!!!!"
        ng.push t
      end
    end
  end
  t = t + 1
end
puts "---"
puts "NG targes = " + ng.to_s


Measured memory_bytes: 29172
from collections import deque
import sys
input = sys.stdin.readline
import bisect as bi
from operator import mul
from functools import reduce
import math

def fast_comb(a,b,mod):
    up = reduce(lambda x,y: x*y%mod, range(a,a-b,-1))
    down = reduce(lambda x,y: x*y%mod, range(1,b+1))
    return (up * pow(down, mod-2, mod)) % mod

def prime(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return is_prime

def readlines(n):
    for _ in range(n):
        map(int, input().split())
        yield

def main():
    n,a,b = map(int,input().split())

    base = (n//(a+b)) * a
    plus = min(n % (a+b), a)

    print(base + plus)

main()


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

int mid(int a,int b,int c){
  return a+b+c-max(max(a,b),c)-min(min(a,b),c);
}

int main(){
     int N,D;
  cin >> N >> D;
  if( N % (2 * D + 1) == 0){
      cout <<  N / (2 * D + 1) << endl;
  }
  else{
      cout << N / (2 * D + 1) + 1 << endl;
  }
  
  
}

Measured memory_bytes: 256
#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()
{
  char s[20];
  cin >> s;

  rep(i,19){
    if(i==5||i==13) cout << " ";
    else cout << s[i];
  }

  cout << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>
 
using namespace std;
int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    
    while(a>0){
        c-=b;
        
        if(c>0){
            a-=d;
        }
        else break;
    }
    if(c<=0){
        cout << "Yes" << endl;
        
    }
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 3592
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<numeric>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define MEM(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int main() {
	IOS;
	bool ok = false;
	string s,t;
	cin >> s >> t;
	REP(i, s.size()) {
		char tmp;
		tmp = s[0];
		REP(j, s.size() - 1)s[j] = s[j + 1];
		s[s.size() - 1] = tmp;
		if (s == t)ok = true;
	}
	cout << (ok ? "Yes" : "No") << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int[] a = new int[n + 1];

		for(int i = 1 ; i < n ; i++) {
			for(int j = i + 1 ; j <= n ; j++) {
				a[Math.min(j - i, Math.abs(x - i) + 1 + Math.abs(j - y))]++;
			}
		}
		String s = "" + a[1];
		StringBuilder sb = new StringBuilder(s);
		for(int i = 2 ; i < n ; i++) {
		sb.append("\n" + a[i]);
		}
		System.out.println(sb.toString());
		sc.close();

	}
}



Measured memory_bytes: 39256
/* 2^30极限 */ 
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define opr iterator
typedef long long ll;
using namespace std;
int ok[31];
int num[100001];
int n;
int prev[100001];
vector<int> odd;
bool check(int a,int b)
{
	return !(!(~((a^b)^1)));
}
int findodd()
{
	int no=odd.size();
	long long t=1;
	int tmp=odd[no-1]+odd[no-2];
	while(1)
	{
		t*=2;
//		cout<<t<<" "<<tmp<<" "<<t*2<<endl; 
		if(t<=tmp&&tmp<t*2)
		{
			break;
		}
	}
//	cout<<t<<endl;
	map<int,int> tim;
//	memset(tim,0,sizeof(tim));
	for(int i=0;i<no;i++)
	{
		tim[odd[i]]=0;
	}
	for(int i=0;i<no;i++)
	{
		tim[odd[i]]++;
	}
/*	cout<<tim.size()<<endl;
	for(int i=1;i<=odd[no-1];i++)
	{
		cout<<tim[i]<<" ";
	}
	cout<<endl;
	vector<int> tim(t+1,0);
	for(int i=0;i<no;i++)
	{
		tim[odd[i]]++;
	}
	for(int i=1;i<=t;i++)
	{
		cout<<i<<" ";
	}
	cout<<endl;
	for(int i=1;i<=t;i++)
	{
		cout<<tim[i]<<" ";
	}
	cout<<endl;*/
	int cnt=0;
	int smallest=odd[0]+odd[1];
	while(t>=smallest)
	{
		for(int i=0;i<no;i++)
		{
			if(tim[odd[i]]&&tim[t-odd[i]])
			{
//				cout<<odd[i]<<" "<<t-odd[i]<<endl;
				int tmp1;
				if(odd[i]!=t-odd[i])
				{
					tmp1=min(tim[odd[i]],tim[t-odd[i]]);
					cnt+=tmp1;
					tim[odd[i]]-=tmp1;
					tim[t-odd[i]]-=tmp1;
				}
				else
				{
					tmp1=tim[odd[i]]/2;
					cnt+=tmp1;
					tim[odd[i]]-=tmp1*2;
				}
			}
		}
		t/=2;
	}
	return cnt;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		odd.pb(x);
	}
	sort(odd.begin(),odd.end());
	int cnt=0;
	cnt+=findodd();
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 188148
#include <stdio.h>

int main(){
	int H, W;
	int i, j;
	
	while( scanf("%d %d", &H, &W) != EOF )

	if (H == 0 && W == 0) {
		break; 
	} else {
		for(i=0; i<H; i++) {
			for(j=0; j<W; j++) {
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 572
#include<iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin >> N;
	for (int i = 1; i <= 9; i++){
		for (int j = 1; j <= 9; j++) {
			if (i * j == N) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

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

int main(){
	int N;
	cin>>N;
	vector<int> A;
	int a;
	for(int i=0;i<N;i++){
		cin>>a;
		A.push_back(a);
	}
	sort(A.begin(), A.end());
	cout<<A.back()-A.front();
	return 0;
}	


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define trace(x) cout << '>' << #x << ':' << x << "\n" 
#define trace2(x,y) cout<< '>' << #x << ':' << x << " | " << #y << ':' << y << "\n" 
#define trace3(a,b,c) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" 
#define trace4(a,b,c,d) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" 
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define endl '\n' 
typedef vector<int> VI;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const ll mod=1000000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxn = 1e5 + 10;

int dp[2005];

int main()
{
    fastIO;
    int s;
    cin >> s;
    dp[0] = 1;
    for(int i = 1; i <= s; ++i)
        for(int j = 3; j <= i; ++j)
            dp[i] = (dp[i] + dp[i - j]) % mod;
    cout << dp[s] << endl; 
    return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll findTrailingZeros(ll n)
{
    ll cnt = 0;
    for (ll i = 5; n / i >= 1; i *= 5)
        cnt += n / i;

    return cnt;
}
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t;
	t=1;
	while(t--)
    {
        ll n,m;
        cin>>n>>m;
        double s=0;
        ll arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
            s+=arr[i];
        }
        s/=(4*m);
        ll cnt=0;
        for(int i=0;i<n;i++)
            if(arr[i] >= s)
            cnt++;
        if(cnt>=m)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.stream.LongStream;

public class Main
{

	public static void main(String[] args)
	{
		System.out.println(LongStream.rangeClosed(1, Integer.parseInt((new Scanner(System.in)).next())).reduce(1, (x, y) -> (x * y) % 1000000007));
	}
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

ll dp[150][2];
int l, k;

int main() {
    cin >> l >> k;
    dp[0][1] = 1;
    rep(i, l) {
        dp[i+1][0] += dp[i][1];
        dp[i+k][0] += dp[i][1];
        dp[i+1][1] += dp[i][0];
    }
    ll ans = 0;
    rep(i, l+1) ans += dp[i][0];
    cout << ans << endl;
}



Measured memory_bytes: 3100
N,M,C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

cnt = 0

for i in range(N):
    result = 0
    for j in range(M):
        result += A[i][j]*B[j]
    result += C

    if result > 0:
        cnt += 1

print(cnt)
        


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

using ll = long long int;
using P = pair<int, int>;
using P3 = pair<int, P>;
using PP = pair<P, P>;
constexpr int INF = 1 << 30;
constexpr ll MOD = ll(1e9) + 7;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};


bool solve(){
    int N, Q;
    cin >> N >> Q;
    vector<P> data(N);
    for(int i=0;i<N;i++){
        cin >> data[i].first;
        data[i].second = i;
    }
    sort(data.rbegin(),data.rend());
    vector<int> s(N+1), id(N);
    for(int i=0;i<N;i++){
        s[i] = -data[i].first;
        id[data[i].second] = i;
    }
    s[N] = INF;
    set<int> st;
    st.insert(N);
    for(int t=0;t<Q;t++){
        string query;
        int x;
        cin >> query >> x;
        if(query == "ADD"){
            st.insert(id[x-1]);
        }else if(query == "REMOVE"){
            st.erase(id[x-1]);
        }else{
            int ok = INF, ng = -1;
            while(abs(ok-ng)>1){
                int mid = (ok+ng)/2;
                int cnt = 0;
                for(auto itr=st.begin();*itr!=N;itr++){
                    auto nxt = itr;
                    ++nxt;
                    int l = lower_bound(s.begin(),s.end(),s[*itr])-s.begin(), r = lower_bound(s.begin(),s.end(),s[*nxt])-s.begin();
                    cnt += min(int(upper_bound(s.begin()+l,s.begin()+r,s[l]+mid)-s.begin())-l,r-l);
                }
                if(N-cnt <= x){
                    ok = mid;
                }else{
                    ng = mid;
                }
            }
            if(ok < INF){
                cout << ok << endl;
            }else{
                cout << "NA" << endl;
            }
        }
    }
    return false;
}

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



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

int s (int x) {
  int a = 0;
  while (x != 0) {
    a += x % 10;
    x /= 10;
  }
  return a;
}

int main() {
  int n;
  cin >> n;
  if (n % s(n) == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
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(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

bool cmp(pii& p1, pii& p2){
    return p1.first + p1.second < p2.first + p2.second;
}

class BRobotArms {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int N;
        in>>N;
        vc<pii> A(N);
        for(auto& a : A) in>>a.first>>a.second;
        sort(ALL(A), cmp);
        int cur = -2 * ten(9), ans = 0;
        for(auto& a : A){
            if(cur<=a.first-a.second){
                cur = a.first + a.second;
                ++ans;
            }
        }
        out<<ans<<'\n';
    }
};


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


Measured memory_bytes: 1024
import sys
N,M,X,Y = map(int,input().split())
if X >= Y:
  print('War')
  sys.exit()
x = input().split()
y = input().split()
x = [int(el) for el in x]
y = [int(el) for el in y]
x.sort(reverse=True)
y.sort()
z = [i for i in range(X+1,Y+1)]
judge = 0
for el in z:
  if x[0] < el and y[0] >= el:
    judge += 1
if judge > 0:
  print('No War')
else:
  print('War')

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#include <random>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int D;

int c[27];
int s[366][27];
int last[27];

vector<int> ans;
ll ans_score;

ll calcScore(){
    rep(i,27) last[i] = 0;
    ll score = 0;
    for(int d = 1; d <= D; ++d){
        int t = ans[d];
        score += s[d][t];
        last[t] = d;
        for(int i = 1; i <= 26; ++i){
            score -= c[i] * (d - last[i]);
        }
    }
    return score;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> D;
    for(int i = 1; i <= 26; ++i) cin >> c[i];
    for(int i = 1; i <= D; ++i){
        for(int j = 1; j <= 26; ++j){
            cin >> s[i][j];
        }
    }
    ans.resize(D, 1);
    ans_score = calcScore();
    //local search
    std::random_device rnd;
    std:: mt19937 mt(rnd());
    std::uniform_int_distribution<> randD(1,D);
    rep(_,10000){
        int d = randD(mt);
        for(int q = 1; q <= 26; ++q){
            int old = ans[d];
            ans[d] = q;
            ll score = calcScore();
            if(ans_score > score) ans[d] = old;
            else ans_score = score;
        }
    }
    rep(i,D) cout << ans[i] << endl;
    return 0;
}


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

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll GCD(ll a, ll b) { if(b==0) return a; else return GCD(b, a%b); }
ll LCM(ll a, ll b) { return a/GCD(a,b)*b; }

class ABA {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int a,b;in>>a>>b;
	    if(b%a==0) out<<a+b<<endl;
	    else out<<b-a<<endl;

	}
};


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


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n , t,c, r,x;
    cin >> n >> t;
    x = -1;
    for(int i =0;i<n;i++){
        cin >>c >>r;
        if(r <= t){
            if(x <0 || x>c){
                x = c;
            }
        }
    }
    if(x<0){
        cout << " TLE ";
    }else{
        cout << x;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int n,b[200],i;
vector<int> ans;
int main(){
    cin>>n;
    for(i=1;i<=n;i++)cin>>b[i];
    
    while(n){
        for(i=n;i&&b[i]!=i;i--){}
        if(!i){
            cout<<-1<<endl;
            return 0;
        }
        ans.push_back(i);
        for(;i<=n;i++)b[i]=b[i+1];
        n--;
    }
    for(i=ans.size()-1;i>=0;i--)cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 256
//解説版
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
using namespace std;
int main(){
    string s; cin>>s;
    int l=s.size();
    string ans="AC";
    if(s[0]!='A'){
        ans="WA";
    }
    int cnt=0;
    for(int i=1;i<l;i++){
        if(isupper(s[i])){
            //大文字が条件以外にあるときとCでないときを排除
            if(i==1||i==l-1||s[i]!='C'){
                ans="WA";
            }
            cnt++;
        }
    }
    //大文字二つ以上の条件にすることでCが二つ以上あるときを排除
    if(cnt!=1){
        ans="WA";
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    k, *s = input().split()
    K.append(int(k))
    S.append([int(si) for si in s])
P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    #このスイッチのonoffの組み合わせの時、すべての電球が点灯するか
    on_switch = [0] * N
    all_lights_on = True
    for j in range(N):
        #j番目のスイッチがon
        if i & (1<<j):
            on_switch[j] = 1
    for l in range(M):
        num_on = 0
        s_connected = S[l]
        for s in s_connected:
            if on_switch[s-1]:
                num_on += 1
        if num_on % 2 != P[l]:
            all_lights_on = False
    if all_lights_on:
    	ans += 1

print(ans)


Measured memory_bytes: 3064
import itertools
import math
N=int(input())
a=[]
kyori_list=[]
for i in range(N):
    x,y=map(int,input().split())
    a.append((x,y))
for j in itertools.permutations(a):
    k=list(j)
    
    cnt=0
    sum=0
    while cnt<N-1:
        kryoi=0
        kyori=((k[cnt+1][0]-k[cnt][0])**2+(k[cnt+1][1]-k[cnt][1])**2)**(1/2)
        cnt+=1
        
        sum+=kyori
    kyori_list.append(sum)
c=0

for i in kyori_list:
    c+=i
    
    
print(c/math.factorial(N))

Measured memory_bytes: 4400
MOD = 10**9+7

def mul(a,b):
    return (a*b) % MOD

N,M = map(int, raw_input().split())
A = max(N,M)
B = min(N,M)

def solve():
    if A-B > 1: return 0
    factorical = [1]
    for n in range (1,A+1):
        f = mul(factorical[n-1], n)
        factorical.append(f)
    if A == B:
        return mul(2, mul(factorical[A], factorical[B]))
    else:
        return mul(factorical[A], factorical[B])

print solve()

Measured memory_bytes: 8964
#include<iostream>
#include<string>

using namespace std;

int main()
{
	//int a,b;
	string str;
	int i = 0;
	int j = 0;
	int cnt = 0;

    cin >> str;
    const char* chara = str.c_str();
    const char* charb = chara;

    while(chara[i] != '\0'){
    	j = 0;
		cnt = 0;
    	while(charb[j] != '\0'){
    		if(charb[j]==chara[i]){
    			cnt++;
    			if(cnt >= 2){
    				cout<<"no"<<endl;
    				return 0;
    			}
    		}
    		j++;
    	}
    	i++;
    }
    cout<<"yes"<<endl;
    return 0;
}


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

int main() {
	int N, A, X1 = 0, X2 = 0, X4 = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A;
		if (A % 4 == 0) X4++;
		else if (A % 2 == 0) X2++;
		else X1++;
	}
	if (X2 == 0) {
		if (X1 <= X4 + 1) cout << "Yes";
		else cout << "No";
	}
	else {
		if (X1 <= X4) cout << "Yes";
		else cout << "No";
	}
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
    
        int W = sc.nextInt();
        int a=sc.nextInt();
        int b =sc.nextInt();
        if(a+W<b){
            System.out.println(b-(a+W));
            return;
        }else if(b+W<a){
            System.out.println(a-(b+W));
            return;
        }else{
            System.out.println(0);
        }

    }

      //最大公約数・最小公倍数（セットで使う）
static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
static int lcm (int a, int b) {return a*b/gcd(a,b);}

}

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



int main(){
    ll n,k;cin>>n>>k;
    ll a[100010];
    rep(i,0,n)cin>>a[i];
    ll an=0;
    for(ll i=43;i>=0;i--){
        ll cn1=0;
        rep(j,0,n){
            if(a[j]&(1LL<<i))cn1++;
        }
        if(cn1*2<n&&(an+(1LL<<i)<=k))an+=(1LL<<i);
    }
    ll ans=0;
    rep(i,0,n)ans+=(a[i]^an);
    cout<<ans<<endl;
}

    









Measured memory_bytes: 1024
a = gets.chop.to_i
c = 1
(2..a).each do |d|
  c *= d
end
sosu = "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997"
sosui = sosu.split(" ").map(&:to_i)
len = sosui.size
tape = Array.new(len)
tape.fill(1)
(0..(len-1)).each do |i|
  while(c%sosui[i]==0)
    tape[i] += 1
    c /= sosui[i]
  end
end
ans = 1
tape.each do |d|
  ans *= d
end
p ans%(10**9+7)

Measured memory_bytes: 3324
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD=1e9+7;
 
//const int MOD=998244353;

long long calc(string s){
    long long ans=0;
    int n=s.size(), l=0, r=0;
    while(l<n){
        while(s[l]==s[r]) r++;
        ans+=(r-l)/2;
        l=r;
    }
    return ans;
    
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string s;
    cin>>s;
    
    long long k;
    cin>>k;
    
    int n=s.size();
    if(k==1 || s[n-1]!=s[0]){
        cout<<k*calc(s);
        return 0;
    }
    
    set<char> sc;
    for(char c:s){
        sc.insert(c);
    }
    if(sc.size()==1){
        cout<<(k*n)/2;
        return 0;
    }
    int l=0,r=n-1;
    while(s[l]==s[0]) l++;
    while(s[r]==s[0]) r--;
    
    string sst="";
    for(int i=l; i<=r; i++) sst+=s[i];
    //cout<<sst;
    //cout<<(l+n-r)/2;
    
    
    cout<<(l/2+(n-1-r)/2+k*calc(sst)+(k-1)*((l+n-1-r)/2)); 
    //cout<<n-1-r;
    
    return 0;
}


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

    typedef long long int ll;
    #define pb         push_back
    #define mp         make_pair
    #define F          first
    #define S          second
    #define fl(i,a,b)  for(ll i=a;i<b;i++)
    #define pll        pair<ll,ll>
    #define pii        pair<int,int>
    #define all(v)     v.begin(),v.end()
    #define M 1000000007
    #define tr(v, it) for(auto it = v.begin(); it != v.end(); it++)
    using namespace std;


   int n,m;
   char graph[1005][1005];
   bool visited[1005][1005];
   ll dp[1005][1005];

    ll dfs(int i,int j)
    {
        if(i==n-1 && j==m-1)
        {
            return 1;
        }
        if(i>=n || j>=m)
            return 0;
        if(!visited[i][j] && graph[i][j]=='.')
        {
            visited[i][j]=true;
            dp[i][j]= ((dfs(i+1,j)%M)+(dfs(i,j+1)%M))%M;
        }


       return dp[i][j];
    }


    int main()
    {

        ios_base::sync_with_stdio(false);
    	cin.tie(NULL);


         cin>>n>>m;

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

            for(int j=0; j<m; j++)
                {
                    cin>>graph[i][j];
                }
         }


         memset(dp,0,sizeof(dp));
         memset(visited,false,sizeof(visited));


        cout<<(dfs(0,0)%M);

       return 0;
    }


Measured memory_bytes: 13636
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

Q, H, S, D = MAP()
N = INT()

l = [(Decimal(0.25), Q, 0.25/Q), (Decimal(0.5), H, 0.5/H), (1, S, 1/S), (2, D, 2/D)]
l.sort(key=lambda x:x[2], reverse=True)
ans = 0
idx = 0
while N != 0:
	n = N//l[idx][0]
	ans += l[idx][1]*n
	N -= l[idx][0]*n

	idx += 1

print(ans)


Measured memory_bytes: 5200
import sys
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")


Measured memory_bytes: 104796
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
using namespace std;
int main(void) {
    
   int n;
   cin>>n;
    int a[200000];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

   long long int sum[200000];
    sum[0]=a[0];

   for(int i=1;i<n;i++){
       sum[i]=sum[i-1]+a[i];
      // cout<<sum[i]<<" ";
   }  

    //cout<<endl;
    long long int min=2*pow(10,9);

   for(int i=0;i<n-1;i++){
       if(min > abs(sum[i]-(sum[n-1]-sum[i]))){
           min = abs(sum[i]-(sum[n-1]-sum[i]));
       }
   }

   cout<<min<<endl;

    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[100001], N,K, h[100001];

int thunder(int ind){
    if(ind==N){
        return 0;
    }
    if(ind==(N-1)){
        return abs(h[N-1]-h[ind-1]);
    }
    if(dp[ind] != -1){
        return dp[ind];
    }
    int tmp = INT_MAX;
    for(int i=1; i<= K && (ind+i) <= N; i++){
        tmp = min(tmp, abs(h[ind+i-1]-h[ind-1])+thunder(ind+i));
    }
//    int tmp = min(abs(h[ind]-h[ind-1])+thunder(ind+1), abs(h[ind+1]-h[ind-1])+thunder(ind+2));
    return dp[ind]=tmp;
}

signed main(){
    memset(dp, -1, sizeof(dp));
    cin>>N>>K;
    for(int i=0; i < N; i++){
        cin>>h[i];
    }
    cout<<thunder(1)<<endl;
    return 0;
}

Measured memory_bytes: 8064
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;

#define INF (1e9)

int N;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int ans = A[0];
    for (int i = 1; i < N; i++) {
        ans = gcd(ans, A[i]);
    }

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


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

using namespace std;

const int LOG = 60;

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  long long t;
  cin >> n >> t;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int m = *max_element(a.begin(), a.end()) + 1;
  vector<int> last(m, -1);
  vector<int> goes(n, -1);
  vector<long long> step(n);
  for (int i = n - 1; ~i; --i) {
    if (last[a[i]] != -1) {
      goes[i] = last[a[i]];
      step[i] = !last[a[i]];
    }
    last[a[i]] = (i + 1) % n;
  }
  for (int i = 0; i < n; ++i) {
    if (goes[i] == -1) {
      goes[i] = last[a[i]];
      step[i] = 1 + !last[a[i]];
    }
  }
  vector<vector<int>> jump(LOG, vector<int>(n));
  vector<vector<long long>> skip(LOG, vector<long long>(n));
  jump[0] = goes;
  skip[0] = step;
  for (int i = 1; i < LOG; ++i) {
    for (int j = 0; j < n; ++j) {
      jump[i][j] = jump[i - 1][jump[i - 1][j]];
      skip[i][j] = skip[i - 1][j] + skip[i - 1][jump[i - 1][j]];
    }
  }
  int p = 0;
  for (int i = LOG - 1; ~i; --i) {
    if (skip[i][p] < t) {
      t -= skip[i][p];
      p = jump[i][p];
    }
  }
  vector<bool> vis(m);
  vector<int> ans;
  for (int i = p; i < n; ++i) {
    if (vis[a[i]]) {
      while (vis[a[i]]) {
        vis[ans.back()] = false;
        ans.pop_back();
      }
    } else {
      ans.push_back(a[i]);
      vis[a[i]] = true;
    }
  }
  if (t > 1) {
    for (int i = 0; i < n; ++i) {
      if (vis[a[i]]) {
        while (vis[a[i]]) {
          vis[ans.back()] = false;
          ans.pop_back();
        }
      } else {
        ans.push_back(a[i]);
        vis[a[i]] = true;
      }
    }
  }
  for (int i = 0; i < (int) ans.size(); ++i) {
    if (i) {
      cout << " ";
    }
    cout << ans[i];
  }
  cout << "\n";
  return 0;
}


Measured memory_bytes: 148180
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <sstream>

#define rep(i, j) for(int i = 0; i < j; i++)
#define all(i) i.begin(), i.end()
#define ll long long
#define bl bool
#define nn printf("\n");
#define na printf("a");
#define nnn(i) printf("%d", i);
#define mod 1000000007

using namespace std;

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

	while (1)
	{
		int n = 0, r = 0; cin >> n >> r;
		if (n == 0 && r == 0) { return 0; }
		int p = 0, c = 0;
		vector<int> bef(n + 5);
		vector<int> aft(n + 5);
		rep(i, n) 
		{
			bef[i] = n - i;
			aft[i] = n - i;
		}
		rep(i, r)
		{
			cin >> p >> c;
			rep(j, p - 1){	aft[c + j] = bef[j];	}
			rep(j, c)	{	aft[j] = bef[p - 1 + j];	}
			bef = aft;
		}
		printf("%d\n", bef[0]);
	}
	return 0;
}

Measured memory_bytes: 1216
X,K,D=map(int,input().split())
X=abs(X)
if X>=0:
    temp=X//D
    if temp>=K:
        last=X-K*D
        print(last)
        exit()
    else:
        ktemp=K-round(temp)
        if ktemp%2==0:
            last=X-D*(round(temp))
            print(abs(last))
            exit()
        else:
            last=X-D*(round(temp))
            last=min(abs(last+D),abs(last-D))
            print(last)
            exit()



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

int main(){
 
  
int year,month,day;
char token; 
 
cin >> year >> token >> month >> token >>  day;
	if(year == 2019){
		if(month < 4){
		cout << "Heisei" << endl;
		}else if(month == 4){
			if(month > 30){
			
				cout << "TBD" << endl;
			}else{
			
				cout << "Heisei" << endl;
			}
		
		}else{
		
		cout << "TBD" << endl;
		}
	
	}else{
	
	cout << "Heisei" << endl;
	}
	

}


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

using namespace std;

#define MAX_N 1121
#define MAX_K 15
typedef long long ll;
 
bool prime[MAX_N];
ll dp[MAX_N][MAX_K];
 
void Prime(){
    fill(prime,prime+MAX_N,true);
    prime[0] = prime[1] = false;
 
    for(int i = 2 ; i*i < MAX_N ; i++){
	if(prime[i]){
	    for(int j = i*i ; j < MAX_N ; j += i){
		prime[j] = false;
	    }
	}
    }
}
 
void init(){
    Prime();
    vector<int> P;
    for(int i = 0 ; i < MAX_N ; i++){
	if(prime[i]){
	    P.push_back(i);
	}
    }
 
    dp[0][0] = 1;
    for(int i = 0 ; i < (int)P.size() ; i++){
	for(int j = MAX_K-2 ; j >= 0 ; j--){
	    for(int k = 0 ; k < MAX_N-P[i] ; k++){
		dp[P[i]+k][j+1] += dp[k][j];
	    }
	}
    }
}
 
int main(){
    int n,k;
 
    init();
    while(cin >> n >> k, n | k){
	cout << dp[n][k] << endl;
    }
    return 0;
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl '\n'
#define pb push_back
#define PI 3.14159265
int M = 1000000007;
int32_t main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int l, r, d;
  cin >> l >> r >> d;
  int ans = 0;
  for (int i = l; i <= r; i++)
  {
    if (i % d == 0)
      ans++;
  }
  cout << ans ;


}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
int n,m[10001];
bool p(int x){
  if(m[x]>=0) return m[x];
  for(int i=2;i*i<=n;i++) {
    if(x%i==0) return m[x]=0;
  }
  return m[x]=1;
}
main() {
  memset(m,-1,sizeof(m));
  while(cin>>n&&n) {
    int mx=5;
    for(int i=2;i<=n-2;i++)if((p(i)&p(i+2)))mx=i;
    printf("%d %d\n",mx,mx+2);
  }
}

Measured memory_bytes: 1192
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main() {
   int a,b;
   long long p;
    cin>>a>>b;
    p=a*b;
    if(p%2==0)
    {
        cout<<"Even";
    }
    else
        cout<<"Odd";
    return 0;
}



Measured memory_bytes: 256