akhauriyash/Code-Regression huggingface dataset:
//c++ -std=gnu++14 a.cpp
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//typedef pair<ll, ll> P;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define revrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);
#define sz(x) ((int)(x).size())

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const int INF = 1 << 30;//10^9
//const ll MOD = 1000000007;
const ll MOD = 998244353;
double EPS = 1e-10;

vector<ll> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};

void pres(double A){printf("%.9lf\n", A);}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

ll lcm(ll x, ll y){
  ll res = x / gcd(x, y);
  res *= y;
  return res;
};


//コンビネーション
const int MAXcomb = 2000010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

const int MAXkai = 200010;
ll kai_memo[MAXkai];
ll kai(ll N){
  if(kai_memo[N] != 0) return kai_memo[N];
  if(N <= 1) return 1;
  return kai_memo[N] = N * kai(N-1) % MOD;
}

ll disit(ll s, ll base = 10){
  ll res = 0;
  while(s){
    res++;
    s /= base;
  }
  return res;
}

ll N, S;
ll A[3010];
ll dp[3010][6010];
void solve(){
  cin >> N >> S;
  rep(i, N) cin >> A[i];
  dp[0][0] = 1;
  rep(i, N){
    rep(j, 3010){
      dp[i+1][j+A[i]] += dp[i][j];
      dp[i+1][j+A[i]] %= MOD;
      dp[i+1][j] += dp[i][j] * 2;
      dp[i+1][j] %= MOD;
    }
  }
  cout << dp[N][S] << endl;
}

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


Measured memory_bytes: 116648
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    val result = solve(new Scanner(System.in))
    if (result.length > 0) println(result)
  }

  def solve(in: String): String = solve(new Scanner(in))

  def solve(sc: Scanner): String = {
    val s = sc.next

    s.count(_ == '1').toString
  }
}


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

