akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
  int h, w;
  cin >> h >> w;
  if (h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }
  //yoko*3
  int mi = w;
  //yoko*2=>tate*2
  int area[3];
  int h1 = h / 3;
  int w1 = w / 2;
  area[0] = w * h1;
  area[1] = w1 * (h - h1);
  area[2] = (w - w1) * (h - h1);
  sort(area, area + 3);
  if (area[2] - area[0] < mi) {
    mi = area[2] - area[0];
  }
  h1 = h / 3 + 1;
  area[0] = w * h1;
  area[1] = w1 * (h - h1);
  area[2] = (w - w1) * (h - h1);
  sort(area, area + 3);
  if (area[2] - area[0] < mi) {
    mi = area[2] - area[0];
  }
  //tate*3
  if (mi > h) {
    mi = h;
  }
  //tate*2=>yoko*2
  h1 = h / 2;
  w1 = w / 3;
  area[0] = w1 * h;
  area[1] = (w - w1) * h1;
  area[2] = (w - w1) * (h - h1);
  sort(area, area + 3);
  if (area[2] - area[0] < mi) {
    mi = area[2] - area[0];
  }
  w1 = w / 3 + 1;
  area[0] = w1 * h;
  area[1] = (w - w1) * h1;
  area[2] = (w - w1) * (h - h1);
  sort(area, area + 3);
  if (area[2] - area[0] < mi) {
    mi = area[2] - area[0];
  }
  cout << mi << endl;
  return 0;
}

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

#define debug(s) cout << s << endl
#define debug1(s, t) cout << s << " " << t << endl
#define debug2(s, t, u) cout << s << " " << t << " " << u << endl
#define printvec(v)       \
    for (auto &&i : v)    \
        cout << i << " "; \
    cout << endl

using namespace std;
using i64 = long long;

int main()
{
    string s;
    int q;
    cin >> s >> q;

    list<char> ls;
    for (auto &&c : s)
    {
        ls.push_back(c);
    }

    int reverse_count = 0;
    for (int i = 0; i < q; i++)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            reverse_count++;
        }
        else if (t == 2)
        {
            int f;
            cin >> f;
            if ((f == 1) ^ (reverse_count % 2 == 1))
            {
                char c;
                cin >> c;
                ls.push_front(c);
            }
            else
            {
                char c;
                cin >> c;
                ls.push_back(c);
            }
        }
    }
    if (reverse_count % 2 == 1)
        reverse(ls.begin(), ls.end());

    for (auto &&c : ls)
    {
        cout << c;
    }
    cout << endl;

    return 0;
}

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

