akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static string Solve(string S, int w)
        {
            var sb = new StringBuilder();
            for (int i = 0; i < S.Length; i += w) { sb.Append(S[i]); }
            return sb.ToString();
        }
        static void Main(string[] args)
        {
            string S = Read();
            int w = ReadInt();
            Console.WriteLine(Solve(S, w));
        }
    }
}


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

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()

typedef tree<pair<ll,ll> ,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

const int MAXN = 305;

ld n, dp[MAXN][MAXN][MAXN];          // Expected time with val1 1s, val2 2s and val3 3s
ll a[MAXN], n1, n2, n3;

ld rec(ll val1, ll val2, ll val3)
{
	if(val1 == 0 && val2 == 0 && val3 == 0) return 0;
	if(dp[val1][val2][val3] != -1) return dp[val1][val2][val3];
	ld res = 1.00;
	if(val1 > 0)
		res = (res + ((ld)val1 / n) * rec(val1 - 1, val2, val3));
	if(val2 > 0)
		res = (res + ((ld)val2 / n) * rec(val1 + 1, val2 - 1, val3));
	if(val3 > 0)
		res = (res + ((ld)val3 / n) * rec(val1, val2 + 1, val3 - 1));
	if(val1 + val2 + val3 < n)
		res = (res * n) / ((ld)(val1 + val2 + val3));
	return dp[val1][val2][val3] = res;
}

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

	cin >> n;
	for(int i=0;i<n;i++) 
	{	
		cin >> a[i];
		n1 += (a[i] == 1);
		n2 += (a[i] == 2);
		n3 += (a[i] == 3);
	}	
	memset(dp, -1, sizeof(dp));
	printf("%.15Lf\n", rec(n1, n2, n3));
    return 0;
}

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

using namespace std;

#define allof(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define exists(s, e) (s.find(e)!=s.end())
#define INF 0x3f3f3f3f
#define f first
#define s second
#define endl '\n'
#define mp make_pair
#define watch(x) cout << (#x) << " is " << (x) << endl;

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

ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

void solve() {
    string str; cin >> str;
    int minx = INT_MAX;
    for(int i=0; i+3<=sz(str); i++) {
        int x = stoi(str.substr(i, 3));
//        watch(x);
        minx = min(minx, abs(x-753));
    }
    cout << minx << endl;
}

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


Measured memory_bytes: 256
S = input().strip()
if len(S) == 1:
  print(0)
else:
  n = 0
  for i, s_i in enumerate(S):
    if i%2 == 0:
      if s_i == '0':
        n += 1
    else:
      if s_i == '1':
        n += 1
  print(min(n, len(S)-n))

Measured memory_bytes: 3188
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <iomanip>
 
using namespace std;
 
typedef long long ll;
typedef pair <long long, long long> pll;
 
ll mod = 998244353;
 
int main(){
  ios_base::sync_with_stdio(false);
  ll h, w, k;
  cin >> h >> w >> k;
  vector <char> red(w);
  vector <vector <char> > mat(h,red);
  for (int i = 0; i < h; i++)
   for (int j = 0; j < w; j++)
    cin >> mat[i][j];
  vector <ll> bcr(h,0);
  vector <ll> bck(w,0);
  ll ub = 0;
  vector <bool> rr(w,false);
  vector <vector <bool> > veza(h,rr);
  for (int i = 0; i < h; i++){
    for (int j = 0; j < w; j++){
      if (mat[i][j] == '#') 
       ub++, bcr[i]++, bck[j]++, veza[i][j] = true;
    }
  }
  vector <vector <ll>> pr(1);
  vector <vector <ll>> pk(1);
  for (int i = 0; i < h; i++){
    ll s = pr.size();
    for (int j = 0; j < s; j++){
     vector <ll> t = pr[j];
     t.push_back(i);
     pr.push_back(t);
    }
  }
  for (int i = 0; i < w; i++){
    ll s = pk.size();
    for (int j = 0; j < s; j++){
     vector <ll> t = pk[j];
     t.push_back(i);
     pk.push_back(t);
    }
  }
  ll bn = 0;
  for (int i = 0; i < pr.size(); i++){
   for (int j = 0; j < pk.size(); j++){
     ll b1 = 0, b2 = 0;
     for (int t = 0; t < pr[i].size(); t++)
      b1 += bcr[pr[i][t]];
     for (int t = 0; t < pk[j].size(); t++)
      b2 += bck[pk[j][t]];
     ll suma = ub - (b1 + b2);
     for (int t = 0; t < pr[i].size(); t++)
      for (int q = 0; q < pk[j].size(); q++)
       if (veza[pr[i][t]][pk[j][q]])
        suma++;
     if (suma == k)
      bn++;
   }
  }
  cout << bn;
}

Measured memory_bytes: 3652
use std::io;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    n.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    n.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn str_join<T: std::string::ToString>(s: &Vec<T>) -> String {
    s.iter()
        .map(|i| i.to_string())
        .collect::<Vec<_>>()
        .join(" ")
}

fn main() {
    loop {
        let mut n = String::new();
        io::stdin().read_line(&mut n).unwrap();
        if n.trim() == "0" {
            break;
        }
        let sum: usize = n
            .trim()
            .chars()
            .map(|d| d.to_string().parse::<usize>().ok().unwrap())
            .sum();
        println!("{}", sum);
    }
}



