akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main(void){
  int n,k;
  int x=0;
  int sum = 0;

  
  scanf("%d", &n);
  scanf("%d", &k);
  for(int i=0;i<n;i++){
  	scanf("%d", &x);
    if(x<(k-x)){
    sum += (2*x);
    }
    else
    sum += (2*(k-x));
   
  }
 /*
  for(int i=0;i<n;i++){
    //handan(x,k);
    if(x<(k/2)){
    sum += (2*x);
    }
    else
    sum += (2*(k-x));
  
    //sum += handan(x,k);
  }
  */
  
  printf("%d", sum);
  return 0;
}

  

Measured memory_bytes: 1712
N = int(input())
A = list(map(int,input().split()))
while len(A) > 1:
    A.sort()
    devided_num = int(A[0])
    devi_lis = [devided_num]
    As = A
    As.pop(0)
    A =[_%devided_num for _ in As if _%devided_num > 0]
    A += devi_lis
print(A[0])

Measured memory_bytes: 14224
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int Z=0;
    //-----------

    string strO,strE;
    
    //入力
    cin>>strO>>strE;
    //Oが必ず多い
    for(int i=0;i< strE.size();i++)
    {
        cout<<strO.at(i);
        cout<<strE.at(i);
    }
    if(strO.size()-strE.size()==1)cout<<strO.back();

    cout<<endl;
    
    //cout<<"NO"<<endl;
    

    

    //------------
    cin>>Z;//何と入力がなければ消さなくてもいいらしい

    return 0;
}

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

#define ll             long long
#define gcd(a,b)       __gcd(a,b)
#define lcm(a,b)       a*(b/gcd(a,b))
#define pii            pair<int, int>
#define pll            pair<ll, ll>
#define pil            pair<int, ll>
#define pli            pair<ll, int>
#define vi             vector<int>
#define vl             vector<ll>
#define vii            vector<pii>
#define vll            vector<pll>
#define vil            vector<pil>
#define vli            vector<pli>
#define mii            map<int, int>
#define mll            map<ll, ll>
#define pb             push_back
#define ppb            pop_back
#define mp             make_pair
#define mt             make_tuple
#define lb             lower_bound
#define ub             upper_bound
#define ff             first
#define ss             second
#define all(v)         v.begin(),v.end()
#define fill(a,b)      memset(a,b,sizeof a)
#define smax(a, b)     a=max(a, b)
#define smin(a, b)     a=min(a, b)
#define sqr(x)         x*x
#define cube(x)        x*x*x
#define asort(a, n)    sort(a+1, a+n+1)
#define FOR(i, l, r)   for(int i=l;i<=r;i++)
#define ROF(i, l, r)   for(int i=r;i>=l;i--)
#define endl           '\n'

int in() {
    int n;
    scanf("%d",&n);
    return n;
}

ll Lin() {
    ll n;
    scanf("%lld",&n);
    return n;
}

double Din() {
    double n;
    scanf("%lf",&n);
    return n;
}

const double gama = 0.57721566490;
const double eps = 0.00000001;
const ll inf = 1e17;
const ll mod = 1e9 + 7;
const int N = 1e6 + 5;

int p[N];
vi g[N];
bool vis[N];
vi id, num;

void dfs(int u) {
    vis[u]=true;
    id.pb(u), num.pb(p[u]);
    for(auto v : g[u]) {
        if(!vis[v])
            dfs(v);
    }
}

bool bs(int x) {
    int low=0, high=num.size()-1;
    while(low<=high) {
        int mid=(low+high)>>1;
        if(num[mid]==x)
            return true;
        if(num[mid]>x)
            high=mid-1;
        else
            low=mid+1;
    }
    return false;
}

