akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var X = ReadLine();
            var tNum = 0L;
            var sNum = 0L;
            foreach(var x in X)
            {
                if (x == 'T')
                {
                    if (0 < sNum) --sNum;
                    else ++tNum;
                }
                else
                    ++sNum;
            }
            WriteLine(sNum + tNum);

            //Out.Flush();
        }

    }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
int pw=1,n;

int main(){
	scanf("%d",&n);
	while(pw<n) pw*=2;
	if(pw==n){puts("No");return 0;}
	puts("Yes");
	if(n==pw-1){
		for(int i=1;i<2*n;i++) printf("%d %d\n",i,i+1);
		return 0;
	}
	printf("2 3\n");
	printf("3 1\n");
	printf("1 %d\n",n+2);
	printf("%d %d\n",n+2,n+3);
	pw=8;
	while(pw-1<=n){
		for(int i=pw/2;i<pw-1;i++) printf("%d %d\n",i,i+1);
		printf("%d %d\n",pw-1,n+pw/2);
		for(int i=pw/2;i<pw-1;i++) printf("%d %d\n",n+i,n+i+1);
		pw*=2;
	}
	pw/=2;
	printf("%d %d\n",n+1,pw);
	printf("%d %d\n",pw,pw+1);
	printf("%d 1\n",pw+1);
	printf("1 %d\n",n+pw);
	printf("%d %d\n",n+pw,n+pw+1);
	for(int i=pw+2;i+1<=n;i+=2){
		printf("%d %d\n",i,i+1);
		printf("%d 1\n",i+1);
		printf("1 %d\n",n+i);
		printf("%d %d\n",n+i,n+i+1);
	}
	if(n%2==1){
		for(int i=4;i<=pw/2;i*=2) printf("1 %d\n",i);
		return 0;
	}
	else{
		int at;
		if(n&2) printf("%d %d\n",n,n+2),at=pw+1;
		else printf("%d %d\n",n,pw),at=pw;
		for(int i=4;i<=pw/2;i*=2){
			if(n&i) printf("%d %d\n",at,i),at=i;
			else printf("1 %d\n",i);		
		}
		printf("%d %d\n",at,2*n);
	}
	
	return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>
#include <math.h>
#define N 2000

int main(void){
	
	int n,x,y;
	scanf("%d %d %d",&n,&x,&y);
	int g[N];
	for(int i = 1; i < n; i++){
		g[i] = n-i;
	}
	int limit = (y-x)/2;
	
	//printf("limit = %d\n", limit);
	
	for(int i = 1; i <= x; i++){
		for(int j = 1; j < limit; j++){
			g[x-i+1+j]++;
			g[y-j-i]--;
			//printf("distace between %d to %d --> from %d to %d\n",i,y-j,y-j-i,x-i+1+j);
		}
		for(int j = 0; y+j <= n; j++){
			g[x-i+1+j]++;
			g[y+j-i]--;
			//printf("distace between %d to %d --> from %d to %d\n",i,y+j,y+j-i,x-i+1+j);
		}
	}
	for(int i = x+1; i < x+limit; i++){
		for(int j = 1; j+i-x < limit; j++){
			g[i-x+1+j]++;
			g[y-j-i]--;
			//printf("distace between %d to %d --> from %d to %d\n",i,y-j,y-j-i,i-x+1+j);
		}
		for(int j = 0; y+j <= n; j++){
			g[i-x+1+j]++;
			g[y+j-i]--;
			//printf("distace between %d to %d --> from %d to %d\n",i,y+j,y+j-i,i-x+1+j);
		}
	}
	for(int i = 1; i < n; i++){
		printf("%d",g[i]);
		if( i < n ) printf("\n");
	}
	
}

Measured memory_bytes: 128
import heapq


def main():
    n = int(input())
    v = list(map(float, input().split()))
    heapq.heapify(v)
    while True:
        a = heapq.heappop(v)
        if not len(v):
            print(a)
            return
        b = heapq.heappop(v)
        heapq.heappush(v, (a + b) / 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9136
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "#":
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
    if c != W - 1 and maze[n + 1] == ".":
        array[n][n + 1] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
    if r != H - 1 and maze[n + W] == ".":
        array[n][n + W] = 1
dist = csgraph.shortest_path(array, directed=False)
print(int(dist[dist < 401].max()))


Measured memory_bytes: 19248
n, Y = gets.chomp.split.map(&:to_i)
x, y , z = -1, -1 ,-1
(0..n).each do |a|
  (0..n-a).each do |b|
    if Y == a*10000 + b*5000 + (n-a-b) * 1000
      x, y, z = a, b, n-a-b
    end
  end
end
puts "#{x} #{y} #{z}"


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 998244353;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd_calc(T a, T b){ if(b){ return gcd_calc(b, a % b); }else{ return a; }}
template<class T> T gcd(T a, T b){ if(a < b) swap(a, b); return gcd_calc(a, b); }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
inline int at(int x, int k){ return (x >> k) & 1; }
random_device rnd;

int main(){
    string S, T, U;
    int A, B;
    cin >> S >> T >> A >> B >> U;
    if(S == U){
        A--;
    }else{
        B--;
    }
    cout << A << " " << B << endl;
}


Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b%mod ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll n,k ;
	cin >> n >> k ;
	if(n==1){
		cout << 0 << endl ;
		return 0 ;
	}
	vll a(n) ;
	for(auto &i:a) cin >> i ;
	ll ans = INF ;
	for(int i=0;i<(1<<n);i++){
		bitset<20> bit(i) ;
		ll cost = 0 ;
		ll cnt = 1 ;
		ll pre = a.at(0) ;
		for(int j=1;j<n;j++){
			if(bit[j]){
				cost += max(pre+1-a.at(j),0LL) ;
				pre = max(pre+1,a.at(j)) ;
				cnt++ ;
			}else{
				if(pre<a.at(j)){
					cnt++ ;
					pre = a.at(j) ;
				}
			}
		}
		if(cnt>=k) ans = min(ans,cost) ;
	}
	cout << ans << endl ;
}


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

public class Hello
{
    public static void Main()
    {
        var a = new bool[110000];
        GeneratePrime(a);
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = int.Parse(line[0]);
            var p = int.Parse(line[1]);
            if (n == -1 && p == -1) break;
            var t = n + 1;
            var ba = new int[25];
            var count = 0;
            while (count < ba.Length)
            {
                if (a[t]) ba[count++] = t;
                t++;
            }
            Console.WriteLine(getAns(ba,p));
        }
    }
    public static int getAns (int[] a ,int p)
    {
        var aL = a.Length;
        var ret = new List<int>();
        for (int i = 0; i < aL; i++)
            for (int j = i; j < aL; j++) ret.Add(a[i] + a[j]);
        ret.Sort();
        return ret[p - 1];
    }
    public static void GeneratePrime(bool[] p)
    {
        int prime;
        var m = p.Length;
        var sqrtMax = Math.Sqrt(m);
        var searchList = Enumerable.Range(2, m - 1).ToList();
        do
        {
            prime = searchList.First();
            p[prime] = true;
            searchList.RemoveAll(n => n % prime == 0);
        }
        while (prime < sqrtMax);
        foreach (var x in searchList)
            p[x] = true;
    }
}



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

