akhauriyash/Code-Regression huggingface dataset:
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;
constexpr int64_t kInf = INT64_MAX / 2L;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t N, W;
  cin >> N >> W;
  vector<int64_t> total_value(W + 1);
  for (int64_t i = 1; i <= N; ++i) {
    int64_t weight, value;
    cin >> weight >> value;
    for (int64_t w = W; w >= 0; --w) {
      int64_t prev_weight = w - weight;
      if (prev_weight >= 0) {
        total_value[w] = max(total_value[w], total_value[prev_weight] + value);
      }
    }
  }
  cout << total_value[W] << endl;
  return 0;
}


Measured memory_bytes: 4000
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = sc.nextInt(), x = sc.nextInt(), t = sc.nextInt();
        int ans = n/x + Math.min(n%x , 1);
        System.out.println(ans*t);
    }    
}

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

currency = sorted(map(int,input().split()))

gra = [float('inf')]*(n+1)
gra[0] = 0
for i in range(m):
    for j in range(currency[i],n+1):
        gra[j] = min(gra[j],gra[j-currency[i]]+1)

print(gra[n])

Measured memory_bytes: 9472
v500 = int(input())
v100 = int(input())
v50 = int(input())
s = int(input())
c = 0
for i in range(v500, -1, -1):
    if 500 * i < s:
        for j in range(v100, -1, -1):
            if 500 * i + 100 * j < s:
                for k in range(v50, -1, -1):
                    if 500 * i + 100 * j + 50 * k == s:
                        c += 1
            elif 500 * i + 100 * j == s:
                c += 1
    elif 500 * i == s:
        c += 1
print(c)

Measured memory_bytes: 3064
s = input()
t = input()
n = len(s)
a = ord("a")
s_al = list()
t_al = list()
for i in range(a, 123):
    s_al.append(s.count(chr(i)))
    t_al.append(t.count(chr(i)))
s_al.sort()
t_al.sort()
if s_al == t_al:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3632
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


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


int n;
double xs, ys, xt, yt, X_[1005], Y_[1005], R_[1005], dist[1005];
typedef pair<double, int> pdi;
vector<pdi> adj[1005];


int main(){

    ios_base::sync_with_stdio(0);

    cin>>xs>>ys>>xt>>yt;
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>X_[i]>>Y_[i]>>R_[i];

    int s = n+1, t = n+2;
    X_[s] = xs;	Y_[s] = ys;	R_[s] = 0;
    X_[t] = xt;	Y_[t] = yt;	R_[t] = 0;
    n += 2;

    for(int i=1;i<=n;i++)
    	for(int j=i+1;j<=n;j++){
    		double dist = sqrt((X_[i]-X_[j])*(X_[i]-X_[j]) + (Y_[i]-Y_[j])*(Y_[i]-Y_[j])) - R_[i] - R_[j];
    		if(dist < 0.0)	dist = 0.0;
    		adj[i].pb({dist, j});
    		adj[j].pb({dist, i});
    	}

    for(int i=1;i<=n;i++)
    	dist[i] = 1e15;
    priority_queue<pdi> pq;

    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){

    	int v = pq.top().ss;
    	double d = -pq.top().ff;
    	pq.pop();

    	if(d > dist[v])	continue;

    	for(auto it : adj[v]){
    		int vv = it.ss;
    		double dd = d + it.ff;
    		if(dd < dist[vv]){
    			dist[vv] = dd;
    			pq.push({-dd, vv});
    		}
    	}
    }

    cout<<fixed<<setprecision(10)<<dist[t];
    return 0;
}









Measured memory_bytes: 20740
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    N, Q, *ABPX = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(ABPX[0 : 2 * N - 2 : 2], ABPX[1 : 2 * N - 2 : 2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    X = [0] * N
    for p, x in zip(ABPX[2 * N - 2 :: 2], ABPX[2 * N - 1 :: 2]):
        X[p - 1] += x

    C = [0] * N
    C[0] = X[0]
    seen = [False] * N
    stack = deque([0])

    while stack:
        v = stack.pop()
        seen[v] = True
        for nv in G[v]:
            if not seen[nv]:
                stack.append(nv)
                C[nv] = C[v] + X[nv]

    print(*C)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 143248
N = int(input())
H = list(map(int, input().split()))
ans = 0
a = 0
for i in range(N - 1):
    if H[i] < H[i + 1]:
        ans = max(ans, a)
        a = 0
        continue
    a += 1
    ans = max(ans, a)
print(ans)


Measured memory_bytes: 14224
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var items = Console.ReadLine().Split().Select(elem => int.Parse(elem)).ToArray();
            var N = items[0];
            var M = items[1];
            var X = items[2];
            var books = Enumerable.Range(0, N).Select(i => Console.ReadLine().Split().Select(elem => int.Parse(elem)).ToList()).ToList();

            var answer = int.MaxValue;
            foreach (var bit in Enumerable.Range(1, (int)Math.Pow(2, N) - 1))
            {
                var totalPrice = 0;
                var algoSums = Enumerable.Range(0, M).Select(elem => 0).ToArray();
                foreach (var chooseBook in books.Where((elem, idx) => (bit & (long)Math.Pow(2, idx)) != 0))
                {
                    totalPrice += chooseBook[0];
                    algoSums = algoSums.Zip(chooseBook.Where((elem, idx) => idx >= 1), (s, c) => s + c).ToArray();
                }

                if (algoSums.All(elem => elem >= X))
                {
                    answer = Math.Min(answer, totalPrice);
                }
            }

            Console.WriteLine(answer == int.MaxValue ? -1 : answer);
        }
    }
}


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<'\n'

