akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int fun(char *);
int fun(char *s)
{
    int cnt=0,i,ans=0;
    int n=strlen(s);
    for(i=0;s[i]!='\0';i++)
    {
        if(s[i]=='S')
        {
            cnt++;
        }
        if(s[i]=='T'&&cnt>0)
        {
            cnt--;
            ans=ans+2;
        }
    }
    return n-ans;
}
int main()
{
    char a[200005];
    scanf("%s",a);
    printf("%d\n",fun(a));
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
 
int main () {
  long long  x;
  cin >>x;
  long long  p = 100;
  int cnt =0;

  while(p<x){
    p += p/100;
    cnt++;
  }

  cout<<cnt<<endl;
return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順



ll F(ll A, ll B) {
    string SA = to_string(A);
    string SB = to_string(B);
    return (SA.size() > SB.size()) ? SA.size() : SB.size();
}
int main() {
    ll X; cin >> X;

    ll Y = (ll)sqrt(X);
    for (ll i = Y; i > 0; i--) {
        if (X % i == 0) {
            cout << F(i, X / i) << endl;
            return 0;
        }
    }
    cout << F(1, X) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-10;
const bool debug = 0;
//------------------------------//
 
int main() {
	string s, ans;
	cin >> s;
	REP(i, s.size()) if (i % 2 == 0) ans += s[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int main(){
  int n;
  string s;
  cin>>n;
  cin>>s;
  int num=1;
  for(int i=1;i<n;i++){
    if(s[i-1]!=s[i])num++;
  }
  cout<<num<<endl;
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int m;
	cin>>m;
	if(m&1)
	{
		m>>=1;
		cout<<m*(m+1);
	}
	else
	{
		m>>=1;
		cout<<m*m;
	}
	return 0;
} 

Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

Measured memory_bytes: 3608
A, B, C = map(int, input().split())
K = int(input())

for i in range(K):
  if A < B < C:
    break
  elif A >= B:
    B *= 2
  elif B >= C:
    C *= 2
  
    
if A < B < C:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9168
#include<iostream>
#include<vector>
#include <utility>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
const int INF = 1001001001;
 
int a[12][12];
 
int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> c(n);
  rep(i,n) {
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }
 
  int ans = INF;
  rep(s,1<<n) {
    int cost = 0;
    vector<int> d(m);
    rep(i,n) {
      if (s>>i&1) {
        cost += c[i];
        rep(j,m) d[j] += a[i][j];
      }
    }
    bool ok = true;
    rep(j,m) if (d[j] < x) ok = false;
    if (ok) ans = min(ans, cost);
  }
  if (ans == INF) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <ctype.h>

const int INF =100000000;

using namespace std;

double func(int t,int y,int r){

  if(t == 1){
    return (1+y*r/100.0);
  }else{
    double ttt = (1+r/100.0);
    for(int h = 1;h < y;h++){
      ttt *= (1+r/100.0);
      //   cout << h << endl;
    }
    return ttt ;
  }
}




int main(){

  while(1){

    int n,y;

    int ans;

    cin >> n ;

    if(!n) break;

    cin >> y;
    double tmp=0;
    for(int i = 0;i < n;i++){
      int b,t,r;
      cin >> b >> r >> t;

      if(tmp < func(t,y,r)){
	ans = b;
	tmp = func(t,y,r);
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 1160
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    std::string s,t;
    cin >> s >> t;
#if 1
    for(int i=0; i<n; i++){
        cout << s[i] << t[i];
    }
#endif
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
  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 << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int x; scanf("%d", &x);
	
	std::map<i64, bool> mp;
	std::map<i64, i64> val;
	for(i64 i = 0; i * i * i * i * i <= 1LL << 60; i++) {
		mp[i * i * i * i * i] = true;
		val[i * i * i * i * i] = i;
	}
	for(i64 i = 0; -i * i * i * i * i <= 1LL << 60; i--) {
		mp[i * i * i * i * i] = true;
		val[i * i * i * i * i] = i;
	}
	
	for(auto v: mp) {
		i64 A = v.first;
		if(!mp[A - x]) continue;

		printf("%lld %lld\n", val[A], val[A - x]);
		break;
	}	
	return 0;
}


Measured memory_bytes: 5020
while True:
    N = int(input())
    if N == 0:
        break
    s = list(map(int, input().split()))
    ans = []
    for i in range(N-1):
        for j in range(N):
            if(i < j):
                if s[i] > s[j] or s[i] < s[j]:
                    tmp = abs(s[i]-s[j])
                    ans.append(tmp)
                if s[i] == s[j] and not i == j:
                    ans.append(0)
    print(min(ans))


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

int main() {
	int size;
	int num;
	int x[1000];
	int y[1000];

	cin >> size >> num;
	size += 1;
	for (int i = 0; i < num; i++) {
		cin >> x[i] >> y[i];
	}

	for (int i = 0; i < num; i++) {
		if (x[i] > (size / 2))x[i] = size - x[i];
		if (y[i] > (size / 2))y[i] = size - y[i];
		int val = x[i] < y[i] ? x[i] : y[i];
		if (val % 3)val = val % 3;
		else val = 3;
		cout << val << endl;
	}
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int a,b; cin>>a>>b;
    for(int i=1; i<=1000; i++){
        if(i*8/100==a&&i/10==b){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}


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

int main(){
    ll n,m;cin>>n>>m;
    pair<ll,ll> p[n];
    rep(i,n){
        ll a,b;cin>>a>>b;
        p[i] = make_pair(a,b);
    }
    sort(p,p+n);
    ll ans = 0;
    for(int i=0;i<n;i++){
        if(m>p[i].second){ans+=p[i].first*p[i].second;m-=p[i].second;}
        else{ans+=p[i].first*m;break;}
    }
    co(ans);
}

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

namespace ConsoleApp1
{
    static class ARoundOne
    {
        static void Main(string[] args)
        {
            var a = int.Parse(Console.ReadLine());
            var b = int.Parse(Console.ReadLine());

            var list = new List<int> { 1, 2, 3 };

            Console.WriteLine(list.First(x => x != a && x != b));
            Console.ReadLine();
        }
    }
}

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

const int INF = 2e9;

int main(){
    char grid[10][10];
    int h,w,k;
    cin >> h >> w >> k;
    rep(i,h){
        rep(j,w) cin >> grid[i][j];
    }
    int ans = 0;
    for(int i = 0;i < (1 << h);i++){
        for(int j = 0;j < (1 << w);j++){
            int count = 0;
            for(int k = 0;k < h;k++){
                for(int l = 0;l < w;l++){
                    if(grid[k][l] == '#' && (i & (1 << k)) && (j & (1 << l))){
                        count++;
                    }
                }
            }
            if(count == k) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
#define MOD 1e9 + 7
#define fir first
#define sec second
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(c,a,b) for(ll c=a;c<b;c++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
	IOS
	string s,t;
	cin>>s>>t;
	map<char,char> m;
	ll cnt[26];
	mem(cnt,0);
	ll i=0;
	for(i=0;i<s.size();i++)
	{
		if(cnt[s[i]-'a'])
		{
			if(m[s[i]]!=t[i])
				return cout<<"No",0;
		}
		else
		{
			cnt[s[i]-'a']++;
			m[s[i]]=t[i];
		}
	}
	mem(cnt,0);
	for(i=0;i<s.size();i++)
	{
		if(cnt[t[i]-'a'])
		{
			if(m[t[i]]!=s[i])
				return cout<<"No",0;
		}
		else
		{
			cnt[t[i]-'a']++;
			m[t[i]]=s[i];
		}
	}
	cout<<"Yes";
}

Measured memory_bytes: 916
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdlib>
#include <cstdio>
using namespace std;

#define rep(i, n) for(int (i) = (0); (i) < (n); (i++))
using ll = long long;

map<string, int> m;


int main() {
    int n; cin >> n;
    double ans = 0.0;

    double a ;

    if(n % 2 == 0){
        a = n / 2;
    }else{
        a = n / 2 + 1;
    }

    ans = a / n;

    printf("%.10f", ans);
}

Measured memory_bytes: 256
use proconio::input;

fn main(){
    input!{
        N: u64,
        A: u64,
        B: u64
    }
    let mut sum:u64 = 0; 
    for i in 0..N+1 {
        let S = i.to_string();
        let mut sum_of_each_digit:u64 = 0;
        for j in S.as_str().chars() {
            let num:u64=j.to_string().parse().unwrap();
            sum_of_each_digit=sum_of_each_digit+num;
        }
        if A<=sum_of_each_digit && sum_of_each_digit<=B {
      sum=sum+i;}
    }
  print!("{}",sum);
}

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

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>b[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;

signed main(){
	llin(n);
	vllin(h,n);
	vll d(n,0);
	d[1]=abs(h[0]-h[1]);
	FOR(i,2,n-1){
		d[i]=min(d[i-2]+abs(h[i]-h[i-2]),d[i-1]+abs(h[i]-h[i-1]));
	}
	sal(d[n-1]);
}


Measured memory_bytes: 1792
// 再帰関数
// dfs 深さ優先探索
// Nx0の2次元配列
//  https://atcoder.jp/contests/apg4b/tasks/APG4b_t
// 重み無し無向グラフ
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG

int const nmax = 8;
bool visited[nmax];
using Graph = vector<vector<int>>;

int dfs(int v, int N, Graph g)
{
    bool all_visited = true;
    for (int i = 0; i < N; i++)
    {
        if (visited[i] == false)
            all_visited = false;
    }
    if (all_visited)
    {
        //       cout << "all visited,v=" << v << endl;
        return 1;
    }

    int ret = 0;
    for (auto i : g[v])
    {
        //        cout << "v=" << v << ",i=" << i << endl;
        //     cout << "ret=" << ret << endl;
        if (visited[i] == true)
        {
            //       cout << "i=" << i << " was visited" << endl;
            continue;
        }
        visited[i] = true;
        ret += dfs(i, N, g);
        visited[i] = false;
    }
    return ret;
}

int main()
{
    int N, M;
    cin >> N >> M;
    Graph g(N);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    for (int i = 0; i < N; i++)
        visited[i] = false;

    visited[0] = true;
    cout << dfs(0, N, g) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F(i,n) for (int i=1; i<=(int)n; i++)
#define FF(i,n) for (int i=0; i<(int)n; i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pi pair < int , int >
#define re(x) (int)x.size()
#define y1 u228
using namespace std;
typedef long long ll;
const int N = 1010;
const int big = 2e9;
const int md = 1e9 + 7;
int n,w[N],s[N],v[N],p[N],ww[N],ss[N],vv[N],mx;
ll f[N][N*10];
bool cmp(int x,int y){
    return min(s[x]-w[y],s[y])>min(s[y]-w[x],s[x]);
    //return min(s[x]+w[x])>(s[y]+w[y]);
}
void up(ll &x,ll y){x=max(x,y);}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    cin>>n;
    F(i,n) cin>>w[i]>>s[i]>>v[i];
    F(i,n) p[i]=i;
    sort(p+1,p+n+1,cmp);
    F(i,n) {ww[i]=w[p[i]];ss[i]=s[p[i]];vv[i]=v[p[i]];}
    F(i,n) {w[i]=ww[i]; s[i]=ss[i]; v[i]=vv[i];}
    F(i,n) mx=max(mx,s[i]);
    up(f[1][s[1]],0ll+v[1]);
    F(i,n-1){
        FF(j,mx+1){
            if (w[i+1]<=j) up(f[i+1][min(j-w[i+1],s[i+1])],f[i][j]+0ll+v[i+1]);
            up(f[i+1][j],f[i][j]);
        }
        up(f[i+1][s[i+1]],0ll+v[i+1]);
    }
    ll ans=0;
    FF(j,mx+1) ans=max(ans,f[n][j]);
    cout<<ans<<endl;
    return 0;
}







Measured memory_bytes: 79104
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import ceil

def gcd(a, b):
    assert a > 0 and b > 0
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

def solve(A, B, C, D):
    if A < B or D < B: return False
    if A % B > C: return False
    if D % B == 0: return True

    g = gcd(B, D)
    r = A % g  # +D -B を繰り返すと x % g == r であるxを訪れる
    # x % g == r and C < x < B である x が存在するなら False を返す
    return not (C < B - g + r)

T = int(input())
for i in range(T):
    A, B, C, D = [int(t) for t in input().split()]
    print('Yes' if solve(A, B, C, D) else 'No')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define str string
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define ff fflush(stdout)
#define IN(a) freopen(a, "r", stdin)
#define OUT(a) freopen(a, "w", stdout) 
#define eps 1e-6
#define PI atan(1) * 4
#define mod 1000000007
#define inf 1000000000000000000
using namespace std;
pii rge[300005];
int bit[100005];
int x;
bool cmp (pii a, pii b) {
	return (a.se - a.fi < b.se - b.fi);
}
void update (int i, int v) {
	if (i > x) return;
	bit[i] += v;
	update(i + (i & (-i)), v);
	return;
}
int query (int i) {
	return ((i == 0) ? 0 : bit[i] + query(i - (i & (-i))));
}
int main () {
	int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q;
	scanf("%d %d", &a, &b);
	SET(bit, 0); x = b;
	for (i = 1; i <= a; i++) {
		scanf("%d %d", &c, &d);
		rge[i] = {c, d};
	}
	sort(rge + 1, rge + a + 1, cmp);
	for (i = 1, j = 1; i <= b; i++) {
		for (; j <= a && rge[j].se - rge[j].fi < i; j++) {
			update(rge[j].fi, 1); update(rge[j].se + 1, -1);
		}
		e = a - j + 1;
		for (k = i; k <= b; k += i) {
			e += query(k);
		}
		printf("%d\n", e);
	}
	return 0; 
}

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

void InsertionSort(int a[],int n){
	int j,v;
	for(int i=1;i<n;i++){
		v=a[i];
		j=i-1;
		while(j>=0&&a[j]>v){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=v;
		cout<<a[0];
		for(int k=1;k<n;k++)cout<<" "<<a[k];
		cout<<endl;
	}
} 


int main(){
	int n;
	cin>>n;
	int a[100];
	for(int i=0;i<n;i++)cin>>a[i];
	cout<<a[0];
	for(int i=1;i<n;i++)cout<<" "<<a[i];
	cout<<endl;
	InsertionSort(a,n);
} 


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

#ifndef LOCAL
#define cerr dolor_sit_amet
#endif

#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int , int > ipair;
typedef pair < ll , ll > lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = numeric_limits<double>::infinity();
const int MOD = 998244353;
const double EPS = 1e-9;
const int DX[] = { 1,  0, -1,  0,  1, -1,  1, -1};
const int DY[] = { 0,  1,  0, -1,  1, -1, -1,  1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll sqr(ll x) { return x*x; } ll sqr(int x) { return (ll)x*x; }
double sqr(double x) { return x*x; } ld sqr(ld x) { return x*x; }
mt19937 mmtw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(mmtw) % (y - x + 1) + x; }

// ========================================================================= //

const int N = 100;
std::unordered_map<bitset<N>, int> dd[N+1];
bitset<N> pref[N+1];
int solve(int n, bitset<N> s) {
    auto it = dd[n].find(s);
    if (it != dd[n].end())
        return it->second;
    if (n == 0)
        return dd[n][s] = 1; 
    int ans = solve(n - 1, s >> 1);
    if (s[0]) {
        ans *= 2;
        if (ans >= MOD)
            ans -= MOD;
    }
    for (int m = 1; m*2 <= n; ++m) {
        bitset<N> ns = pref[m] & s;
        for (int c = 2; c*m <= n; ++c) {
            ns &= s >> (m*(c-1));
            ans = (ans + 1LL*solve(m, ns)*solve(n - m*c, s >> (m*c))) % MOD;
        }
    }
    return dd[n][s] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    for (int i = 1; i <= N; ++i) {
        pref[i] = pref[i - 1];
        pref[i].set(i-1);
    }
    int n;
    string ss;
    cin >> ss;
    n = sz(ss);
    bitset<N> s;
    for (int i = 0; i < n; ++i)
        s.set(i, ss[i] == '1');
    std::cout << solve(n, s) << "\n";

    return 0;
}


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

signed main() {
	int n, m, k;
	std::cin >> n >> m >> k;
	std::vector<int> a(n), b(m);
	for (int i = 0; i < n; i++) { std::cin >> a[i]; }
	for (int i = 0; i < m; i++) { std::cin >> b[i]; }
	for (int i = 1; i < n; i++) { a[i] += a[i - 1]; }
	for (int i = 1; i < m; i++) { b[i] += b[i - 1]; }
	int answer = upper_bound(b.begin(), b.end(), k) - b.begin();
	for (int i = 0; i < n; i++) {
		if (a[i] > k) { break; }
		int result = i + 1;
		result += upper_bound(b.begin(), b.end(), k - a[i]) - b.begin();
		answer = std::max(answer, result);
	}
	std::cout << answer << '\n';
}

Measured memory_bytes: 6344
import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda x:-x[1])
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        for j in range(X[i][0]):
            tmp = heapq.heappushpop(q, X[i][1])
            if tmp < X[i][1]:
                total += (X[i][1] - tmp)
            else:
                break

    print(total)

if __name__ == "__main__":
    main()


Measured memory_bytes: 36156
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;

int main(){
    ll n,m,r; cin>>n>>m>>r;
    vector<ll> v(r);
    REP(i,r)cin>>v[i], v[i]--;
    vector<vector<ll>> g(n,vector<ll> (n, 1e15));
    REP(i,n)g[i][i]=0;
    REP(i,m){
        ll a,b,c; cin>>a>>b>>c;
        a--; b--;
        g[a][b]=c;
        g[b][a]=c;
    }
    REP(k,n)REP(i,n)REP(j,n){
        g[i][j]=min(g[i][j], g[i][k]+g[k][j]);
    }
    ll ans=1e17;
    sort(ALL(v));
    do {
        ll preans=0;
        FOR(i,1,r){
            preans+=g[v[i-1]][v[i]];
        }
        ans=min(preans, ans);
    }while(next_permutation(ALL(v)));
    cout<< ans <<endl;
    return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    ll c, k, res = 0;
    cin >> n >> c >> k;
    vector<ll> t(n);
    rep (i, n) cin >> t[i];
    sort(t.begin(), t.end());
    int r = 0;
    while (r < n) {
        ll cap = 0;
        ll time = t[r];
        while (r < n && cap < c && t[r] <= time + k) {
            r++;
            cap++;
        }
        res++;
    }
    cout << res << endl;
    
    return 0;
}



Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var (
	rdr   = bufio.NewReaderSize(os.Stdin, 1000000)
	reply string
)

func main() {
	var a, b string
	fmt.Scan(&a, &b)
	solve([]string{a, b})
}

func solve(buf []string) {
	ints := atoi(buf)
	A := ints[0]
	B := ints[1]
	a := A
	b := B
	for a != b {
		if a < b {
			a += A
		} else {
			b += B
		}
	}
	reply = strconv.Itoa(a)
	fmt.Println(reply)
}

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func nextSlice() []string {
	return strings.Split(readLine(), " ")
}

func atoi(a []string) (b []int) {
	b = make([]int, len(a))
	for i := range a {
		b[i], _ = strconv.Atoi(a[i])
	}
	return
}

func atof(a []string) (b []float64) {
	b = make([]float64, len(a))
	for i := range a {
		b[i], _ = strconv.ParseFloat(a[i], 64)
	}
	return
}

func scanSlice2(n int) (a []int, b []int) {
	a = make([]int, n)
	b = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	return
}

func scanFloatSlice2(n int) (a []float64, b []float64) {
	a = make([]float64, n)
	b = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	return
}

// ---------------------------------------------------

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

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

func min(a ...int) int {
	min := a[0]
	for i := 1; i < len(a); i++ {
		if min > a[i] {
			min = a[i]
		}
	}
	return min
}

func max(a ...int) int {
	max := a[0]
	for i := 1; i < len(a); i++ {
		if max < a[i] {
			max = a[i]
		}
	}
	return max
}

func sum(a []int) (ans int) {
	for i := range a {
		ans += a[i]
	}
	return
}

// ---------------------------------------------------

func yesOrNo(b bool) {
	if b {
		fmt.Println("Yes")
		return
	}
	fmt.Println("No")
}

func yesorNO(b bool) {
	if b {
		fmt.Println("YES")
		return
	}
	fmt.Println("NO")
}


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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b)a=b;};
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b)a=b;};

Int n;
Int ls[11],rs[11],us[11],ds[11];
vector<Int> ans;

Int used[11];
void dfs(Int bit){
  //cout<<bit<<endl;
  while(bit){
    Int idx=-1;
    for(Int i=0;i<n;i++){
      if((~bit>>i)&1) continue;
      if(idx<0) idx=i;
      if(rs[idx]>rs[i]){
        idx=i;
        continue;
      }
      if(rs[idx]==rs[i]){
        if(us[idx]>us[i]){
          idx=i;
        }
      }
    }
    //cout<<idx<<endl;
    bit^=1<<idx;
    used[idx]=1;
    ans.emplace_back(idx);
    
    Int lft=10000;
    Int rgh=rs[idx];    
    Int top=ds[idx];
    for(Int i=0;i<n;i++){
      if(rs[i]>=ls[idx])
        if(us[i]<top&&top<ds[i])
          chmin(lft,rs[i]);
    }
    
    Int nxt=0;
    for(Int i=0;i<n;i++){
      if(used[i]) continue;
      if((~bit>>i)&1) continue;
      //cout<<i<<":"<<ds[i]<<" "<<ls[i]<<" "<<rs[i]<<endl;
      if(ds[i]<=top&&lft>=ls[i]&&rs[i]>=rgh) nxt|=1<<i;
    }
    //cout<<bit<<" "<<nxt<<":"<<idx<<":"<<lft<<" "<<rgh<<" "<<top<<endl;
    dfs(nxt);    
    bit&=~nxt;    
  }
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int first=1;
  while(cin>>n,n){   
    if(!first) cout<<endl;
    first=0;
    
    for(Int i=0;i<n;i++){
      Int x1,y1,x2,y2;
      cin>>x1>>y1>>x2>>y2;
      ls[i]=max(x1,x2);
      rs[i]=min(x1,x2);
      us[i]=min(y1,y2);
      ds[i]=max(y1,y2);
    }
    memset(used,0,sizeof(used));
    ans.clear();
    Int bit=(1<<n)-1;
    dfs(bit);
    vector<Int> ord(n);
    for(Int i=0;i<n;i++) ord[ans[i]]=i+1;
    for(Int i=0;i<n;i++) cout<<ord[i]<<endl;
  }  
  return 0;
}



Measured memory_bytes: 3224
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx


using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);   
//int n,m,cnt;
//string s[1234];
int visit[100]; 
int cnt=0;
vector< set<int> > adj(1234);

int dfs(int cur){
	int i;
	//cout<<"daad"<<endl;
	cnt++;
	set<int>::iterator it;
	//cout<<cnt<<endl;
	visit[cur]=1;
	//cout<<cur+1	<<"-======="<<endl;
	for(it=adj[cur].begin();it!=adj[cur].end();it++){
		//cout<<*it+1<<"   ";
		if(!visit[*it]){
			//cout<<*it+1<<endl;
			dfs(*it);
		}
	}
	//cout<<endl;
	//cout<<cur+1<<"+++++++++"<<endl;
	return 0;
}
int p[123456],q[123456];

int main(){
    std::ios::sync_with_stdio(false);
    //int n,m;
   int n,m;
   cin>>n>>m;
   int i,a,b;
   rep(i,m){
   		cin>>a>>b;
   		a--;
   		b--;
   		adj[a].insert(b);
   		adj[b].insert(a);
   		p[i]=a;
   		q[i]=b;
   }
   //cout<<"dasd";
   //return 0;
   int lo=0;
   int j;
   
   rep(i,m){
   	//cout<<"boo"<<endl;
   		adj[p[i]].erase(q[i]);
   		adj[q[i]].erase(p[i]);
   		cnt=0;
   		rep(j,n){
   			visit[j]=0;
   		}
   		dfs(0);
   		//cout<<"dsads"<<endl;
   		adj[p[i]].insert(q[i]);
   		adj[q[i]].insert(p[i]);
   		if(cnt!=n)
   			lo++;

   }
   cout<<lo<<endl;

    
}



Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#define INF 100000000

#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;

static const float EPS = 1e-8;

int txr[] = {1,1,1,1,1,2,2,2,3};
int tyr[] = {-2,-1,0,1,2,-1,0,1,0};


int txl[] = {-1,-1,-1,-1,-1,-2,-2,-2,-3};
int tyl[] = {-2,-1,0,1,2,-1,0,1,0};

char stage[60][30];
int cost[1800][1800];

class Data{
public:
	int cost;
	int rhs;
	int lhs;
	bool turn;
	Data(int _cost,int _lhs,int _rhs,bool _turn){
		cost = _cost;
		lhs = _lhs;
		rhs = _rhs;
		turn = _turn;
	}

	bool operator>(const Data& d) const{
		return cost > d.cost;
	}
};

int main(){
	int w,h;
	while(~scanf("%d %d",&w,&h)){
		if(w==0 && h==0) break;
		memset(cost,0x3f,sizeof(cost));
		vector<P> S;
		vector<P> T;
		for(int y=0;y<h;y++){
			for(int x=0;x<w;x++){
				scanf("%s",&stage[y][x]);
				if(stage[y][x]=='S') S.push_back(P(x,y));
				if(stage[y][x]=='T') T.push_back(P(x,y));
			}
		}

		priority_queue<Data,vector<Data>,greater<Data> > que;

		for(int i=0;i<S.size();i++){
			int x = S[i].first;
			int y = S[i].second;
			que.push(Data(0,y*w+x,y*w+x,false));
			que.push(Data(0,y*w+x,y*w+x,true));
		}

		int res = numeric_limits<int>::max();
		while(!que.empty()){
			Data d = que.top();

			int srx = d.rhs % w;
			int sry = d.rhs / w;

			int slx = d.lhs % w;
			int sly = d.lhs / w;
			que.pop();

			if(d.cost >= res) continue;

			if(d.turn){
				for(int i=0;i<9;i++){
					int dx = txl[i] + srx;
					int dy = tyl[i] + sry;

					if(dx < 0 || dx >= w || dy < 0 || dy >= h) continue;
					if(dx>=srx) continue;
					if(abs(dx - srx) + abs(dy - sry) > 3) continue;
					if(stage[dy][dx] == 'X') continue;
					if(stage[dy][dx] == 'T'){
						res = cost[dy*w+dx][d.rhs] = min(cost[dy*w+dx][d.rhs],d.cost);
						continue;
					}

					if(cost[dy*w+dx][d.rhs] <= d.cost + stage[dy][dx]-'0') continue;
					cost[dy*w+dx][d.rhs] = d.cost + stage[dy][dx]-'0';

					que.push(Data(d.cost + stage[dy][dx]-'0',dy*w+dx,d.rhs,false));
					//dfs(dy*w+dx,d.rhs,0,d.cost + stage[dy][dx]-'0');
				}
			}
			else{
				for(int i=0;i<9;i++){
					int dx = txr[i] + slx;
					int dy = tyr[i] + sly;

					if(dx < 0 || dx >= w || dy < 0 || dy >= h) continue;
					if(slx>=dx) continue;
					if(abs(dx - slx) + abs(dy - sly) > 3) continue;
					if(stage[dy][dx] == 'X') continue;
					if(stage[dy][dx] == 'T'){
						res = cost[d.lhs][dy*w+dx] = min(cost[d.lhs][dy*w+dx],d.cost);
						continue;
					}
					if(cost[d.lhs][dy*w+dx] <= d.cost + stage[dy][dx]-'0') continue;
					cost[d.lhs][dy*w+dx] = d.cost + stage[dy][dx]-'0';
					que.push(Data(d.cost + stage[dy][dx]-'0',d.lhs,dy*w+dx,true));
					//dfs(d.lhs,dy*w+dx,1,d.cost + stage[dy][dx]-'0');
				}
			}
		}

		printf("%d\n",res >= 0x3f3f3f3f ? -1 : res);
	}
}

Measured memory_bytes: 13000
#include <iostream>
#include    <iomanip>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define INF 999999999

using namespace std;

double T, X;

int main() {

	cin >> T >> X;
	cout << setprecision(11) << T/X << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<functional>
#include<utility>

#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define P pair<int, int>
#define PLI pair<ll, int>

using namespace std;

typedef long long ll;


const int MOD = 1e9 + 7;

string t, b;
int dp[1005][1005] = {};
int main() {
	cin >> t >> b;
	dp[0][0] = 1;
	rep(i, t.size()) {
		rep(j, b.size()) {
			if (t[i] == b[j]) dp[i + 1][j + 1] += dp[i][j];
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][j + 1] %= MOD;
			dp[i + 1][j] %= MOD;
		}
	}

	int ans = 0;
	rep(i, t.size()+1) {
		ans += dp[i][b.size()];
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 7172
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int a, b, ans=0;
    scanf("%d%d",&a,&b);
    for(int i=a; i<=b; i++)
    {
        int f=i%10, j=i/10000;
        int d=i/10%10, k=i/1000%10;
        if(f==j&&d==k)
            ans++;
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 256
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()

money=1000
kabu=0
for i in range(n-1):
  if a[i]<a[i+1]:
    t_kabu=money//a[i]
    kabu+=t_kabu
    money-=t_kabu*a[i]
  elif a[i]>a[i+1]:
    money+=kabu*a[i]
    kabu=0

money+=kabu*a[n-1]
print(money)

Measured memory_bytes: 9140
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
    };

    // 2次元用の標準入出力
    template<typename T>
    struct inpn {
        std::size_t szi, szj;
        inpn(std::size_t _szi, std::size_t _szj) : szi(_szi), szj(_szj) {}
        operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i)
                for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j];
            return a;
        }
    };

    inp inp1; // input one
}


int main() {

    int n, k;
    cin >> n >> k;
    vector<ll> h = inp(n);

    // dp[i] := 足場iにいるときのコストの総和の最小値
    vector<ll> dp(n , infll);
    dp[0] = 0LL;

    rep(i, n) {
        Rep(j, 1, k + 1) { // j歩進む
            if (i - j < 0) continue;
            chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
        }
    }

    Cout(dp[n - 1]);

    return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner

object Main extends App {

  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val ps = Seq.fill(n)((sc.nextInt, sc.nextInt))

  val total = ps.combinations(2).foldLeft(0.0d){ case (sum, Seq(p1, p2)) =>
      sum + distance(p1, p2)
  }

  val res = total * 2 / n

  println(res)

  def distance(p1: (Int, Int), p2: (Int, Int)): Double = {
    val (x1, y1) = p1
    val (x2, y2) = p2
    Math.sqrt(( x1 - x2) * ( x1 - x2) + ( y1 - y2) * ( y1 - y2) )
  }
}



Measured memory_bytes: 25544
#include <bits/stdc++.h>
    using namespace std;
 
    #define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
    #define mod 1000000007
    #define qmod 998244353
    #define M 1000001
    #define endl "\n"
    #define all(a) (a).begin(),(a).end()
    #define rep(i,a,b) for(int i=a;i<b;++i)
    #define repr(i,a,b) for(int i=a;i>=b;--i)
    #define F first
    #define S second
    #define pb push_back
    #define mp make_pair
 
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    typedef vector<string> vs;
    typedef vector<pii> vii;
    typedef vector<vi> vvi;

    int solve(int a[],int dp[],int n,int k,int i){
        if(i==n-1) return 0;
        if(dp[i]!=-1) return dp[i];
        int mi=1e9;
        for(int j=1;j<=k && (i+j)<n;j++)
            mi=min(mi,abs(a[i]-a[i+j])+solve(a,dp,n,k,i+j));
        return dp[i]=mi;
    }

    int main(){
                    
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin); 
    freopen("output.txt","w",stdout);   
    #endif */
 
        fast;   
        int t=1;
        // cin>>t; 
        while(t--){
            int n,k;
            cin>>n>>k;
            int a[n];
            rep(i,0,n) cin>>a[i];
            int dp[n];
            memset(dp,-1,sizeof(dp));
            cout<<solve(a,dp,n,k,0);
        } 
        return 0;   
    }       


    // First, solve the problem. Then, write the code. 


Measured memory_bytes: 10368
#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() {
    ll n;
    cin >> n;
    cout << n * (n - 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);

  int m = max(a, max(b, c));

  int ans = 0;

  int qa = (m - a) / 2;
  int qb = (m - b) / 2;
  int qc = (m - c) / 2;

  ans = ans + qa + qb + qc;

  a = m - a - qa * 2;
  b = m - b - qb * 2;
  c = m - c - qc * 2;

  int sum = a + b + c;
  if (sum == 0) {
    printf("%d\n", ans);
    return 0;
  }

  if (sum == 2) {
    printf("%d\n", ans + 1);
    return 0;
  }

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


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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MH = 410;

int N, H;
vi g[MH];
int in[MH], out[MH];
bool vis[MH];

bool dfs(int v) {
	vis[v] = 1;
	bool f = 0;
	if (in[v] != out[v]) f = 1;
	for (int to : g[v]) if (!vis[to]) {
		if (dfs(to)) {
			f = 1;
		}
	}
	return f;
}

int main() {
	scanf("%d %d", &N, &H);
	rep(i, N) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		int l = (c == 0 ? a : -c) + H;
		int r = (d == 0 ? -b : d) + H;
		g[l].pb(r); g[r].pb(l);
		++in[r]; ++out[l];
	}
	for (int i = 1; i <= H; ++i) {
		if (in[i + H] > out[i + H]) {
			puts("NO");
			return 0;
		}
		if (in[H - i] < out[H - i]) {
			puts("NO");
			return 0;
		}
	}

	bool ok = 1;
	rep(i, MH) {
		if (in[i] + out[i] > 0 && !vis[i]) {
			if (!dfs(i)) {
				ok = 0;
			}
		}
	}
	puts(ok ? "YES" : "NO");
	return 0;
}

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

#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

int main() {
    ios_base::sync_with_stdio(false);
    ll a,b; cin >> a >> b; cout << a*b << endl;
    return 0;
}



Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
const int SIZE=200000+50;
int a[SIZE],q[SIZE];
int vis[SIZE];
int minn[SIZE],maxx[SIZE];

int main()
{
    int n,k;
	scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    int len=1;
    int same=0;
    for(int i=2;i<=n;i++)
    {
    	if(a[i]>a[i-1]) len++;
    	else
    	{
    		len=1;
		}
		if(len==k) same++;
	}
    int l=1,r=0;
    for(int i=1;i<=n;i++){
        while(r>=l && a[q[r]]>=a[i])r--;
        q[++r]=i;
        while(r>=l && q[l]<i-(k-1)+1)l++;
        minn[i]=a[q[l]];
    }
    l=1,r=0;
    for(int i=1;i<=n;i++){
        while(r>=l && a[q[r]]<=a[i])r--;
        q[++r]=i;
        while(r>=l && q[l]<i-(k-1)+1)l++;
        maxx[i]=a[q[l]];
    }
    int cnt=0;
    for(int i=k;i<=n-1;i++){
    	if(a[i-k+1]<=minn[i]&&a[i+1]>=maxx[i])
    	{
    		cnt++;
		}
	}
	//if(same>=2) same=1;
	printf("%d\n",n-k+1-cnt-max(same-1,0));
}

Measured memory_bytes: 3328
n = int(input())
a = list(int(x) for x in input().split())
judge = [0] + a + [0]
key = [0]*n
ans = 0

for i in range(n):
    x, y, z = [judge[i], judge[i+1], judge[i+2]]
    key_list = [x, y, z]
    if max(key_list) == y or min(key_list) == y:
        key[i] = 2 * min(abs(x-y), abs(y-z))
        ans = ans + abs(y-x)
    else:
        ans = ans + abs(y-x)
ans += abs(a[-1])

for i in range(n):
    print(ans-key[i])

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

int main() {
	int x2000,r,D;
	cin >> r >> D >> x2000;
	int curr = x2000;
	for(int i = 1;i <= 10;i++ ){
		curr = r * curr - D;
		cout << curr << endl;
	}
	return 0;
}


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


class UnionFind
{
    private:
        vector<int> parent;

    public:
        UnionFind( size_t N ): parent(N,-1) {}

        // i をその親に直接つなぎ、その親の値を返す
        int find( int i )
        {
            if( parent[i] < 0 ) return i;
            return parent[i] = find( parent[i] );
        }

        // i が属する木と j が属する木を繋ぐ
        bool unite( int i, int j )
        {
            i = find( i );
            j = find( j );
            if( i == j ) return false;
            // j を i に繋げる
            parent[i] += parent[j];
            parent[j] = i;            
            return true;
        }
};


int main()
{
    int N, K, L;
    cin >> N >> K >> L;

    UnionFind uniRoad( N+1 ), uniRailway( N+1 );
    for( int i = 0; i < K; ++i ){
        int p, q;
        cin >> p >> q;
        uniRoad.unite( p, q );
    }

    for( int i = 0; i < L; ++i ){
        int r, s;
        cin >> r >> s;
        uniRailway.unite( r, s );
    }

    map<pair<int,int>,int> mp;
    for( int i = 1; i <= N; ++i ) ++mp[make_pair( uniRoad.find(i), uniRailway.find(i) )];
    for( int i = 1; i <= N; ++i ){
        cout << mp[make_pair( uniRoad.find(i), uniRailway.find(i) )] << " ";
    }

    return 0;
}


Measured memory_bytes: 13568
#include <bits/stdc++.h>
#define rep(i,a,n)  for (int i=(int)(a); i<=(int)(n); ++i)
#define rrep(i,a,n) for (int i=(int)(a); i>=(int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(f, 0, (x.size()-1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

int N,A,B;
vector<int> X;
void input()
{
    cin>>N>>A>>B;
    X.resize(N);
    rep(i,0,N-1){
        cin>>X[i];
    }
}
void solve()
{
    int ans = 0;
    rep(i,1,N-1){
        int dis = X[i]-X[i-1];
        ans += min(A*dis, B);
    }

    cout<<ans<<endl;

}
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    int A, B, M;
    cin >> A >> B >> M;
    int menor = INFINITO, menora = INFINITO, menorb = INFINITO;
    vi a(A), b(B);
    fo(i, A) {
        cin >> a[i];
        menora = min(menora, a[i]);
    }
    fo(i, B) {
        cin >> b[i];
        menorb = min(menorb, b[i]);
    }

    fo(i, M) {
        int x, y, c;
        cin >> x >> y >> c;
        menor = min(menor, a[x - 1] + b[y - 1] - c);
    }

    cout << min(menor, menora + menorb) << endl;

    return 0;
}

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

typedef long long ll;

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


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

    int n; cin >> n;
    // dp[i] := i 円を引き出す最小手順
    int dp[101010] = {};
    rep(i, 101010) dp[i] = 1e9;
    dp[0] = 0;

    for(int i = 1; i <= n; i++) {
        int tmp6 = 1;
        while(true) {
            if(i-tmp6 < 0) break;
            dp[i] = min(dp[i], dp[i-tmp6]+1);
            tmp6 *= 6;
        }
        int tmp9 = 1;
        while(true) {
            if(i-tmp9 < 0) break;
            dp[i] = min(dp[i], dp[i-tmp9]+1);
            tmp9 *= 9;
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  string s, t, u;
  cin >> s >> t >> u;

  int a, b, c;
  a = s.size();
  b = t.size();
  c = u.size();

  if(s[a-1] == t[0] and t[b-1] == u[0]) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
using namespace std;

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

  int32_t H, N;
  cin >> H >> N;
  vector<pair<int,int>> M(N);
  int32_t max_d = 0;
  for (auto& m : M) {
    cin >> m.first >> m.second;
    max_d = max(max_d, m.first);
  }
  vector<int> dp(H+max_d+1, INT_MAX);
  dp[0] = 0;
  for (int d = 1; d <= H+max_d; d++) {
    for (int i = 0; i < N; i++) {
      int damage = M[i].first;
      int cost = M[i].second;
      if (d - damage < 0) continue;
      if (dp[d-damage] == INT_MAX) continue;
      dp[d] = min(dp[d], dp[d-damage] + cost);
    }
  }
  int res = INT_MAX;
  for (int i = H; i <= H+max_d; i++) {
    res = min(res, dp[i]);
  }

  cout << res << endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59

int main(){
   ll i,j;

   ll n;
   cin>>n;
   ll h[n];
   for(i=0;i<n;i++) cin>>h[i];

   h[0]--;
   for(i=1;i<n;i++){
        if(h[i]<h[i-1]) {
            cout<<"No"<<endl;
            return 0;
        }
        else if(h[i]-1>=h[i-1]) h[i]--;
   }
   cout<<"Yes"<<endl;

   
   return 0;
}


Measured memory_bytes: 1024