int main(){
  int64_t k, n;
  cin >> k >> n;
  vector<int> a(n);
  int max=0;
  cin >> a[0];
  for(int i=1; i<n; i++){
    cin >> a[i];
    if(max < a[i] - a[i-1]){
      max = a[i] - a[i-1];
    }
  }
  if(max < k - (a[n-1]- a[0])){
    max = k - (a[n-1]- a[0]);
  }
  cout << k - max << endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
using namespace std;
typedef long long ll;
inline ll rd()
{
    static ll x,f;
    x=0,f=1ll;
    char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1ll;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10ll+ch-'0';
    return x*f;
}
const int N=1010,mod=1000000007;
struct Matrix{
    int n,m,a[10][10];
    Matrix(){memset(a,0,sizeof a);}
    inline int *operator[](int x){return a[x];}
};
int n,m,K;
bool H,S;
char s[N][N];
 
inline int pls(int a,int b){return a+b>mod?a+b-mod:a+b;}
inline int mns(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int pwr(int x,int k){int res=1;for(;k;k>>=1,x=mul(x,x))if(k&1)res=mul(x,res);return res;}
inline Matrix operator*(Matrix &a,Matrix &b)
{
    Matrix res;res.n=b.n;res.m=a.m;
    fo(i,1,res.n)
        fo(j,1,res.m)
            fo(k,1,b.n)res[i][j]=pls(res[i][j],mul(a[i][k],b[k][j]));
    return res;
}
inline bool cmp(int i,int j){return s[i][j]=='#';}
 
inline void gaoH()
{
    int r=0,k1=0,k2=0,len=0;
    fo(i,1,n){
        if(cmp(i,1)&&cmp(i,m))r++;
        len=0;
        fo(j,1,m){
            if(j>1&&cmp(i,j-1)&&!cmp(i,j)){
                k1=pls(k1,len);k2=pls(k2,len-1);
                len=0;
            }
            if(cmp(i,j))len++;
        }
        if(len)k1=pls(k1,len),k2=pls(k2,len-1);
    }
    Matrix ans,res;
    ans.n=1,ans.m=2;
    ans[1][1]=ans[1][2]=1;
    res.n=res.m=2;
    res[1][1]=k1,res[1][2]=0;
    res[2][1]=mns(0,k2),res[2][2]=r;
    K--;
    for(;K;K>>=1,res=res*res)if(K&1)ans=ans*res;
    printf("%d\n",ans[1][1]);
}
inline void gaoS()
{
    int r=0,k1=0,k2=0,len=0;
    fo(j,1,m){
        if(cmp(1,j)&&cmp(n,j))r++;
        len=0;
        fo(i,1,n){
            if(i>1&&cmp(i-1,j)&&!cmp(i,j)){
                k1=pls(k1,len);k2=pls(k2,len-1);
                len=0;
            }
            if(cmp(i,j))len++;
        }
        if(len)k1=pls(k1,len),k2=pls(k2,len-1);
    }
    Matrix ans,res;
    ans.n=1;ans.m=2;
    ans[1][1]=ans[1][2]=1;
    res.n=res.m=2;
    res[1][1]=k1,res[1][2]=0;
    res[2][1]=mns(0,k2),res[2][2]=r;
    K--;
    for(;K;K>>=1,res=res*res)if(K&1)ans=ans*res;
    printf("%d\n",ans[1][1]);
}
 
int main()
{
    n=rd();m=rd();K=rd()%(mod-1);
    if(K==0||K==1){puts("1");return 0;}
    fo(i,1,n)scanf("%s",s[i]+1);
    H=S=0;
    fo(i,1,n)if(cmp(i,1)&&cmp(i,m)){H=1;break;}
    fo(i,1,m)if(cmp(1,i)&&cmp(n,i)){S=1;break;}
    if(S&&H){puts("1");return 0;}
    if(!S&&!H){int cnt=0;fo(i,1,n)fo(j,1,m)cnt+=cmp(i,j);printf("%d\n",pwr(cnt,K-1));return 0;}
    if(H)gaoH();
    else gaoS();
    return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define    nl   "\n"
#define    End  return 0
#define    gt   greater<int>()
#define    ll   long long int

int main()
{

    int n;
    scanf("%d",&n);
    long long a[n];
    for(int i=0; i<n; i++)
        scanf("%lld",&a[i]);
    int zero =0;
    for(int i=0; i<n; i++)
        if(a[i]==0)
            zero ++;
    if(zero >0)
    {
        printf("0\n");
        return 0;
    }
    long long prod =1;
    for(int i=0; i<n; i++)
    {
        if(a[i ] <=1000000000000000000/ prod )
        {
            prod *=a[i];
        }
        else
        {
            printf("-1\n");
            return 0;
        }
    }
    printf("%lld\n",prod );

}


Measured memory_bytes: 4488
#include <bits/stdc++.h>
using namespace std;
/* 答えをにぶたんで狭めていく系 */

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long

typedef pair<ll, ll> P;

const int MAX = 2000005;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

int x, y;

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vector<bool> isUsed(100001, false);

int main(){
    COMinit();
    int n;
    cin >> n;
    vector<int> a(n+1);
    int left, right;
    int value;

    REP(i, n+1) {
        cin >> a[i];
        if(isUsed[a[i]]) {
            value = a[i];
            break;
        }
        isUsed[a[i]] = true;
    }

    REP(i, n+1) {
        if(a[i] == value) {
            left = i+1;
            break;
        }
    }

    REPN(i, left, n+1) {
        if(a[i] == value) {
            right = i+1;
            break;
        }
    }
    
    //cout << right << " " << left << endl;

    REPN(i, 1, n+2) {
        ll tmp = COM(n+1, i) - COM(n-(right-left), i-1);
        tmp += MOD;
        tmp %= MOD;     
        cout << tmp << endl;
    }

    
    return 0;
}


Measured memory_bytes: 48512
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int a = 0;
         
        for(int i = 0; i < 10; i++){
            a += sc.nextInt();
        }
         
        System.out.println(a);
         
        
    }
}

Measured memory_bytes: 17172
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())

    def dfs(s, num):
        if len(s) == n:
            print(s)
            return

        for i in range(num + 1):
            t = s + chr(97 + i)
            dfs(t, max(num, i + 1))

    dfs("", 0)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 4428
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static const ll mod=1000000007;
ll modpow(ll x,ll y){
if(y==0)
  return 1;
  else if(y%2==0){
    ll z=modpow(x,y/2);
    return (z*z)%mod;
  }else{
  ll z=modpow(x,y/2);
    return (x*((z*z)%mod))%mod;
  }
}
ll H,W,A,B;
ll fac[200005];
ll rev[200005];
int main(){
cin>>H>>W>>A>>B;
  fac[0]=1;rev[0]=1;
  for(ll i=1;i<=200004;i++){
  fac[i]=(i*fac[i-1])%mod;
    rev[i]=modpow(fac[i],mod-2);
  }ll ans=0;
  for(ll i=B;i<W;i++){
  ll a=(rev[i]*((fac[H-A-1+i]*rev[H-A-1])%mod))%mod;
    ll b=(rev[W-1-i]*((fac[W+A-2-i]*rev[A-1])%mod))%mod;
    ans=(ans+(a*b)%mod)%mod;
  }cout<<ans<<endl;
  return 0;
}

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

int main() {
    int i, l, n, b, f, r;
    char a;
    int m[5][4][11] = {0};
    char sm[4] = {'S','H','C','D'};

    cin >> n;
    for(i = 0;i < n; i++) {
        cin >> b >> f >> r >> l;
        m[b][f][r] += l;
    }
    for(b = 1; b <= 4; b++){
        for(f = 1; f <= 3; f++){
            for(r = 1; r <= 10; r++){
                cout << " " << m[b][f][r];
            }
            cout << endl;
        }
        if(b < 4) {
            cout << "####################" << endl;
        }
    }
    return 0;
}




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

