akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace E_ABC166
{
    class MainClass
    {

        static int[] s;
        static long[] al;

        public static void Main(string[] args)
        {
            s = Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse);
            int n = s[0];
            al= Array.ConvertAll(ReadLine().Split().ToArray(), long.Parse);
            // var plus = new Dictionary<long,long>();
            var minus = new Dictionary<long,long>();
            for(int i = 0;i<n;i++){
                // long tmpplus = (i+1) + al[i];
                long tmpminus = (i+1) - al[i];
                // if(plus.ContainsKey(tmpplus)){
                //     plus[tmpplus]++;
                // }else{
                //     plus.Add(tmpplus,1);
                // }
                if(minus.ContainsKey(tmpminus)){
                    minus[tmpminus]++;
                }else{
                    minus.Add(tmpminus,1);
                }
            }

            long ans = 0;


            for(int i = 0;i<n;i++){
                long tmpplus = (i+1) +al[i];
                if(minus.ContainsKey(tmpplus)){
                    ans += minus[tmpplus];
                }
            }

            WriteLine(ans);


        }
    }
}


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

using namespace std;

int main() {
	long long int H, W;
	cin >> H >> W;
	for( size_t i = 0; i < H; i++ ) {
		for( size_t j = 0; j < W; j++ ) {
			string S;
			cin >> S;
			if( S == "snuke" ) {
				cout << (char)('A' + j) << i+1 << endl;
			}
		}
	}
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MODULO 1000000007
#define PI 3.14159265359
typedef long long int ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int A[n];
    for(int i=0;i<n;++i)
    cin>>A[i];
    int lm=A[0];
    long int res=0;
    for(int i=1;i<n;++i)
    {
    	if(A[i]<lm)
    	{
    		res=res+(lm-A[i]);
		}
		else
		{
			lm=A[i];
		}
	}
	cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 4376
// Problem Statement
// Given is a positive integer N
// Find the number of pairs
// (A,B) of positive integers not greater than N hat satisfy the following condition:
// When A and B are written in base ten without leading zeros, the last digit of A is equal to the first digit of B, and the first digit of
// A is equal to the last digit of B.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define ld long double
#define MOD 1000000007
#define nl cout << bl
#define rt ll Q[100005] = {0}
#define mp make_pair
#define test() \
    ull t;     \
    cin >> t;  \
    while (t--)
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define s(ar, n) sort(ar, ar + n)
#define rs(ar, n) sort(ar, ar + n, greater<ll>())
#define oa(a, n)               \
    for (ll i = 0; i < n; i++) \
        cout << a[i] << " ";
#define cn(a, n)               \
    for (ll i = 0; i < n; i++) \
        cin >> a[i];
#define ov(a, n)                    \
    for (ll i = n - 1; i >= 0; i--) \
        cout << a[i] << " ";        \
    nl
#define ovp(a, n)              \
    for (ll i = 0; i < n; i++) \
        cout << a[i].ff << " " << a[i].ss << bl;
#define maxa(ar, N) *max_element(ar, ar + N)
#define mina(ar, N) *min_element(ar, ar + N)
#define present(c, x) ((c).find(x) != (c).end())
#define fastio()                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
typedef pair<int, int> pii;
ll fast_exp(ll base, ll exp)
{
    ll res = 1;
    while (exp > 0)
    {
        if (exp % 2 == 1)
            res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res % MOD;
}
ll fib(ll n)
{
    if (n < 2)
        return n;
    ll a = 0, b = 1, pre;
    int i = 1;
    while (i < n)
    {
        pre = (a + b) % MOD;
        a = b;
        b = pre;
        i++;
    }
    return pre;
}
ll fac(ll n)
{
    if (n % 2 == 0)
        return 2;

    for (ll i = 3; i * i <= n; i += 2)
    {
        if (n % i == 0)
            return i;
    }

    return n;
}
ll fact(ll n)
{
    if (n > 1)
        return n * fact(n - 1);
    else
        return 1;
}
bool sortbysec(const tuple<int, int, int> &a,
               const tuple<int, int, int> &b)
{
    return (get<1>(a) < get<1>(b));
}
int last_digit(int n)
{
    int ans = 0;
    while (n != 0)
    {
        ans = n % 10;
        n /= 10;
    }
    return ans;
}
int main()
{
    int H, A;
    cin >> H >> A;
    if (H % A == 0)
    {
        cout << H / A;
    }
    else
    {
        cout << (H + A) / A;
    }
}


Measured memory_bytes: 3608
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let a: char = sc.get();
    if a >= 'a' && a <= 'z' {
        println!("a");
    } else {
        println!("A");
    }
}


Measured memory_bytes: 2072
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

ans = 0
for i in range(1, n+1, 2):
    arr = factorization(i)
    tmp = 1
    for j, cnt in arr:
        tmp *= (cnt + 1)
    if tmp == 8:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2E3;
int n, m, ans;
vector<int> e[N], p[N], de, di;
vector<pair<int, int>> path;
int parent[N], dep[N], c[N], in[N];
int dfs_now;
void dfs(int u) {
    in[u] = dfs_now++;
    if (parent[u] != -1)
        e[u].erase(find(e[u].begin(), e[u].end(), parent[u]));
    for (int v : e[u]) {
        dep[v] = dep[u] + 1;
        parent[v] = u;
        dfs(v);
    }
}
int lca(int u, int v) {
    while (u != v) {
        if (dep[u] < dep[v])
            swap(u, v);
        u = parent[u];
    }
    return u;
}
void dfs1(int u) {
    reverse(e[u].begin(), e[u].end());
    for (int v : e[u]) {
        dfs1(v);
        c[u] += c[v];
    }
    ans += min(c[u], 2);
    if ((int)p[u].size() >= 2) {
        int i = p[u].back();
        p[u].pop_back();
        int j = p[u].back();
        p[u].pop_back();
        int x = path[i].first;
        int y = path[j].first;
        if (x != y) {
            if (in[x] > in[y]) {
                swap(x, y);
                swap(i, j);
            }
            de[i] = de[j] = (int)path.size();
            p[y].push_back((int)path.size());
            path.emplace_back(x, y);
            de.push_back(-1);
            di.push_back(0);
        }
        di[j] = 1;
    }
    while (!p[u].empty()) {
        int i = p[u].back();
        p[u].pop_back();
        int x = path[i].first;
        int y = parent[u];
        if (x == y)
            continue;
        if (in[x] > in[y]) {
            swap(x, y);
            di[i] = 1;
        }
        de[i] = (int)path.size();
        p[y].push_back((int)path.size());
        path.emplace_back(x, y);
        de.push_back(-1);
        di.push_back(0);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        e[--u].push_back(--v);
        e[v].push_back(u);
    }
    parent[0] = -1;
    dfs(0);
    path.resize(m);
    de.assign(m, -1);
    di.resize(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        int l = lca(--u, --v);
        ++c[u];
        ++c[v];
        c[l] -= 2;
        if (in[u] > in[v])
            swap(u, v);
        p[v].push_back(i);
        path[i] = {u, v};
    }
    dfs1(0);
    for (int i = (int)path.size() - 1; i >= 0; --i)
        if (de[i] != -1)
            di[i] ^= di[de[i]];
    for (int i = 0; i < m; ++i)
        if (di[i] == 1)
            swap(path[i].first, path[i].second);
    cout << ans << "\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        tie(u, v) = path[i];
        cout << ++u << " " << ++v << "\n";
    }
    return 0;
}