int main(){
    string s;
    cin >> s;
    map<char,int>mp;
    REP(i,s.size()){
        mp[s[i]]++;
    }
    bool flag = true;
    for(const auto& x:mp){
        int num = x.second;
        if(3*num-2>s.size())flag = false;
    }
    if(flag)COUT("YES");
    else COUT("NO");
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

const int MOD = 1000000007;

long long max(long long a,long long b){
	if(a<b)return b;
	else return a;	
}
long long min(long long a,long long b){
	if(a>b)return b;
	else return a;	
}
long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	else return gcd(a%b,b);
}

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


long long getDigit(long long n){
	if(n==1)return 1;
	else return log10(n)+1;
}

class Point{
public:
	long long x;
	long long y;
};
long long N,M;
vector<long long>X(100006,0);
bool isOK(long long time){
	long right=0;
	for(int i=0;i<M;i++){
		if(right>=X[i]-1){
			//go right
			right=X[i]+time;
		}else{
			if(right < X[i]-time-2)return false;
			right=max(X[i],X[i]+(time-(2*(X[i]-right)-1)));
		}
		//cout<<right<<endl;
	}
	if(right<N-1)return false;
	return true;
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	long long x1,x2,y1,y2;
	cin>>x1>>y1>>x2>>y2;
	cout<<x2-(y2-y1)<<endl;
	cout<<y2+(x2-x1)<<endl;
	cout<<x1-(y2-y1)<<endl;
	cout<<y1+(x2-x1)<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int infint = 1e9;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)2e3 + 7;
ll n, a, b;
ll grundy(ll a, ll b)
{
	if(a < b)
		return 0;
	if(a % b == 0)
		return a / b;
	else
		return grundy((a * (b - 1)) / b, b);
}
ll grundy2(ll a, ll b)
{
	ll L = 0, R = infint;
	while(R - L > 1)
	{
		ll mid = (L + R) >> 1;
		ll c = a - (a / b) * mid - mid;
		if(c <= 0 || c / b != a / b)
			R = mid;
		else
			L = mid;
	}
	ll q = a / b + 1, T = (a / b) * b;
	if(T % q == a % q)
		return a / b;
	else
		return grundy2(a - R * q, b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	ll ans = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		if(b <= (int)sqrt(a))
			ans ^= grundy(a, b);
		else
			ans ^= grundy2(a, b);
	}
	if(ans == 0)
		cout << "Aoki";
	else
		cout << "Takahashi";
}

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

using namespace std;

#define ll long long int 

ll maxl=1e9+1;

int main()
{
	ll n,m;
	cin>>n>>m;
	ll sum=0;
	for(int i=0,a;i<m;i++)
	{
		cin>>a;
		sum+=a;
	}
	if(n>=sum)
		cout<<n-sum<<endl;
	else 
		cout<<"-1"<<endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);
    
    long n, p;
    cin >> n >> p;
    long long even = 1;
    long long odd = 0;
    for(long i = 0; i<n; i++){
        long x;
        cin >> x;
        if(x%2==0){
            even += even;
            odd += odd;
        }
        else{
            long long a = even;
            long long b = odd;
            even += b;
            odd += a;
        }
    }
    if(p%2==0){
        cout << even;
    }
    else{
        cout << odd;
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a , b;
    cin >> a;
    b = sqrt( a );
    cout << b * b;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    int N, K;
    cin >> N >> K;
    vec<int> V(N);
    rep(i, N) cin >> V[i];

    int ans = 0;
    rep(l, N + 1) rep(r, N + 1) {
        if (l + r > N || l + r > K) continue;
        vec<int> J;
        rep(i, l) J.push_back(V[i]);
        rep(i, r) J.push_back(V[N - 1 - i]);
        sort(all(J));
        int tmpans = accumulate(all(J), 0);
        int k      = min(K - (l + r), (int)J.size());
        rep(i, k) if (J[i] < 0) tmpans -= J[i];
        ans = max(ans, tmpans);
    }
    cout << ans << endl;
}

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int,int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

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

template<typename T>
struct BIT{
    private:
        using Func = function<T(T, T)>;

        int n;
        vector<T> node;

        T init_v;
        Func func;

    public:

        BIT(int N, Func _func, T _init_v) {
            n = N + 1;
            init_v = _init_v;
            func = _func;

            node.resize(n, init_v);
            for(int i=1; i<n; i++) if((i+(i&-i)) < n) node[i+(i&-i)] = func(node[i+(i&-i)], node[i]);
        }

        BIT() {}

        void add(int pos, T v) {
            // 1-indexed
            while(pos < n){
                node[pos] = func(node[pos], v);
                pos += pos & -pos;
            }
        }