int T[20][20],dp[1<<16];
main(){
	int N,i,j,k;
	while(cin>>N, N){
		for(i=0;i<N;i++)
			for(j=0;j<=N;j++) cin>>T[i][j];
		for(i=1;i<(1<<N);i++) dp[i]=1<<30;
		for(i=0;i<(1<<N);i++)
			for(j=0;j<N;j++)
				for(k=0;k<=N;k++)
					if(!k||i&(1<<(k-1))) dp[i|(1<<j)]=min(dp[i]+T[j][k], dp[i|(1<<j)]);
		cout<<dp[i-1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1416
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vi a(3*n);
    rep(i, 3*n) cin >> a[i];
    sort(a.begin(), a.end());
    ll ans = 0;
    for (int i = n; i < 3*n; i += 2) {
        ans += a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
n = int(input())
l = list(map(int, input().split()))
count = 0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      a = l[i]
      b = l[j]
      c = l[k]
      if a==b or b==c or c==a:
        continue
      if a + b > c and b + c > a and c + a > b:
        count += 1
print(count)

Measured memory_bytes: 9208
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for i in range(1,H+1):
  S[i] = '*'+input()+'*'


unsearched_nodes = list(range(1,H*W+1)) # 未探索ノード
distance= [10000]*(W*H+1)
#print(unsearched_nodes,distance)
previous_move = [[-1]*(W+2) for _ in range(H+2)] # 最短経路でそのノードのひとつ前に到達するノードのリスト
previous_color = [''] * (H*W+1)
distance[1] = 0 # 初期のノードの距離は0とする
if S[1][1]=='#':
  distance[1] = 1
while len(unsearched_nodes) != 0: #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
  posible_min_distance = 10001 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
  for node_index in unsearched_nodes: # 未探索のノードのループ
    #print(node_index)
    if posible_min_distance > distance[node_index]: 
      posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
      target_min_index = node_index
  #print(unsearched_nodes,target_min_index,distance)
  unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去
	
  dh = [0,1]
  dw = [1,0]
  target_h = (target_min_index-1) // W + 1
  target_w = target_min_index % W
  if target_w == 0:
    target_w = W
  for i in range(2):
    h = target_h + dh[i]
    w = target_w + dw[i]
    ind = (h-1)*W+w
    route_dis = 0
    if S[h][w]=='*':
      continue
    if S[h][w]=='#':
      if S[target_h][target_w]=='.':
        route_dis = 1
    if distance[ind] > distance[target_min_index] + route_dis:
      distance[ind] = distance[target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
      previous_color[ind] =  S[target_h][target_w]
      
  #print(distance)
print(distance[-1])
#print(*ans, sep='\n')

Measured memory_bytes: 46044
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, a, n) for (ll i = a; i < (ll)n; ++i)
#define repd(i, n) for (ll i = (n)-1; i >= 0; --i)
#define INF 10e12
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pair<string, pair<int, int>>> v(n);
    rep(i, 0, n) cin >> v[i].first >> v[i].second.first, v[i].second.second = i + 1;
    sort(all(v));
    string name;
    rep(i, 0, n)
    {
        int x = i;
        name = v[x].first;
        while (name == v[x].first)
            name = v[x].first, x++;
        for (int j = --x; j >= i; j--)
            cout << v[j].second.second << endl;
        i = x;
    }
}

Measured memory_bytes: 3548
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var aa = cin.ArrayInt(3);
            var k = cin.nextInt();
            Array.Sort(aa);
            Console.WriteLine(aa[0] + aa[1] + aa[2]*Math.Pow(2,k));
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 11348
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <cstring>
#include <functional>
//#include<unordered_map>
//#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P; 
const int N = 1000006;
//////////////////////////////

int n;
Int a[N];
Int dp[N][2];

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	dp[0][0] = 0;
	dp[0][1] = -LINF;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = max(dp[i - 1][0] + a[i], dp[i - 1][1] - a[i]);
		dp[i][1] = max(dp[i - 1][0] - a[i], dp[i - 1][1] + a[i]);
	}
	cout << dp[n][0] << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 5888
#include <cstdio>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)

typedef long long ll;

ll N;

void solve() {
  ll a, b;
  for (ll i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      a = i;
      b = N / i;
    }
  }
  int ans = 0;
  while (a > 0 || b > 0) {
    ans++;
    a /= 10;
    b /= 10;
  }
  printf("%d\n", ans);
}

void input() {
  scanf("%lld", &N);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 1

typedef long long ll;

const double PI = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;


int main(){
    vector<pair<int,int>> dish(5);
    for(int i = 0; i < 5 ; i++){
        int a;
        cin >> a;
        dish[i].first = a % 10;
        if(dish[i].first != 0) dish[i].first = 10 - dish[i].first;
        dish[i].second = a;
    }
    sort(dish.begin(),dish.end());
    int ans = 0;
    for(int i = 0; i < 5; i++){
        ans += dish[i].second + dish[i].first;
    }
    cout << ans - dish[4].first << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
xy=[]
for i in range(n):
    xy.append([int(j) for j in input().split()])
ans=0
import itertools
for l in itertools.permutations("01234567"[:n]): 
    for i in range(n-1):
        x=xy[int(l[int(i)])][0]-xy[int(l[int(i+1)])][0]
        y=xy[int(l[int(i)])][1]-xy[int(l[int(i+1)])][1]
        ans+=((x)**2+(y)**2)**0.5
import math
print(ans/(math.factorial(n)))

Measured memory_bytes: 42600
#include <iostream>

using namespace std;

int main(){
    string S, T;
    cin >> S >> T;
    int n = S.length();
    int r1[26];
    int r2[26];
    fill(r1, r1 + 26, -1);
    fill(r2, r2 + 26, -1);
    bool ans = true;
    for(int i=0; i<n; i++){
        if(r1[S[i]-'a'] == -1){
            r1[S[i] - 'a'] = T[i] - 'a';
        }
        else{
            if(r1[S[i] - 'a'] != T[i] - 'a'){
                ans = false;
                break;
            }
        }
        if(r2[T[i] - 'a'] == -1){
            r2[T[i] - 'a'] = S[i] - 'a';
        }
        else{
            if(r2[T[i] - 'a'] != S[i] - 'a'){
                ans = false;
                break;
            }
        }
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 776
#include<stdio.h>

void insert(int a[], int n);

int main()
{
    int a[1000];
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int i, j;
        for(i = 0; i < n; i++)
            scanf("%d", &a[i]);
        insert(a, n);
    }
}
void insert(int a[], int n)
{
    int i, j;
    int k;
    int t;
    printf("%d", a[0]);
    for(t = 1; t < n ; t++)
        printf(" %d", a[t]);
    printf("\n");
    for(i = 1; i < n; i++)
    {
        k = a[i];
        j = i - 1;
        while(j >= 0&& a[j] > k)
        {
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = k;
        printf("%d", a[0]);
        for(t = 1; t < n ; t++)
            printf(" %d", a[t]);
        printf("\n");
    }
}



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

#define int long long
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 ncr(int n, int r){
	if(r < 0 || n < r) return 0;
	if(r == 0) return 1;
	return n * ncr(n-1, r-1) / r;
}

signed main(){
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> v(n);

	for(int i = 0;i < n;i++){
		cin >> v[i];
	}

	sort(v.begin(), v.end(), greater<int>());

	double ans = v[0];
	int cnt = 1;
	int start = 0; 
	for(int i = 1;i < n;i++){
		if(i < a) ans += v[i];
		if(v[i-1] != v[i]){
			if(i < a){
				start = i;
				cnt = 1;
			}else{
				break;
			}
		}else{
			cnt++;
		}
	}

	int ans_cnt = 0;
	if(start == 0){
		for(int i = a;i <= b;i++){
			ans_cnt += ncr(cnt, i-start);
		}
	}else{
		ans_cnt += ncr(cnt, a-start);
	}

	printf("%.12lf\n", ans/(double)a);
	cout << ans_cnt << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Apr 12 21:00:01 JST 2020
 **/

signed main() {
    Int n;
    std::cin >> n;
    Int ans = 0;
    REP(a, 1, n + 1) {
        REP(b, 1, n + 1) {
            REP(c, 1, n + 1) {
                ans += std::gcd(a, std::gcd(b, c));
            }
        }
    }
    std::cout << ans << std::endl;
}


Measured memory_bytes: 3652
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int N = 1000000;
const int mod = 1000000007;
const int INF = 1 << 30;
#define rep(i,n) for(int i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
#define fi first
#define se second
#define pb push_back
ll ppow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if ((n & 1) == 1)ans = ans + x;
		x = x * x;
		n >>= 1;
		ans %= mod;
	}
	return ans;
}
string YN(bool b) { return(b ? "YES" : "NO"); }
string yn(bool b) { return(b ? "Yes" : "No"); }
string s, ans;
int ch[26], n = -1;
int main() {
	cin >> s;
	rep(i, s.size()) {
		ch[s[i] - 'a']++;
	}
	if (s.size() == 26) {
		for (int i = 25; i >= 0; --i) {
			ch[s[i] - 'a']--;
			if (s[i] != 'z') {
				char c = '0';
				for (int j = s[i] - 'a'+1; j < 26; ++j) {
					if (ch[j] == 0) { c =char(j + 'a'); break; }
				}
				if (c != '0') { rep(j, i)ans += s[j]; ans += c; n = 0; break; }
			}
		}
	}
	else rep(i, 26)if (ch[i] == 0) { s += ('a' + i); n = 1; break; }
	cout << (n == 1 ? s : (n == 0 ? ans : "-1")) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, n, x, a;
  scanf("%lld%lld", &x, &n);
  ++x;
  bool flg[103];
  for(i = 0; i < 103; ++i) flg[i] = true;
  for(i = 0; i < n; ++i) scanf("%lld", &a), flg[++a] = false;
  for(i = 0; ;++i) {
    if(flg[x - i]) {
      printf("%lld", x - i - 1);
      return 0;
    }
    if(flg[x + i]) {
      printf("%lld", x + i - 1);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 1692
#include<iostream>
using namespace std;
int main()
{
  int N;
  cin >> N;
  
  int A[N];
 
  string ANS = "APPROVED";
  
  for(int i=0; i<N; i++){
     cin >> A[i];
  if(A[i]%2==0 and (A[i]%3!=0 and A[i]%5!=0))
    ANS = "DENIED";
  }
  
  cout << ANS << endl;

    
    
    return 0;
}

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

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

def gcd(a,b):
    x=max(a,b)
    y=min(a,b)
    while x%y!=0:
        x,y=y,x%y
    return y
    
Num=A[0]

for i in range(N):
    Num=gcd(Num,A[i])
    
if K%Num==0:
    if K>max(A):
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v{0} {}
    ModInt(ll _v) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M(0) - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return (*this).pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const int MN = 2333;
int n, k;
Mint dp[MN], ndp[MN];
Mint two[MN];

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

    two[0] = 1;
    for (int i = 1; i < MN; i++) {
        two[i] = Mint(2) * two[i - 1];
    }

    cin >> n >> k;
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }
    if (k == 1) {
        cout << two[n - 2] << "\n";
        return 0;
    }
    fill(dp + 2, dp + n + 1, 1);
    for (int i = 1; i < k - 1; i++) {
        for (int j = 2; j <= n - i + 1; j++) {
            ndp[j] = dp[j];
        }
        for (int j = n - i; j >= 2; j--) {
            ndp[j] += ndp[j + 1];
        }
        for (int j = 2; j <= n - i; j++) {
            dp[j] = ndp[j];
        }
    }

    Mint ans = accumulate(dp + 2, dp + n - k + 3, Mint(0));
    ans *= two[max(0, n - k - 1)];
    cout << ans << "\n";

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

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

#ifdef CLION

ifstream ifs("/home/kyuridenamida/atcoder-workspace/hitachi2020/D/in_2.txt");
#define cin ifs
#define scanf DONT_USE_SCANF
#endif


long long dp[50];

void solve(long long N, long long T, std::vector<long long> a,
           std::vector<long long> b) {

    deque<pair<long long, long long> > ps;
    for (int i = 0; i < N; i++)
        ps.push_back({a[i], b[i]});
    long long t = 0;
    int ans = 0;

    sort(ps.begin(), ps.end(), [&](pair<long long, long long> a, pair<long long, long long> b) {
        long long A = a.first;
        long long B = a.second;
        long long C = b.first;
        long long D = b.second;
        long long w = C * B + C;
        long long W = A * D + A;
        return w < W;
    });

    vector<long long> items;
    vector<pair<long long, long long>> dpItems;
    for (int i = 0; i < ps.size(); i++) {
        if (ps[i].first == 0) {
            items.push_back(ps[i].second + 1);
        } else {
            dpItems.push_back({ps[i].first, ps[i].second});
        }
    }

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

    for (int j = 0; j < 50; j++) {
        dp[j] = 2e9;
    }

    dp[0] = 0;


    for (int i = 0; i < dpItems.size(); i++) {
        for (int j = 48; j >= 0; j--) {
            dp[j + 1] = min(dp[j + 1], dp[j] + 1 + dpItems[i].first * (dp[j] + 1) + dpItems[i].second);
        }
    }
    long long maxAns = 0;
    for (int i = 0; i < 49; i++) {
        if (dp[i] <= T) {
            long long r = T - dp[i];
            long long c = i;
            for (int j = 0; j < items.size(); j++) {
                if (r - items[j] >= 0) {
                    r -= items[j];
                    c++;
                }
            }
            maxAns = max(maxAns, c);
        }
    }

    cout << maxAns << endl;


}

int main() {
    long long N;
    cin >> N;
    long long T;
    cin >> T;
    std::vector<long long> a(N);
    std::vector<long long> b(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i];
    }
    solve(N, T, std::move(a), std::move(b));
    return 0;
}


Measured memory_bytes: 12784
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	string  n;
	cin >> n;
	bool f = 0;
	for (int i = 1; i < n.size(); i++) {
		if (n[i] != '0')f = 1;
	}
	ll ans = 0;
	if (f) {
		for (int i = 0; i < n.size(); i++)ans += (n[i] - '0');
	}
	else {
		if (n.size() == 1)ans = (n[0] - '0');
		else ans = 10;
	}
	cout << ans << endl;
	return 0;
}

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

import heapq

def main():
    n = int(input())
    nodes = []
    for i in range(n):
        xi, yi = map(int, input().split())
        nodes.append((i, xi, yi))

    adj = [[] for i in range(n)]
    nodesx = sorted(nodes, key=(lambda x: x[1]))
    for j in range(n - 1):
        i1 = nodesx[j][0]
        i2 = nodesx[j + 1][0]
        adj[i1].append(i2)
        adj[i2].append(i1)
    nodesy = sorted(nodes, key=(lambda x: x[2]))
    for j in range(n - 1):
        i1 = nodesy[j][0]
        i2 = nodesy[j + 1][0]
        adj[i1].append(i2)
        adj[i2].append(i1)

    res = 0
    q = [(0, 0)]
    visited = [False for i in range(n)]
    while q:
        d, i = heapq.heappop(q)
        if visited[i]:
            continue
        visited[i] = True
        res += d
        for j in adj[i]:
            if visited[j]:
                continue
            heapq.heappush(q, (dist(i, j, nodes), j))
    print(res)

def dist(i, j, nodes):
    _, xi, yi = nodes[i]
    _, xj, yj = nodes[j]
    res = min(abs(xi - xj), abs(yi - yj))
    return res

if __name__ == "__main__":
    main()


Measured memory_bytes: 45376
import std.stdio;
import std.ascii;
import std.conv;
import std.string;
import std.algorithm;
import std.range;
import std.functional;
import std.math;
import core.bitop;

void main()
{
    string s = readln.chomp;
    long k = readln.chomp.to!long;
    long firstone = -1;
    foreach (size_t i, char c; s)
        if (c != '1')
        {
            firstone = i;
            break;
        }
    // s[0..firstone].writeln;
    if (k <= firstone)
    {
        "1".writeln;
        return;
    }
    if (firstone == -1)
    {
        s[0].writeln;
        return;
    }
    s[firstone].writeln;
}


Measured memory_bytes: 256
Public Class Program
  Shared Sub Main()
    Dim n As Integer = Integer.Parse(Console.ReadLine())
    Dim arrayA As Integer() = Array.ConvertAll(Of String, Integer)(Console.ReadLine().Split(" "), AddressOf Integer.Parse)
    Dim result As Integer = arrayA(0)
    For i As Integer = 1 To n - 1
      result = result Xor arrayA(i)
    Next
    Console.WriteLine(If(result = 0, "Yes", "No"))
  End Sub
End Class

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

const ll MOD = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	vl a(n);
	FOR(i,0,n) cin >> a[i];

	ll s = 0, t = 0;
	FOR(i,0,n) {
		s = (s + a[i]) % MOD;
		t = (t + a[i]*a[i]) % MOD;
	}

	ll res = (s*s - t) % MOD;
	res = res * (MOD+1)/2 % MOD;
	if (res < 0) res += MOD;
	cout << res << endl;
}



Measured memory_bytes: 4764
n = int(input())
S = [input() for _ in range(n)]

d = {chr(i): 50 for i in range(97, 97+26)}
for s in S:
    dcur = {chr(i): 0 for i in range(97, 97+26)}
    for si in s:
        dcur[si] += 1
    for k in d:
        d[k] = min(d[k], dcur[k])

ks = list(d.keys())
ks.sort()

ans = []

for k in ks:
    ans.extend([k] * d[k])

print(''.join(ans))


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

int dfs(int n, vector<vector<bool>> con, int cur, bool *checked, int visited){
  if (visited == n) return 1;
  int ret = 0;
  for (int i = 0; i < n; i++){
    if (con.at(cur).at(i) && (!checked[i])){
      visited++; checked[i] = true;
      ret += dfs(n, con, i, checked, visited);
      visited--; checked[i] = false;
    }
  }
  return ret;
}
  
int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<bool>> con(8, vector<bool>(8, false));
  for (int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b; a--; b--;
    con.at(a).at(b) = con.at(b).at(a) = true;
  }
  bool checked[8]; checked[0] = true;
  cout << dfs(n, con, 0, checked, 1) << endl;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
s = input()
x = 0
y = 0
firsthappiness = 0
for i in range(n-1):
    if s[i]+s[i+1] == "RL":
        x+=1
    if s[i] == s[i+1]:
        firsthappiness += 1
if s[0] == "L":
    y += 1
if s[n-1] == "R":
    y += 1
for i in range(k):
    if x > 0:
        x -= 1
        firsthappiness+=2
        continue
    if y > 0:
        y -= 1
        firsthappiness += 1
print(min(firsthappiness,n-1))


Measured memory_bytes: 39792
#pragma GCC optimze("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define md 998244353
#define trace(...)
#define ll long long int
#define ld long double
#define fi first
#define se second
#define fr(i,a,b) for(ll i=a;i<=b;i++)
#define frr(i,b,a) for(ll i=b;i>=a;i--)
#define mem(a) memset(a, 0, sizeof(a))
#define vpi std::vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define pb push_back
#define sall(v) sort(v.begin(),v.end())
#define all(v) (v.begin(),v.end())
#define minf -10000000
#define vi vector<int>
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}
ll power(ll x, ll y,ll p) { 
    ll res = 1;      // Initialize result 
    x = x % p;  // Update x if it is more than or equal to p 
    while (y > 0) {  
        if (y & 1) // If y is odd, multiply x with result
            res = (res*x) % p;  
        y = y>>1; // y = y/2 // y must be even now
        x = (x*x) % p;   
    } 
    return res; 
}
ll power(ll x, ll y) { 
    ll res = 1;      // Initialize result 
    while (y > 0) {    
        if (y & 1)// If y is odd, multiply x with result 
            res = (res*x) ;  
        y = y>>1; // y = y/2 // y must be even now 
        x = (x*x);   
    } 
    return res; 
}
 
ll max3(ll a,ll b,ll c){
    return max(a,max(b,c));
}
ll min3(ll a,ll b,ll c){
    return min(a,min(b,c));
}
bool isPrime(ll n) { // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
    return true; 
}
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int nax=1e5+10;

void solve(){
    ll a,b,c,d;cin>>a>>b>>c>>d;
    ll ans=-1e18;
    if(a<=0 && b>=0)ans=0;
    if(c<=0 && d>=0)ans=0;
    ans=max3(ans,a*d,b*c);
    ans=max3(ans,a*c,b*d);
    cout<<ans<<endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout<<fixed<<setprecision(8);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
    int t;
    // cin>>t;
    t=1;
    while(t--){
        solve();
    }
    #ifndef ONLINE_JUDGE
    cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
    #endif
    return 0;
}

Measured memory_bytes: 3576
N = gets.chomp.to_i
l = gets.split(' ')

l = l.map{|x| x.to_i}
l = l.sort_by{|x| x}.reverse

max = l[0]
l = l.drop(1)

sum = 0
l.each do |x|
    sum += x
end

if max < sum then
    print 'Yes'
else
    print 'No'
end

Measured memory_bytes: 1788
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
inline ll read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
#define d read()
ll n,k;
ll ans;
int main(){
	scanf("%lld %lld",&n,&k);
	printf("%lld",min(n-n/k*k,-(n-n/k*k-k)));
	return 0;
}


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

#define int long long

void solve(int tt)
{
    string str;cin>>str;
    if(str=="ABC")
        cout<<"ARC";
    else
        cout<<"ABC";
}

int32_t main()
{
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)
        solve(i);
}

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

void merge(int *,int,int,int);
void mergeSort(int *,int,int);

int count=0;

int main() {
  int i,n,A[1000000];

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

  mergeSort(A,0,n);

  for(i=0;i<n;i++) {
    if(i==n-1) printf("%d\n",A[i]);
    else printf("%d ",A[i]);
  }
    printf("%d\n",count);

  return 0;
}

void merge(int *A,int left,int  mid,int  right){
  int i,j,k,n1,n2;
  double *L, *R;

  n1 = mid - left;
  n2 = right - mid;
  /* L[0...n1], R[0...n2] を生成 */
  L = (double *)malloc(sizeof(double)*(n1+1));
  R = (double *)malloc(sizeof(double)*(n2+1));

  for(i = 0; i <= n1-1 ; i++) L[i] = A[left + i];
  for (i = 0 ;i <= n2-1 ; i++) R[i] = A[mid + i];
  L[n1] = 1.0/0.0;
  R[n2] = 1.0/0.0;
  i = 0;
  j = 0;
  for (k = left ; k <= right-1 ; k++){
    if (L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
      count ++;
    }
    else {
      A[k] = R[j];
      j = j + 1;
      count++;
    }
  }
  free(L);
  free(R);
}

void mergeSort(int *A,int left,int right){
  int mid;
  if (left+1 < right){
    mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

Measured memory_bytes: 8244
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

int main() {
    string s;   cin >> s;
    int ans = 0;
    for (int i = 0; i < s.length(); i++) {
        ans += s[i]-'0';
        ans %= 9;
    }

    if (ans == 0)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;

        return 0;
}

Measured memory_bytes: 3720
#include <stdio.h>
#include <iostream>

using namespace std;

int main(){
    int a;
    int b[100000];
    int flag=0;
    cin>>a;
    for(int i;i<a;i++){
        cin>>b[i];   
    }
    for(int i=0;i<a;i++){
        if(b[i]%2==1)flag++;
    }

    if(flag%2==1)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    
    return 0;
}

Measured memory_bytes: 768
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String[] line = sc.nextLine().split(" ");
		int[] num=new int[6];
		for(int i=0;i<6;i++){
			num[i]=Integer.parseInt(line[i]);
		}
		Dice dice = new Dice(num);
		String str=sc.nextLine();
		for(int i=0;i<str.length();i++){
			if(str.charAt(i)=='W'){
				dice.moveW();
			}else if(str.charAt(i)=='S'){
				dice.moveS();
			}else if(str.charAt(i)=='E'){
				dice.moveE();
			}else if(str.charAt(i)=='N'){
				dice.moveN();
			}
		}
		System.out.println(dice.getUpper());
	}
}

class Dice{
//
	private final int lavel1,lavel2,lavel3,lavel4,lavel5,lavel6;
	private int w,s,e,n;
	private int upper,lower;
//	
	Dice(int[] i){
		lavel1=i[0];
		lavel2=i[1];
		lavel3=i[2];
		lavel4=i[3];
		lavel5=i[4];
		lavel6=i[5];
		
		w=lavel4;
		s=lavel2;
		e=lavel3;
		n=lavel5;
		
		upper=lavel1;
		lower=lavel6;
	}
	
	public int getUpper(){
		return upper;
	}
	
	public void moveW(){
		int i=lower;
		lower=w;
		w=upper;
		upper=e;
		e=i;
	}
	public void moveS(){
		int i=lower;
		lower=s;
		s=upper;
		upper=n;
		n=i;
	}
	public void moveE(){
		int i=lower;
		lower=e;
		e=upper;
		upper=w;
		w=i;
	}
	public void moveN(){
		int i=lower;
		lower=n;
		n=upper;
		upper=s;
		s=i;
	}
}

Measured memory_bytes: 26304
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    readonly Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }

    void solve()
    {
        WriteLine(cin.nextint + cin.nextint / 2);
    }

}