Measured memory_bytes: 5036
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # return: articulation points, bridges
    # The graph must be connected.
    def lowlink(adj, root=1):
        N = len(adj) - 1
        order = [N + 1] * (N + 1)
        low = [N + 1] * (N + 1)
        AP = []
        bridge = []

        st = [root]
        cnt = 1
        par = [0] * (N + 1)
        seq = []
        while st:
            v = st.pop()
            if order[v] != N+1:
                continue
            order[v] = cnt
            seq.append(v)
            low[v] = cnt
            cnt += 1
            for u in adj[v]:
                if order[u] < cnt:
                    if par[v] != u:
                        low[v] = min(low[v], order[u])
                        continue
                else:
                    par[u] = v
                    st.append(u)

        child = [[] for _ in range(N + 1)]
        for v in range(1, N + 1):
            child[par[v]].append(v)

        seq.reverse()
        for v in seq:
            for u in child[v]:
                low[v] = min(low[v], low[u])

        # bridge
        for p in range(1, N+1):
            for c in child[p]:
                if order[p] < low[c]:
                    bridge.append((p, c))

        # articulation point
        for v in range(1, N + 1):
            if v == root:
                if len(child[v]) > 1:
                    AP.append(v)
            else:
                for c in child[v]:
                    if order[v] <= low[c]:
                        AP.append(v)
                        break

        return AP, bridge

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    AP, bridge = lowlink(adj)
    print(len(bridge))


if __name__ == '__main__':
    main()


Measured memory_bytes: 62920
// https://beta.atcoder.jp/contests/abc066

#include <bits/stdc++.h>
using namespace std;

bool visited[100001];
int a[100001];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int push = 0;
    bool ok = false;
    int curr = 1;
    while (true) {
        if (curr == 2) {
            ok = true;
            break;
        }
        if (visited[curr]) break;
        push++;
        visited[curr] = true;
        curr = a[curr];
    }

    if (ok) cout << push << endl;
    else cout << "-1" << endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int N,K;
int need(int x){
  if(x>=K) return 0;
  else return need(x*2)+1;
}

int main(){
  cin>>N>>K;
  vector<int> times(N);
  vector<int> numoftimes(100,0);
  for(int i=0;i<N;i++){
    times[i]=need(i+1);
    numoftimes[times[i]]++;
  }
  int saidai=times[0];
  vector<double> pro(saidai+10);
  pro[0]=1.0;
  for(int i=1;i<=saidai;i++){
    pro[i]=pro[i-1]*0.5;
  }
  double sum=0.0;
  for(int i=0;i<=saidai;i++){
    sum+=pro[i]*(double)numoftimes[i];
  }
  sum=sum/(double)N;
  cout<<setprecision(15)<<sum<<endl;
  return 0;
}



Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


void solve(int n,int m){
    vector<int> cnt(111);
    rep(i,n){
        int k;
        cin>>k;
        rep(j,k){
            int x;
            cin>>x;
            ++cnt[x];
        }
    }
    int ans=0,ma=m-1;
    rep(i,111){
        if(cnt[i]>ma){
            ans=i;ma=cnt[i];
        }
    }
    cout<<ans<<endl;
}
int main(){
    int n,m;
    while(cin>>n>>m,n!=0)solve(n,m);
    return 0;
}


Measured memory_bytes: 3004
#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(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main()
{
    int g[13]={};
    g[4]=g[6]=g[9]=g[11]=1;
    g[2]=2;

    int x,y;
    cin >>x >>y;
    cout << (g[x]==g[y]?"Yes":"No") << endl;
    return 0;
}


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

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string s;
    cin >> s;

    int cur = 0;
    bool ok = true;
    REP(i, s.size()) {
        if (cur >= s.size()) break;

        if (s.find("eraser", cur) == cur) {
            cur += 6;
            continue;
        }

        if (s.find("erase", cur) == cur) {
            cur += 5;
            continue;
        }

        if (s.find("dreamer", cur) == cur) {
            if (cur + 7 >= s.size()) continue;
            if (s[cur + 7] == 'd' || s[cur + 7] == 'e') {
                cur += 7;
                continue;
            }
        }

        if (s.find("dream", cur) == cur) {
            cur += 5;
            continue;
        }

        ok = false;
        break;
    }

    if (ok) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);


        while (true) {
            final int h = sc.nextInt();
            final int w = sc.nextInt();

            if (w == 0 && h == 0) {
                return;
            }

            final int[][] c = new int[w][h];
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    c[i][j] = sc.nextInt();
                }
            }

            final boolean[][] seen = new boolean[w][h];

            int ans = 0;
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    if (c[i][j] == 0 || seen[i][j]) {
                        continue;
                    }
                    dfs(c, seen, w, h, i, j);
                    ans++;
                }
            }

            System.out.println(ans);
        }
    }

    private static void dfs(int[][] c, boolean[][] seen, int w, int h, int x, int y) {
        if (x < 0 || w <= x || y < 0 || h <= y) {
            return;
        }

        if (c[x][y] == 0) {
            return;
        }

        if (seen[x][y]) {
            return;
        }

        seen[x][y] = true;

        dfs(c, seen, w, h, x-1, y-1);
        dfs(c, seen, w, h, x, y-1);
        dfs(c, seen, w, h, x+1, y-1);
        dfs(c, seen, w, h, x-1, y);
        dfs(c, seen, w, h, x, y);
        dfs(c, seen, w, h, x+1, y);
        dfs(c, seen, w, h, x-1, y+1);
        dfs(c, seen, w, h, x, y+1);
        dfs(c, seen, w, h, x+1, y+1);
    }
}



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