        T sum(int pos){
            // 1-indexed
            T res = init_v;
            while(pos > 0){
                res = func(res, node[pos]);
                pos = pos & (pos-1);
            }
            return res;
        }
};

void Main(){
    int N,Q; cin >> N >> Q;
    VI c(N); REP(i,N) cin >> c[i];

    VVI v(N);
    VI last(N+1,-1);
    REP(i,N){
        if(last[c[i]]>=0) v[last[c[i]]].push_back(i);
        last[c[i]] = i;
    }

    vector<vector<P>> q(N);
    REP(i,Q){
        int l,r; cin >> l >> r; l--;
        q[l].emplace_back(r,i);
    }

    VI ans(Q);
    BIT<int> bit(N,[](int a,int b){return a+b;},0);
    RREP(i,N){
        for(int j : v[i]){
            bit.add(j+1,1);
        }
        for(auto& p : q[i]){
            int r = p.first, id = p.second;
            ans[id] = r-i - bit.sum(r);
        }
    }

    REP(i,Q) cout << ans[i] << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}

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

using namespace std;
using ll = long long;

const ll mod = 1e9+7;

vector<int> num;
vector<vector<int>> hen;
vector<bool> seen;
int n, k;

void dfs_cnt(int c)
{
    int cur = (c == 0 ? k : k - 1);
    for(auto i : hen[c])
    {
        if(seen[i])continue;
        seen[i] = true;
        if(cur == 0)cur = 1;
        num[i] = --cur;
        dfs_cnt(i);
    }
}


int main()
{
    cin >> n >> k;
    hen.resize(n);
    num.resize(n);
    seen.resize(n);
    for(int i = 0; i < n - 1; i++){
        int a,b; cin >> a >> b; a--; b--;
        hen[a].push_back(b);
        hen[b].push_back(a);
    }

    seen[0] = true;
    num[0] = k;
    dfs_cnt(0);

    ll ans = 1;
    for(int i = 0; i < n; i++){
        ans *= num[i];
        ans %= mod;
    }
    cout << ans << endl;





}

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

#define int long long
#define uint unsigned int
#define pii pair<int, int>
#define fi first
#define se second

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())

#define PF(a) push_front(a)
#define PB(a) push_back(a)
#define EMPF(...) emplace_front(__VA_ARGS__)
#define EMPB(...) emplace_back(__VA_ARGS__)
#define EMP(...) emplace(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)

#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, -1, sizeof(a))

#define PW(n) (1LL << (n))
#define NUM(x) char(x + '0')
#define ALP(x) char(x + 'a')

using namespace std;

template <class T> inline bool CHMIN(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool CHMAX(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> void SORT(vector<T> &a) { sort(a.begin(), a.end()); }
template <class T> void SORTR(vector<T> &a) { sort(a.rbegin(), a.rend()); }
template <class T> void UNIQUE(vector<T> &a) { a.erase(unique(a.begin(), a.end()), a.end()); }

template <class S, class T> ostream& operator << (ostream& os, const pair<S, T> v) {
  os << "(" << v.first << ", " << v.second << ")"; return os;
}

const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

/* ---------------------------------------------------------------------------------------------------- */

int y, m, d;
char c;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> y >> c >> m >> c >> d;
  cout << (y < 2019 || m < 5 ? "Heisei" : "TBD") << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, K; cin >> N >> K; 
	int ans = 0;  
	for(int i = 0; i < N; i++){
		int H; cin >> H; 
		if(H >= K) ans ++; 
	}
	cout << ans << endl; 
}

Measured memory_bytes: 256
import statistics

def calc_sad_param(b):
    global numbers
    sad_param = 0
    for i in range(len(numbers)):
        sad_param += abs(numbers[i] - i - b)
    return int(sad_param)

n = int(input())
numbers = list(map(int, input().split()))
b_list = [numbers[i] - i for i in range(n)]
print(calc_sad_param(statistics.median(b_list)))

Measured memory_bytes: 27244
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):
    S1, S2 = S
    prev = 0
    counter = 1
    i = 0
    while i<N:
        if S1[i] == S2[i]:
            if prev == 0:
                counter *= 3
            elif prev == 1:
                counter *= 2
            prev = 1
            i += 1
        else:
            if i > 0:
                if S1[i-1] == S1[i] and S2[i-1] == S2[i-1]:
                    i += 1
                    continue
            if prev == 0:
                counter *= 6
            elif prev == 1:
                counter *= 2
            elif prev == 2:
                counter *= 3
            prev = 2
            i += 1
        counter %= MOD
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(2)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import std.stdio;
import std.algorithm;
import std.range;
import std.conv;

void main() {
    string[] input = split(readln());
    int n = to!int(input[0]);
    int a = to!int(input[1]);
    int b = to!int(input[2]);
    bool check() {
        if (a+b-1 > n) return false;
        if (long(a)*b < n) return false;
        return true;
    }
    if (!check()) {
        writeln(-1);
        return;
    }
    int[] num = new int[a];
    int sum = b;
    num[0] = b;
    foreach (i; 1..a) {
        num[i] = 1;
        sum++;
    }
    while (sum < n) {
        foreach (i; 1..a) {
            if (sum == n) break;
            num[i]++;
            sum++;
        }
    }
    int[] ans = new int[n];
    int x = 1;
    foreach (i; 0..a) {
        foreach_reverse (j; x..x+num[i]) {
            ans[j-1] = x++;
        }
    }
    foreach (i; ans) {
        writeln(i);
    }
}

