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

int main(void){
  int N, N_kazu;
  cin >> N;
  N_kazu = N % 10;
  switch(N_kazu){
  case 0:
  case 1:
    cout << "pon" << endl;
    break;
  case 2:
    cout << "hon" << endl;
    break;
  case 3:
    cout << "bon" << endl;
    break;
  case 4:
  case 5:
    cout << "hon" << endl;
    break;
  case 6:
    cout << "pon" << endl;
    break;
  case 7:
    cout << "hon" << endl;
    break;
  case 8:
    cout << "pon" << endl;
    break;
  case 9:
    cout << "hon" << endl;
    break;
  }
  return 0;
}

Measured memory_bytes: 3620
package main

import (
    "fmt"
    "sort"
)

func main() {
    // init
    var N, W int
    fmt.Scan(&N, &W)

    // loop
    dp := make([]int, W + 1)
    for i := 1; i < N + 1; i++ {
        var w, v int
        fmt.Scan(&w, &v)
        dp_ := make([]int, W + 1)
        copy(dp_, dp)
        for j := 1; j < W + 1; j++ {
            if j + w > W{
                continue
            }
            if dp_[j] == 0 {
                continue
            }
            dp[j + w] = Max(dp_[j] + v, dp_[j + w])
        }
        dp[w] = Max(v, dp_[w])
    }

    // output
    sort.Sort(sort.IntSlice(dp))
    fmt.Println(dp[W])
}

func Max(x, y int) int {
    if x < y{
        return y
    }
    return x
}

Measured memory_bytes: 16384
#include<iostream> 
#include<iomanip> 
#include<vector> 
#include<map> 
#include<set> 
#include<algorithm> 
#include<numeric> 
#include<limits> 
#include<bitset> 
#include<functional> 
#include<type_traits> 
#include<queue> 
#include<stack> 
#include<array> 
#include<random> 
#include<utility> 
#include<cstdlib> 
#include<ctime>
//#define _LIBCPP_DEBUG 0
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(a) (a).begin(),(a),end()
#define rep(i,n) for (ll i = 0; i < (ll)(n); ++i)	

int max(ll a, ll b) {
	ll max;
	if (a > b) max = a;
	else max = b;
	return max;
}
int min(ll a, ll b) {
	ll min;
	if (a < b) min = a;
	else min = b;
	return min;
}


int main() {
	int n;
	cin >> n;
	bool can = false;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			int res = i * j;
			if (n == res) can = true;
		}
	}
	if (can) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;

static const double eps = 1e-8;

int path[101][101];
int used[101][11];

void bfs(int s,int d,int n,int c){
	priority_queue<PP,vector<PP>,greater<PP> > que;
	que.push(PP(0,P(s,c)));
	used[s][c] = 0;

	while(!que.empty()){
		int cost = que.top().first;
		int src = que.top().second.first;
		int ticket = que.top().second.second;
		que.pop();

		for(int dst=1;dst<=n;dst++){
			if(used[dst][ticket] > cost + path[src][dst]){
				used[dst][ticket] = cost + path[src][dst];
				que.push(PP(cost + path[src][dst],P(dst,ticket)));
			}

			if(ticket > 0 && used[dst][ticket-1] > cost + path[src][dst]/2){
				used[dst][ticket-1] = cost + path[src][dst]/2;
				que.push(PP(cost + path[src][dst]/2,P(dst,ticket-1)));
			}
		}
	}
}