class Scanner
{
    string[] s; int i;
    readonly char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
    public void join<T>(IEnumerable<T> values) { WriteLine(string.Join(" ", values)); }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n, a[303030], pv;

ordered_set<p> st1, st2;
ll s1, s2;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=3*n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) s1 += a[i], st1.insert(p(a[i], i));
    for(int i=n+1; i<=3*n; i++) st2.insert(p(a[i], i));
    for(auto it=st2.begin(); ; it++){
        pv++; if(pv > n) break;
        s2 += it->x;
    }
    ll mx = s1 - s2;
    for(int i=n+1; i<=n+n; i++){
        int ord = st2.order_of_key(p(a[i], i)) + 1;
        if(ord <= n){
            s2 -= a[i]; s2 += st2.find_by_order(n)->x;
        }
        st2.erase(p(a[i], i));
        if(a[i] > st1.find_by_order(i-n-1)->x){
            s1 -= st1.find_by_order(i-n-1)->x;
            s1 += a[i];
        }
        st1.insert(p(a[i], i));
        mx = max(mx, s1 - s2);
    }
    cout << mx;
}

Measured memory_bytes: 24756
# -*- coding: utf-8 -*-
import math

sx,sy,tx,ty = map(int, raw_input().split())
width = int(math.fabs(ty-sy))
height = int(math.fabs(tx-sx))