Measured memory_bytes: 6012
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define DEB 0
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back


class state{
public:
  int x,y;
  vector<int> ma; // 1base
  state(int _x, int _y, vector<int> m){
    x=_x; y=_y;
    ma.swap(m);
  }
  bool operator<(const state& a)const{
    if( x!=a.x ) return x<a.x;
    if( y!=a.y ) return y<a.y;
    return ma < a.ma;
  }
  bool operator==(const state& a)const{
    return x==a.x && y==a.y && ma==a.ma;
  }
};

const int dx[] = {0,1,0,-1}; //up, right, down, left
const int dy[] = {-1,0,1,0};
int n,m,p;
int sx,sy;
map<state,long long> msi;
char field[52][52];
vector<string> ope;

bool inside(int x, int y){
  return !(x<0 || x>=m || y>=n || y<0 || field[y][x]=='#');
}
int DIR(char c){
  if( c=='U' ) return 0;
  if( c=='R' ) return 1;
  if( c=='D' ) return 2;
  if( c=='L' ) return 3;
}
int main(){	
  while(cin>>n>>m,n|m){
    ope.clear();
    msi.clear();
    rep(i,n){
      cin>>field[i];
      rep(j,m)if( field[i][j]=='S' ){
	sx = j;
	sy = i;
      }
    }
    cin>>p;
    rep(i,p){
      string tmp; cin>>tmp;
      ope.pb(tmp);
    }
    // ª¶ñÅoÄ­éàÌÍí·é
    
    bool gao[16];
    memset(gao,true,sizeof(gao));
    rep(i,ope.size())if( gao[i] ){
      int j;
      for(j=0; j<ope.size(); j++)if( i!=j && gao[j] ){
	if( ope[i].find(ope[j]) != string::npos ){
	  gao[i] = false;
	  break;
	}
      }
    }
    vector<string> tmp;
    rep(i,ope.size())if( gao[i] )tmp.pb(ope[i]);
    ope.swap(tmp);

    queue<state> q;
    bool goal = false;
    long long ans = -1;
    q.push(state(sx,sy,vector<int>(ope.size(),0)));
    msi[state(sx,sy,vector<int>(ope.size(),0))] = 0;
    while( !q.empty() ){
      int x = q.front().x;
      int y = q.front().y;
      vector<int> ma = q.front().ma;
      long long cost = msi[q.front()];
      q.pop();

      rep(k,4){
	vector<int> hoge(ope.size(),0);
	int tx = x + dx[k];
	int ty = y + dy[k];
	if( !inside(tx,ty) )continue;
	bool ok = true;
	rep(j,ma.size()){
	  if( DIR(ope[j][ma[j]+1-1]) == k ){
	    hoge[j] = ma[j]+1;
	    if( hoge[j]==ope[j].length() ){ ok = false; break; }
	  }else{
	    string aaa = ope[j].substr(0,ma[j]) + string(1,k==0?'U':k==1?'R':k==2?'D':'L');
	    int l;
	    for(l=0; l<aaa.size(); l++){
	      int u;
	      for(u=0; u+l<aaa.size(); u++){
		if( aaa[l+u]!=ope[j][u] )break;
	      }
	      if( u+l==aaa.size() ){
		break;
	      }
	    }
	    hoge[j] = aaa.size() - l;
	  }
	}
	if( !ok ) continue;

	if( field[ty][tx]=='G' ){
	  ans = cost + 1;
	  goal = true;
	}
	state ts(tx,ty,hoge);
	map<state,long long>::iterator it = msi.lower_bound(ts);
	if( it!=msi.end() && it->first==ts ){
	  if( it->second > cost+1 ){
	    it->second = cost+1;
	    q.push(ts);
	  }
	}else{
	  msi.insert(it,make_pair(ts,cost+1));
	  q.push(ts);
	}
      }
      if( goal ) break;
    }
    printf("%lld\n",ans);
  }
  return 0;
}

Measured memory_bytes: 9544
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;