Measured memory_bytes: 9136
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int n;
    cin >> n;
    rep(i, n) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            if (!(x % 3 == 0 || x % 5 == 0)) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
data = [list(map(str, input().split())) for _ in range(N)]

m = 0

for i in range(N):
    if data[i][1] == 'BTC':
        m += 380000 * float(data[i][0])
    else:
        m += float(data[i][0])

print(m)

Measured memory_bytes: 2940
n = int(input())
#同じくint型でリスト化する
lst1 = list(map(int,input().split()))
lst1.insert(0,0)
lst1.append(0)
ans = 0
for i in range(1,n+2):
    ans += abs(lst1[i]-lst1[i-1])

for i in range(1,n+1):
    print(ans -abs(lst1[i]-lst1[i-1])-abs(lst1[i+1]-lst1[i])+abs(lst1[i+1]-lst1[i-1]))

Measured memory_bytes: 64148
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll ans = 0, cnt, N;
string S;
char cur;
vector<ll> nums;

ll calcSum(ll n){
    return (0+n)*(n+1)/2;
}

void solve(){
    cur = S[0];
    cnt = 1;

    for(int i = 1; i < N; ++i){
        if(S[i] == cur){
            cnt++;
        } else {
            if(S[i] == '>'){
                nums.push_back(cnt);
                cnt = 1;
                cur = S[i];
            } else {
                nums.push_back(-cnt);
                cnt = 1;
                cur = S[i];
            }
        }
    }

    if(S[N-1] == '>'){
        nums.push_back(-cnt);
    } else {
        nums.push_back(cnt);
    }

    for(auto v: nums){
        // cout << v << endl;
        ans += calcSum(abs(v));
    }

    for(int i = 0; i < nums.size()-1; ++i){
        if(nums[i] > 0 && nums[i+1] < 0) ans -= min(abs(nums[i]), abs(nums[i+1]));
    }

    cout << ans << endl;
        
}

int main(){
    cin >> S;

    N = S.size();

    solve();
}


Measured memory_bytes: 3068
sa = gets.chomp
sb = gets.chomp
sc = gets.chomp

if sa.length > sb.length and sa.length > sc.length
  stage = sa[0]