int main(void)
{
   int i, f=0;
   char s[11], c[11];

   scanf("%s",s);
   for(i=0;i<strlen(s);i++){
      if(s[i]!='B'){
         c[f]=s[i];
         f++;
      }
      else if(f!=0)
         f--;
   }

   for(i=0;i<f;i++)
      printf("%c",c[i]);
   printf("\n");
   return 0;
}

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

int main(){
	int a,b;
	cin >> a >> b;
	int sisa = a - (2 * b);
	if(sisa <= 0){
		cout << 0 << endl;
	}else{
		cout << sisa << endl;
	}
	return 0;
}

Measured memory_bytes: 256
from collections import deque
n, m = map(int, input().split())

graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * n
prev_node = [-1] * n
dist[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for v_next in graph[v]:
        if dist[v_next] == -1:
            dist[v_next] = dist[v] + 1
            prev_node[v_next] = v
            q.append(v_next)

# print(dist)
# print(prev_node)

print('Yes')
for i in range(1, n):
    print(prev_node[i] + 1)


Measured memory_bytes: 34992
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a==5&&b==7&&c==5||a==5&&b==5&&c==7||a==7&&b==5&&c==5)
		cout<<"YES";
	else
		cout<<"NO";
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
plist=list(map(int,input().split()))
#print(plist)

par_list=list(range(N+1))
for i in range(M):
  x,y=map(int,input().split())
  merge(x,y)
#print(par_list)

index_dic={}
comp_list=[]
for i in range(1,N+1):
  par=get_par(par_list[i])
  comp_list.append(par)
  if par in index_dic:
    index_dic[par].append(i)
  else:
    index_dic[par]=[i]
#print(comp_list)
#print(index_dic)

