akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
//#include<cstdio>
using namespace std;
int main(){
    int l;
    cin >> l;
    string str;
    cin >> str;
    int ct[26];
    int i;
    for (i=0; i<26; i++){
        ct[i]=0;
    }
    for(i=0; i<l  ;i++){
        if(str[i]=='a'){
            ct[0]=ct[0]+1;
        }
        if(str[i]=='b'){
            ct[1]=ct[1]+1;
        }
        if(str[i]=='c'){
            ct[2]=ct[2]+1;
        }
        if(str[i]=='d'){
            ct[3]=ct[3]+1;
        }
        if(str[i]=='e'){
            ct[4]=ct[4]+1;
        }
        if(str[i]=='f'){
            ct[5]=ct[5]+1;
        }
        if(str[i]=='g'){
            ct[6]=ct[6]+1;
        }
        if(str[i]=='h'){
            ct[7]=ct[7]+1;
        }
        if(str[i]=='i'){
            ct[8]=ct[8]+1;
        }
        if(str[i]=='j'){
            ct[9]=ct[9]+1;
        }
        if(str[i]=='k'){
            ct[10]=ct[10]+1;
        }
        if(str[i]=='l'){
            ct[11]=ct[11]+1;
        }
        if(str[i]=='m'){
            ct[12]=ct[12]+1;
        }
        if(str[i]=='n'){
            ct[13]=ct[13]+1;
        }
        if(str[i]=='o'){
            ct[14]=ct[14]+1;
        }
        if(str[i]=='p'){
            ct[15]=ct[15]+1;
        }
        if(str[i]=='q'){
            ct[16]=ct[16]+1;
        }
        if(str[i]=='r'){
            ct[17]=ct[17]+1;
        }
        if(str[i]=='s'){
            ct[18]=ct[18]+1;
        }
        if(str[i]=='t'){
            ct[19]=ct[19]+1;
        }
        if(str[i]=='u'){
            ct[20]=ct[20]+1;
        }
        if(str[i]=='v'){
            ct[21]=ct[21]+1;
        }
        if(str[i]=='w'){
            ct[22]=ct[22]+1;
        }
        if(str[i]=='x'){
            ct[23]=ct[23]+1;
        }
        if(str[i]=='y'){
            ct[24]=ct[24]+1;
        }
        if(str[i]=='z'){
            ct[25]=ct[25]+1;
        }
    }
    long long x;
    x  = 1;
    for(i=0;i<26;i++){
        //cout << ct[i]+1  << endl;
        x = (x * (long long)(ct[i]+1)) % (long long)1000000007 ;
    }
    x = x -1;
    cout << x  << endl;
    return 0;
}

Measured memory_bytes: 512
#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:

int p[100010];

// Description: 素集合を管理するデータ構造
// TimeComplexity: 初期化$\mathcal{O}(n)$ 更新$\mathcal{O}(\log n)$
// Verifyed: AOJ DSL_1_A

struct Union_find {
	Union_find(int n) {data.assign(n, -1);}
	int find(int x) {return (data[x] < 0) ? x : data[x] = find(data[x]);}
	void unite(int a, int b) {
		a = find(a), b = find(b);
		if (a != b) {
			if (data[a] < data[b]) swap(a, b);
			data[a] += data[b], data[b] = a;
		}
	}
	bool same(int a, int b) {return find(a) == find(b);}
	int size(int x) {return -data[x];}
	vector<int> data;
};



int main(void){
	int n,m;
	cin >> n >> m;

	rep(i,n) cin >> p[i],p[i]--;

	Union_find uf(n);

	rep(i,m){
		int x,y;
		cin >> x >> y;
		x--,y--;
		uf.unite(x,y);
	}


	int ans = 0;
	rep(i,n) if(uf.same(i,p[i])) ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(){
  int N;
  scanf("%d", &N);

  int s=0;
  int m=N;
  for(int i=0; i<10; i++){
    s+=m%10;
    m/=10;
  }

  if(N%s==0){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int n, cnt, G[15], L[15];
int main()
{
    cin >> n;
    for(int w = 0; w < n; w++)
    {
        cnt = 0;
        for(int i = 0; i < 15; i++) L[i] = 15;
        for(int i = 1; i <= 10; i++)
        {
            cin >> G[i];
            if(G[i] <= L[cnt]) L[++cnt] = G[i];
            else
            {
                for(int j = cnt - 1; j >= 0; j--)
                    if(G[i] < L[j]) {L[j + 1] = G[i]; break;}
            }
        }
        cout << (cnt > 2 ? "NO" : "YES") << endl;
    }
    return 0;
}



Measured memory_bytes: 3056
n,m = gets.split.map(&:to_i)
ar = []
ans = 0
for i in 0..n-1 do
  a = gets.split.map(&:to_i)
  b = a[0]
  for j in 1..b do
    
  ar << a[j]
  end
end
for k in 1..30 do
  c = ar.count(k)
  ans += 1  if c == n
end
p ans

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    int a, b;
    cin >> a >> b;
    bool flg = false;
    for(int i=1; i<4; i++){
        if(a * b * i % 2 == 1) flg = true;
    }
    if(flg) out("Yes");
    else out("No");
}

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, L: "List[int]"):
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                s = L[i] + L[j] + L[k]
                m = max(L[i], L[j], L[k])
                if L[i] != L[j] and L[j] != L[k] and L[k] != L[i] and m < s - m:
                    ret += 1
                    #print(i, j, k)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


Measured memory_bytes: 68276
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int sum0 = 0;
    int sum1 = 0;
    for(int i = 0; i < n; ++i){
        if(s[i] == '1') sum1++;
        else sum0++;
    }
    cout << 2 * min(sum0, sum1) << endl;
	return 0;
} 	

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