elsif sb.length > sa.length and sb.length > sc.length
  stage = sb[0]
else
  stage = sb[0]
end

loop do
  if stage == 'a'
    sa[0] = ""
    stage = sa[0]
  elsif stage == 'b'
    sb[0] = ""
    stage = sb[0]
  elsif stage == 'c'
    sc[0] = ""
    stage = sc[0]
  end

  if sa.length == 0
    puts "A"
    break
  elsif sb.length == 0
    puts "B"
    break
  elsif sc.length == 0
    puts "C"
    break
  end
end

Measured memory_bytes: 1788
import math
N,D=map(int,input().split())
X=[]
for _ in range(N):
    X.append(list(map(int, input().split())))

def do(a,b):
    the=math.sqrt(sum([(a[i] - b[i])**2 for i in range(D)]))
    return the.is_integer()

r=0
for i in range(N):
    for j in range(i+1, N):
        if do(X[i], X[j]):
            r+=1
print(r)


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

typedef long long ll;

using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(0)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define YesNo(x)      cout << ((x) ? "Yes" : "No") << endl
#define YESNO(x)      cout << ((x) ? "YES" : "NO") << endl
#define absi(x)       ( ((x) >= 0) ? (x) : (-(x)) )

int main(int argc, const char* argv[]) {
	string s;
	cin >> s;

	ll ret = 0;
	rep(i, s.length()) {
		if(s[i] == 'o') {
			ret++;
		}
	}

	YESNO(ret + 15 - s.length() >= 8);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//Optimisations
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("O2")
//shortcuts for functions
#define pb push_back
#define mp make_pair
#define ff first 
#define ss second
#define all(v) v.begin(),v.end()
#define prec(n) fixed<<setprecision(n)
#define n_l '\n'
// make it python 
#define gcd __gcd
#define append push_back
#define str to_string
// utility functions shortcuts
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sswap(a,b) {a=a^b;b=a^b;a=a^b;}
#define swap(a,b) {auto temp=a; a=b; b=temp;}
#define init(dp) memset(dp,-1,sizeof(dp));
#define set0(dp) memset(dp,0,sizeof(dp));
#define bits(x) __builtin_popcount(x)
#define SORT(v) sort(all(v))
#define endl "\n"
#define forr(i,n) for(ll i=0;i<n;i++)
// declaration shortcuts
typedef long long int ll;
#define int ll
// Constants
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr ll INF = 1999999999999999997; 
constexpr int inf= INT_MAX;
constexpr int MAXSIZE = int(1e6)+5;
constexpr auto PI  = 3.14159265358979323846L;
constexpr auto oo  = numeric_limits<int>::max() / 2 - 2;
constexpr auto eps = 1e-6;
constexpr auto mod = 1000000007;
constexpr auto MOD = 1000000007;
constexpr auto MOD9 = 1000000009;
constexpr auto maxn = 100006;
//void IOfile(){
//freopen(file_name, reade_mode, stdin);
//freopen(file_name, write_mode, stdout);
//}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int32_t main(){
	fastio();
	int n,q;
	cin >> n >> q;
	vector<array<int,3>>v;
	for(int i = 0; i < n; i++){
		int s,t,x;
		cin >> s >> t >> x;
		v.push_back({x,s,t});
	}
	sort(all(v));
	int ans[q];
	set<int>s;
	map<int,int>f;
	for(int i = 0; i < q; i++){
		int d;
		cin >> d;
		s.insert(d);
		f[d] = i;
		ans[i] = -1;
	}
	for(int i = 0; i < n; i++){
		while(s.size() > 0  and s.lower_bound(v[i][1] - v[i][0]) != s.end()){
			auto t = s.lower_bound(v[i][1] - v[i][0]);
			if(*t < v[i][2] - v[i][0]){
				s.erase(*t);
				ans[f[*t]] = v[i][0];
			}else break;
		}
	}
	for(int i = 0 ; i < q; i++) cout << ans[i] << "\n";
}

Measured memory_bytes: 31364
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

pub struct Graph {
  graph: Vec<Vec<usize>>,
  v: usize,
}

type Edge = (usize, usize);
impl Graph {
  pub const INF: usize = std::usize::MAX;

  pub fn new(edges: &[Edge], v: usize) -> Self {
    let mut graph = vec![Vec::new(); v];
    for &(u, v) in edges {
      graph[u].push(v);
      graph[v].push(u);
    }
    Self { graph, v }
  }

  pub fn new_directed(edges: &[Edge], v: usize) -> Self {
    let mut graph = vec![Vec::new(); v];
    for &(u, v) in edges {
      graph[u].push(v);
    }
    Self { graph, v }
  }

  pub fn add_directed_edge(&mut self, e: Edge) {
    self.graph[e.0].push(e.1);
  }