int main(){
	string s;
	int size, n;
	while (getline(cin, s)) {
		size = s.size();
		for (int i = 0; i < size; i++) {
			if (s[i] == '@') {
				i++;
				n = s[i] - '0';
				i++;
				for (int j = 0; j < n; j++) {
					cout << s[i];
				}
			}else {
				cout << s[i];
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 0
/******************
*  Writer: OTHER  *
******************/
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
using namespace std;

long long dp[51][2510];
int b[55];
int n,a;

int main(){
	
	cin>>n>>a;
	for(int i=0;i<n;i++){
	    cin>>b[i];
	}
	
	dp[0][0]=1;
	for(int x=0;x<n;x++){
		for(int k=50;k>=0;k--)
		for(int y=0;y<=2500;y++){
			if(!dp[k][y])continue;
			dp[k+1][y+b[x]]+=dp[k][y];
		}
	}
	
	long long ans=0;
	for(int k=1;k<=50;k++){
		for(int y=0;y<=2500;y++){
			if(k*a==y)ans+=dp[k][y];
		}
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm> 
#include <string>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(){
	string s;
	cin >> s;
	
	int len = s.size();
	int ans = 0;
	string t;
	char c = s[0];
	for(int i = 1; i < len; ++i){
		if(c != s[i]){
			t += c;
			c = s[i];
		}
	}
	
	if(s[len - 1] == c){
		t += c;
	}
		
	cout << t.size() - 1 << endl;
	
	return 0;
}



Measured memory_bytes: 3644
#include <iostream>
#include <map>

using namespace std;

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

	map<int, int> m;
	for (int i = 0; i < N; i++){
		m[i] = 0;
	}
	for (int i = 1; i < N; i++){
		int A;
		cin >> A;
		m[A - 1]++;
	}

	for (int i = 0; i < N; i++){
		if(m.find(i) != m.end()){
			cout << m[i] << endl;
		}
	}
	return 0;
}


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

int main(){

  int s;
  cin>>s;
  
  vector<int> data(1);
  
  data.at(0)=s;
  
  int answer=0;
  
  bool flag=false;
  
  
  for (int i=0;i<1000000;i++){
    int x;
    if(data.at(i)%2==0){
      x=data.at(i)/2;
    }
    
    else {
      x=3*data.at(i)+1;
    }
    
    for (int j=0;j<i+1;j++){
      if (x==data.at(j)){
        answer=i+2;
        flag=true;
        break;}
    }
    
    if (flag){
      break;
    }
    
    data.push_back(x);
  }
  
  cout<<answer<<endl;
  
      
      
  
}
  













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

typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

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

int r(int r){
    if(r==1) return 1;
    return r * (r-1);
}

int main(){
    char c; cin >> c;
    c = c+1;
    cout << c << endl;
}


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

typedef long long ll;

#define F first 
#define S second 
#define PB push_back
#define MP make_pair 
#define rep(i,a,b) for (ll i=a;i<b;i++)

typedef vector<int> vi;
typedef pair<int,int> pi;


int main()
{

    ll H,W;
    cin>>H>>W;

    vector<vector<char>> map(H+1,vector<char>(W+1,'.'));
    vector<vector<ll>> dp(H+1,vector<ll>(W+1,0));
    rep(i,1,H+1) 
        rep(j,1,W+1)
        cin>> map[i][j];

    if(map[1][2]=='.')
    dp[1][2]=1;
    if(map[2][1]=='.')
    dp[2][1]=1;

    rep(i,1,H+1) {
        rep(j,1,W+1) {

            //cout<<dp[i][j]<<endl;
            //cout<< map[i-1][j] << " & "<<map[i][j-1]<<endl;
            //cout<<" i "<<i<<" j "<<j<<endl;
            if(map[i-1][j] == '.' && map[i][j-1]=='.') {
                dp[i][j] += (dp[i-1][j] + dp[i][j-1])%1000000007;
            } else if(map[i-1][j]=='.') {
                dp[i][j] += dp[i-1][j]%1000000007;
            } else if(map[i][j-1]=='.') {
                dp[i][j] += dp[i][j-1]%1000000007;
            }

            //cout<<" i "<<i<<" j "<<j<<" "<<dp[i][j]<<" map "<<map[i][j]<<endl;
        }
    }

    cout<<dp[H][W]<<endl;
    return 0; 
}



Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int N, M;
    cin >> N >> M;
    cout << N * M << endl;
}



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

using namespace std;

#define F first
#define S second
#define modulo ll (1e9 + 7)
const long double PI = 3.141592653589793238L;

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

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
//    freopen("in.in", "r", stdin);
//    freopen("out.out", "w", stdout);
}

const int N = 1e5 + 9, M = 2e5 + 9, OO = 0x3f3f3f3f;
const ll llOO = 0x3f3f3f3f3f3f3f3f;

int main(){
    init();

    int x;  cin >> x;

    for(ll i = 0;i < 3000;i++){
        for(ll j = 0;j < 3000;j++){
            ll a = i * i * i * i * i;
            ll b = j * j * j * j * j;

            if(a - b == x)  return cout << i << " " << j, 0;
            if(a + b == x)  return cout << i << " " << -j, 0;
        }
    }

}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#include <time.h>
using namespace std;
#include <math.h>
#define ll long long 
// to increase precision
// std::cout<<std::fixed;
// 	std::cout<<std::setprecision(6)<<z;
//clock_t tStart = clock();
//printf("Time taken: %.9fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
#define max1 100001
vector<vector<int> > arr(max1);


int main(){	
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	int ans=0;
	for (int i = 0; i < k; ++i)
	{
		ans+=a[i];
	}
	cout<<ans<<endl;



}

Measured memory_bytes: 5416
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define lla(s) s.rbegin(),s.rend()
#define pcnt(b) __builtin_popcount(b)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int,int>>
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const ll INF = 1e18;

char c[2020][2020];

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h,w;cin>>h>>w;
    rep(i,0,h+2){
        rep(j,0,w+2){
            c[i][j]='#';
        }
    }
    rep(i,1,h+1){
        rep(j,1,w+1){
            cin>>c[i][j];
        }
    }
    int L[h+2][w+2],R[h+2][w+2],U[h+2][w+2],D[h+2][w+2];
    memset(L,0,sizeof(L));memset(R,0,sizeof(R));memset(U,0,sizeof(U));memset(D,0,sizeof(D));
    rep(i,1,h+1){
        rep(j,1,w+1){
            if(c[i][j]=='#'){L[i][j]=0;R[i][j]=0;U[i][j]=0;D[i][j]=0;}
            else{
                L[i][j]=L[i][j-1]+1;U[i][j]=U[i-1][j]+1;D[i][j]=D[i+1][j]+1;R[i][j]=R[i][j+1]+1;
            }
        }
    }
    rrep(i,h,1){
        rrep(j,w,1){
            if(c[i][j]=='#'){L[i][j]=0;R[i][j]=0;U[i][j]=0;D[i][j]=0;}
            else{
                D[i][j]=D[i+1][j]+1;R[i][j]=R[i][j+1]+1;
            }
        }
    }
    int ans = 0;
    rep(i,1,h+1){
        rep(j,1,w+1){
            ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3);
            //cout<<R[i][j]<<' ';//+R[i][j]+U[i][j]+D[i][j]-3<<' ';
        }
    }
    cout<<ans<<endl;
}

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