int main() {
    int n=in(), m=in();
    for(int i=1; i<=n; i++) p[i]=in();
    for(int i=1; i<=m; i++) {
        int x=in(), y=in();
        g[x].pb(y);
        g[y].pb(x);
    }
    int ans=0;
    for(int u=1; u<=n; u++) {
        if(!vis[u]) {
            num.clear(), id.clear();
            dfs(u);
            sort(all(id)), sort(all(num));
            for(int i=0; i<id.size(); i++) {
                if(bs(id[i])) ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}








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

typedef long long int int64;

const int mod=1000000007;

#define ADD(a,b) ((a)+(b)<mod?(a)+(b):(a)+(b)-mod)
#define MUL(a,b) ((int64)(a)*(b)%mod)

int modPow(int r,int n){
  int t=1;
  int s=r;
  while(n>0){
    if(n&1) t=MUL(t,s);
    s=MUL(s,s);
    n>>=1;
  }
  return t;
}

void run(void){
  int n,c;
  scanf("%d%d",&n,&c);
  int *a=(int *)calloc(2*n,sizeof(int));
  int *b=a+n;
  int i,j;
  for(i=0;i<2*n;i++) scanf("%d",a+i);
  const int m=400+1;
  int *pre=(int *)calloc(m*m,sizeof(int));
  for(i=1;i<m;i++) pre[i]=1;
  for(i=1;i<m;i++){
    for(j=1;j<m;j++){
      pre[i*m+j]=MUL(pre[(i-1)*m+j],j);
    }
  }
  for(i=0;i<m;i++){
    for(j=1;j<m;j++){
      pre[i*m+j]=ADD(pre[i*m+j],pre[i*m+j-1]);
    }
  }
  int *dp=(int *)calloc(c+1,sizeof(int));
  dp[0]=1;
  for(i=0;i<n;i++){
    for(j=c;j>=0;j--){
      int local=0;
      for(int k=0;k<=j;k++){
	local=ADD(local,MUL(dp[j-k],ADD(pre[k*m+b[i]],mod-pre[k*m+a[i]-1])));
      }
      dp[j]=local;
    }
  }
  printf("%d\n",dp[c]);
}

int main(void){
  run();
  return 0;
}


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

int main(){
    int N;
    cin>>N;
    int A[N];
    for(int i=0;i<N;++i)cin>>A[i];
    sort(A,A+N);

    int count=0,i=0,sum;
    while(i<N){
        sum=0;
        int temp=A[i];
            while(i<N && A[i]==temp)++i,sum++;
        count+=sum%2;
    }
    cout<<count;
}

Measured memory_bytes: 3616
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


#define M 1000003
#define L 14 /*文字列の長さ*/

char H[M][L]; /* Hash Table */

int getChar(char ch)
{
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}


/* convert a string into an integer value */
long long getKey(char str[])
{
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ )
    {
      sum += p*(getChar(str[i]));
      p *= 5;
    }
  return sum;
}

int h1(int key){ return key%M;}
int h2(int key){ return 1+(key%(M-1));}

int find(char str[])
{
  long long sum;
  int t, j;

  sum = getKey(str);
  for( j=0; j<M; j++ )
    {
      t = ((h1(sum)) + j * (h2(sum)))%M;
      if( strcmp(str,H[t]) == 0 ) return 1;
      else if( H[t][0] == '\0' )
	return 0;
    }
}

int insert(char str[])
{
  long long sum;
  int t, j;

  sum = getKey(str);
  for( j=0; j<M; j++ )
    {
      t = ((h1(sum)) + j * (h2(sum)))%M;
      if( H[t][0] == '\0' )break;
    }
  strcpy(H[t],str);	
}

int main(){
    int i, n, h;
    char str[L], com[9];
    
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ )
      {
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' )
	  {
	    insert(str);
	  }
	else
	  {
	    if (find(str))
	      {
		printf("yes\n");
	      }
	    else
	      {
		printf("no\n");
	      }
	  }
      }
    
    return 0;
}



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

using namespace std;

const int mod = (int) (1e9 + 7);
long long dp[101][100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(12);
    int n, k, x;
    cin >> n >> k;
    dp[0][0] = 1;
    long long pref;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        pref = 0;
        for (int j = 0; j <= k; j++) {
            pref += dp[i - 1][j];
            if (j > x) pref -= dp[i - 1][j - x - 1];
            pref %= mod;
            if (pref < 0) pref += mod;
            dp[i][j] = pref;
        }
    }
    cout << dp[n][k] << "\n";
    return 0;
}

Measured memory_bytes: 78336
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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








int main(){
    int n; std::cin >> n;
    std::vector<int> r(n), c(n);
    for(int i(0); i < n; ++i) std::cin >> r[i] >> c[i];
    //dp[i][j] := iからjまでの計算に必要な回数
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    for(int d(1); d < n; ++d){
        for(int i(0), i_len(n - d); i < i_len; ++i){
            int j(i + d);
            dp[i][j] = INF;
            for(int k(i); k < j; ++k){
                chmin(dp[i][j], dp[i][k] + dp[k+1][j] + r[i]*c[k]*c[j]);
            }
        }
    }
    std::cout << dp[0][n-1] << std::endl;
    return 0;
}



Measured memory_bytes: 3160
n=int(input())
a=[0]*n
a=map(int,input().split())
    
z=0
result=0
min=1000000002

for i in a:
    if i<0:
        z+=1
    result+=abs(i)
    if abs(i)<min:
        min=abs(i)

if z%2==1:
    result-=min*2

print(result)

Measured memory_bytes: 17892
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,A,B = inpl()
print(min(A*N,B))


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

#define ii pair<int, int>
#define lli long long int
#define ll pair<lli, lli>
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

lli bigmod = 1000000007;

lli fex(lli b) {
	lli ret;
	if (b == 0)
		return 1;
	ret = fex(b / 2);
	ret = (ret * ret) % bigmod;
	if (b & 1)
		ret = (ret * 2) % bigmod;
	return ret;
}