path = ''
for i in range(width):
    path += 'U'
for i in range(height):
    path += 'R'
for i in range(width):
    path += 'D'
for i in range(height):
    path += 'L'

path += 'L'
for i in range(width+1):
    path += 'U'
for i in range(height+1):
    path += 'R'
path += 'D'
path += 'R'
for i in range(width+1):
    path += 'D'
for i in range(height+1):
    path += 'L'
path += 'U'
    
print(path)

Measured memory_bytes: 2692
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,pair<ll,ll>> ppl;
const int N=305, M=N*N;
vector<pair<int,int>>edges[N];
int dp[N][N];
int n,m,l;
struct cmp { 
    bool operator()(ppl const& p1, ppl const& p2) { 
        if(p1.first!=p2.first) return p1.first < p2.first; 
        if(p1.second.first!=p2.second.first) return p1.second.first>p2.second.first;
        return p1.second.second<p2.second.second;
    } 
}; 

struct PqElement{
	int capacity,node,cost;
	PqElement(int x,int y,int z):capacity(x),node(y),cost(z) {}
	bool operator <(const PqElement &o) const {
		if(cost == o.cost) {
			return capacity<o.capacity;
		}
		return cost>o.cost;
	}
};
void dijkstra(int s) {
	priority_queue<PqElement>pq;
	pq.push(PqElement(l,s,0));
	while(!pq.empty()) {
		auto x=pq.top();	pq.pop();
		int capacity = x.capacity, node = x.node, cost=x.cost;
		if(dp[s][node]!=-1)	continue;
		dp[s][node]=cost;
		for(auto x:edges[node]) {
			ll v=x.first, w=x.second;
			if(dp[s][v]==-1) {
				if(w<=capacity) {
					pq.push(PqElement(capacity-w,v,cost));
				}else if(l-w>=0){
					pq.push(PqElement(l-w,v,cost+1));
				}	
			}	
		}
	}
}
int main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>m>>l;
	for(int i=0;i<m;i++){
		ll u,v,w;cin>>u>>v>>w;
		u--;v--;
		edges[u].push_back({v,w});
		edges[v].push_back({u,w});
	}
	for(int i=0;i<n;i++) {
		dijkstra(i);
		// cout<<"\n\n";
	}
	int q;cin>>q;
	while(q--){
		ll u,v;cin>>u>>v;
		u--;v--;
		cout<<dp[u][v]<<"\n";
	}
	return 0;
}