answer=0
for par,vlist in index_dic.items():
  v2set=set()
  for v in vlist:
    v2set.add(plist[v-1])
      
  #print(vlist)
  #print(v2set)
  for v in vlist:
    if v in v2set:
      answer+=1
      
print(answer)

Measured memory_bytes: 32348
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
  public static void main(String[] args) {
    Main m = new Main();
    m.run();
  }
  private void run() {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
      String[] s = br.readLine().split("\\s+");
      int n = Integer.parseInt(s[0]);
      int m = Integer.parseInt(s[1]);
      int[] a = Arrays.stream(br.readLine().split("\\s+"))
        .mapToInt(Integer::parseInt).toArray();
      PriorityQueue<Integer> pq = new PriorityQueue<>();
      PriorityQueue<Operation> op = new PriorityQueue<>(Comparator.reverseOrder());
      for (int i=0;i<n;i++) pq.offer(a[i]);
      for (int i=0;i<m;i++) {
        s = br.readLine().split("\\s+");
        int b = Integer.parseInt(s[0]);
        int c = Integer.parseInt(s[1]);
        op.offer(new Operation(b,c));
      }
      for (int i=0;i<m;i++) {
        Operation o = op.poll();
        for (int j=0;j<o.b;j++) {
          int d = pq.peek();
          if (d >= o.c) break;
          d = pq.poll();
          pq.offer(o.c);
        }
      }
      long sum = 0L;
      for (int i=0;i<n;i++) sum += (long)pq.poll();
      System.out.println(sum);
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
  private class Operation implements Comparable<Operation> {
    int b,c;
    Operation(int b,int c) {
      this.b = b;
      this.c = c;
    }
    @Override
    public int compareTo(Operation other) {
      if (c == other.c) return Integer.compare(b,other.b);
      return Integer.compare(c,other.c);
    }
  }
}

Measured memory_bytes: 74268
#include<bits/stdc++.h>
#define N 100009
using namespace std;