int main() {
	lli n, c[200005], ans = 0, temp;
	scanf("%lld", &n);
	for (lli i = 0; i < n; i++)
		scanf("%lld", &c[i]);
	sort(c, c + n);
	for (lli i = 0; i < n; i++) {
		temp = ((n - i + 1) * c[i]) % bigmod;
		ans = (ans + temp) % bigmod;
	}
	ans = (ans * fex(n + n - 2)) % bigmod;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

int n;
int m;
int cnt[100001];
int modcnt[100001];

// take r elements from the set of {x, x+m, x+2m,...}
void take(int x, int r) {
  for (int i = x; i < 100001; i += m) {
    if (cnt[i] % 2) {
      --cnt[i];
      if (!--r)
        return;
    }
  }

  for (int i = x; i < 100001; i += m) {
    int t = min(cnt[i], r);
    r -= t;
    cnt[i] -= t;
    if (!r)
      return;
  }
}

int main() {
  scanf(" %d %d", &n, &m);
  REP (i, n) {
    int tmp;
    scanf(" %d", &tmp);
    ++cnt[tmp];
    ++modcnt[tmp % m];
  }

  int ret = 0;
  REP (i, m) {
    int j = (m-i) % m;
    int z = (i == j) ? modcnt[i] / 2 : min(modcnt[i], modcnt[j]);
    if (z > 0) {
      modcnt[i] -= z;
      modcnt[j] -= z;
      ret += z;
      take(i, z);
      take(j, z);
    }
  }

  REP (i, 100001) {
    ret += cnt[i] / 2;
  }
  
  printf("%d\n", ret);
  
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define pb push_back
#define ld long double
#define f first
#define s second
#define in insert
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e18 + 5;
const int mod = 1e9 + 7;
const int  N = 2e5 + 314;
const long double pi = 3.1415926535897932384626433832795;
void solve(){
	int n;
	string s;
	cin>>n>>s;
	int cnt=0, mx = 0;
	for(int i = 0; i < n; i++){
		if(s[i]=='I')cnt++;
		else cnt--;
		mx=max(mx, cnt);
	}
	cout<<mx;
}
signed main(){
	speed;
	int t=1;
	//cin>>t;
	while(t--)solve();
}

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

int main(void){
    int A, B, C;
    cin >> A >> B >> C;

    if( (A==B and C!=A) or
        (A==C and B!=A) or
        (B==C and A!=B)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

}


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; 
#define ordered_set tree < pairs ,  null_type , greater<pairs>,  rb_tree_tag ,  tree_order_statistics_node_update > 
#define ll long long
#define lld long double
#define vc vector<ll>
#define MOD (ll)(1e9 +7)
typedef pair<ll,ll>pairs;
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
    return res;}

int main() {
	// your code goes here
	std::ios::sync_with_stdio(false);
	ll n,i,j,k,l,c,f;
	string s,t;
	cin>>s>>t;
	i=0;n=s.length();c=0;
	while(i<n){if(s[i]!=t[i])c++;i++;}
	cout<<c;
	return 0;
}


Measured memory_bytes: 3860
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long ll;
typedef pair<int,int>ii;
const int N=1000005;

int arr[51],n,p;
ll power(int a){
  ll ret=1;
  for(int i=1;i<=a;i++)
    ret*=2LL;
  return ret;
}
int main()
{
   //freopen("test.in","r",stdin);
   cin>>n>>p;
   int odd=0;
   for(int i=0;i<n;i++)cin>>arr[i],odd+=arr[i]%2;
   if(!odd){
    if(p)cout<<0;
    else cout<<power(n);
   }
   else{
    cout<<power(n-1);
   }
   return 0;
}


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

const int MAX_N = 1e5+2;
int n;
int a[MAX_N];

void solve()
{
	sort(a,a+n);
	int x=a[n-1], y=-x/2;
	for(int i=0;i<n-1;++i){
		if(abs(1.0*x/2-a[i]) < abs(1.0*x/2-y)) y=a[i];
	}
	cout << x << ' ' << y << '\n';
}

int main()
{
	cin >> n;
	for(int i=0;i<n;++i) cin >> a[i];
	solve();
	return 0;
}

Measured memory_bytes: 3948
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

void func(int N){
	int a,b,c,d,e,f,g,h;
	int ans_a,ans_b,ans_c,ans_d;

	for(int i = 0; i < N; i++){
		scanf("%d %d %d %d %d %d %d %d",&a,&b,&c,&d,&e,&f,&g,&h);

		ans_a = a*e-b*f-c*g-d*h;
		ans_b = a*f+b*e+c*h-d*g;
		ans_c = a*g-b*h+c*e+d*f;
		ans_d = a*h+b*g-c*f+d*e;

		printf("%d %d %d %d\n",ans_a,ans_b,ans_c,ans_d);
	}
}

int main(){

	int N;
	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func(N);
	}

    return 0;
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int N, W;
    cin >> N >> W;
    int w[N], v[N];
    int w_min = pow(10, 9);
    rep(i, N) {
        cin >> w[i] >> v[i];
        w_min = min(w_min, w[i]);
    }

    vector<vector<int>> vec(4);
    rep(i, N) { vec[w[i] - w_min].push_back(v[i]); }
    sort(vec[0].rbegin(), vec[0].rend());
    sort(vec[1].rbegin(), vec[1].rend());
    sort(vec[2].rbegin(), vec[2].rend());
    sort(vec[3].rbegin(), vec[3].rend());

    vector<ll> sum[4];
    rep(l0, 4) {
        ll temp = 0;
        sum[l0].push_back(temp);
        rep(l1, vec[l0].size()) {
            temp += vec[l0][l1];
            sum[l0].push_back(temp);
            // cout << temp << ",";
        }
        // cout << endl;
    }

    ll ans = 0;
    rep(l0, sum[0].size()) {
        rep(l1, sum[1].size()) {
            rep(l2, sum[2].size()) {
                rep(l3, sum[3].size()) {
                    ll weight = 0;
                    weight += l0 * w_min;
                    weight += l1 * (w_min + 1);
                    weight += l2 * (w_min + 2);
                    weight += l3 * (w_min + 3);

                    if (weight > W) {
                        continue;
                    }

                    ll v_now =
                        sum[0][l0] + sum[1][l1] + sum[2][l2] + sum[3][l3];
                    // cout << l0 << "," << l1 << "," << l2 << "," << l3 <<
                    // endl;
                    ans = max(ans, v_now);
                }
            }
        }
    }

    cout << ans << endl;
}
template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    var n = readLine()!!.toInt()
    val map = mutableMapOf<String, Int>()
    map["AC"] = 0
    map["WA"] = 0
    map["TLE"] = 0
    map["RE"] = 0
    repeat(n) {
        val s = readLine()!!
        map[s] = map[s]!! + 1
    }
    println("AC x ${map["AC"]}")
    println("WA x ${map["WA"]}")
    println("TLE x ${map["TLE"]}")
    println("RE x ${map["RE"]}")
}


Measured memory_bytes: 57968
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#define INF 1<<28
#define F first
#define S second
using namespace std;

typedef pair < int, int > P;
vector < P > v[5];
int sx, sy, gx, gy;
int memo[5][5][1111];
 