Measured memory_bytes: 6216
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        public class Button
        {
            public int Index { get; set; }
            public int Next { get; set; }
            public bool Flashed { get; set; }
        }

        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var buttons = new List<Button>();
            for(var i =0;i<N;i++)
            {
                buttons.Add(new Button() { Index = i, Next = int.Parse(Console.ReadLine()), Flashed = false });
            }
            var next = 0;
            var result = 0;
            while(!buttons[next].Flashed)
            {
                if(next==1)
                {
                    Console.WriteLine(result);
                    return;
                }
                buttons[next].Flashed = true;
                result++;
                next = buttons[next].Next-1;
            }
            Console.WriteLine(-1);
        }
    }
}


Measured memory_bytes: 22876
#include<iostream>
#include<string>
using namespace std;
int main() {
	int taro=0, hanako=0;
	string t, h;
	int n;

	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> t >> h;
		if (t > h)taro += 3;
		else if (t < h)hanako += 3;
		else {
			taro++;
			hanako++;
		}
	}
	cout << taro << " " << hanako << endl;
	return 0;
}


Measured memory_bytes: 3136
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
int tx[] = {0,1,1,0,-1,-1};
int ty[] = {1,1,0,-1,-1,0};
 
static const double EPS = 1e-8;

class State{
public:
  int mStep;
  int mX;
  int mY;
  State(int step,int x,int y) : mStep(step), mX(x), mY(y) {}
  bool operator <(const State& s) const{
    return mStep < s.mStep;
  }

