akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct para
{
    ll ile, cena, nr;
};

bool porownanie(para a, para b)
{
    if (a.cena < b.cena)
        return true;
    if (a.cena > b.cena)
        return false;
    if (a.nr < b.nr)
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    ll n, m;
    cin >> n >> m;
    vector<para> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].cena >> a[i].ile;
        a[i].nr = i;
    }
    sort(a.begin(), a.end(), porownanie);
    ll odp = 0;
    for (int i = 0; i < n; ++i)
    {
        if (m > 0)
        {
            ll biore = min(a[i].ile, m);
            odp += biore * a[i].cena;
            m -= biore;
        }
    }
    cout << odp;
    return 0;
}


Measured memory_bytes: 2560
# collect input N integers
# replace every element whose value is Bi with Ci
# get input x and y and compute them to display output 
from collections import Counter
n=input()
a=list(map(int,input().split()))
b=Counter(a)
n=int(input())
ans=sum(a)
for i in range(n):
    x,y=map(int,input().split())
    ans+=b[x]*(y-x)
    print(ans)
    b[y]+=b[x]
    b[x]=0

Measured memory_bytes: 24080
#include <bits/stdc++.h>
using namespace std;
int n,k,p[200005];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;++i)
{
cin>>p[i];p[i]++;
}
long long sum=0,res=0;;
for(int i=1;i<=k;++i) sum+=p[i];
res=sum;
for(int i=k+1;i<=n;++i)
{
sum=sum-p[i-k]+p[i];
res=max(res,sum);
}
if(res&1) cout<<res/2<<".5";
else cout<<res/2;
return 0;
}

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

int main(void) {
	
	int N, M, X;
	cin >> N >> X;
	int Mmin = 1001;
	int Msum = 0;

	for(int i=0; i<N; i++) {
		cin >> M;
		Msum += M;
		if(Mmin > M)
			Mmin = M;
	}
	
	cout << (N + (X - Msum)/ Mmin);

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int cmp(const void *a, const void *b) { 
  return *(int *)a - *(int *)b; 
}
 
int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	int *H = (int *)malloc(sizeof(int)*N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &H[i]);
	}
 
	qsort(H, N, sizeof(int), cmp);
	long long dif;
	long long mindif = 10000000000;
	long long ans;
	for (int i = 0; i + K - 1 < N; i++)
	{
		dif = H[i + K - 1] - H[i];
		if (dif < mindif) {
			mindif = dif;
		}
	}
	ans = mindif;
	printf("%lld\n", ans);
	return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

#define error(args...) { vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c){
	vector<string> v;stringstream ss(s);string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a,Args... args){
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ",err(++it, args...);
}

ll x[100010],w[100010];
ll nx[100010];