int main(){
	//c:number of tickets
	//n:number of towns
	//m:number of buses
	//s:source
	//d:distination
	int c,n,m,s,d;
	while(~scanf("%d %d %d %d %d",&c,&n,&m,&s,&d)){
		if(c==n && n==m && m==s && s==d && d==0) break;
		memset(path,0x3,sizeof(path));
		memset(used,0x3,sizeof(used));

		for(int i=0;i<m;i++){
			int a,b,f;
			scanf("%d %d %d",&a,&b,&f);
			path[a][b] = path[b][a] = min(path[a][b],f);
		}

		bfs(s,d,n,c);
		int res=numeric_limits<int>::max();
		for(int i=c;i>=0;i--) res = min(res,used[d][i]);
		printf("%d\n",res);
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <bitset>
#include <cmath>
#include <stack>
#include <iomanip>
#include <map>
#include <math.h>
#include <list>
#include <deque>
typedef long long ll;
using namespace std;
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; }
ll MOD = 1000000007;
ll INF = 1LL << 60;

ll N;
ll a[1111], b[1111];

int main() {
   cin >> N;
   for (int i = 0; i < N; i++) cin >> a[i] >> b[i];

   ll n = 1;
   ll x = 1, y = 1;
   for (int i = 0; i < N; i++) {
      if (i == 0) {
         n = 1;
      } else {
         n = max((a[i-1]*n + a[i]-1) / a[i], (b[i-1]*n + b[i]-1) / b[i]);
      }
      x = a[i] * n;
      y = b[i] * n;
   }
   cout << x + y << endl;

   return 0;
}

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

using namespace std;

int main()
{
	int ni;
	cin >> ni;
	for (int h = 1; h <= 3500; h++)
		for (int n = 1; n <= 3500; n++)
		{
			long long t = (long long)ni * h * n, d = (long long)4 * h * n - ni * h - ni * n;
			if (0 < d && t % d == 0)
			{
				cout << h << " " << n << " " << t / d << endl;
				return 0;
			}
		}
}

Measured memory_bytes: 256
def main():
    K = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    print(K[int(input())-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
typedef unsigned long long BITMASK; typedef long long ll; typedef long double ld;
#define has_bit(bit_mask, x) ((bit_mask) & (1ULL << (x)))
#define turn_on_bit(bit_mask, x) (bit_mask |= (1ULL << (x)))
#define turn_off_bit(bit_mask, x) (bit_mask &= (~(1ULL << (x))))
#define smallest_on_bit(bit_mask) (__builtin_ctzint((bit_mask) & (-(bit_mask))))
#define CLOCK_START clock_t chrono_clk_beg = clock()
#define CLOCK_END clock_t chrono_clk_end = clock(); cerr << (double(chrono_clk_end - chrono_clk_beg) / CLOCKS_PER_SEC) << " sec"
#define bug(args ...) cerr << __LINE__ << ">> ", err(new istringstream(string(#args)), args), cerr << '\n'
#define decToBin(name, num) string name = bitset<8>(num).to_string();
#define binToDec(name, binary) unsigned long name = bitset<8>(binary).to_ulong();
#define radToDeg(name, radians) double name = radians * 180 / M_PI;
#define all(x) x.begin(), x.end()
#define mapfind(mp, x) (mp.find(x) != mp.end())
#define arrfind(arr, x) (find(all(arr), x) != arr.end())
#define removeDuplicates(vec) sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define printMat(mat) for (auto &x : mat) { for (auto &y : x) cout << y << " "; cout << '\n'; }
#define printArr(arr) for (auto &x : arr) cout << x << " "; cout << '\n';
#define ceil(a, b) ((a+b-1)/b)
#define int ll
#define double ld
#define INF (1LL<<62)
#define M_PI 3.14159265358979323846
void err(istringstream *iss) {} template<typename T, typename ... Args> void err(istringstream *iss, const T &_val, const Args & ... args) { string _name; *iss >> _name; if (_name.back()==',') _name.pop_back(); cerr << _name << " = " << _val << "; ", err(iss, args ...); }
void str_replaceAll(string& str, const string& from, const string& to) { if(from.empty()) return; size_t start_pos = 0; while((start_pos = str.find(from, start_pos)) != std::string::npos) { str.replace(start_pos, from.length(), to); start_pos += to.length(); } }
#define MOD 1000000007

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, W;
    cin >> n >> W;
    vector<pair<int, int>> arr(n);
    int valSm = 0;
    for (auto &x : arr) { cin >> x.first >> x.second; valSm += x.second; }
    int dp[n][valSm+1];
    dp[0][0] = 0;
    for (int j = 1; j <= valSm; ++j) dp[0][j] = (j == arr[0].second) ? arr[0].first : INF;
    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j <= valSm; ++j)
        {
            if (j >= arr[i].second)
                dp[i][j] = min(dp[i-1][j], arr[i].first + dp[i-1][j - arr[i].second]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    int ans = 0;
    for (int j = 0; j <= valSm; ++j)
        if (dp[n-1][j] <= W) ans = j;
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 78336
import java.util.Scanner;

public class Main{
  public static void main(String ars[]){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int ans = 0;
    for(int i = a;;i++){
      for(int j = 2;j <= i;j++){
        if(i % j == 0 && j != i) break;
        if(j == i) ans = i;  
      }
      if(ans != 0) break;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 22868
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if(A==B&&B==C&&C==A){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for (int i=0;i<(n);i++)
#define rep3(i,a,b) for (int i=a;i<(b);i++)
#define out(ans) cout << ans << endl;
#define outs(ans) cout << ans;
using ll = long long;

int main(){

    //imput n, a(n), b(n)
    int n;
    cin >> n;
    int num[4];
    rep(4){num[i]=n%10; n/=10;}
    //vector <int> a(n), b(n);
    //rep(n){ cin >> a[i]; }
    //rep(n){ cin >> b[i]; }

    //main process
    int ans;
    int nk = 100*num[2]+10*num[1]+num[0];
    if(nk==0){
        ans=0;
    }else{
        ans=1000-nk;
    }
    outs(ans)
    return 0;
}










    /*
    Editer: hybs
    Lang: C++
    */


Measured memory_bytes: 3556
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 4100 + 100;
const int LOG = 22;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

int a[MAXN];
vector<pll> dp[20][20];

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

    for (int len = 3; len <= n; ++len) {
        for (int l = 1; l <= n; ++l) {
            for (int r = l + len - 1; r <= n; ++r) {
                vector<pll> vals;
                for (int mid = l + 1; mid <= r - 1; ++mid) {
                    for (auto x:dp[l][mid]) {
                        for (auto y:dp[mid][r]) {
                            vals.pb({x.fi + x.se + y.fi + a[mid], x.se + y.fi + y.se + a[mid]});
                        }
                    }
                }
                sort(all(vals));
                dp[l][r].pb(vals[0]);
                ll mx = vals[0].se;
                for (int i = 1; i < sz(vals); ++i) {
                    if (vals[i].se >= mx) {
                        continue;
                    } else {
                        mx = vals[i].se;
                        dp[l][r].pb(vals[i]);
                    }
                }
            }
        }
    }

    ll ans = inf_ll;
    for(auto x:dp[1][n]){
        ans = min(ans, x.fi + x.se);
    }
    cout << ans + a[1] + a[n]<<"\n";
}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
    //  freopen("../output.txt", "w", stdout);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;
    while (t--)
        solve();

    if (debug)
        cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

Measured memory_bytes: 8692
#include <iostream>

using namespace std;

typedef long long ll;

int n, base = 100000;

int main(void) {
    cin >> n;
    for(int i = 0; i < n; i++) {
        base = base + base * 0.05;
        if(base % 1000 != 0) {
            base += 1000 - (base %1000);
        }
    }
    cout << base << endl;
    return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main() {
	int a, b, c, d, n, cnt = 0;
	while (scanf("%d", &n) != EOF) {
		cnt = 0;
		for (a = 0; a <= 9; a++) {
			for (b = 0; b <= 9; b++) {
				for (c = 0; c <= 9; c++) {
					for (d = 0; d <= 9; d++) {
						if ((a + b + c + d) == n)cnt++;
					}
				}
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
}


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

const int N = 3005;

ll dp[3][N];
int x[3];

ll solveDp(int ind,int n) {
    if(ind==3) {
        if(n==0) {
            return 1;
        } else {
            return 0;
        }
    }
    ll &ret = dp[ind][n];
    if(ret!=-1) {
        return ret;
    }
    ret = 0;
    for(int i=0;i*x[ind]<=n;++i) {
        ret += solveDp(ind+1, n - i*x[ind]);
    }
    return ret;
}

void solve() {
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<3;++i) {
        scanf("%d",&x[i]);
    }
    int n;
    scanf("%d",&n);
    printf("%lld\n", solveDp(0,n));
}

int main(){
    //freopen("input.txt","r",stdin);
    solve();
}

Measured memory_bytes: 256
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

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

const int maxn = 45;
const int mod = 1e9 + 7;

int n, X, Y, Z;

int dp[maxn][(1 << 17) + 5];

void read_input()
{
    cin >> n >> X >> Y >> Z;
}

void add(int&tar, int val)
{
    tar += val;
    if(tar >= mod) tar -= mod;
    if(tar < 0) tar += mod;
}

void solve()
{
    memset(dp, 0, sizeof(dp));
    int all = (1 << (X + Y + Z)) - 1;
    int chcker = (1 << (Z - 1)) | (1 << (Z + Y - 1)) | (1 << (X + Y + Z - 1));
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i)
        for(int mask = 0; mask <= all; ++mask)
            for(int num = 1; num <= 10; ++num)
            {
                int nmask = (mask << num) | (1 << (num - 1));
                nmask &= all;
                if((nmask & chcker) != chcker)
                    add(dp[i + 1][nmask], dp[i][mask]);
            }
    int ans = 1;
    for(int i = 0; i < n; ++i)
        ans = ans * 10LL % mod;
    for(int mask = 0; mask <= all; ++mask)
        add(ans, -dp[n][mask]);
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



Measured memory_bytes: 23296
// Eulerian Path
#include <iostream>
using namespace std;

int node[200]; // node[i] expresses num of node from i
int a, b;

void initialize(){
	for (int i = 0; i < 200; i++) {
		node[i] = 0;
	}
}

bool answer(){
	if(node[1] % 2 == 0 || node[2] % 2 == 0) return false;
	for (int i = 3; i < 200; i++) {
		if(node[i] % 2 == 1) return false;
	}
	return true;
}

int main(){
	initialize();
	while (cin >> a >> b) {
		if (a == 0 && b == 0) {
			if(answer()){
				cout << "OK" << endl;
			}else {
				cout << "NG" << endl;
			}
			initialize();
		}else{
			node[a]++;
			node[b]++;
		}
	}

	return 0;
}

Measured memory_bytes: 0
/*
我的心脏怦怦跳，监管者就在附近
name:
Algorithm:
writer:Lxs(cdx)
place:
nothing is impossible
*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<string>
#include<iostream>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<unistd.h>
#include<stdio.h>
#include<cstring>
#define random(a,b) (rand()%(b-a+1)+a)
using namespace std;
bool prime(int x){
	 int i;
	 if(x<2) return 0;
	 for(i=2;i*i<=x;i++){
		if(x%i==0){return 0;}
	 }
	 return 1;
}
int main()
{
	int n;
	cin>>n;
	int i;
	unsigned long long s=0;
	for(i=1;i<=n;i++){
		if(!(i%3==0||i%5==0)){
			s+=i;
		}
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3676
#include<iostream>
#include<string>
using namespace std;
struct Dice{
  int s[6];
  void roll(char c){
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
    if(c=='R'){
      b=s[1];
      s[1]=s[2];
      s[2]=s[4];
      s[4]=s[3];
      s[3]=b;
    }    
  }
  int top() {
    return s[0];
  }
  int right(){
    return s[2];
  }
  int left(){
    return s[3];
  }
  int front(){
    return s[1];
  }
};
int main(){
  Dice d;
  for(int i=0;i<6;i++) cin >> d.s[i];
  int n;cin >> n;
  while(n--){
    int a,b;cin >> a >> b;
    if(d.left()==a) d.roll('E');
    if(d.right()==a) d.roll('W');
    while(d.top()!=a) d.roll('N');
    while(d.front()!=b) d.roll('R');
    cout << d.right() << endl;
  }
  return 0;
}



Measured memory_bytes: 3100
import collections
s=list(input())
n=len(s)
s.reverse()
l=[0]
a=1
x=0
for i in range(n):
  x+=a*int(s[i])
  x%=2019
  a*=10
  a%=2019
  l.append(x)
L=collections.Counter(l)
L2=list(L.values())
ans=0
for i in range(len(L2)):
  ans+=L2[i]*(L2[i]-1)//2
print(ans)

Measured memory_bytes: 97108
def input_from_console():
    n = int(input().strip())
    h_list = list(map(int, input().split()))
    return n, h_list


def solve(n, h_list):
    import sys
    sys.setrecursionlimit(200000)

    dp = [-1] * (n + 2)
    dp[0] = 0
    dp[1] = abs(h_list[1] - h_list[0])

    def recursive_dp_sover(i):
        if dp[i] != -1:
            return dp[i]
        dp[i] = min(
            recursive_dp_sover(i - 1) + abs(h_list[i] - h_list[i - 1]),
            recursive_dp_sover(i - 2) + abs(h_list[i] - h_list[i - 2])
        )
        return dp[i]

    return recursive_dp_sover(n - 1)


def main():
    n, h_list = input_from_console()
    print(solve(n, h_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

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

int main(){
    int a,b,c;
    int m1,m2,m3;
    cin >> a >> b >> c;
    if(a <= b && b <= c) m1=a, m2=b, m3=c;
    else if(a <= c && c <= b) m1=a, m2=c, m3=b;
    else if(b <= a && a <= c) m1=b, m2=a, m3=c;
    else if(b <= c && c <= a) m1=b, m2=c, m3=a;
    else if(c <= a && a <= b) m1=c, m2=a, m3=b;
    else m1=c, m2=b, m3=a;
    cout << m1 << " " << m2 << " " << m3 << endl;
    return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define all(c) begin(c),end(c)
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
//最大公約数
ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}
//最小公倍数
ll lcm(ll x, ll y) {
  return x/gcd(x, y)*y;
}
//素因数分解
vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i <= n; ++i) {
    if (n%i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}
 
 
 ll mod=998244353;
 
int main() {
  int n,k;
  cin>>n>>k;
  int p[n];

  for(int i=0;i<n;i++){
      cin>>p[i];
  }
  sort(p,p+n);
  int ans=0;
  for(int j=0;j<k;j++){
    ans=ans+p[j];
  }
  cout<<ans;


}



Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
using namespace std; typedef long long ll; const int INF=100; typedef pair<int,int> P;
struct st{ll a,b,c;};
int gcd(ll a, ll b) {if (b==0) return a; else return gcd(b, a%b);}
int main() {
  ll a,b,c; cin>>a>>b>>c;
  ll an=0; bool inf=false;
  vector<st> v;
  while(a%2==0 && b%2==0 && c%2==0) {
    for(st x:v) {
      if (a==x.a&&b==x.b&&c==x.c) {inf=true; break;}
    }
    if (inf) break;
    v.push_back({a,b,c});
    ll d=b/2+c/2,e=a/2+c/2,f=a/2+b/2;
    a=d,b=e,c=f;
    an++;
  }
  if (inf) cout<<-1<<endl;
  else cout<<an<<endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Pair> ps = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			int w = sc.nextInt();
			ps.add(new Pair(i+1, w));
		}
		Collections.sort(ps);
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			sb.append(ps.get(i).n+" ");
		}
		System.out.println(sb.toString().trim());
	}
	static class Pair implements Comparable<Pair>{
		int n, w;
		public Pair(int _n, int _w) {
			 n = _n; w = _w;
		}
		@Override
		public int compareTo(Pair p) {
			return w-p.w;
		}
	}

}


Measured memory_bytes: 63960
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int n, m, q;
int a[50], b[50], c[50];
long long d[50];

long long dfs(vector<int>& now, int index = 0, int mx = 1){
  long long res = 0;
  if(index == n){
    REP(i, q){
      if(now[b[i]] - now[a[i]] == c[i]) res += d[i];
    }
    return res;
  }
  for(int v = mx; v <= m; v++){
    now[index] = v;
    res = max(res, dfs(now, index + 1, v));
    now[index] = 0;
  }
  return res;
}
int main(){
  //using namespace std;
  cin>>n>>m>>q;
  REP(i, q){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
    a[i]--; b[i]--;
  }
  vector<int> now(n, 0);
  long long ans = dfs(now);
  cout << ans << endl;
  return 0;
}


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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 2");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            //12
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 8");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100000 100000");
            //530123477
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {

        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int N = wkArr[0];
        int M = wkArr[1];

        long Answer = 0;

        long InuCnt = DeriveKaijyou(N);
        long SaruCnt = DeriveKaijyou(M);

        //犬始まりの順列
        if (N == M || N + 1 == M) {
            Answer += (InuCnt * SaruCnt) % Hou;
            Answer%=Hou;
        }

        //猿始まりの順列
        if (M == N || M + 1 == N) {
            Answer += (InuCnt * SaruCnt) % Hou;
            Answer%=Hou;
        }

        Console.WriteLine(Answer);
    }

    //階乗を求める
    static long DeriveKaijyou(int pVal)
    {
        long WillReturn = 1;
        for (int I = 1; I <= pVal; I++) {
            WillReturn *= I;
            WillReturn %= Hou;
        }
        return WillReturn;
    }
}


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

int main() {
    long long n, a, m = 1000000001, ans = 0, cnt = 0;
    scanf("%lld", &n);
    for (long long i = 0; i < n; i++) {
        cin >> a;
        if (a < 0) {
            ++cnt;
            a = -a;
        }
        ans += a;
        m = min(m, a);
    }
	cout << ans - (cnt % 2 == 1 ? m * 2 : 0) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

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

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
	string s;
	cin >> s;
	char x[4] = {'A', 'T', 'G', 'C'};
	bool f;
	int cnt, ans = 0;
	REP(i, s.size()){
		cnt = 0;
		FOR(j, i, s.size()){
			f = 0;
			REP(k, 4){
				if(s[j] == x[k]){
					f = 1;
					break;
				}
			}
			if(f) cnt++;
			else break;
		}
		ans = max(ans, cnt);
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
def counting_sort(arr)
  result = Array.new(arr.size)
  counter = Hash.new { |h, k| h[k] = 0 }

  arr.each { |v| counter[v] += 1 }

  1.upto(arr.max) do |v|
    counter[v] = counter[v] + counter[v - 1]
  end

  arr.reverse_each do |v|
    result[counter[v] - 1] = v
    counter[v] -= 1
  end

  result
end

gets
arr = gets.split.map(&:to_i)
puts counting_sort(arr).join("\s")



Measured memory_bytes: 151208
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	string s;
	cin >> s;
	int n = s.length();

	string t;
	for(int i = 0; i < n; i++){
		if(s[i] != 'x') t += s[i];
	}
	int m = t.size();

	if(m == 0){
		cout << 0 << endl;
		return 0;
	}

	for(int i = 0; i < m/2; i++){
		if(t[i] != t[m-1-i]){
			cout << -1 << endl;
			return 0;
		}
	}

	int left = 0, right = n-1,ans = 0;
	while(1){
		if(left == right || left > right) break;
		if(s[left] != s[right]){
			ans++;
			if(s[left] == 'x') left++;
			else right--;
		}else{
			left++;
			right--;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[3007][3007];
int main(){
  int n;
  cin >> n;
  vector<ll> a(n,0);
  ll sum = (ll)0;
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int L=n-1;L>=0;L--){
    for(int R=L;R<n;R++){
        if(L==R){
          dp[L][R] = a[L];
        }
        else{
          dp[L][R] = max(a[L]-dp[L+1][R], a[R]-dp[L][R-1]);
        }
    }
  }
  cout<<dp[0][n-1]<<endl;
}


Measured memory_bytes: 70016
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
//////////////

void solve() {
	int N;
	cin >> N;
	vector<int> A(9);
	for (int i = 0; i < 9; ++i) {
		A[i] = 111 * (i + 1);
	}
	cout << *lower_bound(A.begin(), A.end(), N) << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DChristmas solver = new DChristmas();
        solver.solve(1, in, out);
        out.close();
    }

    static class DChristmas {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            int n = in.ints();
            long x = in.longs();
            long b = x;
            long ans = 0;
            for (int i = n; i >= 0; i--) {
                long h = height(i);
                long mid = (h + 1) / 2;
                if (b == mid) {
                    ans += patties(i - 1);
                    ans++;
                    break;
                } else if (b == 1) {
                    break;
                } else if (b == h) {
                    ans += patties(i);
                    break;
                } else if (b < mid) {
                    b--;
                } else {
                    ans += patties(i - 1);
                    ans++;
                    b -= mid;
                }
            }
            out.println(ans);
        }

        public long height(int n) {
            return (1L << (n + 2)) - 3;
        }

        public long patties(int n) {
            if (n < 0) {
                return 0;
            }
            return (1L << (n + 1)) - 1;
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

        public long longs() {
            return Long.parseLong(string());
        }

    }
}



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

#define ll long long
#define P pair<int, int>
#define F first
#define S second

const ll mod = 1000000007LL;

ll n, k;
ll dp[105][100005];
ll a[105];

void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  dp[0][0] = 0;
  for (int i = 1; i <= k + 1; i++) {
    dp[0][i] = 1;
  }
  for (ll i = 1; i <= n; i++) {
    for (ll c = 1; c <= k + 1; c++) {
      dp[i][c] =
          (dp[i][c - 1] % mod +
           (dp[i - 1][c] - dp[i - 1][c - min(c - 1, a[i]) - 1] + mod) % mod) %
          mod;
    }
  }

  cout << (dp[n][k + 1] % mod - dp[n][k] % mod + mod) % mod;
}

int main(int argc, char const *argv[]) {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

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

  return 0;
}

Measured memory_bytes: 80128
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<vector<int>> adj;
vector<int> dp,vis,indegree;
void dfs(int x){
    vis[x]=1;
    for(int y:adj[x]){
        dp[y]=max(dp[y],1+dp[x]);
        indegree[y]--;
        if(indegree[y]==0) dfs(y);
    }
}

void solve(){
    int n,m,x,y;
    cin>>n>>m;
    adj.resize(n);
    indegree.resize(n);
    for(int i=0;i<m;i++){
        cin>>x>>y;
        x--;y--;
        adj[x].push_back(y);
        indegree[y]++;
    }
    dp=vis=vector<int>(n);
    for(int i=0;i<n;i++){
        if(vis[i]==0 && indegree[i]==0) dfs(i);
    }
    int ans=0;
    for(int i=0;i<n;i++) ans=max(ans,dp[i]);
    cout<<ans;
}

int main() {
	// your code goes here
	//freopen("inptmp0.txt","r",stdin);
	int T;
	
	//cin>>T;
	T=1;
	while(T--){
	    solve();
	}
	return 0;
}


Measured memory_bytes: 14500
m,d=map(int,input().split())
c=0
for i in range(10,d):
  t=1
  flag=True
  for j in list(str(i+1)):
    if int(j)<2:
      flag=False
    t*=int(j)
  if not flag:
    continue
  if t<=m and t!=0:
    c+=1
print(c)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define All(a) a.begin(),a.end()
#define INF 1000000007
const int MOD = 1000000007;
//accumulate(vec.begin(), vec.end(), 0)

int gcd(int x,int y){
  if(x%y==0) return y;
  else return gcd(y,x%y);
}

int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll>h(n);
  for(int i=0;i<n;i++)cin >> h[i];
  sort(All(h));
  ll ans = 0;
  for(ll i=0;i<n-k;i++) ans += h[i];
  cout<< ans <<endl;
}


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

struct stack{
	static const int SS=10000;
	int s[SS];
	int *a;
	stack(){
		for(int i=0;i<SS;i++){
			s[i]=0;
		}
		a=s;
	}
	bool isFull(){return (a-s)==SS;}
	bool isEmpty(){return a==s;}
	void err(const char s[]){
		cerr<<s<<endl;
		exit(1);
	}
	void push(int x){
		if(isFull()){err("push:full");}
		a++;
		*a=x;
	}
	int pop(){
		if(isEmpty()){err("pop:empty");}
		a--;
		return *(a+1);
	}
	void print(){
		cout<<"v ";
		for(int *r=s;r<=a;r++){
			cout<<(*r)<<' ';
		}
		cout<<endl;
	}
};

int main(){
	stack s;
	string str;
	const volatile int minus=-1;//<-正しく動く
	//const int minus=-1;//<-正しく動かない
	//int minus=-1;//<-正しく動く
	
	while(cin>>str){
		switch(str[0]){
			case '+':
			s.push(s.pop()+s.pop());
			break;
			
			case '-':
			s.push(minus*s.pop()+s.pop());
			//s.push(-s.pop()+s.pop());//<-正しく動かない
			break;
			
			case '*':
			s.push(s.pop()*s.pop());
			break;
			
			default:
			s.push(atoi(str.c_str()));
			break;
		}
		//cout<<str[0]<<" ";
		//s.print();
	}
	cout<<s.pop()<<endl;
}


Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;  
typedef long long ll;  
int main()  
{  
    int n,y;  
    scanf("%d%d",&n,&y);  
    int a=1000,b=5000,c=10000;  
    int s1=-1,s2=-1,s3=-1,n1,n2,n3;  
    if(n*1000>y||n*10000<y)  
        s1=-1,s2=-1,s3=-1;  
    else  
    {  
        n3=y/c;  
        for(int i=n3; i>=0; i--)  
        {  
            int flag=0;  
            n2=(y-i*10000)/5000;  
            for(int j=n2; j>=0; j--)  
            {  
   
                n1=(y-i*10000-j*5000)/1000;  
                if(i+j+n1==n&&i*c+j*b+n1*a==y)  
                {  
                    s1=n1,s2=j,s3=i;  
                    flag=1;  
                    break;  
                }  
   
   
            }  
            if(flag)  
                break;  
        }  
    }  
    printf("%d %d %d\n",s3,s2,s1);  
   
}  

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

int n, a, b, p, q, r;

int main()
{
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++)
	{
		int l;
		cin >> l;
		if (l <= a)
			p++;
		else if (l <= b)
			q++;
		else
			r++;
	}
	cout << min(min(p, q), r) << endl;
}

Measured memory_bytes: 764
import sys

from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write

    N = int(readline())
    W = [list(map(int, readline().split())) for i in range(N)]
    E = [list(map(int, readline().split())) for i in range(N)]
    F = [readline() for i in range(N)]
    mcf = MinCostFlow(2*N+2)
    for i in range(N):
        Wi = W[i]; Ei = E[i]; Fi = F[i]
        s0 = sum(Ei[j] for j in range(N) if Fi[j] == "o")
        for j in range(N):
            s = (s0 - Ei[j] if Fi[j] == "o" else s0 + Wi[j])
            mcf.add_edge(i, N+j, 1, s)
        mcf.add_edge(2*N, i, 1, 0)
        mcf.add_edge(N+i, 2*N+1, 1, 0)
    res = mcf.flow(2*N, 2*N+1, N)
    write("%d\n" % res)
    ans = []
    for i in range(N):
        Gi = mcf.G[i]
        Wi = W[i]; Ei = E[i]; Fi = F[i]
        for j in range(N):
            if Gi[j][1] == 0:
                for k in range(N):
                    if j == k or Fi[k] == ".":
                        continue
                    ans.append("%d %d erase" % (i+1, k+1))
                if Fi[j] == ".":
                    ans.append("%d %d write" % (i+1, j+1))
                break
    write("%d\n" % len(ans))
    if ans:
        write("\n".join(ans))
        write("\n")
solve()


Measured memory_bytes: 8780
#![allow(unused_macros)]

// cf. [Rustで競技プログラミングの入力をスッキリ記述するマクロ - Qiita](https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8)
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        H: usize,
        W: usize,
        s: [chars; H],
    }
    use std::collections::{VecDeque, HashSet};
    let mut queue = VecDeque::new();
    let mut visited = HashSet::new();

    queue.push_back((0, 0, 1));

    let mut black = 0;
    for i in 0..H {
        for j in 0..W {
            if s[i][j] == '#' {
                black += 1;
            }
        }
    }

    while let Some((h, w, cnt)) = queue.pop_front() {
        if visited.contains(&(h, w)) {
            continue;
        }
        if h == H - 1 && w == W - 1 {
            println!("{}", H * W - black - cnt);
            return;
        }

        visited.insert((h, w));
        // up
        if h >= 1 && s[h-1][w] == '.' {
            queue.push_back((h-1, w, cnt+1));
        }
        // down
        if h + 1 < H && s[h+1][w] == '.' {
            queue.push_back((h+1, w, cnt+1));
        }
        // left
        if w >= 1 && s[h][w-1] == '.' {
            queue.push_back((h, w-1, cnt+1));
        }
        // right
        if w + 1 < W && s[h][w+1] == '.' {
            queue.push_back((h, w+1, cnt+1));
        }
    }
    println!("-1");
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] l= "afkpuz:bglqv.:chmrw?:dinsx!:ejoty ".split(":");
        next:while (sc.hasNext()) {
            String m=sc.next();
            if(m.length()%2==1) {
                System.out.println("NA");
                continue;
            }
            String a="";
            for(int i=0;i<m.length();i+=2) {
                int x=m.charAt(i)-'0'-1;
                int y=m.charAt(i+1)-'0'-1;
                if(x<0||x>5||y<0||y>4) {
                    System.out.println("NA");
                    continue next;
                }
                a+=l[y].charAt(x);
            }
            System.out.println(a);
        }
    }
}



Measured memory_bytes: 26032
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}

int main()
{
	puts(read()<1000?"ABC":"ABD");
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

typedef long long LL;
#define register re
#define unsigned ud
#define gc() getchar()
#define digit(x) (x>='0' && x<='9')

LL read()
{
    LL x=0, f=1; char c=gc();
    while(!digit(c)){if(c=='-') f=-f; c=gc();}
    while(digit(c))x=(x<<3)+(x<<1)+c-'0', c=gc();
    return x*f;
}

#undef gc
#undef digit

using namespace std;

int n;

int main()
{
    scanf("%d", &n);
    if(n&1)
        printf("%d\n", (n+1)/2-1);
    else
        printf("%d\n", n/2-1);
    return 0;
}


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

using namespace std;

struct SegTree {
	int n;
	vector<int> node;
	SegTree(vector<int> v) {
		int sz = v.size();
		for(n = 1; n < sz; n <<= 1);
		node.resize(2 * n - 1, INT_MAX);
		//最下段にvの値を入れる
		for(int i = 0; i < sz; i++) node[i + n - 1] = v[i];

		//親に値を入れる
		for(int i = n - 2; i >= 0; i--) node[i] = min(node[2*i + 1], node[2*i + 2]);
	}

	void update(int p, int v) {
		p += n - 1;
		node[p] = v;
		while(p > 0) {
			p = (p - 1) / 2; //親の場所は1引いて2で割ると出てくる
			node[p] = min(node[2*p + 1], node[2*p + 2]);
		}
	}

	void sub(int p, int v) {
		int q = p + n - 1;
		v = node[q] - v;
		update(p, v);
	}

	int getmin(int l, int r, int k=0, int nl=0, int nr= -1) {
		if(nr == -1) nr = n;
		if(nr <= l || nl >= r) return INT_MAX;
		if(l <= nl && nr <= r) return node[k];
		int vl = getmin(l, r, 2 * k + 1, nl, (nl + nr) / 2);
		int vr = getmin(l, r, 2 * k + 2, (nl + nr) / 2, nr);

		return min(vl, vr);
	}

	int getmax(int l, int r, int k=0, int nl=0, int nr= -1) {
		if(nr == -1) nr = n;
		if(nr <= l || nl >= r) return INT_MIN;
		if(l <= nl && nr <= r) return node[k];
		int vl = getmax(l, r, 2 * k + 1, nl, (nl + nr) / 2);
		int vr = getmax(l, r, 2 * k + 2, (nl + nr) / 2, nr);

		return max(vl, vr);
	}

	void print() {
		for(int i = 0; i < n; i++) {
			cout << node[i + n - 1] << " ";
		}
		cout << endl;
	}

	void print_all() {
		for(auto x: node) cout << x << " ";
		cout << endl;
	}
};

int main() {
	int N;
	cin >> N;
	vector<int> h(N);
	for(auto &x: h) cin >> x;
	SegTree sg(h);

	int out = 0;
	for(int r = N; r > 0; r--) {
		for(int i = 0; i <= N - r; i++) {
			int n = sg.getmin(i, r + i);
			if(n == 0) continue;
			for(int j = i; j < r + i; j++) {
				sg.sub(j, n);
			}
			out += n;
		}
	}

	cout << out << endl;
}


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

char x[1010];
char y[1010];

int LCSLength();

int main(void){
  int i, q;

  scanf("%d", &q);

  for(i = 0; i < q; i++){
    scanf("%s%s", x, y);
    printf("%d\n", LCSLength());
  }

  return 0;  
}

int LCSLength(void){
  int i,j;
  int m = strlen(x);
  int n = strlen(y);

  int c[m+1][n+1];
  for(i = 1; i <= m; i++)
    c[i][0] = 0;
  for(j = 0; j <= n; j++)
    c[0][j] = 0;
  for(i = 1; i <= m; i++){
    for(j = 1; j <= n; j++){
      if(x[i-1] == y[j-1])
        c[i][j] = c[i-1][j-1] + 1;
      else if(c[i-1][j] >= c[i][j-1])
        c[i][j] = c[i-1][j];
      else
        c[i][j] = c[i][j-1];
    }
  }

 return c[m][n];
}

Measured memory_bytes: 4512