  bool operator >(const State& s) const{
    return mStep > s.mStep;
  }
};

// int CoundVisitedCell(map<P,int>& stage){
//   int count = 0;
//   for(int y=-30;y<=30;y++){
//     for(int x=-30;x<=30;x++){
//       if(stage.find(P(x,y)) == stage.end()) continue;
//       if(stage[P(x,y)] >= 0) count++;
//     }
//   }
//   return count;
// }


int main(){
  int t,n;
  while(~scanf("%d %d",&t,&n)){

    if(t==0 && n==0) break;

    map<P,int> stage;
    for(int i=0;i<n;i++){
      int x,y;
      scanf("%d %d",&x,&y);
      stage[P(x,y)] = -1;
    }

    int sx,sy;
    scanf("%d %d",&sx,&sy);

    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(0,sx,sy));
    stage[P(sx,sy)] = 0;

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

      res++;
      if(s.mStep >= t) continue;

      for(int i=0;i<6;i++){
	int dx = s.mX + tx[i];
	int dy = s.mY + ty[i];

	//obstacle
	if(stage.find(P(dx,dy)) != stage.end()
	   && stage[P(dx,dy)] == -1) continue;

	//small step count is better
	if(stage.find(P(dx,dy)) != stage.end() 
	   && s.mStep+1 >= stage[P(dx,dy)] ) continue;

	stage[P(dx,dy)] = s.mStep+1;
	que.push(State(s.mStep+1,dx,dy));
      }
    }

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