int dist(P a, P b){
  return abs(a.F - b.F) + abs(a.S - b.S);
}
 
 
int solve(int cnt, int now, int idx){
  
  if(cnt == 4) return dist(v[now][idx], P(gx, gy));
  if(~memo[cnt][now][idx]) return memo[cnt][now][idx];
  
  int ans = INF, next = (now+1)%5, cost;
  for(int i=0;i<v[next].size();i++){
    cost = cnt?dist(v[now][idx], v[next][i]):dist(P(sx, sy), v[next][i]);
    ans = min(ans, solve(cnt+1, next, i) + cost);
  }
  
  return memo[cnt][now][idx] = ans;
}
  
int main(){
  
  int w, h;
  char c;
  
  while(scanf("%d %d", &w, &h), w){
     
    for(int i=0;i<5;i++) v[i].clear();
     
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	scanf(" %c", &c);
	if(c == '.') continue;
	else if(c == 'S') sx = j, sy = i;
	else if(c == 'G') gx = j, gy = i;
	else v[c-'1'].push_back( P(j,i) );
      }
    }
     
    int a, b = INF;
    memset(memo, -1, sizeof(memo));
    for(int i=0;i<5;i++) if(b > solve(0,i,0)) a = i+1, b = solve(0,i,0);
  
    b == INF?puts("NA"):printf("%d %d\n", a, b);
  
  }
}

Measured memory_bytes: 1192
n,W = map(int,input().split())

dp = [[[0]*(3*n+1) for _ in range(n)] for _ in range(n)]

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*(j+1)+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

Measured memory_bytes: 37996
#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  
#include <numeric>
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define endl '\n'
using ll = long long;
 
const int precision = 3;
const int modulo =  1000000007; // 10^9 + 7
const ll lmodulo =  1000000007; // 10^9 + 7
 
const double EPS = 1e-9;
const ll inf = 1e18;