int read()
{
    int x=0,flag=1;
    char c=getchar();
    while((c>'9' | c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

int main()
{
    //freopen("input.txt","r",stdin);
    int max1=0,max2=0,k=0,x,n;
    n=read();
    for(int i=1;i<=n;i++)
    {
        x=read();
        if(x>max1) max2=max1,max1=x,k=i;
        else if(x>max2) max2=x;
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",i==k?max2:max1);

	return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>

int main()
{   int a,b;
    scanf("%d%d",&a,&b);
    if(a>b){
        int tmp=b;
        b=a;
        a=tmp;
    }
    if((b-a)%2==0){
    printf("%d",b-(b-a)/2);
    }else{
        printf("IMPOSSIBLE");
    }
    return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <iomanip>
#include <limits>

#define roop(i, n) for(int i=0;i<n;i++)
#define DIV 1000000007
//static const long double pi = 3.1415926535897932;

using namespace std;
using ll = long long int;
using ull = unsigned long long;

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

ll combination(ll n, ll r) {
	if (n < 0 || r < 0 || r > n) return -1;

	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> num(r);
	vector<ll> den(r);

	for (ll i = 0; i < r; i++) {
		num[i] = n - r + i + 1;
		den[i] = i + 1;
	}

	for (ll p = 2; p <= r; p++) {
		ll pivot = den[p - 1];
		if (pivot > 1) {
			ll offset = (n - r) % p;
			for (ll k = p - 1; k < r; k += p) {
				num[k - offset] /= pivot;
				den[k] /= pivot;
			}
		}
	}
	ll result = 1;
	for (ll k = 0; k < r; k++) {
		if (num[k] > 1) result *= num[k];
	}
	return result;
}

vector<string> split(const string& src, const char* delim = ",") {
	vector<string> vec;
	string::size_type len = src.length();

	for (string::size_type i = 0, n; i < len; i = n + 1) {
		n = src.find_first_of(delim, i);
		if (n == string::npos) {
			n = len;
		}
		vec.push_back(src.substr(i, n - i));
	}

	return vec;
}

bool check_int(string str)
{
	if (all_of(str.cbegin(), str.cend(), [](char ch) { return isdigit(ch);}))
	{
		return true;
	}
	return false;
}

int main() {
	int x, k;
	cin >> k >> x;
	if (500 * k >= x) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
#define MAX 100001
#define NIL -1

struct Node
{
  int parent, left, right;
};

Node TREE[MAX];
int n, DEP[MAX];

void print(int u)
{
  int i, c;
  printf("node %d: ", u);
  printf("parent = %d, ", TREE[u].parent);
  printf("depth = %d, ", DEP[u]);

  if (TREE[u].parent == NIL)
    printf("root, [");
  else if (TREE[u].left == NIL)
    printf("leaf, [");
  else
    printf("internal node, [");

  for (int i = 0, c = TREE[u].left; c != NIL; i++, c = TREE[c].right)
  {
    if (i)
      printf(", ");
    printf("%d", c);
  }
  printf("]\n");
}

void setDepth(int u, int p)
{
  DEP[u] = p;
  if (TREE[u].right != NIL)
    setDepth(TREE[u].right, p);
  if (TREE[u].left != NIL)
    setDepth(TREE[u].left, p + 1);
}

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

  for (int i = 0; i < n; i++)
    TREE[i].parent = TREE[i].left = TREE[i].right = NIL;

  for (int i = 0; i < n; i++)
  {
    int id, k, childId;
    scanf("%d%d", &id, &k);
    for (int j = 0; j < k; j++)
    {
      scanf("%d", &childId);
      if (j == 0)
        TREE[id].left = childId;
      else
        TREE[child].right = childId;
      child = childId;
      TREE[childId].parent = id;
    }
  }

  int root;
  for (int i = 0; i < n; i++)
    if (TREE[i].parent == NIL)
      root = i;

  setDepth(root, 0);

  for (int i = 0; i < n; i++)
    print(i);

  return 0;
}

Measured memory_bytes: 7412
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int deck_len = 205;

char *shuffle_n_card(char *deck, int shuffle_num){
    char *deck_copied;
    deck_copied = (char*)malloc(deck_len*sizeof(char));
    memset(deck_copied, '\0', sizeof(deck_copied));

    deck += shuffle_num;
    strcpy(deck_copied, deck);

    deck -= shuffle_num;
    strncat(deck_copied, deck, shuffle_num);

    strcpy(deck, deck_copied);
    return deck;
}

int main(){
    char *deck_string;
    deck_string = (char*)malloc(deck_len*sizeof(char));
    int i, shuffle;
    
    while(1){
        scanf("%s", deck_string);
        if(!strcmp(deck_string, "-"))break;
        int num_of_shuffle;
        scanf("%d", &num_of_shuffle);
        for(i=0; i<num_of_shuffle; i++){
            scanf("%d", &shuffle);
            shuffle_n_card(deck_string, shuffle);
        }
        printf("%s\n", deck_string);
    }
}



Measured memory_bytes: 2044
//21
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  for(int n,m,h,k;cin>>n>>m>>h>>k,n|m|h|k;){
    static bool l[1000][1000];
    fill(l[0],l[1000],false);
    int p[1000];
    for(int i=0;i<n;i++){
      cin>>p[i];
    }
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a>>b;
      l[b][a-1]=true;
    }
    int w[1000];
    for(int i=0;i<n;i++){
      w[i]=i;
    }
    static bool c[1000][1000];
    fill(c[0],c[1000],false);
    for(int i=h-1;i>=0;i--){
      for(int j=0;j<n;j++){
	if(l[i][j]){
	  swap(w[j],w[j+1]);
	  c[w[j]][w[j+1]]=c[w[j+1]][w[j]]=true;
	}
      }
    }
    int m,o=0;
    bool g[1000]={};
    for(int i=0;i<k;i++){
      o+=p[w[i]];
      g[w[i]]=true;
    }
    m=o;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(g[i]&&!g[j]&&c[i][j]){
	  m=min(m,o-p[i]+p[j]);
	}
      }
    }
    cout<<m<<endl;
  }
  return 0;
}
    

Measured memory_bytes: 3116
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

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

            int a = X % 100;

            int count = 0;

            while(a > 0)
            {
                if(a >= 5)
                {
                    a -= 5;
                }
                else if(a >= 4)
                {
                    a -= 4;
                }
                else if(a >= 3)
                {
                    a -= 3;
                }
                else if(a >= 2)
                {
                    a -= 2;
                }
                else if(a >= 1)
                {
                    a -= 1;
                }

                count++;
            }

            if(count > X / 100)
            {
                Console.WriteLine(0);
            }
            else
            {
                Console.WriteLine(1);
            }
        }
    }
}

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