  pub fn add_edge(&mut self, e: Edge) {
    self.graph[e.0].push(e.1);
    self.graph[e.1].push(e.0);
  }

  pub fn shortest_path(&self, start: usize) -> Vec<usize> {
    let mut visited = std::collections::HashSet::new();
    let mut cost_list = vec![Self::INF; self.v];
    let mut que = std::collections::VecDeque::new();
    cost_list[start] = 0;
    visited.insert(start);
    que.push_back(start);
    while let Some(u) = que.pop_front() {
      for &v in &self.graph[u] {
        if visited.contains(&v) {
          continue;
        }
        visited.insert(v);
        let new_cost = cost_list[u] + 1;
        cost_list[v] = new_cost;
        que.push_back(v);
      }
    }
    cost_list
  }
}

fn main() {
  input! {
    n: usize, k: usize,
    av: [Usize1; n]
  };

  let mut edges = Vec::new();
  for i in 0..n {
    let u = i;
    let v = av[i];
    edges.push((u, v));
  }
  let graph = Graph::new_directed(&edges, n);
  let d = graph.shortest_path(0);
  let mut max = 0;
  let mut max_pos = 0;
  for i in 0..n {
    if d[i] < Graph::INF && d[i] > max {
      max = d[i];
      max_pos = i;
    }
  }
  if k <= max {
    let res = d.iter().position(|&x| x == k).unwrap() + 1;
    println!("{}", res);
    std::process::exit(0);
  }

  let rest = k - (max + 1);
  let p = max - d[av[max_pos]] + 1;
  let pos = rest % p + d[av[max_pos]];
  let res = d.iter().position(|&x| x == pos).unwrap() + 1;
  println!("{}", res);
}


Measured memory_bytes: 23968
#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
int main(){
  int n,k;
  int h[100001];
  cin>>n>>k;
  for(int i=0;i<n;i++) cin>>h[i];
  int dp[100001];
  dp[0]=0;
  dp[1]=abs(h[0]-h[1]);
  for(int i=2;i<n;i++){
    int j=max(0,i-k);
    int rec=INF;
    for(;j<i;j++){
      rec=min(rec,dp[j]+abs(h[i]-h[j]));
    }
    dp[i]=rec;
  }
  cout<<dp[n-1]<<endl;

  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
typedef long long ll;
typedef long double ld;
const int MINI INT_MIN;
const ll MINL LLONG_MIN;
ll x,ans,dem=0;
int main(){
    ios_base::sync_with_stdio(0);
    cin>>x;
    ans=100;
    while (ans<x){
        ans+=(ans/100);
        dem++;
    }
    cout << dem << endl;
}


Measured memory_bytes: 3648
program main
	implicit none
	integer i, counter
	character(200) S
	read(*, *) S
	counter = 0
	do i = 2, len_trim(S)-2
		if(S(1:(len_trim(S)-i)/2) == S(1+(len_trim(S)-i)/2:len_trim(S)-i)) then
			write(*, *) len_trim(S)-i
			counter = 1
			exit
		end if
	end do
	if(counter == 0) then
		write(*, *) 1
	end if
end program main

Measured memory_bytes: 768
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}
func nextStr(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

type point struct {
	x, y int
}

type container struct {
	data []point
}

func (c *container) isEmpty() bool {
	return len(c.data) == 0
}
func (c *container) queue(v point) {
	c.data = append(c.data, v)
}
func (c *container) dequeue(v *point) bool {
	if !c.isEmpty() {
		*v = c.data[0]
		c.data = c.data[1:]
		return true
	}
	return false
}

var h, w int
var maze [][]byte
var dx = []int{1, -1, 0, 0}
var dy = []int{0, 0, -1, 1}

func bfs() int {
	d := make([][]int, h)
	for i := 0; i < h; i++ {
		d[i] = make([]int, w)
		for j := 0; j < w; j++ {
			d[i][j] = -1
		}
	}
	var q container
	q.queue(point{0, 0})
	d[0][0] = 0
	for len(q.data) > 0 {
		var p point
		q.dequeue(&p)
		if p.y == h-1 && p.x == w-1 {
			break
		}
		for i := 0; i < 4; i++ {
			nx, ny := p.x+dx[i], p.y+dy[i]
			if 0 <= nx && nx < w && 0 <= ny && ny < h && d[ny][nx] == -1 && maze[ny][nx] == '.' {
				d[ny][nx] = d[p.y][p.x] + 1
				q.queue(point{x: nx, y: ny})
			}
		}
	}
	return d[h-1][w-1]
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	h = nextInt(sc)
	w = nextInt(sc)
	maze = make([][]byte, h)
	black := 0
	for i := 0; i < h; i++ {
		s := nextStr(sc)
		maze[i] = make([]byte, w)
		// fmt.Scan(&maze[i])
		for j := 0; j < w; j++ {
			maze[i][j] = s[j]
			if maze[i][j] == '#' {
				black++
			}
		}
	}
	s := bfs()
	if s != -1 {
		s = h*w - (s + 1) - black
	}
	fmt.Println(s)
}


Measured memory_bytes: 768
#include <iostream>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#define F first
#define S second
const int INF=100000000;

int dp[50][3001];
const int mod=100000;

int main(){
	int n,m,s;
	while(cin >> n >> m >> s){
		if(n==0&&m==0&&s==0) break;
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1; i<=m; ++i){
			for(int j=n*n; j>0; --j){
				for(int k=i; k<=s; ++k){
					dp[j][k]+=dp[j-1][k-i]%mod;
				}
			}
		}
		cout << dp[n*n][s]%mod << endl;
	}
	return 0;
}