int main(void){
	ll n,l,t;
	cin >> n >> l >> t;

	rep(i,n) cin >> x[i] >> w[i];	
	
	ll tar = -1 ,xtar = 0;
	rep(i,n){
		if(w[i]==1)
			nx[i] = (x[i] + t%l)%l;
		else
			nx[i] = (x[i] + l - t%l)%l;

		if(w[i]==1){
			tar = i;
			xtar = nx[i];
		}
	}

	if(tar == -1){
		rep(i,n) cout << nx[i] << endl;
		return 0;
	}
	//rep(i,n) cout << nx[i] << endl;
	sort(nx,nx+n);

	ll bump = 0LL;
	rep(i,n){
		if(w[tar]!=w[i]){
			ll d = x[i] - x[tar];
			if(d < 0) d += l;

			if(d <= 2LL*t){
				ll cur = 1LL;
				cur += max<ll>(2LL * t  - d,0LL)/l;
				bump += cur;
			}
		}
	}

	bump %= n;

	ll idx = -1;
	rep(i,n) if(nx[i] == xtar) idx = i;
	const ll sidx = ( idx + n - ((tar + bump)%n) ) %n;

	//error(idx,tar,bump,sidx);
	rep(i,n) cout << (nx[(i +sidx)%n] + l)%l << endl;
	return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>
#include <ctype.h>
int main(int argc, const char * argv[]) {
    int i, count[26] = {0};
    char ch;
    
    while ( scanf("%c", &ch) != EOF ){
        
        if (isupper(ch)){
            ch=tolower(ch);
        }
        
        int num = ch - 'a';
        count[num]++;
        
    }
    for( i = 0 ; i < 26 ; i++ ){
        printf("%c : %d\n", i + 'a', count[i]);
    }
    return 0;
}

Measured memory_bytes: 548
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;

using namespace std;

class Bit{
public:
  vector<int> bit;
  int N;
  Bit(int N):
    bit(vector<int>(N+1, 0)), N(N){}
  void add(int a, int w){
    for(int x = a; x <= N; x += x&-x) bit[x] += w;
  }
  int sum(int a){
    int ret = 0;
    for(int x = a; x > 0; x -= x&-x) ret += bit[x];
    return ret;
  }
  int get(int k){
    k++;
    int res = 0;
    int N = 1; while(N < (int)bit.size()) N *= 2;
    for(int i = N/2; i > 0; i /= 2){
      if(res+i < (int)bit.size() && bit[res+i] < k){
        k -= bit[res+i];
        res += i;
      }
    }
    return res+1;
  }
};

int binary_serch(int N, vector<int> &d, int x){
  int ok = N;
  int ng = 0;
  while(ok-ng > 1){
    int mid = (ok+ng)/2;
    if(d[mid] > x) ok = mid;
    else ng = mid;
  }

  return ok-1;
}

signed main() {
  int N, D, A;
  cin >> N >> D >> A;

  vector<pair<int, int>> X(N);
  REP(i, N) cin >> X[i].first >> X[i].second;

  sort(ALL(X));

  vector<int> d(N), h(N);
  Bit bit(N+1);
  REP(i, N){
    d[i] = X[i].first;
    h[i] = X[i].second;
  }
  d.emplace_back(INF);
  h.emplace_back(0);

  /* REP(i, N){ */
  /*   cout << bit.sum(i); */
  /*   SPBR(i, N); */
  /* } */

  int ans = 0;
  REP(i, N){
    if(h[i]-bit.sum(i+1) <= 0) continue;
    int cnt = ((h[i]-bit.sum(i+1))+A-1)/A;
    ans += cnt;

    int dist = d[i]+2*D;
    int x = binary_serch(N, d, dist);
    /* cout << d[i]+D << " " << i << " " << x << endl; */
    /* cout << cnt*A << endl; */
    bit.add(i+1, cnt*A);
    bit.add(x+2, -cnt*A);

/*   REP(i, N+1){ */
/*     cout << bit.sum(i); */
/*     SPBR(i, N+1); */
/*   } */

  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 11108
#include <bits/stdc++.h>
// atoi : atoi(変数名.c_str())
// to_string(数値)
// %0桁数d とすると表示桁数が「桁数」に満たない場合に0埋めされる
// find(): int i = 変数名.find(“文字列”) 何番目にあるかを得る
// cout << (条件 ? "Yes" : "No") << endl;
// printf("%02d:%02d:%02d",hour,minute,second);
// 降順 sort(a.begin(),a.end(),greater<int>());
// bitset<ビット数> 変数名;  // すべてのビットが0の状態で初期化される
// bitset<ビット数> 変数名("ビット列");  // 指定したビット列で初期化される
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)

int main(){
  int n,k;
  cin >> n >> k;
  cout << (n%k == 0 ? 0 : 1) << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Ho{
   static void Main(){
     var N = int.Parse(Console.ReadLine());
     var aho = Console.ReadLine().Split();
     var A = new long[N];
     var b = new long[N+1];
    
      for (int i = 0;i<N;i++){
        A[i]= long.Parse(aho[i]);
      }
      var count = new long[N + 1];
      foreach (var a in A)
      {
          count[a]++;
      }
      // iが書かれたボールから2個を取り出す方法の数
      var c = new long[N + 1];
      for (int i = 0; i < N+1; i++)
      {
          c[i] = count[i] * (count[i] - 1) / 2;
      }

      // ボールを除かないときの方法の数
      var sum = c.Sum();

      // aを除くときの方法の数を求める
      foreach (var a in A)
      {
          if (count[a] == 0) continue;
          var newCount = count[a] - 1;
          var ans = sum - c[a] + (newCount * (newCount - 1) / 2);
          Console.WriteLine(ans);
      }
   } 
}

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

using namespace std;

int main(){
    int N,ans=0;
    string S;
    cin >> N;
    vector<string> s(N);
    vector<int> t(N),sum(N);
    for(int i=0;i<N;i++){
        cin >> s[i] >> t[i];
        if(i==0){
            sum[i] = t[i];
        }else{
            sum[i] = sum[i-1] + t[i];
        }
    }

    cin >> S;

    for(int i=0;i<N;i++){
        if(S==s[i]){
            cout << sum[N-1]-sum[i] << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

//割られる数：a
//余りを求めるやつ：valid
long long Modinv(long long a, long long valid = INV)
{
	long long b = valid, u = 1, v = 0;
	while (a)
	{
		if (a < b)
		{
			swap(a, b);
			swap(u, v);
		}
		long long t = a / b;
		a -= t * b;
		u -= t * v;
	}
	v %= valid;
	if (v < 0)
		v += valid;
	return v;
}
//rCnの場合
long long int Combination(long long int r, long long int n)
{
	long long int ans = 1;
	long long int div;

	for (int i = 0; i < n; i++)
	{
		ans *= r - i;
		div = i + 1;

		ans = ans % INV * Modinv(div) % INV;
	}

	return ans;
}

lint Pow(lint n, lint x = 2, lint m = INV)
{
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return Pow(n / 2, x * x % m, m);
	else
		return x * Pow(n - 1, x, m) % m;
}

void execute()
{
	lint N, a, b;
	cin >> N >> a >> b;
	lint sum = 1;

	sum = Pow(N);
	sum--;

	lint ans;
	ans = sum - Combination(N, a);
	if (ans < 0)
		ans += INV;
	ans %= INV;

	ans = ans - Combination(N, b);
	if (ans < 0)
		ans += INV;

	cout << ans << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define int ll
#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int n, m;
    cin>>n>>m;
    int ans = (n * (n - 1)) / 2;
    ans += (m * (m - 1)) / 2;
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=n-1;i>=0;i-=2){
    cout<<a[i]<<" ";
  }
  if(n%2==0){
    for(int i=0;i<n;i+=2){
      cout<<a[i]<<" ";
    }
  }else{
    for(int i=1;i<n;i+=2){
      cout<<a[i]<<" ";
    }
  }
}

Measured memory_bytes: 2944
//AUTHOR - NIMISH UPADHYAY
//FROM IIIT ALLAHABAD
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define NIMISH ios_base::sync_with_stdio(false);cin.tie(NULL);
#define UPADHYAY int t;cin>>t;while(t--)
int main(){
    ll n;
    cin>>n;
    if(n==0)
    cout<<1<<"\n";
    else
    cout<<0<<"\n";
}

Measured memory_bytes: 3580
#include<stdio.h>
int main ()
{
    int n, i;
    int a[101];

    scanf("%d", &n);

    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    for(i = n - 1; 0 <= i; i--)
    {
        printf("%d", a[i]);
        if(0 < i)
        {
            printf(" ");
        }
    }

    printf("\n");

    return 0;
}

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

#define ff              first
#define ss              second
#define int             long long int
#define pb              push_back
#define mp12            make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pq1             priority_queue<int>
#define pqr1            priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

void FIO(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

int modInv(int a,int b,int m){int res=1;a=a%m;while(b>0){if(b&1){res=(res*a)%m;}a=(a*a)%m;b=b>>1;}return res;}

void solve(){
	int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    int dp[k+1];
    memset(dp,0,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=k;i++){
        for(int j=0;j<n;j++){
            if(i-a[j]>=0 and dp[i-a[j]]==0){
                dp[i]=1;

            }
        }
    }
    if(dp[k]==1) cout<<"First";
    else cout<<"Second\n";
    // for(int i=0;i<=k;i++) cout<<dp[i]<<" ";
}
    

int32_t main()
{
   // FIO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();


    return 0;
}


Measured memory_bytes: 4412
n = int(input())
a = list(map(int, input().split()))

ans = 1

if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if (ans > 10 ** 18):
            print(-1)
            ans = -1
            exit()
            #break
print(ans)

Measured memory_bytes: 21508
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=100000+10;
const int maxm=10000+10;
const int mod=(int)1e9+7;
const int INF=0x3f3f3f3f;
const ll LINF=(1LL<<62);
const double PI=acos(-1.0);
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for (int i=(a);i<b;i++)
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define X first
#define Y second
int a[maxn];
int b[50][maxn];
int main(){
#ifdef local
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif
    //ios::sync_with_stdio(false); cin.tie(0);
    int n,c,mx_t=0; scanf("%d%d",&n,&c);
    for (int i=0;i<n;i++){
        int s,t,cc; scanf("%d%d%d",&s,&t,&cc);
        b[cc][s]++;
        b[cc][t]--;
        mx_t=max(mx_t,t);
    }
    for (int i=1;i<=c;i++){
        for (int j=1;j<=mx_t;j++){
            if (b[i][j]==1) a[j]++;
            if (b[i][j]==-1) a[j+1]--;
        }
    }
    int sum=0,ans=0;
    for (int i=1;i<=mx_t;i++){
        sum+=a[i];
        ans=max(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 12544
#include<iostream>
#include<string>
using namespace std;
struct ST
{
	int S;
	int T;
	ST()
	{
		S = T = 0;
	}
};

int main()
{
	string str;
	cin >> str;
	ST st[200010];
	int j = 0;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == 'S')
		{
			st[j].S++;
			i++;
			while (i < str.size() && str[i] == 'S')
			{
				st[j].S++;
				i++;
			}
			i--;
		}
		else
		{
			st[j].T++;
			i++;
			while (i < str.size() && str[i] == 'T')
			{
				st[j].T++;
				i++;
			}
			i--;
			j++;
		}
	}
	int ans = str.size();
	int s = 0;
	for (int i = 0; i < j; i++)
	{
		s += st[i].S;
		if (s <= st[i].T)
		{
			ans -= s * 2;
			s = 0;
		}
		else
		{
			ans -= st[i].T * 2;
			s -= st[i].T;
		}
	}
	cout << ans;
}

Measured memory_bytes: 2172
a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if i*500 + j*100 + k*50 == x:
        ans += 1
print(ans)


Measured memory_bytes: 2940
import java.util.*;

public class Main {
		public static void main(String[] args) {
		
	   Scanner sc = new Scanner(System.in);
	   
	   int N = sc.nextInt();
	   Integer d[] = new Integer[N];
		for (int i=0; i<N; i++) {
			d[i] = sc.nextInt();
		}
		int sum = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(i == j) {
					continue;
				}
				sum +=  d[i] * d[j];
		}
	   }
          System.out.println(sum / 2);
}
}



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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef vector<vl> mt;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<string> vs;
typedef vector<vs> table;
typedef vector<vl> v2;
typedef vector<v2> v3;
typedef vector<v3> v4;


const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 50;

ll n,m;
vl a;
vl b;
vl dp;


int main(){
  cin >> n;
  a = vl(3);
  b = vl(3);
  for(ll i = 0;i < 3;i++) cin >> a[i];
  for(ll i = 0;i < 3;i++) cin >> b[i];
  dp = vl(n+1);
  for(ll i = 0;i <= n;i++){
    for(ll j = 0;j < 3;j++){
      ll nxt = i+a[j];
      if(nxt <= n){
        dp[nxt] = max(dp[nxt], dp[i]+b[j]-a[j]);
      }
    }
  }
  m = n+*max_element(dp.begin(),dp.end());
  dp = vl(m+1);
  for(ll i = 0;i <= m;i++){
    for(ll j = 0;j < 3;j++){
      ll nxt = i+b[j];
      if(nxt <= m){
        dp[nxt] = max(dp[nxt], dp[i]+a[j]-b[j]);
      }
    }
  }
  cout << m+*max_element(dp.begin(),dp.end()) << endl;



}


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

int main()
{
	int R[200000];
	int maxp = -2000000000;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> R[i];
	int minv =R[0];
	for (int i = 1; i < n; i++)
	{
		maxp = max(maxp, R[i] - minv);
		minv = min(minv, R[i]);
	
	}
	cout << maxp << endl;
	return 0;
}

Measured memory_bytes: 3864
import math


def main():
    a, b, h, m = [int(x) for x in input().split()]

    ang_a = (360 * h / 12 + 360 * m / 12 / 60) % 360
    ang_b = 360 * m / 60 % 360
    ang = max(ang_a, ang_b) - min(ang_a, ang_b)
    ang = math.radians(min(360 - ang, ang))

    ans = (a ** 2 + b ** 2 - 2 * a * b * math.cos(ang)) ** 0.5
    return ans


if __name__ == '__main__':
    print(main())


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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
// #define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      long n; scan(n);
      std::string str; scan(str);
      long x = 0, y = 0, s = 0;
      for(long i = 0; i < n; ++i) {
         if( str[i] == '(' ) {
            s += 1;
         }
         if( str[i] == ')' ) {
            if( s > 0 ) s -= 1;
            else y += 1;
         }
      }
      s = 0;
      for(long i = n - 1; i >= 0; --i) {
         if( str[i] == ')' ) {
            s += 1;
         }
         if( str[i] == '(' ) {
            if( s > 0 ) s -= 1;
            else x += 1;
         }
      }
      for(long i = 0; i < y; ++i) putchar('(');
      printf("%s", str.c_str());
      for(long i = 0; i < x; ++i) putchar(')');
      putchar('\n');
   }
};

int main() {
  loop std::unique_ptr<Solver>(new Solver())->solve();
}



Measured memory_bytes: 256
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int D = sc.nextInt();
		double X[][] = new double[N][D];

		double ans = 0;
		int count = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < D; j++) {
				X[i][j] = sc.nextDouble();
			}
		}

		for (int i = 0; i < N; i++) {
			for (int k = i + 1; k < N; k++) {
				for (int j = 0; j < D; j++) {
					ans += Math.pow(X[i][j] - X[k][j], 2);
				}

				for (int l = 0; l * l <= ans; l++) {
					if (l * l == ans) {
						count++;
					}
				}
				ans = 0;
			}
		}
		System.out.print(count);
	}
}