int main() {
	int x;
	cin >> x;
	if (x>=30) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

using namespace std;
typedef long long LL;
static LL INF = (1LL<<62);

using LLPair = pair<LL, LL>;
using WeightedGraph = vector<vector<LLPair>>;
using PriorityQ = priority_queue<LLPair, vector<LLPair>, greater<LLPair>>;

void dijkstra(WeightedGraph &WG, vector<LL> &D, LL s){
	for(int i=0; i<D.size(); i++){
		D[i] = INF;
	}
	D[s] = 0;

	PriorityQ pq;
	pq.push(make_pair(0, s));
	while(!pq.empty()){
		LL pos = pq.top().second; pq.pop();
		for(auto nv : WG[pos]){
			LL to = nv.first;
			LL cost = nv.second;
			if(D[to] > D[pos] + cost){
				D[to] = D[pos] + cost; 
				pq.push(make_pair(D[to], to));
			}
		}
	}
	return;
}

void chminMapV(map<pair<LL, LL>, LL> &m, pair<LL, LL> &k, LL v){
	if(m.count(k) == 0){
		m[k] = v;
	}
	else{
		m[k] = min(m[k], v);
	}
}

LL N, M, R;
int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	vector<LL> r;
	cin >> N >> M >> R;

	for(int i=0; i<R; i++){
		LL t; cin >> t;
		r.push_back(t-1);
	}

	WeightedGraph WG(N);
	for(int i=0; i<M; i++){
		LL a, b, c; cin >> a >> b >> c;
		a--; b--;
		WG[a].push_back(make_pair(b, c));
		WG[b].push_back(make_pair(a, c));
	}

	map<pair<LL, LL>, LL> M;
	for(int i=0; i<r.size(); i++){
		for(int j=i+1; j<r.size(); j++){
			vector<LL> dist(N);
			dijkstra(WG, dist, r[i]);
			LL d = dist[r[j]];
			auto p1 = make_pair(r[i], r[j]);
			auto p2 = make_pair(r[j], r[i]);
			chminMapV(M, p1, d);
			chminMapV(M, p2, d);
		}
	}

	sort(r.begin(), r.end());
	LL ans = INF;
	do{
		LL w = 0;
		for(int i=0; i<r.size()-1; i++){
			auto p = make_pair(r[i], r[i+1]);
			w += M[p];
		}
		if(ans > w){
			ans = w;
		}
	}
	while(next_permutation(r.begin(), r.end()));

	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4700
// ABC163C.cpp

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

int main()
{
    int n;
    cin >> n;
    int a[200005] = {};
    int x;
    for(int i=2;i<=n;i++){
        cin >> x;
        a[x]++;
    }
    for (int i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
}


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

int main() {
	int N;
    cin >> N;
  
  	string ans = "No";
  	bool stop = false;
  
  	for(int i = 0; i <= 25;i++) {
    	for(int j = 0; j < 15; j++) {
        	int sum = 4 * i + 7 * j;
          if(sum == N) {
          	ans ="Yes";
            stop = true;
            break;
          }
        }
      if(stop) break;
    }
  
    cout << ans << endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<string, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3
#define MAX_N 100010

ll p;

struct BIT{
  ll bit[MAX_N];

  void init(){
    memset(bit,0,sizeof(bit));
  }

  ll sum(int i){
    ll s=0;
    while(i>0){
      s=(s+bit[i])%p;
      i-=i&-i;
    }
    return s;
  }

  void add(int i,ll v){
    while(i<=MAX_N){
      bit[i]=(bit[i]+v)%p;
      i+=i&-i;
    }
  }
};

ll a,b,n;
ll idx[100010];

int main(){
	cin.sync_with_stdio(false);
  while(1){
    cin>>a>>b>>p;
    if(a==0&&b==0&&p==0)break;
    vector<P> ss;
    n=b-a+1;
    ss.resize(n);
    rep(i,n){
      ss[i]=P(to_string(i+a),i);
    }
    sort(all(ss));
    rep(i,n){
      idx[ss[i].se]=i;
    }
    BIT dp;
    dp.init();
    rep(i,n){
      ll tmp=dp.sum(idx[i]+1)%p;
      dp.add(idx[i]+1,(tmp+1)%p);
    }
    cout<<dp.sum(n+1)%p<<endl;
  }
	return 0;
}

Measured memory_bytes: 10900
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int x = scanner.nextInt();
		int y = scanner.nextInt();
		System.out.print(x * y + " ");
		System.out.println(2 * (x + y));
	}
}


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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t = "ABC";
    int j = 0;
    int ans = 0;
    rep(i, n) {
        if (s[i] ==  t[j]) {
            j++;
        } else if (s[i] == t[0]) {
            j = 1;
        } else {
            j = 0;
        }
        if (j == 3) {
            ans++;
            j = 0;
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define INF 1001001001  //int32_t
#define MOD 1000000007
#define MOD2 998244353

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

#define mkp make_pair
#define pb push_back

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

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

    if(c <= a+b + 1){
        ans = c + b;
    }else{
        ans = a + 2*b + 1;
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


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

int solve(vector<int>& arr, int n) {
    int res = 1;
    int min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] <= min_val) {
            min_val = arr[i];
            res++;
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << solve(arr, n) << endl;
    return 0;
}

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

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

	ll minr = 2000000000;
	ll maxv = -1000000000;
	rep(i, n) {
		ll r;
		cin >> r;
		maxv = max(maxv, r-minr);
		minr = min(minr, r);
	}
	cout << maxv << endl;
	return 0;
}


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

using namespace std;

int t[100001], x[100001], y[100001];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> x[i] >> y[i];
	}
	bool ans = true;
	for (int i = 0; i < n - 1; i++) {
		int d = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
		int nt = t[i + 1] - t[i];
		if ((d % 2) != (nt % 2)) {
			ans = false;
		}
		if (d > nt) ans = false;
	}
	if (n == 1) {
		int d = x[0] + y[0];
		if ((d % 2) != (t[0] % 2) || d > t[0]) {
			ans = false;
		}
	}
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}

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