int main(void){
    int t[5];
    int T[5];
    int d[5];
    int maxd = 0;
    int sum = 0;
   for(int i = 0; i < 5; i++){
        cin >> t[i];
    }
   for(int i = 0; i < 5; i++){
        T[i] = ((t[i] - 1) / 10 + 1) * 10;
    }
    for(int i = 0; i < 5; i++){
        d[i] = T[i] - t[i];
    }
    for(int i = 0; i < 5; i++){
        if(d[i] > maxd){
            maxd = d[i];
        }
    }
    for(int i = 0; i < 5; i++){
        sum += T[i];
    }
    cout << sum - maxd;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define mxn 100010
using namespace std;

ll a[mxn],n;

int main()
{
	scanf("%lld",&n);ll ans=0;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
	{
		ll cnt=a[i];
		while(i<n && a[i+1]!=0)	cnt+=a[i+1],i++;
		ans+=cnt/2;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 896
from itertools import combinations as comb
n, k = map(int, input().split())
ns = list(map(int, input().split()))
res = float('inf')
perms = list(range(1,n))
for p in comb(perms, k-1):
    res_tmp = 0
    tmp_max = 0
    p = [0] + list(p)
    for i in range(n):
        if i in p and ns[i] <= tmp_max:
            res_tmp += tmp_max - ns[i] + 1
            tmp_max = tmp_max + 1
        else:
            tmp_max = max(tmp_max, ns[i])
    res = min(res, res_tmp)
print(res)

Measured memory_bytes: 9164
i = gets.to_i
n = gets.chomp.split.map(&:to_i)
a = n.sort
cnt = 0
n.size.times do |block|
    if n[block] != a[block]
        cnt += 1
    end
end
if cnt == 2 or cnt == 0 then
    puts "YES"
else
    puts "NO"
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S; cin >> S;
  int Q; cin >> Q;
  int now=1;
  string f="";
  string b="";
  for(int i=0;i<Q;i++){
    int T; cin >> T;
    if(T==1){
      now*=-1;
    }
    if(T==2){
      int F; cin >> F;
      string A; cin >> A;
      if(now==1 && F==1){
        f+=A;
      }
      if(now==-1 && F==2){
        f+=A;
      }
      if(now==1 && F==2){
        b+=A;
      }
      if(now==-1 && F==1){
        b+=A;
      }
    }
  }
  string ans="";
  if(now==1){
    if(f.size()>0){
      for(int i=0;i<f.size();i++){
        ans+=f[f.size()-1-i];
      }
    }
    ans+=S;
    ans+=b;
  }
  if(now==-1){
    if(b.size()>0){
      for(int i=0;i<b.size();i++){
        ans+=b[b.size()-1-i];
      }
      for(int i=0;i<S.size();i++){
        ans+=S[S.size()-1-i];
      }
      ans+=f;
    }
  }
  cout << ans << endl;
  return 0;
}
  
        

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	int x[n];
	int y[n];
	for(int i = 0; i < n; i++) {
		cin >> x[i];
		y[i] = x[i];
	}
	sort(y, y + n);
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(x[i] != y[i]) {
			cnt++;
		}
	}
	if(cnt <= 2) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;	
	}
}

Measured memory_bytes: 256
while True:
    a,b,c=input().split()
    a=int(a)
    c=int(c)
    if b=="?":
        break
    if b=="+":
        print(a+c)
    if b=="-":
        print(a-c)
    if b=="*":
        print(a*c)
    if b=="/":
        print(a//c)





Measured memory_bytes: 5592
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>

using namespace std;


int main(void) {

	int n, q;
	string s;

	cin >> n >> q >> s;

	int l[100000], r[100000];

	int num[100000] = {};

	for (int ser = 1; ser <= n - 1; ser++)
	{
		num[ser] = num[ser - 1];

		if (s[ser-1] == 'A'&&s[ser] == 'C') {
			num[ser]++;
		}


		//cout << num[ser] << "\n";
	}

	//cout << sub << "\n";

	for (int que = 0; que < q; que++)
	{
		cin >> l[que] >> r[que];
		
		int lastnum = num[r[que]-1] - num[l[que]-1];

		cout << lastnum << "\n";
	}

	

	return 0;
}

Measured memory_bytes: 2176
n = int(input())
ans = 0

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for i in range(n + 1):
    k = factorization(i)
    for j in k:
        if j[0] == 2:
            if ans < j[1]:
                ans = j[1]
print(2 ** ans)

Measured memory_bytes: 9412
#include "bits/stdc++.h"
#include "math.h"
#include "string.h"
#include "algorithm"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())


int main(){
  
  string s;
  cin>>s;
  if(s=="AAA"||s=="BBB"){
    cout<<"No"<<endl;
  }
  else{
    cout<<"Yes"<<endl;
  }
}


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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n; cin >> n;
  vector<mint> a(n);
  rep(i, n) {
    ll x; cin >> x;
    a[i] = x;
  }

  mint ans = 0;
  a.insert(a.begin(), 0);
  rep(i, n) a[i+1] += a[i];
  for(int i = 1; i <= n; ++i) {
    mint x = a[i]-a[i-1];
    x *= a[n]-a[i];
    ans += x;
  }
  cout << ans.x << endl;
}

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