const int size = 200;
const int limit = 1000001;
int dp[limit], dp_odd[limit];
int tetra[size], odd[size];

int main(void){
    int size_odd = 0;
    for(int i=1; i<size+1; ++i) {
        ll t = i*(i+1)*(i+2)/6;
        tetra[i-1] = t;
        if(t%2==1) {odd[size_odd]=t; size_odd++;}
    }
    int inf = numeric_limits<int>::max();
    rep(i, limit) dp[i] = dp_odd[i] = inf;
    dp[0] = 0;
    dp_odd[0] = 0;
    rep(i, size) {
        for(int j=tetra[i]; j<limit; ++j) 
            dp[j] = min(dp[j-tetra[i]]+1, dp[j]);
    }
    rep(i, size_odd) {
        for(int j=odd[i]; j<limit; ++j) 
            dp_odd[j] = min(dp_odd[j-odd[i]]+1, dp_odd[j]);
    }

    int n;
    while(cin >> n && n) {
        cout << dp[n] << " ";
        cout << dp_odd[n] << endl;
    }
}


Measured memory_bytes: 10824
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;
map<ll,ll> mp;

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n+1,0);
    for(ll i=1;i<=n;i++){
        ll now; cin>>now;
        a[i]=a[i-1]+now;
        a[i]=(a[i]+k)%k;
    }
    ll ans=0;
    for(ll i=0;i<=n;i++){
        a[i]-=i;
        a[i]%=k;
        a[i]=(a[i]+k)%k;
        if(i>=k) mp[a[i-k]]--;
        ans+=mp[a[i]];
        mp[a[i]]++;
        //cout<<a[i]<<":"<<ans<<endl;
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 17228
"""Even Relation
https://atcoder.jp/contests/abc126/tasks/abc126_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)


class Node:
    def __init__(self, node_id, color):
        self.node_id = node_id
        self.color = color
        self.edges = []

class Edge:
    def __init__(self, to, length):
        self.to = to
        self.length = length


def dfs(node, p):
    for edge in node.edges:
        # 親への枝は何もしない
        if edge.to == p:
            continue
        # 枝が偶数なら子を同じ色で塗る
        if edge.length % 2 == 0:
            graph[edge.to].color = node.color
        else:
            if node.color == 1:
                graph[edge.to].color = 0
            else:
                graph[edge.to].color = 1

        dfs(graph[edge.to], node.node_id)


N = int(input())

# グラフ初期化
graph = [Node(node_id=i, color=-1) for i in range(N + 1)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    graph[u].edges.append(Edge(v, w))
    graph[v].edges.append(Edge(u, w))

# 最初は0始まり
graph[1].color = 0

dfs(graph[1], -1)


for i in range(1, N + 1):
    print(graph[i].color)


Measured memory_bytes: 116028
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define int long long
#define pii pair <int, int>
#define XX first
#define YY second

// constants:
const int mn = 200005;
const int mod = 1000000007;
const long long inf = 4444444444444444444;
const int sminf = 1111111111;
const bool is_multitest = 0;
const bool is_interactive = 0;

// i/o methods:
const bool input_from_file = 0;
const bool output_to_file = 0;
#define filename ""
#define in_extension "inp"
#define out_extension "out"

// data preprocessing: (e.g.: divisor generating, prime sieve)
void preprocess()
{
  
}

// global variables:
int s;
int POW(int u, int v) {
  if (v == 0) return 1;
  int mid = POW(u, v/2);
  mid = (mid*mid)%mod;
  if (v&1) return (mid*u)%mod;
  else return mid;
}
int findans(int n, int k) {
  int tu = 1, mau = 1;
  for (int i = 1; i <= n-1; i++) {
    tu = (tu * (k+i))%mod;
    mau = (mau * (i)) % mod;
  }
  return (tu * POW(mau, mod-2))%mod;
}
// main solution goes here:
void execute(int test_number)
{
  cin >> s;
  int ans = 0;
  for (int i=1; i*3 <= s; i++) {
    ans = (ans + findans(i, s - i*3))%mod;
  }
  cout<<ans;
}
// REMEMBER TO CHOOSE TEST METHODS
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Solution by low_



















signed main()
{
#ifdef lowie
    if (!is_interactive)
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
#else
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);
#endif
    if (!is_interactive)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    preprocess();
    int ntest;
    if (is_multitest) cin >> ntest;
    else ntest = 1;

    for (int testno = 1; testno <= ntest; testno++)
    // use for instead of while to serve facebook hacker cup test format
    {
        execute(testno); // only start coding in this function, not in main
    }
}
// Template by low_
// Contact me via mail: ttuandung1803@gmail.com
// ...or codeforces: https://www.codeforces.com/profile/low_
// ...or linkedIn: https://www.linkedin.com/in/daniel-to-83045a19a/
// I use VS Code. Here's a JSON format for my template: https://pastebin.com/xH2yRdwx


Measured memory_bytes: 3632
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
ll INF = 1000000000;

int main() {
  //
  ll h, w;
  cin >> h >> w;
  vector<string> field(h);
  rep(i, h) { cin >> field[i]; }
  queue<pair<pll, ll>> que;
  ll white = 0;
  rep(i, h) {
    rep(j, w) {
      if (field[i][j] == '#') {
        que.push(make_pair(make_pair(i, j), 0));
      } else {
        white++;
      }
    }
  }
  ll cnt = 0;
  ll di[] = {1, 0, -1, 0};
  ll dj[] = {0, 1, 0, -1};
  // cout << white << endl;
  while (white > 0) {
    pair<pll, ll> p = que.front();
    ll i = p.first.first, j = p.first.second;
    // cnt = max(cnt, p.second);
    que.pop();
    rep(k, 4) {
      ll ni = i + di[k];
      ll nj = j + dj[k];
      if (0 <= ni && ni < h && 0 <= nj && nj < w) {
        if (field[ni][nj] != '#') {
          field[ni][nj] = '#';
          // cout << ni << "," << nj << ":" << p.second + 1 << endl;
          white--;
          cnt = max(cnt, p.second + 1);
          que.push(make_pair(make_pair(ni, nj), p.second + 1));
        }
      }
    }
  }
  cout << cnt << endl;
  return 0;
}


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

using namespace std;

int main()
{
 	int n;
  	cin >> n;
  	map<string, int> m;
  	for(int i = 0; i < n; ++i)
    {
     	string s;
      	cin >> s;
      	++m[s];
    }
  
  	cout << "AC x " << m["AC"] << endl;
  	cout << "WA x " << m["WA"] << endl;
  	cout << "TLE x " << m["TLE"] << endl;
  	cout << "RE x " << m["RE"] << endl;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector< int> v(n + 1);
    while (n--) {
        int x; cin >> x;
        v[x]++;
    }
    vector< int> cnt;
    for (int x : v) if (x) cnt.emplace_back(x);
    sort(cnt.rbegin(), cnt.rend());
    int res = 0;
    for (int i = k; i < cnt.size(); i++) res += cnt[i];
    cout << res << endl;
}

Measured memory_bytes: 2168
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;

int main(){
	int n;
	int count=0;
	string name;
	cin >> n >> name;
	vector<string> signs(n);
	for(int i=0; i<n; ++i){
		cin >> signs[i];
		//cout << signs[i].size() << "\n";
	}
	int namelen=name.size();
	for(int i=0; i<n; ++i){
		int len=signs[i].size();
		string sign=signs[i];
		for(int start=0; start<len; ++start){
			for(int step=1; start+(namelen-1)*step<len; ++step){
				for(int j=0; j<namelen; ++j){
					if(sign[start+step*j]!=name[j]){
						goto fail;
					}
				}
				count++;
				//cout << sign << "\n";
				goto naxtk;
fail:;
			}
		}
naxtk:;
	}
	cout << count << "\n";
	return 0;
}

Measured memory_bytes: 1236
#[allow(unused_imports)]
use std::cmp::{max, min};
use std::io::{stdin, stdout, BufWriter, Write};
use std::collections::HashMap;

#[derive(Default)]
struct Scanner {
    buffer: Vec<String>,
}

impl Scanner {
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            stdin().read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

fn main() {
    let mut scan = Scanner::default();
    let out = &mut BufWriter::new(stdout());
    let n = scan.next();
    let mut dict = HashMap::new();

    for _i in 0..n {
        let op: String = scan.next();
        let k: String = scan.next();
        if op == "insert" {
            dict.insert(k, true);
        } else {
            if dict.contains_key(&k) {
                writeln!(out, "yes").ok();
            } else {
                writeln!(out, "no").ok();
            }
        }
    }
}



Measured memory_bytes: 37352
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var NK = ReadLine().Split().Select(int.Parse).ToArray();
        var S = ReadLine();
        for (int i = 0; i < S.Length; i++)
        {
            if (i != NK[1] - 1) Write(S[i]);
            else
            {
                Write(char.ToLower(S[i]));
            }
        }
        WriteLine();

    }
}




Measured memory_bytes: 11348
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    price = sorted(list(map(int, input().split())))

    print(sum(price[:2]))

if __name__ == '__main__':
    main()

Measured memory_bytes: 10296
fun main(arr:Array<String>) {
    val moji = readLine()!!.split(" ")
    val count = readLine()!!.split(" ").map { it.toLong() }.toMutableList()
    val word = readLine()!!
    val idx = moji.indexOf(word)
    count[idx] -= 1L
    println(count.joinToString(" "))
}

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(12);
    cout << fixed;
    cin.tie(0);

    int n;
    cin >> n;
    cout << (1000000 - n) % 1000 << endl;

    return 0;
}


Measured memory_bytes: 3648
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  long long t1, t2, a1, a2, b1, b2;
  cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
  long long x = t1 * (a1 - b1);
  long long y = t2 * (a2 - b2);
  if (x + y == 0) {
    cout << "infinity\n";
    return 0;
  }
  if ((__int128) x * (x + y) >= 0) {
    cout << 0 << '\n';
    return 0;
  }
  __int128 p = abs(x);
  __int128 q = abs(x + y);
  cout << (long long) (p / q * 2) + (p % q != 0) << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%I64d",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
#define INF                         (int)1e9
#define EPS                         1e-9
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
#define forall(i,a,b)               for(int i=a;i<b;i++)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define MOD                         1000000007
typedef long long ll;
/*For you see , each day i love you
 more.Today more than yesterday
  less than tomorrow.*/
using namespace std;

int main()
{
	ll n;cin>>n;
	ll val1 = 1 , val2 = 1 , val3 = 1;
	
	for(int i = 0;i<n;i++)
	{
		val1 = (val1 * 10)%MOD;
		val2 = (val2 * 8)%MOD;	
		val3 = (val3 * 9)%MOD;
	}
	
	cout<<(val1 + val2 - val3 - val3 + MOD + MOD)%MOD<<endl;
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i >= n; --i)
typedef long long ll;
#define mod 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

int solve(string S, int a) {
  int ans = 0;
  rep(i, 0, S.size()) {
    if((i+a) % 2) {
      if(S[i] == '0') ans++;
    } else {
      if(S[i] == '1') ans++;
    }
  }
  return ans;
}

int main() {
  string S; cin >> S;
  int ans = 1e9;
  cout << min(solve(S, 0), solve(S, 1)) << endl;
  return 0;
}


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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

int a,b;

signed main() {
    cin >> a >> b;
    cout << max(0LL, a-b-b) << endl;
}



Measured memory_bytes: 256
def main():
    import sys
    X,N=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    if not P:
        print(X)
        return
        
    P.sort()
    diff=10**5
    cand=0
    for i in range(min(X,min(P))-1,max(X,max(P))+2):
        if i not in P:
            d=abs(X-i)
            if d<diff:
                diff=d
                cand=i
    print(cand)


main()

Measured memory_bytes: 9224
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
using namespace std;
int inf = 1e9;
class UnionFind {
public:
  vector<int> data;
  vector<int> sizes;
  UnionFind(int size) {
    data.resize(size, 0);
    sizes.resize(size, 0);
    for(int i=0; i<size; i++) data[i] = i;
  }
  int find(int x) {
    if(x == data[x]) return x;
    return data[x] = find(data[x]);
  }
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if( x == y ) return;
    if( sizes[x] < sizes[y] ) swap(x, y);
    data[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }

};

int main() {

  int n, k, l;
  cin >> n >> k >> l;
  vector<int> p(k);
  vector<int> q(k);
  vector<int> r(l);
  vector<int> s(l);
  for(int i=0; i<k; i++) cin >> p[i] >> q[i];
  for(int i=0; i<l; i++) cin >> r[i] >> s[i];

  UnionFind road(n);
  for(int i=0; i<k; i++){
    p[i]--;
    q[i]--;
    road.unite(p[i], q[i]);
  }
  UnionFind rail(n);
  for(int i=0; i<l; i++){
    r[i]--;
    s[i]--;
    rail.unite(r[i], s[i]);
  }
  map< pair<int, int>, int> mp;
  for(int i=0; i<n; i++){
    mp[{road.find(i), rail.find(i)}]++;
  }
  for(int i=0; i<n; i++){
    if( i == n-1 ) cout << mp[{road.find(i), rail.find(i)}] << endl;
    else cout << mp[{road.find(i), rail.find(i)}] << " ";
  }


  return 0;
}


Measured memory_bytes: 16640
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;


void solve(){
  ll n,a,b;
  cin>>n>>a>>b;
  if(a==0&&b==0){
    cout<<0;
    return;
  }
  cout<<n/(a+b)*a+min(a,n%(a+b));
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


Measured memory_bytes: 256
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

dp = [False]*(K+1)

for i in range(K+1):
    f = False
    for j in range(N):
        if A[j] > i:
            break
        if dp[i-A[j]]:
            continue
        f = True
    dp[i] = f
    
if dp[K]:
    ans = "First"
else:
    ans = "Second"
        
print(ans)

Measured memory_bytes: 44012
#include<bits/stdc++.h>
#define N (100005)
#define ll long long
#define itn int
#define scafn scanf
#define debug(x) cerr<<#x<<" : "<<x<<endl
#define CM cerr<<(&MOP2-&MOP1)/1024.0/1024.0<<endl
using namespace std;
template <class T> inline T Min(T x, T y){
    return x<y?x:y;
}
template <class T> inline T Max(T x, T y){
    return x>y?x:y;
}
bool MOP1;
int n,m;
struct node{
	int cost,val;
	bool operator < (const node &a)const{
		return val==a.val?cost>a.cost:val>a.val;
	}
	void read(){
		scanf("%d%d",&cost,&val);
	}
	void deb(){
		printf("%d %d\n",cost,val);
	}
}A[N];
int f[N];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int ans;
bool MOP2;
int main(){	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)A[i].read();
	for(int i=1;i<=m+1;i++)f[i]=i;
	sort(A+1,A+1+n);
//	for(int i=1;i<=n;i++)A[i].deb();
	for(int i=1;i<=n;i++){
		int c=A[i].cost;
		int v=A[i].val;
		if(c>m)continue;
		int now=find(f[c]);
		if(now>m)continue;
		ans+=v,f[now]++;
	}
	printf("%d\n",ans);
	return 0;
}






Measured memory_bytes: 1408
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
 
using namespace std;
 
#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
 
template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }
 
typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx3[4] = {1, 0, -1, 0};
int dy3[4] = {0, 1, 0, -1};
int dx[8] = {1, 0, -1, -1, -1, 0, 1, 1};
int dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dx2[16] = {0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1};
int dy2[16] = {2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2};
struct state{
  int x, y, S;
  int c;
  state() {}
  state(int x, int y, int S, int c) : x(x), y(y), S(S), c(c) {}
  bool operator < (const state& s) const {
    return c > s.c; //rev
  }
};
 
int main(){
  int W, H;
  while(cin>>W>>H && (W||H)){
    vector<string> grid(H);
    REP(y, H) cin>>grid[y];
    int cnt = 0;
    REP(y, H)REP(x, W)if(grid[y][x] == 'M'){
      grid[y][x] = cnt + '0';
      cnt++;
    }
    const int goalS = (1<<cnt) - 1;
    int move[100][100] = {};
    REP(y, H)REP(x, W) move[y][x] = 1;
    REP(y, H)REP(x, W){
      if(grid[y][x] == '#'){
        REP(r, 8){
          int nx = x + dx[r], ny = y + dy[r];
          if(nx >= 0 && ny >= 0 && nx < W && ny < H){
            move[ny][nx] = 3;
          }
        }
        REP(r, 16){
          int nx = x + dx2[r], ny = y + dy2[r];
          if(nx >= 0 && ny >= 0 && nx < W && ny < H){
            move[ny][nx] = max(move[ny][nx], 2);
          }
        }
      }
    }
    int dist[1<<5][100][100];
    priority_queue<state> que;
    REP(y, H)REP(x, W)REP(i, 1<<5)dist[i][y][x] = INF;
    REP(y, H)REP(x, W)if(grid[y][x] == 'S'){
      dist[0][y][x] = 0;
      que.push(state(x, y, 0, 0));
    }
    int ans = INF;
    while(!que.empty()){
      state s = que.top(); que.pop();
      if(s.S == goalS && grid[s.y][s.x] == 'G'){
        ans = s.c;
        break;
      }
      REP(r, 4){
        int nx = s.x + dx3[r];
        int ny = s.y + dy3[r];
        if(!(nx >= 0 && ny >= 0 && nx < W && ny < H)) continue;
        if(grid[ny][nx] == '#') continue;
        int nc = s.c + move[s.y][s.x];
        int nS = s.S;
        if(grid[ny][nx] <= '5' && grid[ny][nx] >= '0'){
          nS = nS | (1<<(grid[ny][nx]-'0'));
        }
        if(dist[nS][ny][nx] > nc){
          dist[nS][ny][nx] = nc;
          que.push(state(nx, ny, nS, nc));
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 4504
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if((a+b)>=(a-b)&&(a+b)>=(a*b)){
        cout<<a+b<<endl;
    }else if((a+b)<=(a-b)&&(a-b)>=(a*b)){
        cout<<a-b<<endl;
    }else cout<<a*b<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

vector<ll> divisor(ll n)
{
    vector<ll> ret;
    for (ll i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}

ll gcd(ll a, ll b)
{
    ll tmp;
    ll c;
    if (a < b)
    {
        tmp = a;
        a = b;
        b = tmp;
    }

    do
    {
        c = a % b;
        a = b;
        b = c;
    } while (c != 0);

    return a;
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

int main(void)
{
    ll a, b, k;

    cin >> a >> b >> k;

    ll x = gcd(a, b);

    vector<ll> d;
    d = divisor(x);

    cout << d[d.size() - k] << endl;
}


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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

int main()
{
		int K;
	string S;
	cin >> K >> S;
	if (S.size()<=K) {
		ce(S)
	}
	else {
		ce(S.substr(0,K) + "...")
	}
    return 0;
}



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

int main() {
  int N;
  cin >> N;
  vector<int> A(N),B(N),C(N-1);
  for (int i=0 ; i<N ; i++)
    cin >> A.at(i);
  for (int i=0 ; i<N ; i++)
    cin >> B.at(i);
  for (int i=0 ; i<N-1 ; i++)
    cin >> C.at(i);
  
  int MANZOK=0;
  for (int i=0 ; i<N ; i++){
     MANZOK+=B.at(A.at(i)-1);
    if (i==0)
      continue;
    if (A.at(i)-A.at(i-1)==1){
     MANZOK+=C.at(A.at(i)-2);
    }
  }
  cout << MANZOK << endl;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
ll A[101010];
ll B[101010];
ll hoge() {
	int i;
	ll ret=0;
	FOR(i,N-1) ret+=abs(B[i]-B[i+1]);
	//FOR(i,N) cout<<B[i]<<" ";
	//cout<<endl;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	ll ma=0;
	ll ret=0;
	if(N%2==0) {
		FOR(i,N/2) {
			B[i*2+1]=A[i];
			B[i*2]=A[i+N/2];
		}
		ma=max(ma,hoge());
	}
	else {
		B[N-1]=A[N/2];
		FOR(i,N/2) {
			B[(i*2)+1]=A[i];
			B[(i*2)]=A[N/2+1+i];
		}
		ma=max(ma,hoge());
		FOR(i,N/2) {
			B[(N/2-1-i)*2]=A[i];
			B[1+(i*2)]=A[N/2+1+i];
		}
		ma=max(ma,hoge());
	}
	cout<<ma<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main(){
int A,B;
  cin >> A >> B;
  
  if(A>=10 || B>=10)
    cout <<"-1" << endl;
  else
    cout << A*B << endl;
  
}

Measured memory_bytes: 256
#define P(x) cout << #x" = " << x << endl
#define PP(x, y) cout << "("#x", "#y") = (" << x << ", " << y << ")" << endl
#define PPP(x, y, z) cout << "("#x", "#y", "#z") = (" << x << ", " << y << ", " << z << ")" << endl

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> to(100000, vector<int>());
vector<vector<int>> from(100000, vector<int>());
vector<int> tsorted;
int ind[100000];
bool visited[100000];

void tsort(int node) {
    visited[node] = true;
    for (int nnode : to[node]) {
        if (visited[nnode]) continue;
        tsort(nnode);
    }
    ind[node] = tsorted.size();
    tsorted.push_back(node);
}

int n, m, e;
int main(){
    cin >> n >> m;
    e = n + m - 1;
    for (int i = 0; i < e; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        to[a].push_back(b);
        from[b].push_back(a);
        visited[i] = false;
    }

    for (int i = 0; i < e; ++i) {
        if (!visited[i]) tsort(i);
    }
    // for (int node: tsorted) {
    //     cout << node << " ";
    // }
    // for (int i = 0; i < n; ++i) {
    //     cout << tsorted[i] << " " << ind[i] << endl;
    // }

    for (int i = 0; i < n; ++i) {
        vector<int> fromi = from[i];
        // P(fromi.size());
        if (fromi.size() == 0) {
            cout << 0 << endl;
            continue;
        }
        int minind = n;
        int mini;
        // P(i);
        for (int par: fromi) {
            // P(par);
            if (minind > ind[par]) {
                minind = ind[par];
                mini = par;
            }
        }
        cout << mini + 1 << endl;
    }
}

Measured memory_bytes: 15996
#include "bits/stdc++.h"

using namespace std;

void solve()
{
	int A, B, C;
	cin >> A >> B>> C;
	cout << min(C, B/A) << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 764
#include<stdio.h>

int main() {
   int a,b,c;
   scanf("%d", &a);
   scanf("%d", &b);
   scanf("%d", &c);
   int i,tmp;
   for(i=0; i<10; i++){
       tmp = a*c - b;
       c=tmp;
       printf("%d\n", tmp);
   }
}

Measured memory_bytes: 128