void solve () {
	int n, W;  cin >> n >> W;
	vector<int> weight(n), value(n);
	
	for (auto i = 0; i < n; ++i) {
		cin >> weight[i] >> value[i];
	}

	int maxVal = accumulate(value.begin(), value.end(), 0);

	vector<vector<ll>> dp(2, vector<ll>(maxVal + 1, inf));
	dp[0][0] = 0;

	for (auto i = 1; i <= n; ++i) {
		const auto & w = weight[i - 1];
		const auto & cv = value[i - 1];
		auto cur = i % 2;
		auto prev = (i - 1) % 2;
		for (int v = maxVal; v >= 0; --v) {
			dp[cur][v] = dp[prev][v];
			if (v - cv >= 0) {
				dp[cur][v] = min(dp[cur][v], dp[prev][v - cv] + w);
			}
		}
	}

	int ret = 0;
	for (int i = 0; i<= maxVal; ++i) {
		if(dp[n % 2][i] <= W) {
			ret = max(ret, i);
		}
	}
	cout << ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(precision);
  cout.setf(ios_base::fixed);
  solve();
  return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int next_lunlun(int F){
    vector<int> X;
    if(F<10)return F+1;
    while(F>0){
        X.push_back(F%10);
        F/=10;
    }
    REP(i,X.size()){
        if(i==X.size()-1){
            if(X[i]==9){
                REP(j,X.size()){
                    X[j]=0;
                }
                X.push_back(1);
            }else{
                X[i]+=1;
                RREP(j,i){
                    X[j]=max(0ll,X[j+1]-1);
                }
            }
            break;
        }
        
        if(X[i]!=9 && abs(X[i]+1 - X[i+1])<=1){
            X[i]+=1;
            RREP(j,i){
                X[j]=max(0ll,X[j+1]-1);
            }
            break;
        }
    }
    
    int R=0;
    RREP(i,X.size()){
        R*=10;
        R+=X[i];
    }
    return R;
}


signed main(void){
    int K;
    cin >> K;
    int F=0;
    REP(i,K){
        F = next_lunlun(F);
        //cout << F << endl;
    }
    cout << F << endl;
    return 0;
}



Measured memory_bytes: 256
// Problem : E - Active Infants
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//QWsin
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

typedef long long ll;
const int INF=1<<30;

const int maxn=2000+10;
int num[maxn],id[maxn];
int cmp(int a,int b){
	return num[a]>num[b];
}
ll dp[maxn][maxn];
int main()
{
	int n;cin>>n;
	rep(i,1,n) cin>>num[i];
	rep(i,1,n) id[i]=i;
	sort(id+1,id+n+1,cmp);
	
	memset(dp,-2,sizeof dp);
	dp[0][0]=0;
	ll ans=0;
	rep(i,1,n){
		rep(j,0,i){//左边的数量
			//放左边
			if(j  >0)dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1ll*num[id[i]]*abs(id[i]-j));
			if(i-j>0)dp[i][j]=max(dp[i][j],dp[i-1][j]+1ll*num[id[i]]*abs(id[i]-(n-(i-j)+1)));
			if(i==n) ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

#define  fastio         ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define  foo(i,a,n)     for(ll i = (a); i <= n; i++)
#define  frr(i,a,n)     for(ll i = (a); i >= n; i--)
#define  fo(i,n)        for(ll i = 0; i < n; i++)
#define  all(x)         (x).begin(),(x).end()
#define  mset(x,val)    memset(x,val,sizeof(x))
#define  newl           cout<<"\n"
#define  pb             push_back
#define  mp             make_pair
#define  s              second
#define  f              first
#define  dline          cerr<<"///REACHED///\n";
#define  deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define  deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define  deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef  long long             ll;
typedef  long double           ld;
typedef  pair<ll,ll>           pll;
typedef  vector<ll>            vll;
typedef  vector<pll>           vpll;

const ll   MOD   =  1e+9+7;
const ll   INF   =  0x7f7f7f7f7f7f7f7f;
const int  INFi  =  0x7f7f7f7f;
const ll   MAXN  =  1e+5+7;

vll adj[MAXN];ll visit[MAXN]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

//<<-----Declare Variable Here------->>//
int q=1;
ll n;
ll a,b,v,w,t;
//<<-----Implement Functions Here---->>//


//<<-----Start of Main--------------->>//
void MAIN(){
		cin>>a>>v>>b>>w>>t;
		
		
		ll d = abs(b - a);
		
		if(w>=v)cout<<"NO"<<endl;
		else
		{
			ll v1 = (v-w);
			ll t1 = d/v1;if(d%v1!=0)t1++;
			if(t1<=t)cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}


}

int main(){
	fastio;randomINIT;

	//cin>>t;
	while(q--){
		MAIN();
	}

   
}

Measured memory_bytes: 5948
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


N = int(input())
S = input()

cnt = 0
ans = int(1e9)
for c in S:
    if c == "E":
        cnt += 1

for c in S:
    if c == "E":
        cnt -= 1
        ans = min(ans, cnt)
    else:
        ans = min(ans, cnt)
        cnt += 1
print(ans)


Measured memory_bytes: 42336
a = input()
count = 0
mojiretu_01 = ""
mojiretu_10 = ""

for i in range(len(a)):
    if i % 2 == 0:
        mojiretu_01 += "0"
        mojiretu_10 += "1"
    else:
        mojiretu_01 += "1"
        mojiretu_10 += "0"
count01 = 0
count10 = 0

for i in range(len(a)):
    if a[i] != mojiretu_01[i]:
        count01 += 1
    else:
        count10 += 1

print(min(count01, count10))

Measured memory_bytes: 3316
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod = 1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int rd(int x, int c)
{
	return (x&((1<<c)-1))|((x>>c+1)<<c);
}
int ad(int x, int c, int b)
{
	return (x&((1<<c)-1))|(b<<c)|((x>>c)<<c+1);
}
int n, a, b;
vector<int> solve(int n, int a, int b)
{
	assert(__builtin_popcount(a)%2!=__builtin_popcount(b)%2);
	
	vector<int> ret;
	if (n==1)
	{
		ret.PB(a);
		ret.PB(b);
		return ret;
	}
	int c = -1, t = -1;
	for (int i=0; i<n; i++)
	{
		if (((a>>i)&1)!=((b>>i)&1))
		{
			if (c==-1)
			{
				c = i;
				t = ((a>>i)&1);
			}
		}
	}
	assert(c!=-1&&t>=0&&t<=1);
	vector<int> v0 = solve(n-1, rd(a, c), rd(a, c)^1);
	vector<int> v1 = solve(n-1, rd(a, c)^1, rd(b, c));
	for (auto x : v0) ret.PB(ad(x, c, t));
	for (auto x : v1) ret.PB(ad(x, c, t^1));
	return ret;
}
int main()
{
	cin>>n>>a>>b;
	int cnta = __builtin_popcount(a);
	int cntb = __builtin_popcount(b);
	if ((cnta-cntb)%2==0) puts("NO");
	else
	{
		puts("YES");
		vector<int> ans = solve(n, a, b);
//		for (auto x : ans) {for (int i=0; i<n; i++) putchar('0'+((x>>i)&1)); putchar(' ');}
		for (auto x : ans) printf("%d ", x);
	}
	return 0;
}


Measured memory_bytes: 1628
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]A - Round Up the Mean
            var line = ReadLine();
            double a = line[0];
            double b = line[1];
            double d = (a + b) / 2;

            Console.WriteLine(Math.Ceiling(d));
        }

        static List<int> ReadLine()
        {
            var line = Console.ReadLine().TrimEnd();
            var array = line.Split(' ');
            var numbers = new List<int>();

            foreach (var s in array)
            {
                int num = int.Parse(s);
                numbers.Add(num);
            }

            return numbers;
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;

ll mod=1e9+7;

int main(){
	int n; cin >> n;
	vector<int> t(n),a(n);
	ll ans=1;
	for(int i=0;i<n;i++){
		cin >> t[i];
	}
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	if(t[n-1]!=a[0]){
		cout << 0 << endl;
		return 0;
	}
	else{
		for(int i=1;i<n-1;i++){
			if(t[i]<t[i-1]||a[i]>a[i-1]){
				cout << 0 << endl;
				return 0;
			}
			if(t[i]>t[i-1]&&a[i]>a[i+1]&&t[i]!=a[i]){
				cout << 0 << endl;
				return 0;
			}
			if(t[i]==t[i-1]&&a[i]>a[i+1]&&a[i]>t[i]){
				cout << 0 << endl;
				return 0;
			}
			if(a[i]==a[i+1]&&t[i]>t[i-1]&&a[i]<t[i]){
				cout << 0 << endl;
				return 0;
			}
			if(t[i]==t[i-1]&&a[i]==a[i+1]){
				ans*=min(t[i],a[i]);
				ans%=mod;
			}
		}
	}
	cout << ans << endl;
}

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

int main(){
    int N, ans=0;    
    cin >> N;
    vector<int> p(N);

    for(int i=0; i<N; i++)
	cin >> p[i];

    for(int i=0; i<N-2; i++){
	if(p[i]<p[i+1] && p[i+1]<p[i+2])
	    ans++;
	else if(p[i]>p[i+1] && p[i+1]>p[i+2])
	    ans++;		    
    }
    
    
    cout << ans << "\n";
}




Measured memory_bytes: 256
#!/usr/bin/env python
from collections import defaultdict, deque
import math
from math import factorial
import fractions
import re

BIGNUM = 10 ** 9 + 7

def main():
    #N, x = map(int, input().split())
    #As = list(map(int, input().split()))
    N = int(input())
    As = list(map(int, input().split()))
    As.append(100000)

    magic_num = 0
    prev = None
    seq = 1
    for a in As:
        if prev is not None:
            if prev == a:
                seq += 1
            else:
                if seq > 1:
                    magic_num += seq // 2
                seq = 1
        prev = a

    print(magic_num)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5056
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
  #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl "\n"
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
    string s;
    cin>>s;
    for(int i=0;i<(int)s.size();i++){
	 	s[i]=(s[i]=='1'?s[i]='9':s[i]='1');
	}
	cout<<s<<endl;
}
int32_t main(){
   IOS;
   solve();
   //debug();
  #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
  #endif	
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1
    if d[a] > 1:
        t[a] = False

A = sorted(set(A))
for a in A:
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))