using namespace std;

int main(int argc, char * argv[]) {
    int64_t N;
    cin >> N;

    int64_t best = N - 1;
    for (int64_t i = 2; i * i <= N; ++i) {
        if (N % i == 0) {
            int64_t steps = (i - 1) + (N / i - 1);
            if (steps < best)
                best = steps;
        }
    }
    cout << best << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void test_case() {
	int n;
	scanf("%d", &n);
	vector<long long> a(n);
	for(int i = 0; i < n; ++i) {
		scanf("%lld", &a[i]);
	}
	char s[n+1];
	scanf("%s", s);
	assert((int) strlen(s) == n);
	vector<long long> base;
	for(int i = n - 1; i >= 0; --i) {
		// if(a[i] == 0) {
			// continue;
		// }
		long long x = a[i];
		for(long long b : base) {
			x = min(x, x^b);
		}
		if(x == 0) {
			continue;
		}
		if(s[i] == '0') {
			base.push_back(x);
		}
		else {
			puts("1");
			return;
		}
	}
	puts("0");
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		test_case();
	}
}


Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
inline void read (int &x) {
    char ch = getchar(); int f = 0; x = 0;
    while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); if (f) x = -x;
} int n, m;
signed main() {
    read (n), read (m);
    printf ("%d\n", n * (n - 1) / 2 + m * (m - 1) / 2);
    return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func PlacingMarbles(nums string) int{
	sum := 0
	for _, num := range nums{
		if string(num) == "1" {
			sum++
		}
	}
	return sum
}

func main(){
	//2. Placing Marbles
	var s string
	fmt.Scan(&s)
	marbles := PlacingMarbles(s)
	fmt.Println(marbles)
}

Measured memory_bytes: 512
fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let n = get_line().parse::<u8>().unwrap();
    for i in 1..10 {
        for j in 1..10 {
            if i * j == n {
                println!("Yes");
                return;
            }
        }
    }
    println!("No");
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll power(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)

//your code here!

int main(void){
    ll N, A, odd=0;
    scanf("%lld", &N);
    rep(i, N) {
        scanf("%lld", &A);
        if(A%2) odd++;
    }
    puts((odd%2) ? "NO":"YES");
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
#include<set>

using namespace std;

#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
#define esta(x,v) (find((v).begin(),(v).end(),(x)) !=  (v).end())
#define index(x,v) (find((v).begin(),(v).end(),(x)) - (v).begin())
#define debug(x) cout << #x << " = "  << x << endl
#define pb push_back
#define mp make_pair

typedef long long tint;
typedef pair<int,int> pint;
typedef pair<tint,tint> ptint;
typedef unsigned long long utint;
typedef long double ldouble;

typedef vector<int> vint;

int toNumber (string s)
{
	int Number;
	if ( ! (istringstream(s) >> Number) ) Number = 0; // el string vacio lo manda al cero
	return Number;
}

string toString (int number)
{
    ostringstream ostr;
    ostr << number;
    return  ostr.str();
}

tint ele(tint a, tint b){
	if(b==0)return 1;
	if(b%2==0){
		return ele(a*a, b/2);
	}else{
		return a*ele(a*a, b/2);
	}
}

tint mcd(tint a, tint b){
	if(a==0)return b;
	return mcd(b%a, a);
}

double d_abs(long a, long b){
	if(a>b){
		return a-b;
	}
	return b-a;
}

void solve(){
	tint a, b, n;
	string s;
	vector<tint> v;
	cin>>a>>b;
	if(a%3==0 || b%3==0){
		cout<<0<<endl;
		return;
	}
	tint s1, s2, s3;
	tint c=max(a,b);
	tint d=min(a,b);
	tint ans=c*d;
	forsn(i, 1, c+1){
		s1=i*d;
		tint lado=c-i;
		tint p1=max(lado, d);
		tint p2=min(lado, d);
		//cout<<p1<<"!!!"<<p2<<endl;
		s2=(p1/2)*p2;
		s3=c*d-s1-s2;
		//cout<<s1<<","<<s2<<","<<s3<<endl;
		ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
		if(p1%2){
			s2=((p1+1)/2)*p2;
			s3=c*d-s1-s2;
			ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
			//cout<<s1<<","<<s2<<","<<s3<<endl;
		}
		
		p2=max(lado, d);
		p1=min(lado, d);
		s2=(p1/2)*p2;
		s3=c*d-s1-s2;
		//cout<<s1<<","<<s2<<","<<s3<<endl;
		ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
		if(p1%2){
			s2=((p1+1)/2)*p2;
			s3=c*d-s1-s2;
			ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
			//cout<<s1<<","<<s2<<","<<s3<<endl;
		}
	}
	
	
	d=max(a,b);
	c=min(a,b);
	forsn(i, 1, c+1){
		s1=i*d;
		tint lado=c-i;
		tint p1=max(lado, d);
		tint p2=min(lado, d);
		//cout<<p1<<"!!!"<<p2<<endl;
		s2=(p1/2)*p2;
		s3=c*d-s1-s2;
		//cout<<s1<<","<<s2<<","<<s3<<endl;
		ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
		if(p1%2){
			s2=((p1+1)/2)*p2;
			s3=c*d-s1-s2;
			ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
			//cout<<s1<<","<<s2<<","<<s3<<endl;
		}
		
		p2=max(lado, d);
		p1=min(lado, d);
		s2=(p1/2)*p2;
		s3=c*d-s1-s2;
		//cout<<s1<<","<<s2<<","<<s3<<endl;
		ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
		if(p1%2){
			s2=((p1+1)/2)*p2;
			s3=c*d-s1-s2;
			ans=min(ans,   max(s1,max(s2,s3))-min(s1,min(s2,s3)) );
			//cout<<s1<<","<<s2<<","<<s3<<endl;
		}
	}
	cout<<ans<<endl;
}




int main (){
	int T;
	T=1;
	while(T--){
		solve();
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep2(i,n) for(ll i=1;i<=(n);i++)
#define rep3(i,i0,n) for(ll i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}

bool comparex(tuple<ll,ll,ll> a, tuple<ll,ll,ll> b) {

    return get<1>(a) < get<1>(b);
        
}
bool comparey(tuple<ll,ll,ll> a, tuple<ll,ll,ll> b) {

    return get<2>(a) < get<2>(b);
        
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};
vector<vector<ll>> T;
vector<Pi> E;
vector<bool> seen;
ll N;

mint ans;
ll dfs(ll v, ll p){
    ll res = 1;
    vector<ll> ts;
    rep(i,T[v].size()){
        if(T[v][i] != p){
            ll t = dfs(T[v][i],v);
            res += t;
            ts.pb(t);
            
        }
    }
    if(p != -1){
        ts.pb(N-res);
    }

    mint now = mint(2).pow(N-1) - 1;
    rep(i,ts.size()){
        now -= mint(2).pow(ts[i]) - 1;
    }
    ans += now;

    return res;

}

int main() {
    

    cin >>N;
    T.resize(N);
    E.resize(N-1);
    seen.resize(N);
    rep(i,N-1){
        ll a,b;
        cin >>a>>b;
        a--;
        b--;
        T[a].pb(b);
        T[b].pb(a);
        E[i] = mp(a,b);

    }
    dfs(0,-1);

    ans /= mint(2).pow(N);

    cout << ans.x << endl;




    return 0;
    

}


Measured memory_bytes: 35648
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=1145141919810364364;

int main(){
	int n,z,w; cin>>n>>z>>w;
	int a[n]; rep(i,n) cin>>a[i];
	if(n==1) cout<<abs(a[0]-w)<<endl;
	else cout<<max(abs(a[n-1]-w),abs(a[n-2]-a[n-1]))<<endl;
	return 0;
}


Measured memory_bytes: 256
INF = 10000000

while True:
    n = int(input())
    if n == 0:
        break
    
    table = [[INF for i in range(10)] for j in range(10)]
    
    for l in range(n):
        a,b,c = [int(i) for i in input().split()]
        table[a][b] = c
        table[b][a] = c
        

    for k in range(10):
        for i in range(10):
            for j in range(10):
                if table[i][j] > table[i][k] + table[k][j]:
                    table[i][j] = table[i][k] + table[k][j]

    ans = INF
    ansid = 0
    for i in range(10):
        tmp = 0
        flag = False
        for j in range(10):
            if table[i][j] < INF and i != j:
                tmp = tmp + table[i][j]
                flag = True
        if tmp < ans and flag:
            ans = tmp
            ansid = i

    print(ansid,ans)



Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
 
#define MOD (1000000007)
#define f first
#define s second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];
typedef long long int ll;
#define ld long double
const int N = 2e5+30;
//https://codeforces.com/problemset/page/2?tags=1700-1700
 
 
void solve(){
   int n;
   cin>>n;
   int a[n+3];
   int dp[n+3];
   for(int i=1;i<=n;i++){
     dp[i] = 1e9;
   }
   for(int i=1;i<=n;i++){
     cin>>a[i];
   }
   dp[1]  = 0;
   for(int i=1;i<=n;i++){
     if(i-1>=1){
       dp[i] = min(dp[i],dp[i-1]+abs(a[i]-a[i-1]));
     }
     if(i-2>=1){
       dp[i] = min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
     }
   }
   cout<<dp[n]<<'\n';
}
 
 
int main(){
 	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	int T;
  //cin >> T;
  //cout<<prs.size()<<'\n';
	 T = 1;
  //visited[1]=1;
	while(T--){
		solve();
	}
}

Measured memory_bytes: 4304
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace _20170409_AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= n; i++)
            {
                int x = i;
                if (x % 3 == 0)
                {
                    sb.Append(' ');
                    sb.Append(i);
                }
                else
                {
                    for (; x > 0; x /= 10)
                    {
                        if (x % 10 == 3)
                        {
                            sb.Append(' ');
                            sb.Append(i);
                            break;
                        }
                    }
                }
            }

            Console.WriteLine(sb.ToString());

            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 9340
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef ONLINE_JUDGE
const int N = 1e6+50;
#else
const int N = 1e2+10;
#endif



int chk(ll x) {
	return 0<=x&&x<=1e9;
}
int main() {
	const ll bas = 1e9;
	ll s;
	scanf("%lld", &s);
	if (s==1e18) {
		cout<<"0 0 "<<bas<<' '<<0<<' '<<0<<' '<<bas<<endl;
		return 0;
	}
	ll p = s/bas;
	ll r = s%bas;
	r = bas-r;
	++p;
	cout<<"0 0 "<<p<<' '<<1<<' '<<r<<' '<<bas<<endl;
}








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

#define FOR(n) for(int i=0;i<n;i++)
#define ll long long

ll mob=1000000007;

using namespace std;
int main()
{ 
int h,w,n;
  cin>>h>>w>>n;
if(h>w)
{if(n%h==0)
  cout<<n/h;
 else 
   cout<<(n/h)+1;


}
else 
{

if(n%w==0)
  cout<<n/w;
 else 
   cout<<(n/w)+1;


}


return 0;
}


Measured memory_bytes: 256
def matchtest(S,T):
    tlen = len(T)
    slen = len(S)

    ans = -1
    for i in range(slen-tlen,-1,-1):
        found = True
        for j in range(tlen):
            if S[i+j] == '?' or S[i+j] == T[j]:
                pass
            else:
                found = False
                break
        if found == True:
            ans = i
            break
    return ans

S = input()
T = input()

pos = matchtest(S,T)
if pos == -1:
    ans = 'UNRESTORABLE'
else:
    ans = ''
    for i in range(len(S)):
        if pos <= i and i < pos+len(T):
            ans += T[i-pos]
        else:
            if S[i] != '?':
                ans += S[i]
            else:
                ans += 'a'

print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

struct UnionFind{
	vector<int> p;
	UnionFind(int n){
		p.resize(n, -1);
	}

	int find(int x){
		if(p[x] == -1)return x;
		else return find(p[x]);
	}
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y)return;
		p[x] = y; 
	}
	
};

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

  UnionFind uf(n);
  for(int i = 0; i < q; ++i){
  	int com, x, y;
  	cin >> com >> x >> y;
  	if(com == 0){
  		uf.unite(x, y);
  	}
  	else{
  		if(uf.find(x) == uf.find(y)){
  			cout << 1 << endl;
  		}
  		else cout << 0 << endl;
  	}
  }

  return 0;
}