Measured memory_bytes: 1752
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
using ll = long long;

int main() {
	ll n;
	cin >> n;
	int ans = 20;
	for (int i = 1;i < sqrt(n)+1;i++) {
		if (n%i == 0) {
			int j = n / i;
			int a = 0;
			for (int k = 0;k < 11;k++) {
				if (j / 10 == 0) {
					a++;
					ans = min(ans, a);
					break;
				}
				a++;
				j /= 10;
			}
		}
	}
	cout << ans << endl;
}


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

int main(){
	ll L,R;
	cin >> L >> R;
	
	R = min(R,L+2019);
	
	
	int ans = 2018;
	for (ll i = L; i <= R-1; ++i) {
		for (ll j = L+1; j <= R ; ++j) {
			int temp = (i*j)%2019;
			ans = min(ans,temp);
		}
	}
	
	cout << ans;
	
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
const int N = 5e5+5;
char s[N];

long long getSum(long long a){
    return (a)*(1+a)/2;   
}

long long max(long long a,long long b){ return a>b?a:b; }

int main(){
    scanf("%s",s);
    int n = strlen(s);
    long long ans = 0;
    long long u = -1;
    int p = 0;
    //s[p]前一个是u
    while(p<n){
        //printf("p = %d\n",p);
        if(s[p]=='<'){
            //printf("skip\n");
            u++;
            ans += u;
            p++;
        }
        else{
            int next = p;
            while(next+1<n && s[next+1]=='>') next++;
            int need = next-p+1;
            //u+1 is bigger
            //printf("need = %d\n",need);
            ans += getSum(need) + max(0,u+1-need);
            u = -1;
            p = next+1;
        }
    }
    if(s[n-1]=='<') ans += (u+1);   
    printf("%lld\n",ans);
    return 0;
}

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

int main(){
  size_t N;
  string S, T;
  cin >> N >> S >> T;
  for(int i = 0; i < N; ++i){
    if(S.substr(i,N-i) == T.substr(0,N-i)){
      cout << S.length()+i << endl;
      return 0;
    }
  }
  cout << S.length()+T.length() << endl;
  return 0;
}


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

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<long long>; using vvll = vector<vll>;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> istream &operator>>(istream &, vector<T> &);
template <class T> ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U> istream &operator>>(istream &, pair<T, U> &);
template <class T, class U> ostream &operator<<(ostream &, const pair<T, U> &);
template <class T> struct Inf { static constexpr T inf() { return std::numeric_limits<T>::has_infinity ? std::numeric_limits<T>::infinity() : std::numeric_limits<T>::max(); } };
template <> struct Inf<int> { static constexpr int inf() { return 0x3f3f3f3f; } };
template <> struct Inf<long long> { static constexpr long long inf() { return 0x3f3f3f3f3f3f3f3fLL; } };
constexpr int INF = Inf<int>::inf(); constexpr ll BINF = Inf<ll>::inf();
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}
// Preprocessing & "Global" variables {{{
struct Solver {
	Solver() {}
	int solve();
};
// }}}


int Solver::solve() {
	int n, k; cin >> n >> k;
	vi a(n); cin >> a;
	// int pos = distance(a.begin(), find(a.begin(), a.end(), 1));
	// int lft = pos;
	// int rig = n - lft - 1;
	cout << (n + k - 3) / (k - 1) << endl;
	return 0;
}

// Template Main {{{
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	Solver solver;
	#ifdef JUDGE_MULTI_CASE
		int t; cin >> t; for (int i = 1; i <= t; i++)
	#endif
	solver.solve();
	// cout << "Case #" << i << ": ", solver.solve();
	return 0;
}

template <class T> istream &operator>>(istream &is, vector<T> &v) {
	for (auto it=v.begin();it!=v.end();++it) is >> *it;
	return is;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	for (auto it=v.begin();it!=v.end();) os << *it, os << " \n"[++it==v.end()];
	return os;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
	return is >> p.first >> p.second;
}

template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << p.first << ' ' << p.second;
}
// }}}

// vim: fdm=marker