int n,m,tx,ty,tot,tp,a[N],q[N],fst[N],pnt[N<<1],nxt[N<<1];
int f[N],g[N],c[N],d[N],fa[N]; bool vis[N],dlt[N]; long long ans;
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
void dfs(int x){
	int i,y; vis[x]=1; f[x]=d[x]&1; g[x]=f[x]^1;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (dlt[y]) continue;
		if (!vis[y]){
			fa[y]=x; d[y]=d[x]^1;
			dfs(y);
			f[x]+=f[y]; g[x]+=g[y];
		} else if (y!=fa[x] && !tx){
			tx=x; ty=y;
		}
	}
	c[x]=f[x]-g[x];
	if (fa[x] && !dlt[x]) ans+=abs(c[x]);
}
void gg(){ puts("-1"); exit(0); }
int main(){
	scanf("%d%d",&n,&m);
	if (n&1) gg();
	int i,x,y;
	for (i=1; i<=m; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	dfs(1);
	if (!tx){ tx=n; ty=fa[n]; }
	if (!(d[tx]^d[ty])){
		if (c[1]&1) gg();
		x=c[1]/2;
	} else if (c[1]) gg();
	for (i=tx; i!=ty; i=fa[i]) q[++tp]=i; q[++tp]=ty;
	for (i=1; i<=tp; i++) dlt[q[i]]=1;
	ans=0;
	memset(vis,0,sizeof(vis));
	for (i=1; i<=tp; i++) dfs(q[i]);
	for (i=1; i<tp; i++) a[i]=a[i-1]+c[q[i]];
	if (d[tx]^d[ty]){
		sort(a+1,a+tp+1);
		x=a[tp+1>>1];	
	}
	for (i=1; i<=tp; i++) ans+=abs(x-a[i]);	
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 9856
n,m = map(int,input().split())
h = list(map(int,input().split()))
target = [0 for _ in range(n)]
win = [0 for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    target[a-1] += 1
    target[b-1] += 1
    if h[a-1] > h[b-1]:
        win[a-1] += 1
    elif h[b-1] > h[a-1]:
        win[b-1] += 1

count = 0
for j in range(n):
    if target[j] == win[j]:
        count += 1

print(count)

Measured memory_bytes: 19980
/*#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC target("avx2")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>

#define int long long

#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define endl '\n'


using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 mrand(random_device{}());

const double PI = acos((double)-1);
const double eps = 1e-7;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;

void solve();
void scan();

signed main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cout << fixed; cout.precision(15);
	solve();
	return 0;
}

void solve() {
	int n;
	ll k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i]; a[i]--;
	}
	int s = 0;
	int x;
	if (k > n) {
		vector<bool> used(n, false);
		vector<int> d(n);
		ll cnt = 1;
		x = a[0];
		while (!used[x]) {
			used[x] = true;
			//cout << x << endl;
			d[x] = cnt;
			x = a[x];
			cnt++;
		}
		k -= d[x];
		cnt -= d[x];
		k %= cnt;
	}
	else x = 0;
	for (int i = 0; i < k; i++)
		x = a[x];
	cout << x + 1 << endl;
	return;
}

Measured memory_bytes: 6364
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//�]���؂�グ�� =>  (a + b - 1) / b 

signed main(){
	string s,t; cin>>s>>t;
  int ans=0;
  rep(i,0,3)ans+=(s[i]==t[i]);
  cout<<ans;
	
	return 0;
}


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

int main() {
  int64_t n;
  std::cin >> n;
  int64_t m4 = 0, m2 = 0, m1 = 0;

  for (int64_t i = 0; i < n; i++) {
    int64_t t;
    std::cin >> t;
    if (t % 4 == 0) {
      m4++;
    } else if (t % 2 == 0) {
      m2++;
    } else {
      m1++;
    }
  }

  if (m1 <= m4 || (m1 - 1 == m4 && m2 == 0)) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  return 0;
}

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

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;

using namespace std;


signed main() {
  int N, K;
  cin >> N >> K;

  vector<int> H(N);
  REP(i, N) cin >> H[i];

  sort(ALL(H), greater<int>());

  int ans = 0;
  FOR(i, K, N){
    ans += H[i];
  }

  cout << ans << endl;

  return 0;
}

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

int main()
{
  char s[21],tmp;
  int len;

  while(cin >> s){
    len = 0;
    while(s[len++]);
    for(int i=0;i<(len-1)/2;i++){
      tmp = s[i];
      s[i] = s[len-i-2];
      s[len-i-2] = tmp;
    }
    s[len-1] = '\0';

    cout << s << endl;
  }
  return 0;
}

Measured memory_bytes: 0
use std::f64::consts::PI;
use std::io::*;
use std::str::FromStr;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let a: f64 = sc.next();
    let b: f64 = sc.next();
    let c: f64 = sc.next::<f64>() / 180. * PI;

    println!("{:.8}", a * b * c.sin() / 2.);
    println!(
        "{:.8}",
        a + b + (a.powi(2) + b.powi(2) - 2. * a * b * c.cos()).sqrt()
    );
    println!("{:.8}", b * c.sin());
}

/* ========== Scanner ========== */

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn read<T: FromStr>(&mut self) -> Option<T> {
        let token = self
            .reader
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn next<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.read() {
            s
        } else {
            writeln!(stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

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

    fn char(&mut self) -> char {
        self.next::<String>().chars().next().unwrap()
    }
}



Measured memory_bytes: 5200
n = int(input())
w = list(map(int,input().split()))
s = sum(w)
g = 10**5
cnt = 0
for i in range(n):
    cnt += w[i]
    if abs(s-cnt*2) <= g:
        g = abs(s-cnt*2)
        ans = abs(s-cnt*2)
print(ans)

Measured memory_bytes: 9180
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
vi g[200005];
ll ans[200005];
void dfs(int i,int p){
    for(ll x:g[i])if(x!=p){
        ans[x]+=ans[i];dfs(x,i);
    }
}
void solve(){
    ll n,q;cin>>n>>q;
    rep(i,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    rep(i,q){
        ll c,d;cin>>c>>d;
        ans[c-1]+=d;
    }
    dfs(0,-1);
    rep(i,n){
        if(i)cout<<' ';
        cout<<ans[i];
    }
    cout<<endl;
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

Measured memory_bytes: 20864
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  set<int> st;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (st.count(a)) {
      cout << "NO\n";
      return 0;
    }
    st.insert(a);
  }
  cout << "YES\n";
  return 0;
}

Measured memory_bytes: 9600
#include <stdio.h>

int main(void){
  int j,i,n,p[200005],min=200005,count=1;
  scanf("%d",&n);
   for(i=0;i<n;i++){
     scanf("%d",&p[i]);
  }
   j=p[0];
   for(i=0;i<n;i++){
     if(j>p[i]){
       j=p[i];
       count++;
     }
   }
   printf("%d\n",count);
  return 0;
}


Measured memory_bytes: 2464
#include <iostream>
#include <algorithm>
#define INF (2 << 28)
using namespace std;

int main(){
    
    int n, k, a[111111];
    int sum[111111];
    
    while(cin >> n >> k, n||k){
        fill_n(sum, 111111, 0);
        for(int i = 0; i < n; i++) cin >> a[i];
        
        sum[0] = a[0];
        for(int i = 0; i < n; i++) sum[i] = sum[i - 1] + a[i];
    
        int maxi = -INF;
        for(int i = k; i < n; i++)
            maxi = max(maxi, sum[i] - sum[i - k]);
        
        cout << maxi << endl;
    }
}

Measured memory_bytes: 1984
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include<string>
#include<vector>
#include<algorithm>
const long long int maxn = 1e3+2;
const long long int mod = 1e3+2;

int main()
{
	fr
	ll a[6], k;
	for(ll i=1;i<=5;i++)
		cin>>a[i];	cin>>k;
	for(ll i=1;i<=5;i++)
	{
		for(ll j=1;j<=5;j++)
		{
			if(i!=j)
			{
				if(abs(a[i]-a[j]) > k)
				{
					cout<<":("<<endl;	return 0;
				}
			}
		}
	}	
	cout<<"Yay!"<<endl;
	return 0;	
}


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

typedef long long ll;

#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back

const long double PI = acos(-1);

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll GetDigit(ll num) {return log10(num)+1;}

int main(){
  ll x;
  cin >> x;
  
  cout << x/11*2 + (x%11!=0) + (x%11>6) << endl;
  return 0;
}

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

int main() {
    string S, T; cin >> S >> T;

    int cnt = 0;
    for(int i=0; i<3; i++){
        if(S.at(i) == T.at(i)){
            cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  int q;
  scanf("%d",&q);
  std::vector<std::string > X(q);
  std::vector<std::string > Y(q);
  for (int i=0; i<q; i++){
    std::cin >> X[i];
    std::cin >> Y[i];
  }
  int val[1002][1002];
  for (int k=0; k<q; k++){
    for (int i=0; i<X[k].length(); i++){
      for (int j=0; j<Y[k].length(); j++){
        if (X[k][i]==Y[k][j]){
          if (i==0 && j==0){
            val[i][j]=1;
          }
          if (i>0 && j>0){
            val[i][j]=val[i-1][j-1]+1;
          } else {
            val[i][j]=1;
          }
        } else if (i==0 && j==0){
          val[i][j]=0;
        } else if (i==0){
          val[i][j]=val[i][j-1];
        } else if (j==0){
          val[i][j]=val[i-1][j];
        } else {
          val[i][j]=std::max(val[i-1][j], val[i][j-1]);
        }
      }
    }
    int length = val[X[k].length()-1][Y[k].length()-1];
    printf("%d\n", length);
  }
  return 0;
}



Measured memory_bytes: 7160
#include <bits/stdc++.h>
#define inf 100000000;

using namespace std;
int h, w, i, j;
char s[100][100];
int fin[100][100];
char stmp;

int min(int a, int b) {
    return a > b ? b : a;
}

int dfs(int i, int j, int sum, bool prev) {
    if (i == h-1 && j == w-1) {
        if (s[i][j] == '#' && !prev) sum++;
        fin[i][j] = min(fin[i][j], sum);
    } else {
        if (s[i][j] == '#') {
            if (prev) {
                fin[i][j] = min(fin[i][j], sum);
                if (i < h-1 && fin[i+1][j] > sum) dfs(i+1, j, sum, true);
                if (j < w-1 && fin[i][j+1] > sum) dfs(i, j+1, sum, true);
            } else {
                fin[i][j] = min(fin[i][j], sum+1);
                if (i < h-1 && fin[i+1][j] > sum+1) dfs(i+1, j, sum+1, true);
                if (j < w-1 && fin[i][j+1] > sum+1) dfs(i, j+1, sum+1, true);
            }
        } else {
            fin[i][j] = min(fin[i][j], sum);
            if (i < h-1 && fin[i+1][j] > sum) dfs(i+1, j, sum, false);
            if (j < w-1 && fin[i][j+1] > sum) dfs(i, j+1, sum, false);
        }
    }
    return fin[h-1][w-1];
}

int main() {
    scanf("%d%d%*c", &h, &w);
    for (i=0;i<h;i++) for (j=0;j<w;j++) fin[i][j] = inf;
    for (i=0; i<h; i++){
        for (j=0;j<w;j++) {
            scanf(" %c", &stmp);
            s[i][j] = stmp;
        }
    }
    printf("%d\n", dfs(0, 0, 0, false));
    return 0;
}

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

int main() {
  long long n,a,b;
  cin>>n>>a>>b;
  long long r=n/(a+b);
  long long sub=n-r*(a+b);
  long long ans=r*a;
  if(sub<=a) ans+=sub;
  else ans+=a;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import re

N, K = map(int, input().split())
S = input().strip()

LL = re.finditer('L+', S)
RR = re.finditer('R+', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l.group(0)) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r.group(0)) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])

if happy >= N:
    happy = N - 1

print(happy)


Measured memory_bytes: 5364
import itertools
import collections
import bisect

def main():
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())
    e = int(input())
    k = int(input())
    if e - a <= k:
        print('Yay!')
    else:
        print(':(')

if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second

int n, m, x;
vector<int> c(12);
vector<vector<int>> l(12);

int main(){
    fastio;
    cin >> n >> m >> x;
    for(int i=0; i<n; i++){
        cin >> c[i];
        for(int j=0; j<m; j++){
            int temp;
            cin >> temp;
            l[i].pb(temp);
        }
    }
 
    ll lim = pow(2, n);
    ll ans = 1e18;
    ll cost = 0;
    bool f = false;

    for(ll i=0; i<lim; i++){
        cost = 0;
        vector<int> mx(m);
        for(int j=0; j<n; j++){
            if(i&(1<<j)){
                cost += c[j];
                for(int k=0; k<m; k++){
                    mx[k] += l[j][k];
                }
            }
        }
        bool flag = true;
        for(int j=0; j<m; j++){
            if(mx[j] < x){
                flag = false;
                break;  
            }
        }
        if(flag){
            ans = min(ans, cost);
            f = true;
        }
    }
    if(f) cout << ans << endl;
    else cout << "-1\n";

    return 0;
}

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

int n;

void counting_sort(unsigned int A[], unsigned int B[], int k) {
  int *C;
  C = (int*)malloc(k+10);

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

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

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

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


int main() {
  unsigned int *A, *B;

  scanf("%d", &n);

  A = (unsigned int*)malloc(sizeof(unsigned int) * n);
  B = (unsigned int*)malloc(sizeof(unsigned int) * n);

  for (long int i = 0; i < n; i++) {
    scanf("%u", &A[i]);
  }

  counting_sort(A, B, 10010);

  for (int i = 0; i < n; i++) {
    if(i > 0) cout << " ";
    cout << B[i];
  }

  cout << endl;
}



Measured memory_bytes: 18808
<?php

function input($func = null) {
    if ($func === null) {
        return trim(fgets(STDIN));
    } else {
        return $func(trim(fgets(STDIN)));
    }
}
function input_array($func = null) {
    if ($func === null) {
        return explode(' ', trim(fgets(STDIN)));
    } else {
        return array_map(function($v) use ($func) {
            return $func($v);
        }, explode(' ', trim(fgets(STDIN))));
    }
}

list($n, $a, $b) = input_array();

$max = min($a, $b);
$min = max($a + $b - $n, 0);

echo "{$max} {$min}\n";


Measured memory_bytes: 4604
package main

import "fmt"

func initialize_grid(width int,height int)[][]int{
	var grid [][]int
	for i:=0;i<height+1;i++{
		var grid_row  []int
		for j:=0;j<width+1;j++{
			grid_row = append(grid_row,0)
		}
		grid = append(grid,grid_row[:])
	}
	return grid
}

func ma(x int,y int)int{
	if x >= y{
		return x
	}else{
		return y
	}
}

func main()  {
	//Take input
	var num int
	var st1,st2 string
	var string_pairs [][]string
	fmt.Scan(&num)
	for i:=0;i<num;i++{
		var string_pair []string
		fmt.Scan(&st1)
		fmt.Scan(&st2)
		string_pair = append(string_pair,st1,st2)
		string_pairs = append(string_pairs,string_pair)
	}
	//DP
	//initialize grid
	for i:=0;i<num;i++{
		string_1 := string_pairs[i][0]
		string_2 := string_pairs[i][1]

		dp := initialize_grid(len(string_2),len(string_1))

		for j:=1;j<len(string_1)+1;j++{
			for k:=1;k<len(string_2)+1;k++{
				if string_1[j-1] == string_2[k-1]{
					dp[j][k] = dp[j-1][k-1] + 1
				}else{
					dp[j][k] = ma(dp[j-1][k],dp[j][k-1])
				}
			}
		}
		fmt.Println(dp[len(string_1)][len(string_2)])
	}
}



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

namespace AtCoder
{
    public class Code9
    {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();

            Console.WriteLine(funcMain(s1));

            Console.ReadKey();
        }

        static public string funcMain(string arg1)
        {
            // 8パターンごとき力業で解けばよいと思う
            var i = new int[4];
            i[0] = int.Parse(arg1[0].ToString());
            i[1] = int.Parse(arg1[1].ToString());
            i[2] = int.Parse(arg1[2].ToString());
            i[3] = int.Parse(arg1[3].ToString());

            string op="";

            for (var j = 0; j < 8; j++)
            {
                op = "";
                switch (j)
                {
                    case 0:
                        op = "+++";
                        break;
                    case 1:
                        op = "++-";
                        break;
                    case 2:
                        op = "+-+";
                        break;
                    case 3:
                        op = "-++";
                        break;
                    case 4:
                        op = "+--";
                        break;
                    case 5:
                        op = "-+-";
                        break;
                    case 6:
                        op = "--+";
                        break;
                    case 7:
                        op = "---";
                        break;
                    default:break;

                }

                int i2 = i[0];
                for (var k = 0; k < op.Length; k++)
                {
                    switch (op[k])
                    {
                        case '+':
                            i2 +=i[k+1];
                            break;
                        case '-':
                            i2 -= i[k+1];
                            break;
                        default: break;
                    }

                }
                if (i2 == 7)
                    break;
            }

            return string.Format("{0}{1}{2}{3}{4}{5}{6}=7", i[0], op[0], i[1], op[1], i[2], op[2], i[3]);
        }

    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll i, j;
    ll n;
    cin >> n;
    ll a[n];
    for (i = 0; i < n; i++) cin >> a[i];
    ll c = 1000 / a[0];
    ll p = 1000 - c * a[0];
    for (i = 0; i < n; i++) {
        if (i == n - 1) {
            p += a[i] * c;
            cout << p << endl;
            return 0;
        } else if (a[i] > a[i + 1]) {
            p += a[i] * c;
            c = p / a[i + 1];
            p -= a[i + 1] * c;
        }
    }
}

Measured memory_bytes: 3588
from itertools import product

n = int(input())
s = list(input() for _ in range(n))

name = [0 for _ in range(5)]
for i in range(n):
    if s[i][0] == "M":
        name[0] += 1
    elif s[i][0] == "A":
        name[1] += 1
    elif s[i][0] == "R":
        name[2] += 1
    elif s[i][0] == "C":
        name[3] += 1
    elif s[i][0] == "H":
        name[4] += 1

res = 0
for pattern in product([0, 1], repeat=5):
    if sum(pattern) == 3:
        p = 1
        for i, j in enumerate(pattern):
            if j == 1:
                p *= name[i]
        res += p
print(res)

Measured memory_bytes: 9784
#include <iostream>

using namespace std;

int main(){
    long N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    for(long n = 0; n < N; n++){
        long m = N-n-1;
        if(A+C*n-D*m <= B && A+D*n-C*m >= B){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

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

int main(){
  string str;
  cin>>str;
  string str2="CODEFESTIVAL2016";
  int cnt=0;
  for(int i=0;i<str2.size();i++){
    if(str2[i]!=str[i])cnt++;
       }
    cout<<cnt<<endl;
  
  return 0;
}


Measured memory_bytes: 764
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] data = br.readLine().split(" ");
		
		int a = Integer.parseInt(data[0]);
		
		System.out.println((a/3600)+":"+(a%3600/60)+":"+(a%60)); 
	}
}

Measured memory_bytes: 24300
#include <iostream>

int main()
{
    int X, Y;   // 頭　あし 
    std::cin >> X >> Y;

    bool isYes = false;

    for(int i=0; i<=100; i++)
    {
        for(int j=0; j<=100; j++)
        {
            if( (2*i + 4*j) ==Y )
            {
                if(i+j == X){isYes = true;}
            }
        }
    }

    if(isYes)
    {
        std::cout << "Yes" << std::endl;
    }
    else
    {
        std::cout << "No" << std::endl;
    }
    
    return 0;
}

Measured memory_bytes: 3592
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 1};
int dy[] = {1, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int H, W, dp[1010][1010];
char board[1010][1010];

signed main() {
    cin >> H >> W;
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            cin >> board[i][j];
        }
    }

    dp[0][0] = 1;
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<2; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if(nx >= H or ny >= W or board[nx][ny] == '#') continue;
                (dp[nx][ny] += dp[i][j]) %= MOD;
            }
        }
    }

    cout << dp[H-1][W-1] << endl;
    return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
  
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
 
#define pb emplace_back
#define fi first
#define se second

using namespace std;
 
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
 
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-8;
const ll MOD = 1e9+7;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
 
// head

struct Mod{
  unsigned n;
  Mod(){}
  Mod( ll x ){
    if( x < 0 ) n = x%MOD+MOD;
    else n = x%MOD;
  }
};
Mod operator + ( Mod a  , Mod b ){ return Mod( a.n + b.n ); }
Mod operator +=( Mod &a , Mod b ){ return a = a + b; }
Mod operator - ( Mod a ){ return Mod( MOD - a.n ); }
Mod operator - ( Mod a  , Mod b ){ return Mod( a.n + MOD - b.n ); }
Mod operator -=( Mod &a , Mod b ){ return a = a - b; }
Mod operator * ( Mod a  , Mod b ){ return Mod( (ll)a.n * b.n ); }
Mod operator *=( Mod &a , Mod b ){ return a = a * b; }
Mod modpow( Mod x , ll k ){
  Mod res = 1;
  while( k ){
    if( k & 1 ) res *= x;
    k /= 2;
    x *= x;
  }
  return res;
}
ll extgcd( ll a , ll b , ll &x , ll &y ){
  ll d = a;
  if( b != 0 ){
    d = extgcd( b , a % b , y , x );
    y -= a / b * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
Mod inv( Mod a ){ ll x, y; assert( extgcd( a.n , MOD , x , y ) == 1 ); return Mod( x ); }
// Mod inv( Mod a ){ return modpow( a , MOD-2 ); }
Mod operator / ( Mod a  , Mod b ){ return Mod( (ll)a.n * inv(b).n ); }
Mod operator /=( Mod &a , Mod b ){ return a = a / b; }


int n, c;
int a[410], b[410];

Mod s[410][410];
 
Mod dp[410][410];
 
int main(){
 
  n = in();
  c = in();
  REP( i , n ){
    a[i] = in();
  }
  REP( i , n ){
    b[i] = in();
  }

  REP( i , c+1 ){
    REP( j , 409 ){
      s[i][j+1] = s[i][j] + modpow( j , i );
    }
  }

  /*
  REP( j , c+1 ){
    dp[n][j] = 0;
  }
  REP( i , n+1 ){
    dp[i][0] = 1;
  }
  */

  dp[n][0] = 1;
  
  for( int i = n-1; i >= 0; i-- ){
    // cout << i << ": ";
    REP( j , c+1 ){
      REP( k , j+1 ){
	dp[i][j] += dp[i+1][j-k] * ( s[k][ b[i] + 1 ] - s[k][ a[i] ] );
	/*
	if( i == 1 and j == 0 ){
	  cout << "* " << dp[i+1][j-k].n << " " << s[k][ b[i] + 1 ].n << " " << s[k][ a[i] ].n << endl;
	}
	*/
      }
      // cout << dp[i][j].n << " ";
    }
    // cout << endl;
  }
 
  printf( "%d\n" , (int)dp[0][c].n );
  
  return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif
struct book{
    string name;
    int score;
    int ans;
};
bool comp(const book &a,const book &b){
    if(a.name==b.name){
        return a.score>b.score;
    }else{
        return a.name<b.name;
    }
    return a.name<b.name;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<book>v;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        int a;
        cin>>a;
        struct book b;
        b.ans=i+1;
        b.score=a;
        b.name=s;
        v.push_back(b);
    }
    sort(v.begin(),v.end(),comp);
    for(int i=0;i<n;i++){
        cout<<v[i].ans<<endl;
    }
    
    return 0;
    
}



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

using namespace std;

int N;
vector<int> G[100005];

int dfs(int v, int prev)
{
	if(G[v].size() == 1) return 0;
	
	int ret, sum = 0, cnt = 0;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == prev) continue;
		ret = dfs(G[v][i], v);
		sum += ret;
		if(ret > 0) cnt++;
	}
	
	if(prev != -1){
		if(G[v].size()-2 >= cnt) sum += (G[v].size()-2)-cnt;
	}else{
		if(G[v].size()-1 >= cnt) sum += (G[v].size()-1)-cnt;
	}
	return sum;
}

int main(void)
{
	cin >> N;
	int a, b;
	for(int i = 0; i < N-1; i++){
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	int s = -1;
	for(int i = 0; i < N; i++){
		if(G[i].size() >= 3){
			s = i;
			break;
		}
	}
	if(s == -1){
		cout << 1 << endl;
		return 0;
	}
	
	cout << dfs(s, -1) << endl;
	return 0;
}

Measured memory_bytes: 9984