Measured memory_bytes: 3176
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

   private static final String INPUT_FILE_PATH = "";

   void solve() {
      int n = in.nextInt();
      int[] a = new int[n];
      for (int i = 0; i < n; i++) a[i] = in.nextInt();
      long ans = 0;
      for (int i = 1; i < n; i++) {
         if (a[i] < a[i - 1]) {
            ans += (a[i - 1] - a[i]);
            a[i] = a[i - 1];
         }

      }
      out.println(ans);
   }

   private final InputReader in;
   private final PrintWriter out;

   private Main(InputReader in, PrintWriter out) {
      this.in = in;
      this.out = out;
   }

   private static class InputReader {
      private BufferedReader br;
      private StringTokenizer st;

      public InputReader(InputStream inputStream) {
         this.br = new BufferedReader(new InputStreamReader(inputStream), 32768);
         this.st = null;
      }

      public String nextToken() {
         while (st == null || !st.hasMoreTokens()) {
            try {
               st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
               throw new RuntimeException(e);
            }
         }
         return st.nextToken();
      }

      public int nextInt() {
         return Integer.parseInt(nextToken());
      }

      public long nextLong() {
         return Long.parseLong(nextToken());
      }

      public double nextDouble() {
         return Double.parseDouble(nextToken());
      }
   }

   public static void main(String[] args) throws Exception {
      InputStream inputStream = INPUT_FILE_PATH.isEmpty()
         ? System.in
         : new FileInputStream(new File(INPUT_FILE_PATH));
      OutputStream outputStream = System.out;

      InputReader inputReader = new InputReader(inputStream);
      PrintWriter printWriter = new PrintWriter(outputStream);

      new Main(inputReader, printWriter).solve();

      printWriter.close();
   }

}