signed main(void){
    int n; cin >> n;
    if(n%2!=0){
        cout << 0 << endl;
        return 0;
    }

    int p = 1;
    int ans = 0;
    n = n/10;
    while(0<n){
        ans += n;
        n/=5;
    }


    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
    int H, N;
    int A[1000000];
    int i;
    scanf("%d %d", &H, &N);
    for(i = 0; i < N; i++)
    {
        scanf("%d", &A[i]);
        H = H - A[i];
    }
    if (H <= 0)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return (0);
}

Measured memory_bytes: 512
def prime(p):
    memo = []
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.append(i)
    if p != 1:
        memo.append(p)
    return memo


import collections

n,p = map(int,input().split())

memo = prime(p)

c = collections.Counter(memo)

score_sorted = sorted(c.items(), key=lambda x:-x[0])

if n == 1:
    ans = p
else:
    kake = []
    for i , j in score_sorted:
        if n <= j:
            kake.append(i**(j//n))
    ans = 1
    for i in kake:
        ans *= i

print(ans)

Measured memory_bytes: 38640
#include<stdio.h>
int main(void){
	int n;
	int count;
	int i,j,k,l;
	while(scanf("%d",&n)!=EOF){
		count=0;
		for(i=0;i<10;i++){
			for(j=0;j<10;j++){
				for(k=0;k<10;k++){
					for(l=0;l<10;l++){
						if(i+j+k+l==n){
							count++;
						}
					}
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 596
using System;
using System.Text.RegularExpressions;

namespace Atcoder2
{
    class Program
    {

        public static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int wantNum = int.Parse(input[0]);
            int maxNum = int.Parse(input[1]);
            int time = int.Parse(input[2]);

            int ans = wantNum / maxNum;
            if(wantNum % maxNum == 0)
            {
                Console.WriteLine(time * ans);
            } else
            {
                Console.WriteLine(time * (ans + 1));
            }
        }

    }
}

Measured memory_bytes: 27480
H, W = map(int,input().split())
S = [input() for i in range(H)]
ok = True
def check(i,j,H,W,S):
    flag = False
    if i+1 <= H-1:
        if S[i+1][j] == "#":
            flag = True
    if i-1 >= 0:
        if S[i-1][j] == "#":
            flag = True
    if j+1 <= W-1:
        if S[i][j+1] == "#":
            flag = True
    if j-1 >= 0:
        if S[i][j-1] == "#":
            flag = True
    return flag
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            ch = check(i,j,H,W,S)
            if not ch:
                ok = False
                break
    if not ok:
        break
if ok:
    print("Yes")
else:
    print("No")

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

int main() {
  
  string s; cin >> s;
  int m = (s[5] - '0') *10 + (s[6] - '0');
  if(m > 4) cout << "TBD" << endl;
  else cout << "Heisei" << endl;
  
  return 0;
}

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

struct node {
    ll a, b, c;
};

ll solve(ll *w, ll *v, ll W, ll n) {
    ll dp[n + 1][W + 1];
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= W; ++j) {
            if(i == 0 || j == 0) dp[i][j] = 0;
            else {
                dp[i][j] = dp[i - 1][j];
                if(w[i - 1] <= j)
                    dp[i][j] = max(dp[i][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
            }
        }
    }
    return dp[n][W];
}

int main() {
    ll n, W;
    cin >> n >> W;
    ll w[n], v[n];
    for(int i = 0; i < n; ++i)
        cin >> w[i] >> v[i];
    cout << solve(w, v, W, n);
}


Measured memory_bytes: 82436
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int N_MAX = 8;
int main()
{
  int n,i,t=0;
  int p[N_MAX];
  double res=0;
  double x[N_MAX],y[N_MAX];
  cin >> n;
  for(i=0;i<n;i++){
    cin >> x[i] >> y[i];
    p[i]=i;
  }
  do {
    for(i=0;i<n-1;i++)
      res+=sqrt((x[p[i+1]]-x[p[i]])*(x[p[i+1]]-x[p[i]])
                +(y[p[i+1]]-y[p[i]])*(y[p[i+1]]-y[p[i]]));
    t++;
  } while(next_permutation(p,p+n));
  res/=t;
  cout << setprecision(12) << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>

using ll = long long;

int main(){
    ll x,k,d,min,ans;
    std::cin >> x>>k>>d;
    x = std::llabs(x);
    if(x>0){
        min = x/d;
        if(min>=k){
            ans = x-d*k;
        }else{
            ans = x-d*min;
            if((k-min)%2!=0){
                ans -= d;
            }
        }
    }else{
        if(k%2==0){
            ans = 0;
        }else{
            ans = d;
        }
    }
    ans = std::llabs(ans);
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b[100000],c=0,d=0;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>b[i];
    if(i!=0){
      if(b[i-1]>=b[i]) d++;
      else d=0;
    }
    c=max(d,c);
  }
  cout<<c<<"\n";
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  int n;
  cin >> n;
  cout << (24-n) + 24 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using llong = long long;
using P = pair<int, int>;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int main() {
   string s, p;
   cin >> s >> p;
   rep(i, s.size()) {
      bool isok = true;
      rep(j, p.size()) {
         if (s[(i + j) % s.size()] != p[j]) {
            isok = false;
         }
      }
      if (isok) {
         cout << "Yes" << endl;
         return 0;
      }
   }
   cout << "No" << endl;
   return 0;
}


Measured memory_bytes: 3212
# c
n = int(input())
*h, = map(int, input().split())
step = 0
mstep = 0
for i, j in zip(h, h[1:]):
    if i >= j:
        step += 1
    else:
        mstep = max(mstep, step)
        step = 0
print(max(mstep, step))

Measured memory_bytes: 63856
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//STANDARD DATA TYPES
#define ll long long
#define llu unsigned long long
#define ld long double
//ADV DATA TYPES
#define pii pair < int , int >
#define pll pair < ll, ll >
#define mp make_pair
#define ff first
#define ss second
//C ++ DS
#define vi vector < int >
#define vll vector < ll >
#define pb push_back
#define pf push_front
#define iter :: iterator
#define all(x) x.begin(),x.end()

//priority_queue < pii, vector < pii >, greater < pii > > pq;
//lower_bound(v.begin(),v.end(),20);//for any sorted container
//CONSTANTS
#define MOD (int)(1e9+7)
#define INF 0x3f3f3f3f
#define MAXN (int)(1e5+1)
//MOD OPERATIONS
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
inline ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
inline ll addmod(ll a, ll val, ll p = MOD) {{if ((a = (a + val)) >= p) a -= p;} return a;}
inline ll submod(ll a, ll val, ll p = MOD) {{if ((a = (a - val)) < 0) a += p;}return a;}
inline ll mult(ll a, ll b, ll p = MOD) {return (ll) a * b % p;}
//DEBUG
#define shout()  {cout << "I'm Here...!!!" << endl;}
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
int main()
{
	fastio;
	int h,w;
	cin>>h>>w;
	vector<char> a[h+1];
	vector<int> dp[h+1];
	for(int i=0;i<=h;i++)
	{
		a[i].resize(w+1);
		dp[i].resize(w+1);
	}
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			cin>>a[i][j];
        }
        cout<<endl;
	}
	for(int i=0;i<=h;i++)
	{
		for(int j=0;j<=w;j++)
		{
			if(i==0 || j==0)dp[i][j]=0;
			else if(i==1&&j==1)dp[1][1]=1;
			else
			{
				if(a[i-1][j]=='.')dp[i][j]=addmod(dp[i][j],dp[i-1][j]);
				if(a[i][j-1]=='.')dp[i][j]=addmod(dp[i][j],dp[i][j-1]);
			}
		}
	}
	cout<<dp[h][w]<<endl;
}


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

using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;


ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
    ll r=1;a%=mo;
    while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
    return r;
}

int32_t main() {
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    
    ini(n);
    ini(n1);
    int tmp = 0;
    int dp[430000];
    for(int i = n1;i>=1;i--){
        dp[i]= modpow(n1/i,n);
        for(int i1 = i*2;i1<=n1;i1+=i)dp[i]-=dp[i1];
        dp[i] = (dp[i]%mo+mo)%mo;
        tmp+=(dp[i]*i)%mo;
        tmp%=mo;
    }
    out(tmp);
    
    
  
    
    
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 4340
N,L = map(int,input().split())

if L >= 0:
  print(int((2*L+N)*(N-1)/2))
  
elif L+N-1 < 0:
  print(int((2*L+N-2)*(N-1)/2))

else:
  print(int((2*L+N-1)*N/2))
  

Measured memory_bytes: 2940
import java.util.Scanner;

//A Point in a Triangle
public class Main{

	public static double ex(double ox, double oy, double x1, double y1, double x2, double y2){
		double vx1 = x1-ox;
		double vy1 = y1-oy;
		double vx2 = x2-ox;
		double vy2 = y2-oy;
		return vx1*vy2-vx2*vy1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			double[][] p = new double[3][2];
			for(int i=0;i<3;i++){
				p[i][0] = sc.nextDouble();
				p[i][1] = sc.nextDouble();
			}
			double px = sc.nextDouble();
			double py = sc.nextDouble();

			boolean f = true;
			boolean g = true;
			for(int i=0;i<3;i++){
				double ex = ex(p[i][0], p[i][1], p[(i+1)%3][0], p[(i+1)%3][1], px, py);
				if(ex >= 0){
					f = false;
				}
				if(ex <= 0){
					g = false;
				}
			}
			System.out.println(f||g?"YES":"NO");
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
#define d first
#define t second
using namespace std;
typedef long l;
l N,K,i,num,p,tmp;
vector<pair<l,l> >td;
bool used[1<<17];
priority_queue<l,vector<l>,greater<l>>q;
int main(){
  cin>>N>>K;
  td.resize(N);
  for(i=0;i<N;i++)cin>>td[i].t>>td[i].d;
  sort(td.rbegin(),td.rend());
  for(i=0;i<K;i++){
    tmp+=td[i].d;
    if(used[td[i].t])q.push(td[i].d);
    else used[td[i].t]=true,num++;
  }
  p=tmp+num*num;
  for(i=K;i<N;i++){
    if(!used[td[i].t]){
      if(!q.size())break;
      used[td[i].t]=true;
      tmp+=td[i].d;
      tmp-=q.top();q.pop();
      p=max(p,tmp+(++num)*num);
    }
  }
  cout<<p<<endl;
  return 0;
}


Measured memory_bytes: 2556
//============================================================================
// Name        : desk.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include<stdio.h>
#include<iostream>
#include <algorithm>
using namespace std;
int main(){
int w,n;
cin>>w>>n; //w????¨???????n????????\?????????????????°
int N[w]; //???????????°
for(int i=0;i<w;i++){
	N[i]=i+1; //?¨??????°?????\???????§?
}
for(int i=0;i<n;i++){
	int a,b;
	char c;
	cin>>a>>c>>b; //char???,?????\????????¨
	swap(N[a-1],N[b-1]); //swap??§??´??\??\?????????
}
for(int i=0;i<w;i++){
	cout<<N[i]<<endl; //?????¨?????????
}
  return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n, m;
    cin >> n;
    vector<int> arr1(n);
    for (int i = 0; i < n; i++)
        cin >> arr1[i];
    cin >> m;
    vector<int > arr2(m);
    for (int i = 0; i < m; i++)
        cin >> arr2[i];
    bool key;
    key = includes(begin(arr1), end(arr1),begin(arr2), end(arr2));
    if (key)
        cout << "1" << endl;
    else cout << "0" << endl;
}


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

using namespace std;

int main() {
	int n;
	cin >> n;
	set<string> names[5];
	for (int i = 0;i < n;i++) {
		string s;
		cin >> s;
		switch (s[0]) {
		case 'M':
			names[0].insert(s);
			break;
		case 'A':
			names[1].insert(s);
			break;
		case 'R':
			names[2].insert(s);
			break;
		case 'C':
			names[3].insert(s);
			break;
		case 'H':
			names[4].insert(s);
			break;
		}
	}
	long long num = 0;
	for (int i = 0;i < 3;i++) {
		for (int j = i + 1;j < 4;j++) {
			for (int k = j + 1;k < 5;k++) {
				num += names[i].size()*names[j].size()*names[k].size();
			}
		}
	}
	cout << num;
	return 0;
}


Measured memory_bytes: 9600
/*
 * carrot_tour.cpp
 *
 *  Created on: 2017/05/30
 *      Author: Nishio
 */
#include<bits/stdc++.h>
#define REP(i,n,N) for(int i=(n);i<(int)(N);i++)
#define p(s) cout<<(s)<<endl;
#define F first
#define S second
typedef long long ll;
using namespace std;

const int ctinf=1e5;
double dp[10000][21][21];//num,prev,now = minr

double vec_len(int x1,int x2,int y1,int y2){
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

int dot_pro(int x1,int x2,int x3,int y1, int y2, int y3){
	return (x2-x1)*(x3-x2)+(y2-y1)*(y3-y2);
}

double ctcos(int x1,int x2,int x3,int y1,int y2,int y3){
	return dot_pro(x1,x2,x3,y1,y2,y3)/(vec_len(x1,x2,y1,y2)*vec_len(x2,x3,y2,y3));
}
int main(){
	int n;
	double r,theta;
	cin>>n>>r>>theta;
	REP(i,0,r) REP(j,0,21) REP(k,0,21) dp[i][j][k]=ctinf;
	double co=cos(theta*M_PI/180.0);
	int x[20],y[20];
	REP(i,0,n) cin>>x[i]>>y[i];
	int ans=0;
	vector<int> ok[21][21];
	REP(prev,0,n) REP(now,0,n){
		if(prev==now) continue;
		REP(next,0,n){
			if(prev==next||now==next) continue;
			if(ctcos(x[prev],x[now],x[next],y[prev],y[now],y[next])<co)continue;
			ok[prev][now].push_back(next);
		}
	}
	REP(i,1,n) if(vec_len(x[0],x[i],y[0],y[i])<r){
		dp[1][0][i]=vec_len(x[0],x[i],y[0],y[i]);
		ans=1;
	}
	//int from,to;

	REP(i,2,r){
		REP(prev,0,n){
			REP(now,0,n){
				if(prev==now) continue;
				for(auto next:ok[prev][now]){
					if(dp[i-1][prev][now]+vec_len(x[now],x[next],y[now],y[next])<=r){
						dp[i][now][next]=min(dp[i][now][next],dp[i-1][prev][now]+vec_len(x[now],x[next],y[now],y[next]));
						ans=i;
					}
				}
			}
		}
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 37856
import java.util.*; 
import java.lang.*; 


public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
                
                int N = scan.nextInt();
                int[] A = new int[N+1];
                int cnt = 0;
                long ans = 0;
                
                for(int i=1; i<=N;i++){
                    A[i] = scan.nextInt();
                }
                
                int[] min = new int[N+1];
                int[] max = new int[N+1];
                for(int i=1; i<=N;i++){
                     min[i] = i+A[i];
                     max[i] = i-A[i];
                }
                
                int[] sum = new int[N+1];
                for(int i=1;i<=N;i++){
                     if(max[i]>0) ans = ans + sum[max[i]];
                     if(min[i]<=N) sum[min[i]]++;
                }
                System.out.println(ans);
        }
}

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

     public static void main(String []args){
      Scanner scan = new Scanner(System.in);
      int n = scan.nextInt() ;
          if(n%f(n) == 0){
              System.out.println("Yes");
          }  else{
              System.out.println("No");
          }
      }
      static int f(int x ){
          String s = Integer.toString(x);
          char c[] = s.toCharArray();
          int sum = 0 ;
          for(int i = 0 ; i<c.length ; i++){
              sum+=Character.getNumericValue(c[i]);
          }
          return sum ;
      }
}

Measured memory_bytes: 22868
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

#define rep(i, n, m) for (int i = n; i <= m; i++)
#define Rep(i, n, m) for (int i = m; i >= 1; i--)

typedef long long ll;

int main() {
    string S;
    cin >> S;
    int cont = 0, Max = 0;
    rep(i, 0, S.size()-1) {
        if (S[i] == 'A' || S[i] == 'T' || S[i] == 'C' || S[i] == 'G') {
            cont++;
            Max = max(Max, cont);
        } else {
            Max = max(Max, cont);
            cont = 0;
        }
    }
    cout << Max << endl;
}

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

const long long int INF = 1001001001001001001;

long long int A, B, C, D;

map<long long int, long long int> dp;
map<long long int, bool> flg;
long long int f(long long int N) {
  if (flg[N]) return dp[N];
  if (N == 0) return 0;
  if (N == 1) return D;
  
  long long int res = INF;
  if (N < INF / D) res = min(res, N * D);
  
  if (N % 2 == 0) {
    res = min(res, f(N/2) + A);
  } else {
    res = min(res, f((N-1)/2) + D + A);
    res = min(res, f((N+1)/2) + D + A);
  }
  
  if (N % 3 == 0) {
    res = min(res, f(N/3) + B);
  } else {
    int m = N % 3;
    res = min(res, f((N-m)/3) + m*D + B);
    res = min(res, f((N-m+3)/3) + (3-m)*D + B);
  }
  
  if (N % 5 == 0) {
    res = min(res, f(N/5) + C);
  } else {
    int m = N % 5;
    res = min(res, f((N-m)/5) + m*D + C);
    res = min(res, f((N-m+5)/5) + (5-m)*D + C);
  }
  
  flg[N] = true;
  return dp[N] = res;
}

int main() {
  int T;
  cin >> T;
  
  for (int t = 0; t < T; ++t) {
    long long int N;
    cin >> N >> A >> B >> C >> D;
    dp.clear(), flg.clear();
    cout << f(N) << endl;
  }
}


Measured memory_bytes: 5236
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
#define show(x) cout << #x << " is " << x << "\n";
typedef vector<ll> vi;
#define fi first
#define se second
const ll inf = 9e18;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

//const ll N = 1e5 + 1;
//vector<ll> adj[N];
//bool visited[N];

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

	ll n;
	cin>>n;
	ll op = n%10;
	if(op == 3) cout<<"bon";
	else if(op == 0 ||op == 1 ||op == 6 ||op == 8) cout<<"pon";
	else cout<<"hon";


	return 0;
}


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

int main(){
  ll k;
  cin >> k;
  ll mod = 0;
  ll v = 7;
  ll cnt = 0;
  while(cnt <= 2*k) {
    cnt++;
    (mod += v) %= k;
    if(mod == 0) {
      cout << cnt << endl;
      return 0;
    }
    (v *= 10) %= k;
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int n, k;
	std::vector<int> cards;
	cards.reserve(100000);

	while (std::cin >> n >> k, n + k != 0) {
		bool whiteExist = false;

		for (int i = 0; i < k; ++i) {
			int c;
			std::cin >> c;

			if (c == 0)
				whiteExist = true;
			else
				cards.push_back(c);
		}

		cards.push_back(n + 100);
		std::sort(cards.begin(), cards.end());

		int maxChain = 0;
		int nowChain = 1, prevChain = 0;
		bool canWhiteChain = false;

		for (size_t i = 1; i < cards.size(); ++i) {
			if (cards[i] - cards[i - 1] == 1)
				++nowChain;
			else {
				maxChain = std::max(
					maxChain,
					(canWhiteChain ? nowChain + prevChain + 1 : nowChain)
				);

				canWhiteChain = whiteExist && cards[i] - cards[i - 1] == 2;

				prevChain = nowChain;
				nowChain = 1;
			}
		}

		std::cout << maxChain << std::endl;

		cards.clear();
	}
}

Measured memory_bytes: 3044
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		int W, H, x, y, r;
	    try (Scanner sc = new Scanner(System.in)) {
	    	W = sc.nextInt();
	    	H = sc.nextInt();
	    	x = sc.nextInt();
	    	y = sc.nextInt();
	    	r = sc.nextInt();
	    }

	    if (x-r < 0 || x+r > W) {
	    	System.out.println("No");
	    }

	    else if (y-r < 0 || y+r > H) {
	    	System.out.println("No");
	    }
	    else {
	    	System.out.println("Yes");
	    }
	}

}



Measured memory_bytes: 26304
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
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; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




int main() {
  ll n,k;
  cin>>n>>k;
  
  vector<ll> p(n);
  ll x,y;
  cin>>x;
  ll dai=x;

  repo(i,n){
    cin>>p[i];
    x=gcd(x,p[i]);
    dai=max(dai,p[i]);
  }

  cout << (k%x==0 && k<=dai ? "POSSIBLE":"IMPOSSIBLE") << endl;

}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
#include <stack>
using namespace std;
 
#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926
 
typedef long long int ll;
 
//ll chk[55];
//ll num[55];
//ll num2[55];
//ll num[ten5];
//ll num2[ten5];
//char cmap[10][10];
//priority_queue<long long int> pq;
//stack<int> stk;
//vector<pair<ll,ll>> vint;
//vector<ll> vtime;
//deque<ll> deq[55];
//list<int> li;
//set<int> sint;
//set<ll> sll;
//map<ll,ll> mp;
 
 
 
int main()
{
    //int m,n,o=0,i,j,k;
    long long int sum=0,sum2=0,n1=0,n2=0,n3,range;
    double ans=0.0,half;
    long long int m,n,o,i,j,k=1;
    long long int a,a1,a2,a3,a4,a5,a6;
    a=a1=a2=a3=a4=a5=a6=0;
    //float f,g,h;
    //string s,s1;
    //char now,pre,c;
    cin>>n>>m;
    if(n%m==0) cout<<n/m;
    else cout<<n/m+1;
    return 0;
}

Measured memory_bytes: 256
/**
    AUTHOR:Jun_SH
    TIME:2019/6/16
    PROBLEM:ABC130_b
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l[105];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,x;
    cin>>n>>x;
    for(ll i=1;i<=n;++i){
        cin>>l[i];
    }
    ll sum=0;
    ll ans=0;
    ll tot=1;
    while(sum<=x&&tot<=n+1){
        ans++;
        sum+=l[tot++];
    }
    cout<<ans<<endl;
}


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

int main(){
while(1){
	int r,c,a[12][10002];
	scanf("%d%d",&r,&c); if(r==0&&c==0)break;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			scanf("%d",&a[i][j]);
		}
	}

	int ret=0;
	for(int S=0;S<1024;S++){
		int sum=0;
		for(int j=0;j<c;j++){
			int ans=0;
			for(int i=0;i<r;i++){
				ans+=a[i][j]^((S>>i)&1);
			}
			sum+=max(ans,r-ans);
		}
		ret=max(ret,sum);
	}

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

Measured memory_bytes: 1568
#include <bits/stdc++.h>
int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector<int> a(n);
  for (auto& x : a) std::cin >> x;
  auto make_left = [&] (auto& a) {
    std::vector<int> left(n + 1, 0);
    for (int i = 0; i < n; i++) {
      left.at(i + 1) = std::max(a.at(i), left.at(i));
    }
    return left;
  };
  auto left = make_left(a);
  std::reverse(a.begin(), a.end());
  auto right = make_left(a);
  std::reverse(right.begin(), right.end());
  for (int i = 0; i < n; i++) {
    std::cout << std::max(
      left.at(i),
      right.at(i + 1)
    ) << std::endl;
  }
  return 0;
}

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

using ll = long long;
using pll = pair<ll, ll>;
#define rep(i, j) for(int i=0; i < (int)(j); i++)

class Solver {
  public:
    const int SUM_MAX = 9 * 14 + 1;
    enum {
        SMALL = 0,
        EQUAL = 1,
        BIG   = 2,
    };
    
    bool solve() {
        string s; cin >> s;
        for(auto &c: s) c -= '0';
        int s_sum = 0; for(auto &c : s) s_sum += c;
        ll s_prod = 1; for(auto &c : s) s_prod *= (c + 1);
        
        // n?????????, small or equal or big as int, sum, prod, 
        // [int][bool][int][ll]        
        vector<vector<vector<map<ll, ll>>>> dp;

        // init
        dp.resize(s.size() + 1);
        rep(i, dp.size()) {
            dp[i].resize(3);
            rep(j, dp[i].size()) {
                dp[i][j].resize(SUM_MAX);
                if(i == 0 and j == EQUAL) {
                    dp[i][j][0][1] = 1;
                }
            }
        }
        
        // calc
        rep(n, s.size()) { 
            rep(comp, 3) { 
                rep(sum, SUM_MAX) {
                    for(pll p : dp[n][comp][sum]) {
                        ll prod = p.first, cnt = p.second;
                        
                        rep(i, 10) {
                            if(comp == EQUAL) {
                                int next_comp = i == s[n] ? EQUAL : (i > s[n] ? BIG : SMALL);
                                dp[n + 1][next_comp][sum + i][prod * (i + 1)] += cnt;
                            } else {
                                dp[n + 1][comp][sum + i][prod * (i + 1)] += cnt;
                            }                                
                        }
                        
                    }
                }
            }
        }

        // collect result
        ll ans_sum = 0;
        for(int comp : {SMALL, EQUAL, BIG}) {
            rep(sum, s_sum) {
                for(pll p : dp[s.size()][comp][sum]) {
                    ans_sum += p.second;                    
                }
            }
        }
        
        ll ans_prod = 0;
        for(int comp : {SMALL, EQUAL, BIG}) {
            for(pll p : dp[s.size()][comp][s_sum]) {
                if(p.first < s_prod) {
                    ans_prod += p.second;
                }
            }
        }
        
        ll ans_int = 0;
        ans_int = dp[s.size()][SMALL][s_sum][s_prod];

        // end
        cout << ans_sum + ans_prod + ans_int << endl;
        
        return 0;
    }    
};

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

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

int main(){
    int k;
    vector<int>num(5);
    rep(i,5)cin>>num[i];
    cin>>k;
    bool flag=true;
    for(int i=1;i<5;i++){
        if(num[i]-num[0]<=k)continue;
        else{flag=false;}
    }
    for(int i = 2;i<5;i++){
        if(num[i]-num[1]<=k)continue;
        else{flag=false;}
    }
    for(int i = 3; i < 5;i++){
        if(num[i]-num[2]<=k)continue;
        else{flag=false;}
    }
    if(num[4]-num[3]>k)flag=false;
    if(flag)cout<<"Yay!"<<endl;
    else{
        cout<<":("<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.System.*;

public class Main{
  public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
	  
	  int N = sc.nextInt();
	  int[] A = new int[N];
	  int maxInt = 0;
	  int secondInt = 0;
	  boolean isEqual = false; //同じ値の最大値が２以上あるか
	  for(int i=0; i<N; i++) {
		  A[i] = sc.nextInt();
		  if (maxInt < A[i]) {
			  secondInt = maxInt;
			  maxInt = A[i];
			  isEqual = false;
		  } else if  (maxInt == A[i]){
			 isEqual = true;
		  } else {
			  if(A[i] > secondInt)
				  secondInt = A[i];
		  }
	  }
	  
	  for(int i=0; i<N; i++) {
		  if (maxInt > A[i]) {
			  out.println(maxInt);
		  } else if (isEqual) {
			  out.println(maxInt);
		  } else {
			  out.println(secondInt);
		  }
	  }
	  
  }
}

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

int main() {

  int n;
  cin >> n;

  vector<int> A(n);
  vector<int> B(n);

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

  vector<int> C(100001);

  for (int i = 0; i < n; i++) {
    C[A[i]]++;
  }

  for (int i = 1; i < 100001; i++) {
    C[i] = C[i] + C[i - 1];
  }

  for (int i = n - 1; 0 <= i; i--) {
    B[C[A[i]] - 1] = A[i];
    C[A[i]]--;
  }

  for (int i = 0; i < n; i++) {
    cout << B[i];
    if (i != n - 1) {
      cout << " ";
    }
  }
  cout << endl;

  return 0;

}


Measured memory_bytes: 18860
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


/*
長さNの整数列(N <= 2*10^5)の内N/2(切り捨て)の要素を、どの要素も隣接しないように選んだ時の最大和

Nが偶数のときは二パターンのみ。

Nが奇数のときは、以下のように考える。

A1から見たとき、選択権を持ちながら二回スキップできる。
一回もスキップしていない場合、一意に定まるA1, A3, A5, ...
ある地点でスキップした場合、A_x(xは偶数),A_x+2, A_x+4, A_x+6
二回スキップした場合、A_N, A_N-2, A_N-4, ...

一回目のスキップから二回目のスキップの区間の最適値を求めれば解ける？

解の二分探索？
　ある値Xを超えることができる場合が存在するか否かをO(N)で算出できれば解ける？

skipの位置で考えようとしても、パターンが掴みにくそう
dp[i][skip_num][selected]: 
　i番目の時点で、skip_num回skipをした際の、最大数(selected=1のとき、i番目の数字を選択)

dp[i+1][skip_num][0] = max(dp[i][skip_num][1], dp[i][skip_num-1][0]) 
dp[i+1][skip_num][1] = dp[i][skip_num-1][0] + a[i]

0 <= skip_num <= 2

dp[n][1/2][0/1]のうち最大値が答え

oxoxoxs
oxoxsox
oxoxsso
oxsoxox
oxsoxso
oxssoxo
soxoxox
soxoxso
soxsoxo
ssoxoxo

*/

#define INF 10e15

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

    vector<vector<ll>> dp(3, vector<ll>(2, -INF));
    //dp[i][j]: i:skip回数、j=1の時a[i]を選択している状態における最大値
    dp[0][1] = a[0];
    dp[1][0] = 0;
    for (int s = 1; s < n; s++)
    {
        vector<vector<ll>> tdp(3, vector<ll>(2, -INF));
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                tdp[i][0] = dp[i][1];
                tdp[i][1] = dp[i][0] + a[s];
                if (i!=0){
                    tdp[i][0] = max(dp[i-1][0], tdp[i][0]);
                }
               // printf("%d, %d, %lld\n", i,j, tdp[i][j]);
            }
        }
        dp = tdp;
    }

    ll ans = -INF;
    if (n%2 == 0){
        ans = max(dp[1][1], dp[0][0]);
        cout << ans << endl;
        return 0;
    }

    for (int i = 1; i < 3; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << endl;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for(int i = 0; i < N; ++i){
        cin >> vec[i];
    }
    int count = 0;
    bool isOdd = false;
    while(true){
        for(int i = 0; i < N; ++i){
            if(vec[i]%2 != 0){
                isOdd = true;
            }
        }
        if(isOdd)
            break;
        ++count;
        for (int i = 0; i < N; ++i) {
            vec[i] /= 2;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
L = 4
table = [[1.1, Float::INFINITY], [0.6, 1.1], [0.2, 0.6], [0, 0.2]]
left  = Array.new(L, 0)
right = Array.new(L, 0)

count = ->(a, counter) {
  table.each_with_index do |d, i|
    counter[i] += 1 if d[0] <= a and a < d[1]
  end
  counter
}

$<.readlines.map {|l| l.split.map(&:to_f)}.each do |l, r|
  left  = count.(l, left)
  right = count.(r, right)
end

L.times do |i|
  puts "#{left[i]} #{right[i]}"
end


Measured memory_bytes: 6868