Measured memory_bytes: 3696
use std::io::Read;
use std::collections::HashSet;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut it = buf.split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let tmp_s: String = it.next().unwrap().parse().unwrap();
    let s: Vec<char> = tmp_s.chars().collect::<Vec<char>>();

    let mut ans = 0;
    for i in 0..n {
        let mut kind = 0;
        let mut exist1 = HashSet::new();
        let mut exist2 = exist1.clone();
        for j in 0..i {
            exist1.insert(s[j]);
        }
        for j in i..n {
            exist2.insert(s[j]);
        }
        for c in exist1.iter() {
            if exist2.contains(c) {
                kind += 1;
            }
        }
        ans = std::cmp::max(ans, kind);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
//NOT TO SUBMIT IN WRONG PLACE OR BY WRONG COMPILER
//ABC 159, task d, 2020/09/08
//ms,
/*
方針は完璧だった。
recをintにしたのがバグの原因。
recそのものがintでおさまらないことはない。
だけどcasesに加えるとき、右辺の計算が一度intで処理されてしまうんだと思う。
*/

int main(void){
  int N;
  vector<int> rec(200001);//インデックスはボールに書かれた数字、要素は個数
  vector<int> a;
  int64_t cases=0;

  for(int i=0;i<200000;i++) rec[i]=0;

  cin >>N;
  for(int i=0;i<N;i++){
    int tmp_a;
    cin >>tmp_a;
    rec[tmp_a]++;
    a.push_back(tmp_a);
  }

  int64_t one=1;
  for(int i=1;i<200000;i++) cases+=one*rec[i]*(rec[i]-1)/2;

  for(int i=0;i<N;i++){
    int same_balls =rec[a[i]];
    int64_t ans=cases - same_balls*(same_balls-1)/2;
    ans += (same_balls-1)*(same_balls-2)/2;
    cout <<ans <<endl;

  }


  return 0;
}
/*
*/


Measured memory_bytes: 5088
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    rep(i, 0, n){
        cin >> a[i] >> b[i];
    }
    int ans = 0;
    for(int i = 30; i >= 0; i--){
        int tmpk = k;
        if(k & (1 << i)){
            tmpk = 0;
            for(int j = 30; j > i; j--) tmpk = tmpk * 2 + !!(k & (1 << j));
            tmpk = tmpk * 2;
            for(int j = i - 1; j >= 0; j--) tmpk = tmpk * 2 + 1;
        }
        int sum = 0;
        rep(j, 0, n){
            if((a[j] | tmpk) == tmpk) sum += b[j];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define int         int64_t
#define ii          pair<int,int>
#define dd          pair<double,double>
#define vi          vector<int>
#define pb          push_back
#define all(x)      (x).begin(), (x).end()
#define checkBit(v, p)      (v&(1LL << p))
#define loop(i,a,b) for(int i = a;i < int(b);i++)
#define x           first
#define y           second
using namespace std;
int inf = 2e9, mod = 1e9 + 7;

int32_t main()
{
    ios_base::sync_with_stdio(false); cout << fixed <<setprecision(0);
    int n,sum = 0, res = 0; cin >> n;
    vi arr(n);
    for(auto &v:arr) cin >> v;
    for(;*max_element(all(arr)) >= n;){
        sum = 0;
        for(auto &v:arr) sum += v/n;
        res += sum;
        for(auto &v:arr) v = sum - v/n + v%n;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long

int h[100010];
int dp[1000010];
int main()
{
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> h[i];
	}
	dp[0] = 0; dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < N; i++) {
		dp[i] = min(dp[i - 2] + abs(h[i - 2] - h[i]), dp[i - 1] + abs(h[i - 1] - h[i]));
	}
	cout << dp[N - 1] << endl;
}

Measured memory_bytes: 2944
#include <stdio.h>
int main(void)
{
    char sd[50]={};
    char t[50]={};
    scanf("%s",sd);
    scanf("%s",t);
    int cut=0,cusd=0;
    while(t[cut]!=NULL)
      cut++;
    while(sd[cusd]!=NULL)
      cusd++;
    int ju=cusd-cut+1;
    int ck=0;
    while(ju>0 && ck==0)
    {
        ju--;
        for(int p=ju;p<cut+ju;p++)
        {
            if(sd[p]==t[p-ju] || sd[p]==0x3f)
              ck++;
        }
        if(ck==cut)
          ck=1;
        else
          ck=0;
    }
    if(ck==0)
    {
        printf("UNRESTORABLE");
        return 0;
    }
    for(int q=ju;q<cut+ju;q++)
    {
        sd[q]=t[q-ju];
    }
    for(int r=0;r<cusd;r++)
    {
        if(sd[r]==0x3f)
          sd[r]='a';
    }
    printf("%s",sd);
}


Measured memory_bytes: 128
n, m = map(int, input().split())
ans = ['t'] * n

for _ in range(m):
    s, c = map(int, input().split())
    if ans[s-1] =='t' or ans[s-1] == str(c):
        ans[s-1]= str(c)
    else:
        print(-1)
        exit(0)
if ans[0] == 't' and n >1:
    ans[0]=str(1)

ans = ''.join(ans).replace('t', str(0))
ans = int(ans)
l = str(ans)
if len(l) != n:
    print(-1)
else:
    print(ans)

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




class Node {
   public:
   // long vertex;
   vector<long> to;
   // vector<long> length;
   // int grp;
   bool seen = false;
   bool finish = false;
   Node(){;};
};
vector<Node> vGr;

void dfs(int vertex) {
   if (vGr[vertex].seen) return;
   vGr[vertex].seen = true;
   for (auto el : vGr[vertex].to) {
      dfs(el);
   }
   vGr[vertex].finish = true;
   return;
};

int main(void) {
   int N,M;
   cin>>N>>M;
   vGr.resize(N);
   for (int i = 0; i<M;i++) {
      long u,v,w;
      cin>>u>>v>>w;
      vGr[u-1].to.push_back(v-1);
      // vGr[u-1].length.push_back(w);
      vGr[v-1].to.push_back(u-1);
      // vGr[v-1].length.push_back(w);
   }

   int comp = 0;
   for (int i = 0; i < N;i++) {
      if (!vGr[i].finish) {
         dfs(i);
         comp++;
      }
   }
   cout<<comp<<endl;
   return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef pair<string , int> s_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#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 rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
#define show(x) cout << #x << " = " << x << endl
typedef long long int64;
const int64 INF = 1LL << 58;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<typename T> void remove(T & vector, unsigned int index){vector.erase(vector.begin() + index);}

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

    int H, W, N; cin >> H >> W >> N;
    vei a(N); rep(i,N) cin >> a[i];
    ve_vei res(H, vei(W));

    int sum = 0;
    rep(j,N) {
        rep(i, a[j]) {
            if( (sum / W) % 2 == 0 ) res[ sum / W ][sum % W] = j + 1;
            else res[ sum / W][W - sum % W - 1] = j + 1;
            sum++;
        }
    }
    rep(i,H) rep(j,W) {
        if(j != W - 1) cout << res[i][j] << " ";
        else cout << res[i][j] << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#define MANM 10000

int dp[2][MANM+5]/*[MAXN*/={0};
int n=0;
int c[MANM+1]={0};


int mins(int a,int b){
  //if(a==0)return b;
  if(a<b /*|| b==0*/)return a;
  else return b;
}

int saiki(int p,int q){
 
  /*if(p==1 || q==0 || p==q ||  dp[p][q]!=0){
    return dp[p][q];
  }*/
  int a=0;
  int b=0;
  int i=0;
  int j=0;
  dp[1][1]=0;
  dp[1][0]=c[1];
  for(i=2;i<=p;i++){
    a=i%2;
    b=(i+1)%2;
    dp[a][0]=c[i];
    for(j=1;j<=i;j++){
      dp[a][j]=mins(dp[b][j-1],dp[b][i-j]+c[i-1]);
    }
  }
  return dp[p%2][q];
}
//dp[1][1]=0
//dp[1][0]=0
//dp[i][0]=0
//dp[i][j]=左から[i]までで、右端を含む組がj長になるの。
//dp[i][j]=min{dp[i-1][j-1],dp[i-1][i-j]+c[i-1]}
int main(void){
 
  scanf("%d",&n);
  int i=0;
  for(i=1;i<n;i++){
    scanf("%d",&(c[i]));
  }
  
  int ans=saiki(n,n/2);
  printf("%d\n",ans);
  return 0;
}

  

Measured memory_bytes: 1144
s = input()
if s == "zyxwvutsrqponmlkjihgfedcba":
  print(-1)
elif len(s) == 26:
  l = []
  for i in range(26)[::-1]:
    ds = s[i]
    l.append(ds)
    if ds != max(l):
      l.sort()
      for j in l:
        if ds < j:
          break
      print(s[:i]+j)
      break
else:
  for i in list("abcdefghijklmnopqrstuvwxyz"):
    if i in s:
      continue
    else:
      print(s+i)
      break

Measured memory_bytes: 9060
import java.util.Scanner;


public class Main {

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

		int[] A = new int[S.length()];
		A[0] = 1;
		for(int i =1  ; i < S.length() ; i++){
			if(S.substring(i, i+1).equals(S.substring(i-1,i))){
				A[i] = A[i-1];
			}
			else{
				A[i] = A[i-1]+1;
			}
		}
/*
		for(int i = 0 ; i < S.length(); i++){
			System.out.println(A[i]);
		}
*/
		System.out.println(A[S.length()-1]-1);


	}
}


Measured memory_bytes: 36432
def main():
  N = int(input())
  S = tuple(input())
  ans = 0
  for i in range(1000):
    if i<10:
      cnt0= 0
      cnt1 = 0
      for j in range(N):
        if 2<=cnt0 and S[j]=="%d"%i:
          ans+=1
          break
        if S[j]=="0":
          cnt0+=1
          continue
    elif 10<=i<=99:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[1]:
          ans+=1
          break
        if S[j]=="0" and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[0]:
          cnt1 +=1
          continue
    elif 100<=i:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[2]:
          ans+=1
          #print(i)
          break
        if S[j]=="%s"%i[0] and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[1]:
          cnt1 +=1
          continue
  print(ans)
main()
      
      


Measured memory_bytes: 46812
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int,int> pii;
typedef pair <db,db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const double EPS = 1e-9;
const ll MOD=998244353;
const ll hell=1000000007;
const int INF = 1e18;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

const int N=100005;

int dp[1005][1005];

void solve()
{
int n,m;
cin>>n>>m;
string s[n];
for(int i=0;i<n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(s[i-1][j-1]=='#')
        dp[i][j]=0;
        else
        {
            if(i==1&&j==1)
            dp[i][j]=1;
            else
            {
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%hell;
            }
            
        }
        
    }
}
cout<<dp[n][m]<<endl;



}




int32_t main()
{
    IOS;
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        
        solve();
    }
    return 0;
}

Measured memory_bytes: 12592
#include <stdio.h>

int cnt[200005];

int main(void) 
{
    int n,i; 
    scanf("%d", &n);
    for (i = 1; i < n; i++) 
    {
        int tt; scanf("%d", &tt);
        cnt[tt]++;
    }
    for ( i = 1; i <= n; i++)
        printf("%d\n", cnt[i]);
        return 0;
}


Measured memory_bytes: 2508
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    string s;
    cin >> n >> s;

    ll ans = 0;
    exrep(i, 1, n-1) {
        string t1 = s.substr(0, i);
        string t2 = s.substr(i, n-i);
        vl v1(26), v2(26);
        rep(j, i) {
            v1[t1[j] - 'a']++;
        }
        rep(j, n-i) {
            v2[t2[j] - 'a']++;
        }
        ll now = 0;
        rep(j, 26) {
            if(v1[j] > 0 && v2[j] > 0) {
                now++;
            }
        }
        chmax(ans, now);
    }

    out(ans);
    re0;
}

Measured memory_bytes: 256
N = int(input())
S = ['']

res = []

for _ in range(N):
    A = int(input())
    s = []
    for _ in range(A):
        s.append(list(map(int, input().split())))
    S.append(s)

allp = 2**N - 1

for i in range(allp, -1, -1):
    pat = bin(i).replace('0b', '')
    pat = pat.zfill(N)
    h_list = []
    l_list = []
    for (i, p) in enumerate(pat):
        t = i + 1
        if p == '1':
            if t in l_list:
                break
            h_list.append(t)
            for s in S[t]:
                if s[1] == 1:
                    if s[0] in l_list:
                        break
                    h_list.append(s[0])
                else:
                    if s[0] in h_list:
                        break
                    l_list.append(s[0])
            else:
                continue
            break
        else:
            if t in h_list:
                break
            l_list.append(t)
    else:
        res.append(pat)

maxA = 0
for r in res:
    maxA = max(maxA, r.count('1'))
print(maxA)


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N;
	cin >> N;
	int K;
	cin >> K;
	vector<int> A(N);
	rep(i, 0, N)cin >> A[i];
	sort(all(A));
	int sum = 0;
	rep(i, 0, K)sum += A[i];
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
#define inf 2000000000
#define limit 10000000
int arr[10005],dp[limit],choc[3]={1,2,5};
vector<int> v;
int main(){
    int n;cin>>n;
    double t,a;cin>>t>>a;
    double diff = inf;
    int ans = 0;
    for (int i=1;i<=n;i++) {
        double x;cin>>x;
        double y = t-x*0.006;
        if (abs(y-a)<diff) {
            diff=abs(y-a);
            ans=i;
        }
    }
    cout<<ans<<"\n";
    
}

Measured memory_bytes: 256
#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>
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)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

map<pair<int,ll>,ll> dp;
ll num[60];

ll rec(int n,ll k){
    if(k==0)return 0;
    if(n==0)return k==1;
    if(dp[{n,k}])return dp[{n,k}];
    ll ret=0;
    ret+=rec(n-1,min(k-1,num[n-1]));
    if(k>=num[n-1]+2){
        ++ret;
        ret+=rec(n-1,min(num[n-1],k-num[n-1]-2));
    }
    return dp[{n,k}]=ret;
}

int main(){
    ll n,k;
    cin>>n>>k;
    num[0]=1;
    rep(i,50)num[i+1]=2*num[i]+3;
    cout<<rec(n,k)<<endl;
    return 0;
}


Measured memory_bytes: 256