Measured memory_bytes: 55844
//smartphone
#include "bits/stdc++.h"
using namespace std;
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define all(x) (x).begin(),(x).end()
#define tsort(v) sort((v).begin(), (v).end())
#define trev(v) tsort(v); reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif
typedef long long lint;

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

template<class T>bool maxi(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool mini(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

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

    int n;cin>>n;
    vector<int> a(n);rep(i,n){cin>>a[i];a[i]-=i;}
    tsort(a);lint m=a[n/2],ans=0;
    rep(i,n)ans+=abs(a[i]-m);co(ans);
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
const ll INF = 1e17;
const int MOD = 1e9 + 7;
ll a,b,c;

int main(void) {
	cin >> a >> b >> c;
	ct(a*b / 2);

	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define hi cout<<'h'<<'i'<<'\n' 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)
int dp[3005][3005][2];// i items, j time, k*
int cost[3005],val[3005];
int n;

int main()
{
    int i,j,t;
    boost;

    cin>>n>>t;
    rep(i,1,n+1)
    {
        cin>>cost[i]>>val[i];
    }

    rep(i,1,n+1)
    {
        rep(j,1,t)
        {
            dp[i][j][0]=dp[i-1][j][0];
            if(cost[i]<=j) dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-cost[i]][0]+val[i]);
            dp[i][j][1]=dp[i-1][j][1];
            if(cost[i]<=j) dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-cost[i]][1]+val[i]);
            dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][0]+val[i]);
        }
    }
    cout<<dp[n][t-1][1];
    
    return 0;
}



