akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

typedef long long LL;
typedef unsigned long long ULL;

#define debug printf("fuck %d\k", __LINE__);

inline LL read() {
	LL res = 0, bo = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if (ch == '-') bo = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { res = (res << 1) + (res << 3) + ch - '0'; ch = getchar(); }
	return bo * res;
}

template<typename T> void read(T &x) { x = read(); }
template<typename T, typename ...Argv> void read(T &a, Argv &...argv) { read(a); read(argv...); }

const int N = 1010;
int a[N][N], k;

int main() {
	read(k);
	if (k <= 500) {
		std::cout << k << std::endl;
		for (int i = 1; i <= k; ++ i) {
			for (int j = 1; j <= k; ++ j) {
				std::cout << i << ' ';
			}
			puts("");
		}
		return 0;
	}
	std::cout << 500 << std::endl;
	int n = 500;
	for (int i = 1; i <= n; ++ i) {
		int x = i, y = 1;
		for (int j = 1; j <= n; ++ j) {
			if (!x) x = n;
			if (!y) y = n;
			a[x][y] = i;
			-- x; -- y;
		}
	}
	int tot = k - n;
	for (int i = 1; i <= tot; ++ i) {
		int x = i, y = 1;
		for (int j = 1; j <= n; ++ j) {
			if (!x) x = n;
			if (!y) y = n;
			if (j & 1) a[x][y] = i + n;
			-- x; -- y;
		}
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			std::cout << a[i][j] << ' ';
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 3200
n, m = map(int, input().split())
lis = []

for i in range(n):
    a, b = map(int, input().split())
    lis.append([a, b])
lis.sort()
c = 0
ans = 0
while True:
    if m <= lis[c][1]:
        ans += m * lis[c][0]
        break
    else:
        ans += lis[c][0] * lis[c][1]
        m -= lis[c][1]
        c +=1
   
print(ans)

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

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define read        freopen("in.txt", "r", stdin)
#define write       freopen("out.txt", "w", stdout)
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define PB push_back
#define F first
#define S second
#define MP make_pair

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

const int M = 998244353 ;
const int MAX = (2e5) + 10;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int ara[MAX];
multiset<pii> msota;

void update(int x,int y) {
    if(x > y) swap(x, y);
    msota.insert( {x, y} );
}

pii getMax() {
    return *(msota.rbegin());
}

void eraseMax() {
    msota.erase(getMax());
}

int main() {
    ios::sync_with_stdio(false);
    //read;
    //write;

    int n;

    cin >> n;
    FOR(i,0,n-1) {
        cin >> ara[i];
    }

    sort(ara, ara + n);
    reverse(ara, ara + n);

    ll prin  = 0;
    FOR(i,1,n-1) {
        prin += ara[ (i/2) ];
    }
    cout << prin << endl;
    return 0;
}



Measured memory_bytes: 4428
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const int mod=1000000007;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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


// ll memo[2020][2020];
// int pascal_triangle(){
//   for(int i = 0; i < 2020; i++){
//     for(int j = 0; j < i+1; j++){
//       if(j == 0 || j == i) memo[i][j] = 1;
//       else{
// 	memo[i][j] = (memo[i-1][j-1]+memo[i-1][j]);
//       }
//     }
//   }
//   return 0;
// }


int factrial(int n){
  if(n == 0) return 1;
  return n*factrial(n-1);
}

int divisor(int a){
  int cnt = 0;
  for(int i=1; i <= a; i++) if(a%i == 0) cnt++;
  return cnt;
}

// int comb(int n, int k){
//   return fact(n) / (fact(n-k)*fact(k));
// }

vector<pair<int,pair<int,int>>> v;

int main(){
  int N;
  cin >> N;
  int ans= 0;
  for(int i = 1; i <= N; i+=2){
    if(divisor(i) == 8) ans++;
  }
  cout << ans << endl;

}
  




Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
int main(){
int n,m,cnt;
int x[2021];
int a[101];
cin >> n;
for(int i=1;i<=n;i++){
cin >> x[i];
}
cin >> m;
for(int i=1;i<=m;i++){
cin >> a[i];
}
for(int i=1;i<=m;i++){
	cnt=0;
	if(x[a[i]]==2019) continue;
	for(int j=1;j<=n;j++){
		if(x[a[i]]+1==x[j]){cnt++;}
	}	
	if(cnt==0) x[a[i]]++;
}
for(int i=1;i<=n;i++){
	cout << x[i] << endl;
}
return 0;
}



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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    vector<int> a(3);
    REP(i, 3)cin >> a[i];
    sort(ALL(a), greater<int>());
    cout << abs(a[0] - a[1]) + abs(a[1] - a[2]) << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fu(i,r,t) for(int i=r;i<=t;i++)
#define fd(i,r,t) for(int i=r;i>=t;i--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl '\n'
using namespace std;
const int INF=1e17+5;
const int maxn=1e5+5;
int n,m,a[maxn],b[maxn],ans,sum;
vector<int>t;
int32_t main()
{
    IOS;
    cin>>n;
    fu(i,1,n)cin>>a[i];
    int key=1;
    fu(i,1,n)
    {
        if(key)
        {
            ans+=a[i];
            key=!key;
        }else{
            ans-=a[i];
            key=!key;

        }
    }
    b[n]=ans;
    b[0]=b[n];
    fu(i,1,n-1)
    {
        b[i]=2*a[i]-b[i-1];
    }
    cout<<b[n]<<" ";
    fu(i,1,n-1)
    {
        cout<<b[i]<<" ";
    }
    return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int main () {
  string S;
  cin >> S;
  vector<long> data(26);
  for(int i = 0; i < S.size(); i++){
    data.at(S.at(i) - 'a')++;
  }
  if(S.size() == 26){
    for(int i = 25; i >= 0; i--){
      for(int j = S.at(i) - 'a' + 1; j < 26; j++){
        if(data.at(j) == 0){
          for(int k = 0; k < i; k++){
            cout << S.at(k);
          }
          cout << (char)('a' + j) << endl;
          return 0;
        }
      }
      data.at(S.at(i) - 'a')--;
    }
    cout << -1 << endl;
  } else {
    for(int i = 0; i < 26; i++){
      if(data.at(i) == 0){
        cout << S << ((char)('a' + i)) << endl;
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] H = new int[N];
		for (int i = 0; i < N; i++) {
			H[i] = sc.nextInt();
		}
		int[] T = new int[N];
		for (int i = 0; i < N; i++) {
			T[i] = 1;
		}
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			if (H[a] < H[b]) {
				T[a] = 0;
			} else if (H[a] > H[b]) {
				T[b] = 0;
			} else {
				T[a] = 0;
				T[b] = 0;
			}
		}
		int ans = 0;
		for (int t : T) {
			ans += t;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 59808
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPL(i,f,n) for(int i=f, i##_len=(n); i<i##_len; ++i)
typedef long long ll;

int main() {
	string MARCH = "MARCH";
	cin.tie(0);
	ios::sync_with_stdio(false);

	int A,B,C;
	cin >> A >> B >> C;
	int M = max(max(A, B),C);
	int ans;
	if (M % 2 == (A + B + C) % 2) {
		ans = (3 * M - (A + B + C)) / 2;
	}
	else {
		ans = (3 * (M+1) - (A + B + C)) / 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

int root(int x, vector<int>& par){
  if(par[x] < 0){
    return x;
  }else{
    return par[x] = root(par[x],par);
  }
}

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

int pow(int x, int n){
  if(n == 0)return 1;
  if(n % 2 == 0)return pow(x * x % MOD, n/2);
  else return x * pow(x, n-1) % MOD;
}


signed main(){
  int l,r;cin>>l>>r;
  if(r-l >= 2019){
    cout << 0 << endl;
    return 0;
  }
  int ret = INF;
  repd(i,l,r+1){
    repd(j,i+1,r+1){
      ret = min(ret, (i%2019)*(j%2019)%2019);
    }
  }
  cout << ret << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;cin >> s;
	int n = s.length();
	int k = 1,r = n;
	for (int i=1; i<n; i++) {
		if (s[i] != s[i-1]) {
			r = min(r, max(i, n-i));
		}
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
long long n10 = 1, n9 = 1, n8 = 1, ans, l= 1000000007, n;
int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++) 
	{
        n10 = n10 * 10 % l;
        n9 = n9 * 9 % l;
        n8 = n8 * 8 % l;
    }
 
    ans = n10 - (n9 * 2 - n8);
    
    while (ans < 0) 
		ans += l;
	
    cout << ans << endl;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ld long double
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
// const ll INF = 1LL << 30;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

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

int main() {
    ll n; cin >> n;
    string ans = "";
    while(n){
        ll a = n % 26;
        if(a == 0) ans.push_back('z');
        else ans.push_back(char('a'+a-1));

        ll b = n;
        n /= 26;
        if(b%26 == 0) n--;
    }
    reverse(ALL(ans));
    co(ans);

    return 0;
}


Measured memory_bytes: 3628
using System;
using System.Linq;

namespace aizu
{
    class OnlineJudge
    {
        static void Main()
        {
            string data;
            while((data = Console.ReadLine()) != null) {
                Console.WriteLine(data.Split().Select(p => int.Parse(p)).Sum().ToString().Length);
            }
        }
    }
}

Measured memory_bytes: 5884
/*alurquiza*/
//https://matcomgrader.com/problem/9623/dictionary-search/
//Segment Tree + binary search
#include <bits/stdc++.h>

using namespace::std;

typedef long long LL;
const int MOD = 1e9 + 7;

LL pot(int base,int exp){
	if(exp == 1)
		return base;
	if(exp % 2 == 0){
		LL aux = pot(base,exp / 2);
		return aux * aux % MOD;
	}
	return pot(base,exp - 1) * base % MOD;
}

long long fact(int ini,int fin){
	LL r = 1;
	while(ini <= fin)
		r = r * ini++ % MOD;
	return r;
}

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

	// freopen("milkvisits.in","r",stdin);
	// freopen("milkvisits.out","w",stdout);

	int N;
	cin >> N;

	int a,b;
	cin >> a >> b;

	LL sol = (pot(2,N) - 1 + MOD) % MOD;
	LL tmp1 = fact(N - a + 1,N)	* pot(fact(1,a),MOD - 2) % MOD;
	LL tmp2 = fact(N - b + 1,N)	* pot(fact(1,b),MOD - 2) % MOD;

	sol = ((sol - tmp1 - tmp2) + 2 * MOD) % MOD;

	cout << sol << '\n';

	return 0;
}

//g++ -std=c++11 -Wall DS.cpp -o main

Measured memory_bytes: 256
#inport
import sys
import numpy as np
from collections import deque


#input
N,M = [int(x) for x in sys.stdin.readline().split()]
g = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    g[a].append(b)
    g[b].append(a)



quetmp = deque([1])
d = [None] * (N+1)
d[1] = 0
num_crew = 1
while quetmp:
    v = quetmp.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v
            quetmp.append(i)
            num_crew = num_crew + 1

if num_crew == N:
    print('Yes')
    for i in range(N-1):
        print(d[i+2])
else:
    print('No')

Measured memory_bytes: 51756
#include<iostream>
using namespace std;
int main() {
	int H, W;
	cin >> H >> W;
	bool goodh[110], goodw[110];

	char a[110][110];
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> a[i][j];
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			if (a[i][j] == '#') {
				goodh[i] = true;
				goodw[j] = true;
			}
	for (int i = 0; i < H; i++)
		if (goodh[i]) {
			for (int j = 0; j < W; j++)
				if (goodw[j])
					cout << a[i][j];
			cout << endl;
		}
	return 0;
}



Measured memory_bytes: 256
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,Q;
    cin >> N >> Q;
    ll a[100010];
    rep(i,0,N) cin >> a[i];
    sort(a, a+N);
    rep(i,0,Q){
        ll l,r;
        cin >> l >> r;
        ll p1 = upper_bound(a, a+N, r) - a;
        ll p2 = lower_bound(a, a+N, l) - a;
        print(p1 - p2);

    }

    

}


Measured memory_bytes: 3908
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
  long long int n,m;
  while(cin >>n>>m,n||m){
    vector<pair<long long int, long long int> > road;
    for(int i=0,a,b; i<n; i++){
      cin >>a>>b;
      road.push_back(make_pair(b,a));
    }
    long long int ans = 0;
    sort(road.begin(),road.end());
    for(int i=n-1; i>=0; i--){
      if(road[i].second < m){m-=road[i].second;road[i].second = 0;}
      else{road[i].second-=m;m = 0;}
      ans+=road[i].first*road[i].second;
    }
    cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1584
// template.cpp

// Defines.
//#define DEBUG
#define NUMBER_OF_DIGITS 6

// Includes.
#include <bits/stdc++.h>

#ifdef DEBUG
#include <chrono>
#endif

// Usings.
using namespace std;

// Main function.
int main()
{
#ifdef DEBUG
	chrono::system_clock::time_point start, end;
	
	start = chrono::system_clock::now();
#endif
	
	// settings.
	ios::sync_with_stdio(false);
	
	//cout << fixed;
	//cout << setprecision(NUMBER_OF_DIGITS);
	
	// logic.
	int n;
	cin >> n;
	
	int xs[n];
	int ys[n];
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		
		int x = 0;
		int y = 0;
		for (int j = 0; j < a; j++)
		{
			int x_in, y_in;
			cin >> x_in >> y_in;
			
			x |= (1 << (x_in - 1));
			if (y_in == 1)
			{
				y |= (1 << (x_in - 1));
			}
			else
			{
				y &= (~(1 << (x_in - 1)));
			}
		}
		
		xs[i] = x;
		ys[i] = y;
	}
	
	int max = 0;
	for (int i = 0; i < (1 << n); i++)
	{
		bool flag = true;
		for (int j = 0; j < n; j++)
		{
			if ((i & (1 << j)) != 0)
			{
				if (((xs[j] & ys[j]) & i) != (xs[j] & ys[j]))
				{
					flag = false;
					break;
				}
				
				if (((xs[j] & (~ys[j])) & (~i)) != (xs[j] & (~ys[j])))
				{
					flag = false;
					break;
				}
			}
		}
		
		if (flag == true)
		{
			if (__builtin_popcount(i) > max)
			{
				max = __builtin_popcount(i);
			}
		}
	}
	
	cout << max << endl;

#ifdef DEBUG
	end = chrono::system_clock::now();
	
	double elapsed = chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
	cout << elapsed << "[ms]" << endl;
#endif
	
	return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<string>

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

int w,h;
std::string f[20];
int cnt;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

void rec(int x, int y){
	int mx, my;

	f[y][x] = '#';
	cnt++;

	rep(i,4){
		mx = x + dx[i];
		my = y + dy[i];

		if(mx < 0 || mx >= w)continue;
		if(my < 0 || my >= h)continue;
		if(f[my][mx] != '.')continue;
		rec(mx, my);
	}
}




int main(){
	while(std::cin >> w >> h, (w||h)){
		rep(i,h){
			std::cin >> f[i];
		}
		cnt = 0;
		rep(i,h){
			rep(j,w){
				if(f[i][j] == '@')rec(j,i);
			}
		}
		std::cout << cnt << std::endl;
	}
	return 0;
}

Measured memory_bytes: 0
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {

	var a int

	fmt.Scan(&a)

	for i := 1; i <= a; i++ {
		if i%3 == 0 || strings.Index(strconv.Itoa(i), "3") != -1 {
			fmt.Printf(" %d", i)
		}
	}

	fmt.Print("\n")

}

//a, _ := strconv.ParseFloat(tmp[0], 64)



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

using namespace std;

int main(){

    int N, M;
    cin >> N >> M;

    map <int, int> count;

    for (int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        count[a] ++;
        count[b] ++;
    }

    for (int i = 1; i <= N; i++){
        cout << count[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include<string.h>
#include <math.h>
#include <stack>
#define ll long long
using namespace std;
typedef struct Node {
	ll a, b;
	bool operator<(const Node &o)const {
		if (a == o.a)
			return b < o.b;
		return a < o.a;
	}
};
Node arr[100010];
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld", &arr[i].a, &arr[i].b);
	}
	ll cnt = 0;
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		if (arr[i].b < m) {
			cnt += arr[i].b * arr[i].a;
			m -= arr[i].b;
		}
		else {
			cnt += arr[i].a * m;
			break;
		}
	}
	printf("%lld\n", cnt);
}

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

int main(){
  int N ; 
  cin >>N ; 
  vector<int> d(N) ; 
  for(int i = 0 ; i < N ; i++) cin >> d.at(i) ; 
  
  sort(d.begin(),d.end()) ; 
  
  int cnt = 0 ;  
  
  for(int i = 0 ; i < N-1 ; i++){
    if(d.at(i) == d.at(i+1)){
      cnt++ ; 
    }
  }
  cout << N -  cnt << endl ; 
}

Measured memory_bytes: 3612
#include <iostream>
#include <stdio.h>
#include <string.h>
#define Max 100005
using namespace std;
char a[Max];
int main()
{
    scanf("%s",a);
    int len=strlen(a),k=99999;
    for(int i=1;i<len;i++)
    {
    	if(a[i] != a[i-1])
    	{
			k=min(k,max(i,len-i));
    	}
    }
    printf("%d\n",k==99999?len:k);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#define ll long long
#define INF 0x3f3f3f3f
#define SIS std::ios::sync_with_stdio(false)
using namespace std;

int main()
{
    string s;
    while(cin>>s)
    {
        if(s[0]==s[1]&&s[1]==s[2]&&s[0]==s[2])
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

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

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

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    void solve() {
        input();
        int N, A, B;
        cin >> N >> A >> B;
        int ans = min(B, A * N);
        cout << ans << endl;

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(n,a) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

int dp[1100]={};
int a[10]={1,5,10,50,100,500};

void f(int n){
  int k = 1000-n;
  cout<<dp[k]<<endl;
}

int main(){
  int n;
  fill(dp,dp+1100,inf);
  dp[0]=0;
  rep(i,1100){
    rep(j,6){
      if(i-a[j]<0) continue;
      dp[i]=min(dp[i],dp[i-a[j]]+1);
    }
  }
  while(1){
    cin>>n;
    if(n==0) break;
    f(n);
  }
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
const long mod = 1e9 + 7;
int main(){
    int h,d;
    cin >> h >> d;
    char c[h][d];
        for(int i=0;i<h;i++){
        for(int j=0;j<d;j++){
            cin >> c[i][j];
        }
    }
    int dp[h+1][d+1]= {0,};
    for(int i=1;i<=h;i++){
        if(c[0][i-1] == '.')
            dp[1][i] = 1;
        else
        {
            break;
        }
        

    }
    for(int i=1;i<=d;i++)
    {
        if (c[i-1][0] == '.')
            dp[i][1] = 1;
        else
        {
            break;
        }
    }
    for(int i=2;i<=h;i++){
        for(int j=2;j<=d;j++){
                if(c[i-1][j-1] == '.')
                     dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod ;
                else
                {
                    dp[i][j] = 0;
                }
                
        }
    }
    cout<<dp[h][d]<<endl;
    
    
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
int waru10(int n){
  int sum=0;
  while(n>0){
    sum+=n%10;
    n/=10;
  }
  return sum;
}
int main()	{
  int n,a,b;
  cin>>n>>a>>b;
  int sum;
  int am=0;
  rep(i,n){
    sum=waru10(i);
  if(a<=sum && sum<=b)
    am+=i;
  }
  cout<<am<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
// #include <numeric>
#include <complex>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define repr(i, a, b) for(int i=int(a); i>=int(b); i--)
#define reps(i,n) for(int i=1;i<=int(n);++i)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define iceil(x,y) (x+y-1)/y
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define all(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;
typedef long long int ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII> PP;

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

int main()
{
	FAST;

	int N,T;
	cin >> N >> T;
	int ci,ti;
	int  ans=INT_MAX;
	rep(i,N) {
		cin >> ci >> ti;
		if (ti <= T) {
			if (ci < ans) ans = ci;
		}
	}
	if (ans == INT_MAX) cout << "TLE\n";
	else cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n,count = 0,check = 0;
  scanf("%d",&n);
  int a[n];
  for(int i=0; i < n; ++i){
    scanf("%d",&a[i]);
  }
  while(1){
    for(int i=0; i < n; ++i){
      if(a[i]%2 == 1){
        check = 1;
        break;
      }else a[i]/=2;
    }
    if(check == 1) break;
    else count++;
  }
  printf("%d",count);
  return 0;
}



Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>

using namespace std;
typedef long long ll;

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

int main() {

    ll N;
    cin >> N;
    vector<ll> P(N);
    vector<ll> Q(N);
    rep(i,N) cin >> P[i];
    rep(i,N) cin >> Q[i];
    vector<ll> S(N);
    rep(i,N) S[i] = i+1;
    ll X,Y;
    ll i = 0;
    do {
        if(S==P) X = i;
        if(S==Q) Y = i;
        i++;
    } while(next_permutation(S.begin(), S.end()));
    cout << abs(Y-X) << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	aca := make([]int, n)
	waa := make([]int, n)
	for i := 0; i < m; i++ {
		var p int
		var s string
		fmt.Scan(&p, &s)
		if aca[p-1] == 0 && s == "AC" {
			aca[p-1]++
		} else if aca[p-1] == 0 && s == "WA" {
			waa[p-1]++
		}
	}
	wa := 0
	ac := 0
	for i := 0; i < n; i++ {
		ac += aca[i]
		if aca[i] != 0 {
			wa += waa[i]
		}
	}
	fmt.Println(ac, wa)
}


Measured memory_bytes: 5504
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false);
	string S,T;cin >> S >> T;
	T.pop_back();
	cout << (S == T ? "Yes\n" : "No\n");
	cin.tie(nullptr);
}


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

struct tick {
	int t,x,y;
	bool operator <(const tick &x) const {
		return t < x.t;
	}
} t[100009];
int main()
{
	int n;
	scanf("%d",&n);
	t[0].t = 0;
	t[0].x = 0;
	t[0].y = 0;
	for(int i = 1;i <= n;++i) {
		scanf("%d%d%d",&t[i].t,&t[i].x,&t[i].y);
	}
	std::sort(t,t+n+1);
	for(int i = 1;i <= n;++i) {
		int dist = abs(t[i].x - t[i-1].x) + abs(t[i].y - t[i-1].y);
		if(((t[i].t - t[i-1].t) + dist) % 2 == 1 || dist > t[i].t - t[i-1].t) {
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
}

Measured memory_bytes: 1408
#include <iostream>
using namespace std;
int main() {
    int n, l;
    cin >> n >> l;
    if (l > 0) {
        cout << (n*(2*l+n-1))/2 - l << endl;
    } else if (l < 1-n) {
        cout << ((n-1)*(2*l+n-2))/2 << endl;
    } else {
        cout << (n*(2*l+n-1))/2 << endl;
    }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;


/*----------------------------------------------------------------*/
signed main(){

    string s;
    cin >> s;
    
    int mx = 0;
    int a,b;
    for(int i = 0;i < s.size();i++){
        int cnt = 0;
        rep(j,s.size()){
            if(i+j >= s.size() || (s[i+j] != 'A' && s[i+j] != 'T' && s[i+j] != 'C' && s[i+j] != 'G'))break;
            cnt++;
        }
        mx = max(mx,cnt);
    }
    cout << mx << endl;
    

	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://ddcc2020-qual.contest.atcoder.jp/tasks/ddcc2020_qual_b
// rm -r -f test;oj dl https://abc122.contest.atcoder.jp/tasks/abc122_b

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char const *argv[]) {
  string s1,s2;
  for(int i=0;i<4;i++){
    char c;
    cin>>c;
    if(i<2){
      s1.push_back(c);
    }else{
      s2.push_back(c);
    }
  }

  if((s1<="12"&&s1!="00")&&(s2<="12"&&s2!="00")){
    cout<<"AMBIGUOUS"<<endl;
  }else if((s1<="12"&&s1!="00")&&(s2=="00"||s2>="13")){
    cout<<"MMYY"<<endl;
  }else if((s1=="00"||s1>="13")&&(s2<="12"&&s2!="00")){
    cout<<"YYMM"<<endl;
  }else{
    cout<<"NA"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)
#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;

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;
}

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    else return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

int INF = 1e9+7;

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

int main(){
    int n;
    cin >> n;
    vector<double> p(n);
    rep(i,n) cin >> p[i];
    vector<vector<double>> dp(n+1,vector<double>(n+1,0.0));
    dp[0][0] = 1.0;
    rep(i,n) rep(j,i+1){
        dp[i+1][j] += dp[i][j]*(1.0-p[i]);
        dp[i+1][j+1] += dp[i][j]*p[i];
    }
    int m = (n+1)/2;
    double ans = 0.0;
    for(int i = m; i<=n; i++){
        ans += dp[n][i];
    }
    cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 70656
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i,x,y) for(int i=(x);i<(y);++i)
#define REP(i,x,y) for(int i=(x);i<=(y);++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll INF=1e18+7;
const int maxn=5e3+5;

int n;
int a[maxn],pos[maxn];
ll f[maxn][maxn],g[maxn][maxn];
ll A,B;

int main(){
	scanf("%d%lld%lld",&n,&A,&B);
	REP(i,1,n) scanf("%d",a+i),pos[a[i]]=i;
	REP(i,1,n) REP(j,0,n) g[i][j]=INF;
	REP(i,1,n) REP(j,1,n){
		f[i][j]=g[i-1][j];
		if(j>pos[i]) f[i][j]+=A;
		else if(j<pos[i]) f[i][j]+=B;
		g[i][j]=min(g[i][j-1],f[i][j]);
	}
	//REP(i,1,n){
		//REP(j,1,n) printf("%lld ",f[i][j]);
		//puts("");
	//}
	printf("%lld\n",g[n][n]);
	return 0;
}



Measured memory_bytes: 391552
#include <bits/stdc++.h>
using namespace std;
/* {{{ */
/*-------------------------------*/
#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 rep(i, n) for(int i = 0; i < (n); i++)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define all(i) (i).begin(),(i).end()
#define rall(i) (i).begin(),(i).end(),greater<int>()
#define PB push_back
#define pb push_back
#define mp make_pair 
#define FI first
#define SE second

#define int long long

typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<long long> llv;
typedef vector<pint> vpint;
/*-------------------------------*/
/* }}} */

int n, m;
int d[1010], c[1010];
int dp[1010][1010];

int rec(int x, int y)
{
  if (dp[x][y] != -1) return dp[x][y];
  
  int res = 0;
  
  if (x == n) res = 0;
  else if (y == m) res = 198298398;
  else res = min(rec(x + 1, y + 1) + d[x] * c[y], rec(x, y + 1));

  return dp[x][y] = res;
}

signed main(void)
{
  cin >> n >> m;
  rep(i, n) cin >> d[i];
  rep(i, m) cin >> c[i];

  memset(dp, -1, sizeof(dp));

  cout << rec(0, 0) << endl;

  return 0;
}

Measured memory_bytes: 11096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=305,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int a[N][N],n;
bool b[N][N]; 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(k!=i&&k!=j&&i!=j){
					if(a[i][j]==a[i][k]+a[k][j]) b[i][j]=1;
					else if(a[i][j]>a[i][k]+a[k][j]) return puts("-1"),0;
				}
	ll ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			if(!b[i][j]) ans+=a[i][j];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 4260
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <iomanip>
#include <sstream>
using namespace std;

int sum_digit(int n){
  if( n == 0 ) return 0;
  else return n%10 + sum_digit(n/10);
}

int main()
{
  int i,j,k,N,Y; cin >> N >> Y;
  bool OK = false;
  bool falg = false;
  
  for(i = 0; i <= N; i++){
  	for(j = 0; j <= N-i; j++){
    	k = N-i-j;
        int money = i * 10000 + j * 5000 + k * 1000;
      if(money == Y){
        OK = true;
      }
      if(OK) break;
    }
    if(OK) break;
  }
  
  if(OK) cout << i << ' ' << j << ' ' << k << endl;
  else cout << -1 << ' ' << -1 << ' ' << -1 << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;

int main() {
  int A, B, C; cin >> A >> B >> C;
  int K; cin >> K;
  while (K >= 0) {
    if (A >= B) B *= 2;
    else if (B >= C) C *= 2;
    else break;
    --K;
  }
  if (K >= 0) cout << "Yes" << endl;
  else        cout << "No" << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
long double const pi = std::acos(-1.0L);
typedef pair<int,int> P;
const int INF = 1001001001;

int main() {
  string s;
  cin >> s;
  if(s[0]<91){
    cout << "A" << endl;
  }
  else cout << "a" << endl;
  return 0;
}

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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;
#define INF (1ll<<60)

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(A v) {
bool first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int H, W, K;
const ll MOD = 1000000007;
ll dp[105][10];
ll dp1[2000][10];

ll rec1(int b, int i) {
    if (i >= W) return 1;
    if (dp1[b][i] != -1) return dp1[b][i];
    if (b & (1 << i)) {
        return dp1[b][i] = rec1(b, i + 1);
    } else {
        return dp1[b][i] = (rec1(b, i + 1) + rec1(b, i + 2)) % MOD;
    }
}

ll rec(int h, int w) {
    if (h == H + 1 && w == K) return 1;
    if (h == H + 1) return 0;
    if (dp[h][w] != -1) return dp[h][w];
    ll ans = 0;

    if (w < W) {
        int b = 0;
        if (w > 1) b |= (1 << (w - 1));
        b |= (1 << w);
        b |= (1 << (w + 1));
        ll c = rec1(b, 1);
        ans = (ans + ((c * rec(h + 1, w + 1)) % MOD)) % MOD;
    }

    if (w > 1) {
        int b = 0;
        b |= (1 << (w - 1));
        b |= (1 << w);
        b |= (1 << (w - 2));
        ll c = rec1(b, 1);
        ans = (ans + ((c * rec(h + 1, w - 1)) % MOD)) % MOD;
    }

    int b = 0;
    if (w > 1) b |= (1 << (w - 1));
    b |= (1 << w);
    ll c = rec1(b, 1);
    ans = (ans + ((c * rec(h + 1, w)) % MOD)) % MOD;

    return dp[h][w] = ans;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> H >> W >> K;
    memset(dp, -1, sizeof(dp));
    memset(dp1, -1, sizeof(dp1));
    // int b = 0;
    // b |= (1 << 1);
    // b |= (1 << 2);
    // cout << rec1(b, 1) << endl;
    cout << rec(1, 1) << '\n';
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	void solve() {
		using intv = vector<int>;

		int N, M, X;
		cin >> N >> M >> X;

		intv C( N );
		vector<intv> A( N, intv( M ) );
		for( int i = 0; i < N; ++i ) {
			cin >> C[i];
			for( int j = 0; j < M; ++j ) { cin >> A[i][j]; }
		}

		int ans = INT_MAX;
		int ebits = 1 << N;
		for( int bt = 0; bt < ebits; ++bt ) {
			intv k( M );
			int cost = 0;
			for( int i = 0; i < N; ++i ) {
				if( (bt>>i) & 1 ) {
					cost += C[i];
					for( int j = 0; j < M; ++j ) { k[j] += A[i][j]; }
				}
			}

			bool ok = true;
			for( int i = 0; i < M; ++i ) {
				if( k[i] < X ) {
					ok = false;
					break;
				}
			}
			if( ok && cost < ans ) { ans = cost; }
		}

		cout << (ans != INT_MAX ? ans : -1) << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();
	return 0;
}


Measured memory_bytes: 3676
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>

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

int gcd(int a, int b) {
	int c;

	if (a < b) {
		a += b; b = a - b; a -= b;
	}

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

	return a;
}

int main() {

	int N, X, x[112345];

	scanf("%d %d", &N, &X);
	rep(i, N) scanf("%d", &x[i]);

	vector<int> vec(x, x + N);
	vec.push_back(X);
	sort(vec.begin(), vec.end());

	vector<int> diffs;

	rep(i, N) if (vec[i + 1] - vec[i]) diffs.push_back(vec[i + 1] - vec[i]);

	sort(diffs.begin(), diffs.end());

	int t = diffs[0];
	rep(i, diffs.size()) {
		t = gcd(t, diffs[i]);
	}

	printf("%d\n", t);
	return 0;
}

Measured memory_bytes: 1912
#include <stdio.h>
int main(){
	int H, W, N;
	scanf("%d", &H);	//row
	scanf("%d", &W);	//column
	scanf("%d", &N);	//yg item
	
	if(H < W){
		H = W;
	}
	
	if(N % H == 0){	//kalo banyak row bisa dibagi yg mau diisi
		printf("%d\n", N/H);	//print hasilnya
	}
	else if(N % H != 0) {	//kalo gabisa
		printf("%d\n", (N/H)+1);	//print hasilnya trs +1
	}
	return 0;
}

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

int main() {
  int n; cin >>n;
  vector<int>a(n);
  long long sum=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    sum+=a[i];
  }
  int t;
  cin>>t;
  for(int i=0;i<t;i++){
    int j,k;
    cin>>j>>k;
    long long kotae=sum-a[j-1]+k;
    cout<<kotae<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
b = [int(input()) for _ in range(m)]

for i in range(n):
    answer = 0
    for j in range(m):
        answer += a[i][j] * b[j]

    print(answer)


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

int main()
{
	string s,t;
	cin>>s>>t;
	
	for(int i=0;i<s.length();i++)
	{
		cout<<s[i];
		if(i<t.length())
			cout<<t[i];
	}
	
	return 0;

}

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

int main() {
  int N , sum;
  sum = 0;
  cin >> N;
  
  for(int i = 0; i < N; i++){
  	int l , r;
    cin >> l >> r;
    sum += r - l + 1 ;
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int ma=0;
	for(int i=0;i<s.size();i++){
        int cnt = 0 ;
        int cur = i;
		while(s[cur]=='A'||s[cur]=='T'||s[cur]=='C'||s[cur]=='G'){
            cnt++ ;
            cur++;
		}
        ma = max(ma,cnt) ;
	}
	cout<<ma<<endl;
  return 0 ; 
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	static BufferedReader reader;
	final static boolean MODE_DEBUG = false;
	//static field here
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		reader = new BufferedReader(new InputStreamReader(System.in));
		//code here
		String S = readLine()[0];
		String S2 = readLine()[0];
		
		if(S.length()!=S2.length()-1) {
			print("No");
			return;
		}
		for(int i=0;i<S.getBytes().length;i++) {
			if(S.getBytes()[i]!=S2.getBytes()[i]) {
				print("No");
				return;
			}
		}
		
		print("Yes");
		//String[] s = readLine();
		//print(num);
	}
	
	//functions here
	//note that all methods should be STATIC


	private static <T> int arraySearch(T needle, T[] heystack) {
		for(int i=0;i<heystack.length;i++) {
			if(needle.equals(heystack[i])) {
				return i;
			}
		}
		return -1;
	}
	private static int[] sort(int[] base) {
		int[] copy = array_copy(base);
		Arrays.sort(copy);
		return copy;
	}
	private static int[] array_copy(int[] base) {
		int[] copy = new int[base.length];
		for(int i=0;i<base.length;i++) {
			copy[i] = base[i];
		}
		return copy;
	}
	private static int[] asArray(ArrayList<Integer> ints) {
		int[] intlist = new int[ints.size()];
		for(int i=0;i<intlist.length;i++) {
			intlist[i] = ints.get(i);
		}
		return intlist;
	}
	private static String[] readLine(){
		try{
			return reader.readLine().split(" ");
		}catch(Exception e){
			e.printStackTrace();
			return new String[]{e.getMessage()};
		}
	}
	private static int[] readLineInt(){
		try{
			String[] s = readLine();
			int[] ints = new int[s.length];
			for(int i=0;i<ints.length;i++) {
				ints[i] = Integer.parseInt(s[i]);
			}
			return ints;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static byte[] readLineByte(){
		try{
			String[] s = readLine();
			byte[] bytes = new byte[s.length];
			for(int i=0;i<bytes.length;i++) {
				bytes[i] = Byte.parseByte(s[i]);
			}
			return bytes;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static char[] readLineChar(){
		try{
			String[] s = readLine();
			char[] chars = new char[s.length];
			for(int i=0;i<chars.length;i++) {
				chars[i] = (char)Integer.parseInt(s[i]);
			}
			return chars;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static void print(Object o){
		System.out.println(o);
	}
	private static void print(){
		System.out.println();
	}
	private static void printd(Object o){
		if(MODE_DEBUG)System.err.println(o);
	}
	private static void printd(){
		if(MODE_DEBUG)System.err.println();
	}
}


Measured memory_bytes: 32652
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

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

ll cal(ll a) {
	if (a == 0) return 1;
	else {
		return (a * cal(a - 1)) % MOD;
	}
}

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

	ll ans=0;
	if (n == m) {
		ans = (2 * cal(n)*cal(m))%MOD;
	}
	else if(n == m+1 || n == m-1){
		ans = (cal(n)*cal(m)) % MOD;
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    long long ans = 0;
    for (int r = 0; r <= 3000; ++r) {
        for (int g = 0; g <= 3000; ++g) {
            int left = N - r * R - g * G;
            if (left >= 0 && left % B == 0) {
                ++ans;
            }
        }
    }
    cout << ans;
    return 0;
}



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

int main()
{
    int a, b;
    cin >> a >> b;
    cout << max({a + b, a - b, a * b}) << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n,i=0;
    scanf("%d",&n);
    char s[n],t[n];
    scanf("\n");
    while((s[i]=getchar())!=' ')
    {
        i++;
    }
    i=0;
    while((t[i]=getchar())!='\n')
    {

        i++;
    }
    for(i=0;i<n;i++)
    {

         printf("%c%c",s[i],t[i]);

    }
    return 0;
}


Measured memory_bytes: 128