Measured memory_bytes: 1380
#include <stdio.h>
int main(){
    int h, w;
    int i, j;

    while(1){
        scanf("%d %d",&h, &w);
        if(h == 0 && w == 0) break;

        for(i = 0; i < h; i++){
            printf("#");
            for(j = 1; j < w; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}


Measured memory_bytes: 2068
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import Data.List

readIntsLines :: IO [[Int]]
readIntsLines = map (map (fst . fromJust . BC.readInt) . BC.words) . BC.lines <$> BC.getContents

solve :: [(Int, Int)] -> Int -> Integer
solve _ 0 = 0
solve ((a, b):abs) m = fromIntegral (count * a) + solve abs (m - count)
  where count = min b m

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  let toTuple [a, b] = (a, b)
  abs <- sortOn fst . map toTuple <$> readIntsLines
  print $ solve abs m

Measured memory_bytes: 46460
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))



h,w = map(int,input().split())
a = [(list(input())) for _ in range(h)]

ans1 = []
ans2 = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    if not("#" in a[i]):
        continue
    else:
        ans1.append(a[i])

cnt = 0
for i in range(w):
    bre = True
    for j in range(len(ans1)):
        if ans1[j][i] == "#":
            bre = False
    if not(bre):
        for k in range(len(ans1)):
            ans2[k][cnt] =  ans1[k][i]
        cnt += 1

for i in range(h):
    for j in range(w):
        if ans2[i][j] != 0:
            print(ans2[i][j],end="")
    print()







Measured memory_bytes: 4596
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;

int main() {

    string S;
    cin >> S;

    int counter = 0;
    for (int i = 0; i < S.size(); ++i) {
        string s = S.substr(i, 1);
        if (s == "x") {
            ++counter;
        }
    }

    if (counter > 7) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}


Measured memory_bytes: 256