Measured memory_bytes: 70784
#include <stdio.h>
#include <string.h>

int main(void)
{
  char s[10];
  char t[10];
  char u[10];
  int a, b;
  
  scanf("%s %s", s, t);
  scanf("%d %d", &a, &b);
  scanf("%s", u);
  
  if (strcmp(s, u) == 0){
    printf("%d %d\n", a - 1, b);
  }
  else
  printf("%d %d\n", a, b - 1);
  return 0;
}

Measured memory_bytes: 128
N = int(input())
H = list(map(int, input().split()))

max = 0
count = 0
H.append(10**9+1)

#全探索
for i in range(N):
    #右のほうが低いとき
    if H[i] >= H[i+1]:
        count += 1
    #そうじゃないときに何段移動したかを保存
    else:
        if max <= count:
            max = count
            count = 0
        else:
            count = 0
            
print(max)

Measured memory_bytes: 15020
n=int(input())
A=[int(input()) for _ in range(n)]
m=max(A)
p=A.index(m)
l=1
for i in range(n):
	if i!=p:
		l=max(l,A[i])
for i in range(n):
	if i==p:
		print(l)
	else:
		print(m)

Measured memory_bytes: 12532
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#include<limits.h>
int main(){
    int N;
    scanf("%d",&N);
    int ans[100002]={0};
    for(int x=1;x<=(int)sqrt(N);x++){
        for(int y=1;y<=(int)sqrt(N);y++){
            for(int z=1;z<=(int)sqrt(N);z++){
                ans[x*x+y*y+z*z+x*y+y*z+z*x]++;
            }
        }
    }
    for(int i=1;i<=N;i++)
        printf("%d\n",ans[i]);
}


Measured memory_bytes: 2516
gets
xs = gets.split.map(&:to_f)
ys = gets.split.map(&:to_f)

1.upto(3) do |p|
  puts xs.zip(ys).map {|x| (x[0] - x[1]).abs ** p }.reduce(:+) ** (1/p.to_f)
end

puts xs.zip(ys).map {|x| (x[0] - x[1]).abs }.max

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

const int N=1e5+5;
int dp[N];
int solve(int n) {
	if ( n==9 || n==6 ) return 1;
	if ( n<10 ) return n;
	if ( dp[n] ) return dp[n];
	int a=1,b=1;
	int res=1e9;
	while ( a*9<=n ) {
		a*=9;
		res=min(res,solve(n-a));
	}
	while ( b*6<=n ) {
		b*=6;
		res=min(res,solve(n-b));
	}
	return dp[n]=res+1;
}

int main() {
	int n;
	cin >> n;
	cout << solve(n) << '\n';
    return 0;
}

Measured memory_bytes: 1152
def main():
    n = int(input())
    ss = list(input())

    ans = float("inf")
    ans = [0] * n
    cum_sum_w = [0] * (n+1)
    cum_sum_e = [0] * (n+1)
    for i in range(n):
        if ss[i] == 'W':
            add = 1
        else:
            add = 0
        cum_sum_w[i+1] = cum_sum_w[i] + add
    for i in range(n):
        if ss[i] == 'E':
            add = 1
        else:
            add = 0
        cum_sum_e[i+1] = cum_sum_e[i] + add
    for i in range(n):
        ans[i] = cum_sum_w[i] + (cum_sum_e[n] - cum_sum_e[i+1])
    print(min(ans))


if __name__ == "__main__":
    main()


Measured memory_bytes: 46780
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long ll;

ll w[100005], v[100005];
ll dp[103][100005];