int main() {
 int N;
 cin >> N;
  vector<long long> A(N+1);
  vector<long long> B(N);

  for(int i = 0;i<N+1;i++){
    cin >> A[i];
  }
  for(int i = 0;i<N;i++){
    cin >> B[i];
  }
  long long  ans = 0;
  for(int i = 0;i<N;i++){
    if(A[i] < B[i]){
      ans += A[i];
      B[i] = B[i] -A[i];
      A[i] = 0;
      if(B[i] < A[i+1]){
        ans += B[i];
        A[i+1] = A[i+1] - B[i];
        B[i] = 0;
        
      }
      else if(B[i] >= A[i+1]){
        ans += A[i+1];
        B[i] = B[i] - A[i+1];
        A[i+1] = 0;
      }
    }
    if(A[i] >=B[i]){
      ans += B[i];
      A[i]= A[i]-B[i];
      B[i]= 0;
    }
  }
  cout << ans << endl;
    
  
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	std::vector<int> vec = {1, 5, 10, 50, 100, 500};
	int tmp = 0;
	for(int i = 0; i < vec.size(); i++) {
		int n; scanf("%d", &n);
		
		tmp += n * vec[i];
	}
	
	printf("%d\n", tmp >= 1000);
	return 0;
}



Measured memory_bytes: 3204
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    string s; cin>>s;

    vint sum(N+1,0);
    REP(i,N){
        sum[i+1]=sum[i]+(s[i]=='W');
    }
    
    int ans=N;
    REP(i,N){
        int l=sum[i];
        int r=N-(i+1)-(sum[N]-sum[i+1]);
        ans=min(ans,l+r);
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a % b);
}
int main()
{
    long long n;
    cin >> n;
    vector<long long> a(n), b(n, 0);
    map<long long, int> mp;
    long long x = -1;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
        mp[a[i]]++;
    }
    sort(begin(b), end(b));
    for (int i = 0; i < n; i++)
    {
        if (mp[a[i]] == 1 && a[i] == b[n - 1])
        {
            cout << b[n - 2] << endl;
        }
        else if (mp[a[i]] == 2 && a[i] == b[n - 1])
        {
            cout << b[n - 1] << endl;
        }
        else
        {
            cout << b[n - 1] << endl;
        }
    }
}

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

int main() {
  int N, A;
  cin >> N;
  pair<int, int> P[N];
  rep(i, N){
    cin >> A;
    P[i]=make_pair(A, i+1);
  }
  sort(P, P+N);
  rep(i, N){
    cout << P[i].second;
    if(i!=N-1) cout << " ";
    else cout << endl;
  }
}

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

ll W, H, K;

ll dp[10][200];
llvec num;
ll prop=0;


ll dpf(ll n, ll h){
  if(dp[n][h]>=0){
    return dp[n][h];
  }else{
    dp[n][h]=0;
    if(h==1){
      if(n==0)dp[n][h]=1;
    }else{
      ll tmp = prop;
      if(n-1>=0){
        dp[n][h] =mod(dp[n][h] +dpf(n-1, h-1)*num[n-1], MOD);
        tmp -= num[n-1];
      }
      if(n+1<=W-1){
        dp[n][h] =mod(dp[n][h]+ dpf(n+1, h-1)*num[n], MOD);
        tmp -= num[n];
      }
      dp[n][h] =mod(dp[n][h] + dpf(n, h-1)*tmp, MOD);
    }
    return mod(dp[n][h], MOD);
  }
}

bool chk(ll i, ll k){
  bool ans = true;
  ans = ans and (i>>k&1);
  rep(j, W-1){
    ans = ans and ((i>>j&1)==0 or (i>>(j+1)&1)==0);
  }
  return ans;
}
bool pro(ll i){
  bool ans = true;
  rep(j, W-2){
    ans = ans and ((i>>j&1)==0 or (i>>(j+1)&1)==0);
  }
  return ans;
}