Measured memory_bytes: 23252
#include<stdio.h>
#define N 101
#define WH 0
#define BL 1
#define GA 2 

int n,m[N][N];

int a[N],b[N],c[N],t=0;

void tansaku(int u){
  int e;
  a[u] = GA;
  b[u]=++t;
  for(e=1;e<=n;e++){
    if(m[u][e]==1 && a[e]==WH){
      tansaku(e);
    }
  }
  a[u] = BL;
  c[u] = ++t;
}


void depth(){
  int u;
  for(u=1;u<=n;u++){
    a[u]=WH;
    t=0;
  }

  for(u=1;u<=n;u++){
    if(a[u] == WH){
      tansaku(u);
    }
  }

}


int main(){
  int u,i,j,k,l;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      m[i][j] = 0;
    }
  }
  for(i=1;i<=n;i++){
    scanf("%d %d",&u,&k);
    for(j=1;j<=k;j++){
      scanf("%d",&l);
      m[i][l] = 1;
    }
  }
  depth();
  for(i=1;i<=n;i++){
    printf("%d %d %d",i,b[i],c[i]);
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
const int Maxn = 1e6;

int main(){
	int n,k;
	cin>>n>>k;
	if(n<k) printf("1\n");
	else{
		if(n%k==0) printf("0\n");
		else printf("1\n");
	}
}

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();
		String num = String.valueOf(n);
		char[] nums = num.toCharArray();
		int sum = 0;
		for(int i=0; i<nums.length; i++) {
			sum += Character.getNumericValue(nums[i]);
		}
		if(n%sum == 0) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
}


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