int main() {
	int N, W; cin >> N >> W;
	int s = 0;
	for (int i = 0; i < N; i++) cin >> w[i] >> v[i], s += v[i];
	for (int i = 0; i <= N; i++) {
		for (int j = 1; j <= s; j++) dp[i][j] = 2e18;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= v[i]; j++) dp[i + 1][j] = dp[i][j];
		for (int j = 0; j <= s - v[i]; j++) {
			dp[i + 1][j + v[i]] = min(dp[i][j + v[i]], dp[i][j] + w[i]);
		}
	}
	ll ans = 0;
	for (int j = s; j >= 0; j--) {
		if (dp[N][j] <= W) {
			cout << j << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 82176
while True:
    a = int(input())
    if  a == 0:
        break
    else:
        b = 1000-a
        c = b%500
        d = c%100
        e = d%50
        f = e%10
        g = f%5
        print(b//500+c//100+d//50+e//10+f//5+g)



Measured memory_bytes: 5584
h, w = map(int, input().split())
while h != 0 or w != 0 :
        for i in range(h) :
                if i%2 == 0 :
                        print("#." * (w // 2) + "#" * (w % 2))
                else :
                        print(".#" * (w // 2) + "." * (w % 2))
        print()
        h, w = map(int, input().split())


Measured memory_bytes: 5612
#include <stdio.h>

int main(void)
{
    int a;
    char s[16];

    scanf("%d", &a);
    scanf("%s", s);

    if (a >= 3200)
    {
        printf("%s\n", s);
    }
    else
    {
        printf("red\n");
    }

    return 0;
}

Measured memory_bytes: 128
# abc166 B

n, k = map(int, input().split())
ld = []
la = []

for i in range(k):
    ld.append(int(input()))
    la.append(list(map(int, input().split())))

ln = [1] * (n+1)

ln[0] = 0

for a in la:
    for s in a:
        ln[s] = 0

print(sum(ln))


Measured memory_bytes: 67860
n,m,c = map(int, input().split())

b = list(map(int, input().split()))

ans = 0

for i in range(n):
    total = 0
    a = list(map(int, input().split()))
    for j in range(m):
        total += a[j]*b[j]
    total += c
    if total > 0:
        ans += 1

print(ans)

Measured memory_bytes: 9148
//Practice more and more
//learn for better
#define bn begin()
#define en end()
#define mx 5000010
#define pb push_back
#define PI (2.0*acos(0.0))
#define ALL(a) a.begin(),a.end()
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rep(a,b) for(int a=0;a<b;++a)
#define fastio ios::sync_with_stdio(false)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int>  vi;
typedef vector<ll>   vll;
bool m[200010];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
	int a,b,n,i,t,tmp;
	cin>>a>>b;
	if(b>=a*2&&b<=a*4&&b%2==0)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;

	return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second

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

	string s1,s2;

	ll a = 0,b = 0;

	REP(i,n) {
		cin >> s1 >> s2;

		if(s1 == s2) {
			a++;b++;
		}else if(s1 > s2) {
			a += 3;
		}else
			b += 3;

	}
	cout << a << " " << b << endl;
	return 0;
}



Measured memory_bytes: 3156
n = int(input())

a = list(map(int, input().split()))

res = 1

if 0 in a:
    print(0)
else:
    for i in range(n):
        res *= a[i]

        if a[i] == 0:
            break
        if res > 10**18:
            print(-1)
            break


    if res > 10**18:
        pass
    else:
        print(res)


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


#define int long long
#define mp make_pair
#define pb push_back
#define st first
#define nd second

typedef long long ll;
typedef pair < ll , ll > pp;
const int mod = 1e9 + 7;
const int N   = 2e5 + 5;

int q,a,b,j,n,n2,x,y,mx,t;

signed main(){
    cin >> q;
    for(; q-- ;){
        cin >> a >> b;
        if(a > b) swap(a,b);
        t = 2*sqrt(a*b) + 1;

        for(j=t; j && j > t-20; j--){
            n = j;
            n2 = (n+1)/2;
            mx = 0;
            x = n2+1; y = n-x+1;
            if(x >= a) x++;
            if(y >= b) y++;
            mx = x * y;
            x = n2; y = n-x+1;
            if(x >= a) x++;
            if(y >= b) y++;
            mx = max(mx , x * y);
            x = n2-1; y = n-x+1;
            if(x >= a) x++;
            if(y >= b) y++;
            mx = max(mx , x * y);

            x = a; y = n-x+1;
            if(x >= a) x++;
            if(y >= b) y++;
            mx = max(mx , x * y);
            x = n-b+1; y = n-x+1;
            if(x >= a) x++;
            if(y >= b) y++;
            mx = max(mx , x * y);

            if(mx < a*b) break;
        }

        cout << j << endl;
    }

    return 0;
}

Measured memory_bytes: 256
# coding: utf-8

# In[12]:


import numpy as np


# In[33]:


N, M = map(int,input().split())
X = np.array([int(x) for x in input().split()])


# In[34]:


if N >= M:
    print(0)
else:
    sorted_x = np.sort(X)
    dist = sorted_x[1:] - sorted_x[:-1]
    ans = np.sort(dist)[::-1][N-1:].sum()
    print(ans)



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

bool isPalin(int i);

int main () {
	int a, b;
	int ans = 0;
	cin >> a >> b;
	for (int i = a; i <= b; i++) {
		if (isPalin(i)) {
			ans++;
		}
	}
	cout << ans << endl;
	fflush(stdout);
	return 0;
}
bool isPalin(int i) {
	int a = i % 10;
	int b = i / 10;
	int d = i / 1000;
	int e = i / 10000;
	if (a != e) {
		return false;
	} else if (b % 10 != d % 10) {
		return false;
	} else {
		return true;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin>>N;
  vector<long long> p(N);
  for(int i=0;i<N;i++)
    cin>>p.at(i);
  long long min=p.at(0)+1,count=0;
  for(int i=0;i<N;i++){
    if(p.at(i)<min){
      min=p.at(i);
      count++;
    }
  }
  cout<<count<<endl;
}

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

int n, a, m, sm;

int main(){
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d", &a);
    m = max(m, a);
    sm += a;
  }
  puts(sm > m*2 ? "Yes" : "No");
}

Measured memory_bytes: 256
N = int(input())

A = [list(map(int,input().split())) for i in range(2)]
B = [[0 for i in range(N)] for j in range(2)]

B[0][0] = A[0][0]
for i in range(2):
    for j in range(N):
        for x, y in [[0, -1], [-1, 0]]:
            id = i+x
            jd = j+y
            if id < 0 or id >= 2 or jd < 0 or jd >= N: continue
            c = B[id][jd]+A[i][j]
            if c > B[i][j]:
                B[i][j] = c
        


print(B[1][N-1])

Measured memory_bytes: 9168
# 日:1 月:2 火:3 水:4 木:5 金:6 土:7
x = {}
x['SUN']=7
x['MON']=1
x['TUE']=2
x['WED']=3
x['THU']=4
x['FRI']=5
x['SAT']=6

S = input()
if S=='SUN':
  print(7)
else:
  print(7-x[S])

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
class JNum{
	static constexpr uint64_t mod = 1000000007;
	uint64_t num;
public:
	JNum(uint64_t x):num(x%mod){}
	JNum operator+(const JNum& j)const{
		return (num + j.num)%mod;
	}
	JNum operator*(const JNum& j)const{
		return (num * j.num)%mod;
	}
	void operator+=(const JNum& j){
		num += j.num;
		num %= mod;
	}
	void operator*=(const JNum& j){
		num *= j.num;
		num %=mod;
	}
	uint64_t out()const{return num;}
};
using namespace std;
template<typename T>
void get(T& t){cin >> t;}
int main(void){
	uint64_t N,K;
	get(N);get(K);
	vector<uint64_t> a(N),b(N);
	for(int i=0;i<N;i++){
		get(a[i]);get(b[i]);
	}
	uint64_t ans = 0;
	uint64_t k = K;
	while(true){
		uint64_t v=0;
		for(int i=0;i<N;i++){
			if((a[i] & ~k)==0)v+=b[i];
		}
		ans = max(v,ans);
		uint64_t low = K & -K;
		k = (K & ~low) | (low-1);
		if(K==0)break;
		K &= ~low;
		
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){
	int i, n, k;
	int *a, *b;

	a = (int *)malloc(200001 * sizeof(int));
	b = (int *)malloc(200001 * sizeof(int));

	scanf("%d", &n);

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

	
	if(n == 1) {
		printf("%d", a[1]/10);
	}

	else if(n % 2 == 0){
		i = 1;
		while(n - 2 * (i - 1) != 2) {
			b[i] = a[n - 2 * (i - 1)];
			i++;
		}

		b[i] = a[2];
		i++;
		k = 0;

		while(2 * k + 1 != n - 1) {
			b[i] = a[2 * k + 1];
			i++;
			k++;
		}
		b[i] = a[n - 1];

	}

	else if(n % 2 == 1 && n != 1){
		i = 1;
		while(n - 2 * (i - 1) != 1) {
			b[i] = a[n - 2 * (i - 1)];
			i++;
		}

		b[i] = a[1];
		i++;
		k = 1;

		while(2 * k != n - 1) {
			b[i] = a[2 * k];
			i++;
			k++;
		}
		b[i] = a[n - 1];

	}

	for(i = 1; i <= n; i++) {
		printf("%d ", b[i]);
	}
	free(a);
	free(b);   
}

Measured memory_bytes: 3712
#include <iostream> 
#include <string>
using namespace std;
int main() {
    int n, k;
    string s;
    cin >> n >> s >> k;
    for (int i = 0; i < n; i++) if (s[i] != s[k-1]) s[i] = '*';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left
A,B,Q = map(int,input().split())
inf = float('inf')
S = [-inf] + [int(input()) for i in range(A)] + [inf]
T = [-inf] + [int(input()) for i in range(B)] + [inf]
X = [int(input()) for i in range(Q)]
for x in X:
    si = bisect_left(S,x); ti = bisect_left(T,x)
    ans = inf
    for s in [S[si-1],S[si]]:
        for t in [T[ti-1],T[ti]]:
            d1 = abs(s-x) + abs(t-s)
            d2 = abs(t-x) + abs(s-t)
            ans = min(ans,d1,d2)
    print(ans)

Measured memory_bytes: 17412