Measured memory_bytes: 52032
#include <iostream>
using namespace std;
int main(void){
   int n, pm1, pe1, pj1;
   while(true){
       cin >> n;
       if(n == 0){
           break;
       }
       for(int i = 0; i < n; i++){
           cin >> pm1 >> pe1 >> pj1;
           if(pm1==100 || pe1==100 || pj1==100){
               cout << "A" << endl;
           }
           else if((pm1+pe1)/2 >= 90){
               cout << "A" << endl;
           }
           else if((pm1+pe1+pj1)/3 >= 80){
               cout << "A" << endl;
           }
           else if((pm1+pe1+pj1)/3 >= 70){
               cout << "B" << endl;
           }
           else if((pm1+pe1+pj1)/3 >= 50 && (pm1>=80 || pe1>=80)){
               cout << "B" << endl;
           }
           else{
               cout << "C" << endl;
           }
       }
   }
}


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

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxm = 3e5+35;
const int maxn = 2e3+23;
int main(){
    int a,b,k; cin >> k >> a >> b;
    for(int i = a;i <= b; ++i){
        if(i%k == 0) return puts("OK"),0;
    }
    puts("NG");
    return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int D_MAX_V=10000;
struct D_wolf{
	int t,c,r;
	D_wolf(){}
	D_wolf(int t1,int c1,int r1){t=t1;c=c1;r=r1;}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];
void add_edge(int a,int b,int c){
	D_G[a].push_back(D_wolf(b,c,D_G[b].size()));
	D_G[b].push_back(D_wolf(a,0,D_G[a].size()-1));
}
void D_bfs(int a){
	for(int i=0;i<D_MAX_V;i++)D_level[i]=-1;
	D_level[a]=0;
	queue<int>Q;
	Q.push(a);
	while(Q.size()){
		int at=Q.front();Q.pop();
		for(int i=0;i<D_G[at].size();i++){
			if(D_G[at][i].c==0)continue;
			if(D_level[D_G[at][i].t]>=0)continue;
			D_level[D_G[at][i].t]=D_level[at]+1;
			Q.push(D_G[at][i].t);
		}
	}
}
int D_dfs(int a,int b,int c){
	if(a==b)return c;
	for(;D_iter[a]<D_G[a].size();D_iter[a]++){
		if(D_level[a]<D_level[D_G[a][D_iter[a]].t]&&D_G[a][D_iter[a]].c>0){
			int f=D_dfs(D_G[a][D_iter[a]].t,b,min(c,D_G[a][D_iter[a]].c));
			if(f){
				D_G[a][D_iter[a]].c-=f;
				D_G[D_G[a][D_iter[a]].t][D_G[a][D_iter[a]].r].c+=f;
				return f;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int ret=0;
	while(1){
		D_bfs(s);
		for(int i=0;i<D_MAX_V;i++)D_iter[i]=0;
		int f=D_dfs(s,t,99999999);
		if(f==0)return ret;
		ret+=f;
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q,r;scanf("%d%d%d",&p,&q,&r);
		add_edge(p,q,r);
	}
	printf("%d\n",max_flow(0,a-1));
}

Measured memory_bytes: 1392
def main():
    N, M = map(int, input().split())
    INF = float('inf')
    
    L = 2 ** N
    dp = [INF] * L
    dp_next = [INF] * L
    
    nums = [2 ** i for i in range(N)]
    
    for i in range(M):
        a, b = map(int, input().split())
        b = sum([nums[c-1] for c in list(map(int, input().split()))])            
    
        dp[b] = min(dp[b], a)
        for j in range(L):
            n = j | b
            dp_next[n] = min(dp[n], dp_next[n], dp[j]+a)
        
        for j in range(L):
            dp[j] = dp_next[j]
            
    if dp[-1] == INF: print(-1)
    else: print(dp[-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 3284
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

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

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
string data[100];
int main(){
	int n,q;
	cin>>n>>q;
	//memset(data, '0', sizeof(data));
	//int tmp_min =INF;
	for(int i =0;i < n;i++){
		int x;
		string str;
		cin>>x>>str;
		data[x]=str;
		//tmp_min =min(tmp_min,x);
	}

	string ans ="";
	for(int i =0;i <=q;i++){
		if(data[i]!="\0"){
			ans =data[i];
		}
	}
	if(ans=="\0"){
		ans ="kogakubu10gokan";
	}
	cout <<ans<<endl;
	return 0;
}

Measured memory_bytes: 1208
#include <stdio.h>
main()
{
	int a;
	int h;
	int m;
	int s;
	
	scanf("%d",&a);
	h=a/3600;
	m=(a-3600*h)/60;
	s=a-3600*h-60*m;
	
	printf ("%d:",h);
	printf ("%d:",m);
	printf ("%d\n",s);
	return 0;
}

Measured memory_bytes: 592
NIL = -1
class Node:
  def __init__(self):
    self.parent = NIL
    self.left = NIL
    self.right = NIL
    self.type = NIL
    self.depth = NIL
    self.sibling = NIL
    self.degree = NIL
    self.height = NIL

def setHeight(u):
  h1 = h2 = 0
  if T[u].right != NIL:
    h1 = setHeight(T[u].right) + 1
  if T[u].left != NIL:
    h2 = setHeight(T[u].left) + 1
  if h1 == h2 == NIL:
    return NIL
  else:
    return max(h1, h2)

def getDepth(u):
  d = 0
  while T[u].parent != NIL:
    u = T[u].parent
    d += 1
  return d

def getSibling(u):
  if T[u].parent == NIL:
    return NIL
  if T[T[u].parent].left != u and T[T[u].parent].left != NIL:
    return T[T[u].parent].left
  if T[T[u].parent].right != u and T[T[u].parent].right != NIL:
    return T[T[u].parent].right
  return NIL

def getDegree(u):
  deg = 0
  if T[u].left != NIL:
    deg += 1
  if T[u].right != NIL:
    deg += 1
  return deg

n = int(input())
T = [0]*n
for i in range(n):
  T[i] = Node()
for i in range(n):
  id, l, r = map(int,input().split())
  T[id].left = l
  T[id].right = r

for i in range(n):
  if T[i].left != NIL:
    T[T[i].left].parent = i
  if T[i].right != NIL:
    T[T[i].right].parent = i

for i in range(n):
  if T[i].parent == NIL:
    T[i].type = 'root'
  elif T[i].parent != NIL and (T[i].left != NIL or T[i].right != NIL):
    T[i].type = 'internal node'
  else:
    T[i].type = 'leaf'

for i in range(n):
  T[i].depth = getDepth(i)
  T[i].sibling = getSibling(i)
  T[i].degree = getDegree(i)
  T[i].height = setHeight(i)

for i in range(n):
  print('node ',i,': parent = ',T[i].parent,', sibling = ',T[i].sibling,', degree = ',T[i].degree,', depth = ',T[i].depth,', height = ',T[i].height,', ',T[i].type,sep = '')



















Measured memory_bytes: 5648
#include <iostream>

int main(){
    int n, dp[100010][3], input[100010][3];
    std::cin >> n;
    for(int i = 0; i < n; i++){
        std::cin >> input[i][0] >> input[i][1] >> input[i][2];
        dp[i][0] = dp[i][1] = dp[i][2] = 0;
    }
    dp[0][0] = input[0][0];
    dp[0][1] = input[0][1];
    dp[0][2] = input[0][2];
    for(int i = 1; i < n; i++){
        dp[i][0] = std::max(dp[i-1][1], dp[i-1][2]) + input[i][0];
        dp[i][1] = std::max(dp[i-1][0], dp[i-1][2]) + input[i][1];
        dp[i][2] = std::max(dp[i-1][0], dp[i-1][1]) + input[i][2];
    }
    int max = 0;
    for(int i = 0; i < 3; i++){
        max = std::max(max, dp[n-1][i]);
    }
    std::cout << max << std::endl;
}


Measured memory_bytes: 2560
#include<iostream>
using namespace std;
int n,m,k,a[11][1010],b[11],ans=999999,fl;
int check(int x)
{
    int i,q;
    q=b[1];
    if(q>k) return 0;
    for(i=0;i<n-1;i++)
    {
        if((x&(1<<i))!=0) q=0;
        q+=b[i+2];
        if(q>k) return 0;
    }
    return 1;
}
int main()
{
    char s;
    int i,j,now,u;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
     {
         cin>>s;
         a[i][j]=s-'0';
     }
    for(i=0;i<(1<<n-1);i++)
    {
        now=0;
        for(j=1;j<=n;j++) b[j]=0;
        fl=0;
        for(j=0;j<n-1;j++) if((i&(1<<j))!=0) now++;
        for(j=1;j<=m;j++) 
        {
            for(u=1;u<=n;u++) b[u]+=a[u][j];
            if(check(i)==0) 
            {
                for(u=1;u<=n;u++) b[u]=a[u][j];
                if(check(i)==0) fl=1;
                now++;
            }
        }
        if(fl==0) ans=min(ans,now);
    }
    cout<<ans;
    cin>>i;
}


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



int main() {

    int N;
    int A[100001];
    cin >> N;
    for (int i = 0; i < N + 1; i++) cin >> A[i];
    //今の深さの点の数
    long long now = 1;
    //int mae = 0;
    long long ans = 0;
    //末端の数
    long long sum = 0;
    //分岐した回数
    long long route = 1;
    
    for (int i = 0; i < N + 1; i++)
    {
        sum += A[i];
    }
    int s = sum;
    //cout << sum << endl;
    for (int i = 0; i < N + 1; i++)
    {
        /*
        //cout << now <<route<< endl;
        ans += now;
        //cout << now<< " ";
        now -= A[i];
        sum -= A[i];
        now = min(now * 2, sum);

        //cout << now << endl;
        if (i != N && now <= 0)
        {
            cout << -1 << endl;
            return 0;
        }
        else if (i == N && now != 0)
        {
            cout << -1 << endl;
            return 0;
        }*/

        
        ans += now;
        now -= A[i];
        sum -= A[i];
        //できるだけ早く分岐しておく
        long long a = now;
        /*
        //now 2倍ルート
        if (route + a < sum)
        {
            //新しい分岐はa個
            now += a;
            route += a;
        }
        //nowがそれ以降の和になるルート
        else
        {
            //基本的にrouteは1+枝の数
            //ある瞬間のroute-1がそれまでの葉の数と等しければいい
            //分岐した数だけ葉が増える、route+=nはA[i]=nを意味する
            //つまりrouteはそれまでのA[i]の和、route= sum-sumA[i]
            //now-A[i]（分岐＝葉の数）=葉以外の数、
            //葉の枚数＋全部の和-分岐の数（）

            //now=sum-sumA[i-1]なら、

            //新しい分岐はsum-route個
            //（最終的な道の数）ー（今の道の数）をnow（今の道の数）に足して（最終的な道の数）にする
            //now += sum - route;
            now = s;
            route += sum - route;
        }*/
        now = min(a * 2, sum);

        if (i != N && now <= 0)
        {
            cout << -1 << endl;
            return 0;
        }
        else if (i == N && now != 0)
        {
            cout << -1 << endl;
            return 0;
        }


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

Measured memory_bytes: 4000
package main

import "fmt"

func main() {
	var h, w, k int
	count := 0

	// 標準入力から3つ値を受け取る
	fmt.Scan(&h, &w, &k)

	// 行列を保持するスライス
	c := make([]string, h, h)

	// 拡張for文(foreach)
	// cの各要素に対して標準入力の値を格納
	for i := range c {
		fmt.Scan(&c[i])
	}

	// 各行のステイ・赤を決める数値
	for i := 0; i < 1<<h; i++ {
		// 各列のステイ・赤を決める数値
		for l := 0; l < 1<<w; l++ {
			// 数えた黒の数を入れる変数sharpNum
			sharpNum := countSharp(c, i, l)

			if sharpNum == k {
				count++
			}
		}
	}

	fmt.Println(count)
}

// iは該当行を変更させるかどうかを確認する指標。2進数表記で対象行が1なら赤に変える、0ならそのまま
// lは該当列を変更させるかどうかを確認する指標。2進数表記で対象列が1なら赤に変える、0ならそのまま
func countSharp(c []string, i, l int) int {
	sharpNum := 0

	for p := 0; p < len(c); p++ {
		// 行の変更有無を持つ数値の該当行の値を調べる
		if (i >> p & 1) == 1 {
			continue //赤なので、すべて黒＝後の処理は必要ない
		}

		// 黒のまま残るか、残らないかチェック→残る場合は黒としてカウントする
		for q := 0; q < len(c[0]); q++ {
			if (l >> q & 1) == 1 {
				continue
			}

			if c[p][q] == '#' {
				sharpNum++
			}
		}
	}

	return sharpNum
}


Measured memory_bytes: 1768
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		long x = scan.nextLong();
		int uresi500 = 1000;
		int uresi5 = 5;
		int count500 = 0;
		int count5 = 0;


		while(x >= 500) {
			x -= 500;
			count500++;
		}

		while(x >= 5){
			x -= 5;
			count5++;
		}

		int re = count500*uresi500 + count5*uresi5;

		System.out.println(re);

		scan.close();

	}

}


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

#define ll long long
#define mod 1000000007

using namespace std;

bool prime[1010];
ll cnt[1010];

int main()
{
    int n;
    cin >> n;

    memset(prime,true,1010*sizeof(prime[0]));

    for(int i=2;i<1010;i++)
    {
        if(prime[i])
        {
            for(int j=2*i;j<1010;j+=i)
                prime[j] = false;
        }
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=i;j++)
        {
            int temp = i;

            while(prime[j] && temp%j == 0)
            {
                cnt[j]++;
                temp /= j;
            }
        }
    }

    ll ans = 1;

    for(int i=2;i<=n;i++)
    {
        if(prime[i])
        {
            cnt[i]++;
            ans = (ans%mod * cnt[i]%mod)%mod;
        }
    }

    cout << ans << endl;
}

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

int w, h;
char tiles[20][21];

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

bool isRegion(int x, int y){
    return x >= 0 && x < w && y >= 0 && y < h;
}

int main(){
    while(1){
        cin >> w >> h;
        if(!w && !h) break;
        
        int sx, sy;
        for(int i = 0; i < h; i++){
            cin >> tiles[i];
            
            auto j = find(tiles[i], tiles[i]+w, '@');
            if(j != tiles[i] + w){
                sx = j - tiles[i]; sy = i;
            }
        }
        
        int cnt = 0;
        queue<pair<int, int> > q;
        q.push(make_pair(sx, sy));
        while(!q.empty()){
            cnt++;
            int x = q.front().first, y = q.front().second;
            q.pop();
            
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i], ny = y + dy[i];
                
                if(isRegion(nx, ny) && tiles[ny][nx] == '.'){
                    tiles[ny][nx] = '#';
                    q.push(make_pair(nx, ny));
                }
            }
        }
        cout << cnt << endl;
        
    }
}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
long long n,a[100010],dp[100010];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    dp[1]=0;
    dp[2]=abs(a[1]-a[2]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    printf("%lld",dp[n]);
    return 0;
}


Measured memory_bytes: 5352
s = gets.chomp
c = s.reverse.each_char.map(&:to_i)
dd = 0

ans = 0

c.each_with_index do |f, i|
  if f + dd < 5 || ((f + dd) == 5 && (!c[i+1] || c[i+1] < 5))
    ans += (f + dd)
    dd = 0
  else
    ans += 10 - (f + dd)
    dd = 1
  end
end

puts ans + dd


Measured memory_bytes: 14468
from math import factorial
from itertools import permutations
def main():
    n = int(input())
    town_coor = []
    for _ in range(n):
        town_coor.append(tuple(map(int, input().split())))

    dists = [[0]*n for _ in range(n)]
    for j1 in range(n):
        for j2 in range(n):
            dists[j1][j2] = ((town_coor[j1][0] - town_coor[j2][0])**2 + (town_coor[j1][1] - town_coor[j2][1])**2)**0.5


    towns = [i for i in range(n)]
    roads = permutations(towns, n)
    sum_roads = 0
    for road in roads:
        sum_road = 0
        for i1 in range(n-1):
            sum_road += dists[road[i1]][road[i1+1]]
        sum_roads += sum_road
    print(sum_roads / factorial(n))

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188