/**************************************
** A main function starts from here  **
***************************************/
int main(){
  cin >> H >> W >> K;
  num = llvec(W-1, 0);
  rep(i, pow(2, W-1)){
    if(pro(i))prop++;
    rep(j, W-1){
      if(chk(i, j))num[j]++;
    }
  }
  //DUMP(i, num)<< prop << endl;
  fill(dp[0], dp[10], -100);
  cout << dpf(K-1, H+1);
  return 0;
}


Measured memory_bytes: 4084
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe

readInt = fst . fromJust . BS.readInt

getIntListN n = map readInt <$> replicateM (fromIntegral n) BS.getLine

calc :: [Int] -> Bool -> Int
calc [] lo = 0
calc (x : xs) lo
  | x `mod` 10 == 0 = x + calc xs lo
  | lo = x + calc xs False
  | otherwise = ((x + 9) `div` 10) * 10 + calc xs lo

main = do
  xs <- getIntListN 5
  let xs' = sortBy (\x y -> compare (x `mod` 10) (y `mod` 10)) xs
  print $ calc xs' True


Measured memory_bytes: 380
import java.util.*;
public class Main {
	 public static long gcd(long x,long y){
        if(x < y) return gcd(y, x);
        if(y == 0) return x;
        return gcd(y, x % y);
    }
    public static long lcm(long x,long y){                                                              
        return x*y/gcd(x,y);                                                                                                                                                                                                                
    }
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long d = sc.nextLong();
        long e = (b-a+1)/c;
        if(a%c+(b-a+1)%c-1>=c||(a%c==0 &&(b-a+1)%c!=0)){e++;}
        long f = (b-a+1)/d;
        if(a%d+(b-a+1)%d-1>=d||(a%d==0 &&(b-a+1)%d!=0)){f++;}
        long g = (b-a+1)/lcm(c,d);
        if(a%lcm(c,d)+(b-a+1)%lcm(c,d)-1>=lcm(c,d)||(a%lcm(c,d)==0 &&(b-a+1)%lcm(c,d)!=0)){g++;}
		System.out.println(b-a+1-e-f+g);
	}
}


Measured memory_bytes: 22228
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int MOD = 1000000007;
const char ENDL = '\n';

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);

    int n,l;
    cin >> n >> l;
    VI a(n);
    REP(i,n){
        cin >> a[i];
    }

    bool f=false;
    int p;
    FOR(i,1,n){
        if (a[i-1]+a[i]>=l){
            f = true;
            p=i;
        }
    }
    if (f){
        cout << "Possible" << ENDL;
        FOR(i,1,p){
            cout << i << ENDL;
        }
        for (int i = n-1; i >p; --i) {
            cout << i << ENDL;
        }
        cout << p << ENDL;

    } else{
        cout << "Impossible" << ENDL;
    }

    return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int n,d;cin >> n >> d;
  vector<vector<int>> x(n,vector<int>(d));
  rep(i,n) rep(j,d) cin >> x[i][j];
  vector<int> sqr;
  rep1(i,200) sqr.push_back(i*i);

  int res=0;
  rep(i,n) rep(j,n){
    if(i>=j) continue;
    int tmp=0;
    rep(k,d){
      tmp += (x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
    }
    bool f = false;
    rep(k,sqr.size()){
      if(tmp==sqr[k]){
	f = true;break;
      }
    }
    if(f) res++;
  }
  cout << res << "\n";
  return 0;
}


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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i ,a, b) for (int i = a ; i <= b ; i++)
#define sz(a) int(a.size())
#define cuti(a) cout << a << endl;
#define cutii(a,b) cout << a << " " << b << endl;
#define cutiii(a,b,c) cout << a << " " << b << " " << c << endl;
#define vec(a) vector<int > a;

template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }

typedef pair<int ,int > pii;
typedef long long LL;
const long long oo = 1e9 + 7;

int a,b,c,d,e,f;
set<int > water,sugar;
set<int >:: iterator l,k;
double density;
int mass , duong;

int main() {
  //  freopen("test.txt","r",stdin);
    cin >> a >> b >> c >> d >> e >> f;
    int tmp = (f/100) * e;

    for (int i =0 ; (100 *a*i ) <= f ; i++) {
        for (int j = 0 ; 100*(a*i + b*j ) <= f; j++) {
            water.insert( 100*a*i + 100*b*j);
        }
    }

     for (int i =0 ; i*c <= f ; i++) {
        for (int j = 0 ; (i * c + j* d) <= f ; j++) {
            sugar.insert( c*i + d*j);
        }
    }
    mass = 100*a;

    for ( l = water.begin() ; l != water.end() ; l++) {
        for ( k = sugar.begin() ; k != sugar.end() ; k++) {
            if ( *l+ *k > f) break;
            if ( *l * e < 100*(*k) ) break;
            if ( 1.0*duong*100 / mass  < 1.0**k*100 / ( *l+ *k)) {
                mass = *l + *k;
                duong = *k;
            }
        }
    }
    cout << mass << " " << duong << endl;
}


Measured memory_bytes: 384