int main(void) {
  int n;
  cin >> n;
  if (n == 0) cout << 2 << endl;
  if (n == 1) cout << 1 << endl;
  else {
    n -= 1;
    long long ans = 1, f = 2, tmp;
    while (n > 0) {
      tmp = ans;
      ans += f;
      f = tmp;
      n--;
    }
    cout << ans << endl;
  }
  
  return 0;
}
      

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define INF 9999999
using namespace std;

int a[100000+5];

int main(){
    int n;
    long long ans;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",a+i);
    sort(a,a+n);
    if(n&1){
        //2k+1
        int m1=a[n/2-1],m2=a[n/2],m3=a[n/2+1];
        long long s1=0,s2=0;
        for(int i=0;i<n/2-1;i++)s1+=a[i];
        for(int i=n/2+2;i<n;i++)s2+=a[i];
        ans=2*(s2-s1)+max(2*m3-m2-m1,-2*m1+m3+m2);
    }else{
        int m1=a[n/2-1],m2=a[n/2];
        long long s1=0,s2=0;
        for(int i=0;i<n/2-1;i++)s1+=a[i];
        for(int i=n/2+1;i<n;i++)s2+=a[i];
        ans=2*(s2-s1)+m2-m1;
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 640
#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 vvi vector<vi>
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    string s;
    cin >> s;

    int primA = -1, ultZ = -1;
    fo(i, (int) s.size() ) {
        if ( s[i] ==  'A' ) {
            primA = i;
            break;
        }
    }
    for ( int i = s.size() - 1; i >= 0; i-- ) {
        if ( s[i] == 'Z' ) {
            ultZ = i;
            break;
        }
    }
    cout << ultZ - primA + 1 << endl;

    return 0;
}

Measured memory_bytes: 640
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;
typedef long long ll;

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

int main(){
int N,M;
cin>>N>>M;
vector<int> H(N);
vector<int> A(M);
vector<int> B(M);
set<int> C;

rep(i,N)cin>>H[i];
rep(i,M)cin>>A[i]>>B[i];
rep(i,M){
    if(H[A[i]-1]>H[B[i]-1]){
        C.insert(B[i]);
        

    }
    else if(H[A[i]-1]<H[B[i]-1]){
        C.insert(A[i]);
        

    }
    else {
        C.insert(A[i]);
        C.insert(B[i]);
        
    }
}
cout<<N-C.size()<<endl;

return 0;

}

Measured memory_bytes: 7168
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

static const int INTINF = (2147483647 >> 1); // 10^9 + 5000
static const ll LLINF = (9223372036854775807 >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;

namespace Kunitaka{
    template<
        typename TYPE,
        std::size_t SIZE
    >
    std::size_t array_length(const TYPE (&array)[SIZE])
    {
        return SIZE;
    }
}
using namespace Kunitaka;
namespace Printer{
    void br(){
        cout << endl;
    }

    void loop_cnt(int i){
        cout << "i = " << i << endl;
    }

    void loop_cnt(int i, int j){
        cout << "i = " << i << ", " << "j = " << j << endl;
    }

    template<class T>
    void print(T x){
        cout << x << endl;
    }

    template<class T, class S>
    void print(T x, S y){
        cout << x << "," << y << endl;
    }

    template<class T, class S, class U>
    void print(T x, S y, U z){
        cout << x << "," << y << "," << z << endl;
    }

    template<class T, class S>
    void print(pair<T, S> p){
        cout << p.first << ", " << p.second << endl;
    }

    template<
        typename TYPE,
        std::size_t SIZE
    >
    void print(const TYPE (&array)[SIZE]){
        int lim = array_length(array);
        for(int i=0; i<lim; i++){
            if(i) cout << " ";
            cout << array[i];
        }
        cout << endl;
    }

    template<class S>
    void print(vector<S> v){
        for(int i=0; i<v.size(); i++){
            if(i) cout << " ";
            cout<< v[i];
        }
        cout << endl;
    }

    template<class S>
    void print(vector<vector<S> > vv){
        for(int i=0; i<vv.size(); i++){
            for(int j=0; j<vv[i].size(); j++){
                if(j) cout << " ";
                cout << vv[i][j];
            }
            cout << endl;
        }
    }

    void yesno(bool x){
        if(x) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
};
using namespace Printer;

int main(int argc, const char * argv[]) {
    //提出時、消す
    //--------------//


    // input
    cout << fixed << setprecision(10);
    ll N, A, B; cin >> N >> A >> B;
    if(A == 0 && B == 0) {
        print(0);
        return 0;
    }
    ll tmp = N / (A+B);

    print(tmp * A + min(N - N /(A+B) * (A+B), A));
    
    return 0;
}


Measured memory_bytes: 256
//BISMILLAHIR RAHMANIR RAHIM

#include <bits/stdc++.h>
#define loop(i,n) for(int i=0;i<n;i++)
#define pi acos(-1.00)

using namespace std;



int main()
{
int n,m,i;
cin>>n>>m;
    string s[200];
    for(i=0;i<n;i++)
    {
        cin>>s[i];
    }
    sort(s,s+n);
    for(i=0;i<n;i++)
        cout<<s[i];

}



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


int sum(int n)
{
  if(n==1)
  {
    return 1;
  }  
  return sum(n-1)+n;
}  


int main() {
  ll N;
  cin>>N;
  vector<string> word(N);
  rep(i,N)
  {
    cin>>word.at(i);
  }
  sort(word.begin(),word.end());
  ll ans=0;
  rep(i,N)
  {
    if(i==0)
    {
      ans++;
    }
    else
    {
      if(word.at(i)!=word.at(i-1))
      {
        ans++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int a[100100];
int b[100100];

int main(void){
  int n,aa,bb;
  string s;
  cin >> n >> aa >> bb;
  cin >> s;
  fill(a,a+100100,0);
  fill(b,b+100100,0);
  for(int i = 1;i <= n;++i){
    a[i] = a[i-1];
    b[i] = b[i-1];
    //cout << a[i] << " " << b[i] << endl;
    if(s[i-1] == 'a' &&
       a[i] < aa+bb){
      cout << "Yes" << endl;
      ++a[i];
    }else if(s[i-1] == 'b' &&
	     a[i] < aa+bb &&
	     b[i] < bb){
      cout << "Yes" << endl;
      ++a[i];
      ++b[i];
    }else{
      cout << "No" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
const ll mod = 1000000007;
const ll INF = 1e+14;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define _GLIBCXX_DEBUG

char inttochar(int a){
    if(a==0) return'a';
    if(a==1) return'b';
    if(a==2) return'c';
    if(a==3) return'd';
    if(a==4) return'e';
    if(a==5) return'f';
    if(a==6) return'g';
    if(a==7) return'h';
    if(a==8) return'i';
    if(a==9) return'j';
    if(a==10) return'k';
    if(a==11) return'l';
    if(a==12) return'm';
    if(a==13) return'n';
    if(a==14) return'o';
    if(a==15) return'p';
    if(a==16) return'q';
    if(a==17) return'r';
    if(a==18) return's';
    if(a==19) return't';
    if(a==20) return'u';
    if(a==21) return'v';
    if(a==22) return'w';
    if(a==23) return'x';
    if(a==24) return'y';
    if(a==25) return'z';
}
ll sum26(ll n){
    ll a=pow(26,n)-1;
    return 26*a/25;
}

int main(){
    ll n;
    cin>>n;
    n--;
    int limit=1;
    while(sum26(limit)<=n){
        limit++;
    }
    //limitが桁数

    ll think=n-sum26(limit-1);
    vector<char> preans;
    rep(i,limit){
        preans.push_back(inttochar(think%26));
        think/=26;
    }
    string s;
    per(i,limit){
        s+=preans[i];
    }
    cout<<s<<endl;
}

Measured memory_bytes: 3968
#include <utility>
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define nil 0


class hashTable{
private:
  int size;
  std::vector<long> v;
public:
  hashTable(long size_){size=size_; v.reserve(size_); v.resize(size_,0); };
  long h1(long x){ return x%size; };
  long h2(long x){ return 1 + x%(size-1); };
  long hash(long x, long i){ return (h1(x) + i*h2(x)) % size; };
  long str2long(string s);
  void insert(string s);
  bool search(string s);
  void prlongv();
};

void hashTable::insert(string s){
  long key = str2long(s);
  long i=0;
  while (1) {
    long j=hash(key, i);
    if (v[j]==0) {
      v[j]=key;
      break;
    }else{
      i++;
    }
  }
}

bool hashTable::search(string s){
  long key = str2long(s);
  long i=0;
  while (1) {
    long j=hash(key, i);
    if (v[j]==key) {
      return true;
    }else if (v[j]==0 || i>=size) {
      return false;
    }else{i++;}
    }
  }


long hashTable::str2long(string s){
  long val=0;
  for (size_t i = 0; i < s.length(); i++) {
    if (s[i]=='A') val+= 1 * pow(10,i);
    else if (s[i]=='C') val+= 2 * pow(10,i);
    else if (s[i]=='G') val+= 3 * pow(10,i);
    else if (s[i]=='T') val+= 4 * pow(10,i);
    else val+= 5 * pow(10,i);
  }
  return val;
}

void hashTable::prlongv(){
  for (size_t i = 0; i < size; i++) {
    std::cout << i << ":"  << v[i] << ", ";
  }
  std::cout  << '\n';
}

int main(int argc, char const *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; std::cin >> n;
  string s;
  hashTable h = hashTable(1000000);
  for (size_t i = 0; i < n; i++) {
    std::cin >> s;
    if (s=="insert") {
      std::cin >> s;
      h.insert(s);
    }else if (s=="find") {
      std::cin >> s;
      if (h.search(s)) {
        std::cout << "yes" << '\n';
      }else{
        std::cout << "no" << '\n';
      }
    }
  }

  return 0;
}



Measured memory_bytes: 10768
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append("."+ input()+ ".")
s_list.append("."*(W+2))
s_list.insert(0,"."*(W+2))

result = []
for i in range(1, H+1):
    line = []
    for j in range(1, W+1):
        if s_list[i][j]=="#":
            line.append("#")
            continue
        count = 0
        count += 0 if s_list[i][j-1] == "." else 1
        count += 0 if s_list[i+1][j-1] == "." else 1
        count += 0 if s_list[i+1][j] == "." else 1
        count += 0 if s_list[i+1][j+1] == "." else 1
        count += 0 if s_list[i][j+1] == "." else 1
        count += 0 if s_list[i-1][j+1] == "." else 1
        count += 0 if s_list[i-1][j] == "." else 1
        count += 0 if s_list[i-1][j-1] == "." else 1
        line.append(str(count))
    result.append(line)
for i in range(H):
    print("".join(result[i]))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int a, b, c;
int n;
string d;
#define rep(i,n) for(int i=0; i<n; i++)
int main(){
    cin >> a;
  	cin >> d;
    if(a >= 3200) cout << d;
  	else cout << "red";
}

Measured memory_bytes: 256
N = int(input())
S = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
X = [-1] * (N+1)
X[0] = 0
for i in range(1, N+1):
    mi = X[i-1] + 1
    for s in S:
        if s <= i:
            mi = min(mi, X[i-s] + 1)
    X[i] = mi

print(X[N])

Measured memory_bytes: 41836
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
int main() {
    Int N, K; cin >> N >> K;
    Int a = N - N / K * K;
    Int b = abs(a - K);
    cout << min(a, b) << endl;
    return 0;
}


Measured memory_bytes: 256
k,x = map(int, input().split())
mi = x - k + 1
ma = x + k - 1
t_min = max(mi, -1000000)
t_max = min(ma, 1000000)
L = list(range(t_min, t_max+1))
arr = [str(i) for i in L]
arr=' '.join(arr)
print(arr)

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#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 double EPS = 1e-8;
  
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

class State{
public:
  int freq[8];
  vector<int> matrix;
  int height;
  State(int _freq[8],const vector<int>& _matrix,int _h){
    memcpy(freq,_freq,sizeof(int)*8);
    matrix = _matrix;
    height = _h;
  }
  bool operator<(const State& s) const{
    return height < s.height;
  }
  bool operator>(const State& s) const{
    return height > s.height;
  }
};

bool is_clear(const vector<int>& matrix,int freq[12],int W){
  for(int i=0;i<matrix.size();i++){
    if(matrix[i] != i) return false;
  }

  for(int i=0;i<W;i++){
    if(freq[i] != 0) return false;
  }
  return true;
}

bool is_valid(const vector<int>& matrix,int freq[12],int W){
  for(int i=0;i<W;i++){
    if(freq[i] < 0) return false;
  }
  return true;
}

int main(){
  int W,H;
  while(~scanf("%d %d",&W,&H)){
    vector<int> matrix;
    for(int i=0;i<W;i++){
      matrix.push_back(i);
    }
    map<string,int> dp;
    int freq[8];
    memset(freq,0,sizeof(freq));

    for(int i=0;i<H;i++){
      int line;
      scanf("%d",&line);
      line--;
      swap(matrix[line],matrix[line+1]);
      freq[line]++;
    }
    
    vector<int> patterns;
    for(int S=0;S<=(1<<(W-1)) - 1;S++){
      bool isok = true;
      for(int prohibit=2;prohibit <= W;prohibit++){
	int base = (1<<prohibit) - 1;

	for(int pos = 0; pos + prohibit <= W; pos++){
	  if((base & S) == base) {
	    isok = false;
	    break;
	  }
	  base <<= 1;
	}
      }

      for(int pos=0;pos<W;pos++){
	if(freq[pos] <= 0 && (S & (1<<pos))){
	  isok = false;
	}
      }

      if(isok){
	patterns.push_back(S);
      }
    }

    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(freq,matrix,0));

    int res = H;
    while(!que.empty()){
      State s = que.top();
      que.pop();

      if(!is_valid(s.matrix,s.freq,W)) continue;

      if(s.height >= H){
	goto found;
      }

      if(is_clear(s.matrix,s.freq,W)){
	res = s.height;
	goto found;
      }

      for(int i=0;i<patterns.size();i++){
	vector<int> next_matrix = s.matrix;
	int S = patterns[i];
	int next_freq[8];
	memcpy(next_freq,s.freq,sizeof(int)*W);
	
	for(int j=0;j<=W-1;j++){
	  if(S & (1<<j)){
	    swap(next_matrix[j],next_matrix[j+1]);
	    next_freq[j]--;
	  }
	}

	que.push(State(next_freq,next_matrix,s.height+1));
      }
    }

  found:;
    printf("%d\n",res);
  }
}

Measured memory_bytes: 15788
#include <iostream>
using namespace std;
int coin[6] = {500,100,50,10,5,1};

int main() {
  int price,change,res=0;
  while(cin >> price) {
    if(price == 0) break;
    change = 1000 - price;
    for(int i=0;i<6;i++) {
      res += change/coin[i];
      change -= (change/coin[i]) * coin[i];
    }
    cout << res << endl;
    res = 0;
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define  mp make_pair
#define pb push_back
const int mod  = 1e9 + 7;
bool isPrime(int n)
{
    for (int i = 2; i < n; i++) if (n % i == 0)return false;
    return true;
}
struct cmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b)
    {
        int len1 = a.second - a.first + 1;
        int len2 = b.second - b.first + 1;
        if (len1 != len2) return len1 > len2;
        return a.first < b.first;
    }
};
bool comp(pair<pair<int, int>, int>& a, pair<pair<int, int>, int>& b)
{
    int diff1 = abs(a.first.first - a.first.second);
    int diff2 = abs(b.first.first  - b.first.second);

    if (diff1 > diff2)
        return true;
    return false;
    // return (a.first.second > b.first.second);

}
void findAns()
{
    int n, k;
    cin >> n >> k;

    int height[n];
    for (auto&it : height) cin >> it;

    int dp[n];

    dp[0] = 0;
    dp[1] = abs(height[0] - height[1]);
    int minValue;
    int j;
    for (int i = 2; i < n; i++)
    {
        minValue = INT_MAX;
        j = max(i - k, 0);
        while (j < i)
        {
            minValue = min(minValue, dp[j] + abs(height[j] - height[i]));
            j++;
            //cout << minValue << " ";
        }

        dp[i] = minValue;
    }
    cout << dp[n - 1];
    return;







}
int main()
{

    fastio;
    // ll int t;
    // cin >> t;

    // while (t--)
    findAns();

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    int h1,h2,k1,k2,a,b,c,d,h,k;
    cin>>h1>>h2>>k1>>k2>>a>>b>>c>>d;
    h=h1*a+(h1/10)*c+h2*b+(h2/20)*d;
    k=k1*a+(k1/10)*c+k2*b+(k2/20)*d;
    
    if(h>k){
    cout<<"hiroshi"<<endl;
    }
    if(h<k){
    cout<<"kenjiro"<<endl;
    }
    if(h==k){
    cout<<"even"<<endl;
    }
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(ll x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    vll b(n);
    rep(i, n){
        cin >> b[i];
    }
    repr(i, 1, n){
        a[i] += a[i-1];
    }
    for(int i = n-2; i >= 0; i--){
        b[i] += b[i+1];
    }
    dump(a);
    dump(b);
    ll ans = 0;
    rep(i, n){
        chmax(ans, a[i]+b[i]);
    }
    cout << ans << endl;
    return 0;
}

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

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

////////////////////////////////////////////////////////////////

ll chmin(ll &a, ll b){ return a = (a<b) ? a : b;}

int main(void) {
	string s;
	cin >> s;
	reverse(s.begin(), s.end());//s[i]がi桁目となるようにする
	ll n = s.size() + 1;
	s += '0';

	const ll MAX = 9 * n + 1;//すべての紙幣を9枚ずつ使う

	//dp[i][j]: (i-1)桁目まで見た時に必要な最小枚数
	//jは i-1桁目で繰り下がりが必要かどうか 1:必要 0:なし
	vector<vector<ll>> dp(n+1, vector<ll>(2, MAX));
	dp[0][0] = 0;
	//dp[0][1] = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<2; j++){
			int a = s[i] - '0';
			int b = j;//(i-1)桁目でa=0としたら，i桁目で繰り下がりが起きるが，繰り下がりがおきたら aが-1されるけど,それをbが+1されたとする
			//i桁目をs[i]にする場合
			chmin(dp[i+1][0], dp[i][j] + a + b);

			//i桁目を0にする場合
			b = 10 - (a+j);
			chmin(dp[i+1][1], dp[i][j] + 0 + b);			
		}

	}
	//cout << " dp: " << endl; print_vec2(dp);
	cout << dp[n][0] << endl;



	
}


Measured memory_bytes: 58828
import math
n=int(input())
lists=list(map(int,input().split()))
sums=[0 for i in range(n)]
c=0
for i in range(n):
    c+=lists[i]
    sums[i]=c
#累積和
ans=10**10
for i in range(1,n-2):
    a=sums[i]
    b=sums[n-1]-sums[i]

    #aが左側の分割、bが右側の分割
    a_left=0
    a_right=i-1
    b_left=i
    b_right=n-1
    for j in range(20):
        c=(a_left+a_right)/2
        if 2*sums[math.floor(c)]>a:
            a_left=a_left
            a_right=math.floor(c)
        elif 2*sums[math.floor(c)]<=a:
            a_left=math.floor(c)
            a_right=a_right
    for j in range(20):
        d=(b_left+b_right)/2
        if 2*(sums[math.floor(d)]-sums[i])>b:
            b_left=b_left
            b_right=math.floor(d)
        elif 2*(sums[math.floor(d)]-sums[i])<=b:
            b_left=math.floor(d)
            b_right=b_right

    A1=sums[a_left]
    A2=sums[a_left+1]
    B1=sums[b_left]
    B2=sums[b_left+1]
    J=abs(max(a-A1,A1,a+b-B1,B1-a)-min(a-A1,A1,a+b-B1,B1-a))
    K=abs(max(a-A2,A2,a+b-B2,B2-a)-min(a-A2,A2,a+b-B2,B2-a))
    L=abs(max(a-A2,A2,a+b-B1,B1-a)-min(a-A2,A2,a+b-B1,B1-a))
    M=abs(max(a-A1,A1,a+b-B2,B2-a)-min(a-A1,A1,a+b-B2,B2-a))
    ans=min(J,K,L,M,ans)
print(ans)


Measured memory_bytes: 106404