akhauriyash/Code-Regression huggingface dataset:
n=int(input())
a=input()
b=input()
c=input()
cnt=0
for i in range(n):
    if a[i]==b[i] and b[i]==c[i]:
        pass
    elif a[i]==b[i] or b[i]==c[i] or a[i]==c[i]:
        cnt+=1
    else:
        cnt+=2
print(cnt)

Measured memory_bytes: 3064
fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    var list = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    insertionSort(list, n)
}

fun insertionSort(a: MutableList<Int>, n: Int){
    for (i in 0 until n) {
        val tmp = a[i]
        var j = i - 1
        while (j >= 0 && a[j] > tmp) {
            a[j + 1] = a[j]
            j--
        }
        a[j + 1] = tmp
        for (k in 0 until n) {
            print(a[k])
            if(k != a.size-1) {
                print(" ")
            } else {
                println()
            }
        }
    }
}


Measured memory_bytes: 37284
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300+10;
char a[maxn][maxn];
int ans[maxn][maxn];
int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    int cnt=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='#')
                ans[i][j]=cnt++;
        }
    }
    for(int i=1; i<=n; i++)
    {
        int temp=0,cn;
        for(int j=1; j<=m; j++)
        {
            if(a[i][j]=='#')
            {
                temp=j;
                // cout<<ans[i][j]<<endl;
                for(int k=j-1; ans[i][k]==0&&k>=1; k--)
                {
                    ans[i][k]=ans[i][j];
                    //cout<<k<<" ";
                }
                //cout<<endl;
            }
        }
        if(temp!=0)
        {
            int cn=ans[i][temp];
            for(; temp<=m; temp++)
                ans[i][temp]=cn;
        }
    }



    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(ans[i][j]==0)
            {
                int k=i;
                while(ans[k][j]==0&&k<=m)
                    k++;
                int cn=ans[k][j];
                //cout<<"cn i,j:"<<cn<<" "<<i<<" "<<j<<endl;
                while(k>=i)
                    ans[k][j]=cn,k--;
            }
        }
    }
    int i=n;
    for(int j=1; j<=m; j++)
    {
        if(ans[i][j]==0)
        {
            int k=i;
            while(ans[k][j]==0&&k>=1)
                k--;
            int cn=ans[k][j];
            //cout<<"cn i,j:"<<cn<<" "<<i<<" "<<j<<endl;
            while(k<=i)
                ans[k][j]=cn,k++;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }

}


Measured memory_bytes: 1280
n, a, b = list(map(int, input().split()))

ans = 0
for num in range(1, n+1):
    p = num
    digit_sum = 0
    while p > 0:
        digit_sum += p % 10
        p //= 10
    if a<= digit_sum <= b:
        ans += num
print(ans)


Measured memory_bytes: 9028
N,K = gets.chomp.split(" ").map(&:to_i)
coord = N.times.map{gets.chomp.split(" ").map(&:to_i)}.sort_by{|i,j|i}
a = Array.new(N+1).map{Array.new(N+1,0)}
ans = 10**20
x,y = 2.times.map{Hash.new}
coord.each_with_index do |b,i|
  x[b[0]] = i+1
end
coord.sort_by{|i,j|j}.each_with_index do |b,i|
  y[b[1]] = i+1
end
coord.each do |i,j|
  a[x[i]][y[j]] = 1
end
x = x.invert
y = y.invert
for i in 1..N
  for j in 1..N
    a[i][j] += a[i][j-1]
  end
end
for i in 1..N
  for j in 1..N
    a[j][i] += a[j-1][i]
  end
end
for i in 1..N-1
  for j in i+1..N
    for k in 1..N-1
      for l in k+1..N
        if a[j][l]+a[i-1][k-1]-a[i-1][l]-a[j][k-1] >= K
          ans = [ans,(x[j]-x[i])*(y[l]-y[k])].min
        end
      end
    end
  end
end
puts ans

Measured memory_bytes: 3836
fun main(args:Array<String>){
  var s = readLine()!!.toInt()
  var a = s/100
  var b = s%100
  if(b<13 && 0<b){
    if(a<13 && 0<a){
      println("AMBIGUOUS")
    }
    else{
      println("YYMM")
    }
  }
  else{
    if(a<13 && 0<a ){
      println("MMYY")
    }
    else{
      println("NA")
    }
  }
}

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

int main() {
  long long N;
  cin >> N;
  
  vector<long long>H(N);
  for (int i = 0; i < N; i++) {
    cin >> H.at(i);
  }
  
  for (int i = 0; i < N-1; i++) {
    if (H.at(i) > H.at(i+1)){
      cout << "No" << endl;
      return 0;
    }
    else if (H.at(i) <= H.at(i+1) - 1){
      H.at(i+1)--;
    }
  }
  
  cout << "Yes" << endl;
}
 

Measured memory_bytes: 3988
n = int(input())
l = []
for i in range(n):
    a = int(input())
    for j in range(a):
        a1, a2 = map(int, input().split())
        l.append([i, a1-1, a2])
ans = 0
for i in range(1 << n):
    uso = False
    # print(i)
    for ll in l:
        # ll[0]が正直なのかをチェック]
        # print(ll)
        if i >> ll[0] & 1:  # 正直
            if ((i >> ll[1]) & 1) == ll[2]:
                pass
            else:
                uso = True
                break
        # else:  # 嘘
        #    if ((i >> ll[1]) & 1) == ll[2]:
        #        uso = True
        #        break
    if uso == False:
        # print(bin(i))
        ans = max(ans, len(str(bin(i)).replace('0b', "").replace('0', "")))
print(ans)


Measured memory_bytes: 3064
import sys
readline = sys.stdin.readline

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

N = int(readline())
res = []
for i in range(1, N):
  if i*i > 8*N:
    break
  if (8*N)%i:
    continue
  res.append(i)
  res.append(8*N//i)


def sqrt(x):
    ok = 0
    ng = 10**18
    while (ng-ok) > 1:
        med = (ok+ng)//2
        if med*med <= x:
            ok = med
        else:
            ng = med
    return ok
    

M = 8*N

ans = 2*N-1
for r in res:
    if r == 1:
        continue
    u = M//r
    if u == 1 or u == 2:
        continue
    if gcd(r, u) > 2:
        continue
    gc, xx, yy = egcd(r, u)
    if gc == 1:
        xx *= 2
        yy *= 2
    xx *= -1
    yy *= -1
    xx %= u
    k = xx*r
    Ml = k*(k+2)
    j = (sqrt(1+Ml)-1)//2
    ans = min(ans, j)
print(ans)


Measured memory_bytes: 73892
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 2*1e5;
const int mod = 1e9+7;

int main() {
    string a, b; cin >> a >> b;
    int a_n = a.size();
    int b_n = b.size();
    if (a_n > b_n) cout << "GREATER" << endl;
    else if (a_n < b_n) cout << "LESS" << endl;
    else {
        if (a < b) cout << "LESS" << endl;
        else if (a > b) cout << "GREATER" << endl;
        else cout << "EQUAL" << endl;
    }
}

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

// 定数
const int GOAL_PRICE = 1000000;

int main(){
    // 変数
    int n;                              // 項目数
    int number;                         // 社員番号
    long long int price, quantity;      // 単価・数量
    std::map<int, long long int> result;     // 結果
    std::vector<int> contents;               // 入力内容

    while (true){
        std::cin >> n;

        if (n == 0) break;

        bool isExcess = false;
        result.clear();
        contents.clear();

        number = 0;
        price = 0;
        quantity = 0;

        for (int i = 0; i < n; i++){
            std::cin >> number >> price >> quantity;
            // 計算結果の追加
            if (!result[number]){
                contents.push_back(number);
                result[number] = 0;
            }
            result[number] += price * quantity;
        }

        for (int number : contents){
            if (result[number] >= GOAL_PRICE){
                std::cout << number << std::endl;
                isExcess = true;
            }
        }

        if (!isExcess){
            std::cout << "NA" << std::endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;

int r, c, k;
int grid[3005][3005];
int dp[3005][3005][4]; //row col taken

int compute(int i,int j,int taken){
    if(i>r || j>c)return 0;
    int &ans=dp[i][j][taken];
    if(ans!=-1)return ans;
    if(taken>=3){
        ans=max(compute(i+1,j,0),compute(i,j+1,taken));
    }
    else{
        ans=max({compute(i+1,j,0)+grid[i][j],compute(i,j+1,taken+1)+grid[i][j],compute(i,j+1,taken)});
    }
    return ans;
}
int32_t main() {

    fast
    cin >> r >> c >> k;
    int x, y, value;

    for(int i = 0; i < k; i++) {
        cin >> x >> y >> value;
        grid[x][y] = value;
    }
    memset(dp,-1,sizeof dp);
    int ans=compute(0,0,0);
    cout << ans<< endl;




    return 0;
}



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

int find_numdigits(int n) {
  int digits = 0;
  while (n != 0) {
    n /= 10;
    digits++;
  }
  return digits;
}

int main() {
  long long N;
  cin >> N;
  int m = find_numdigits(N);
  for (long long i = 1; i * i <= N; i++) {
    if (N % i != 0) continue;
    long long j = N / i;
    int cur = max(find_numdigits(i), find_numdigits(j));
    m = min(m, cur);
  }
  cout << m << endl;
  return 0;
}


Measured memory_bytes: 256
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

N = int(input())
ans = 0
"""
memo = {}
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            key = "&".join(map(str,sorted([i,j,k])))
            m = memo.get(key)
            if(m):
                ans += m
            else:
                gcdnum = gcd(i,j,k)
                ans += gcdnum
                memo[key] = gcdnum
"""
memo = {}
for i in range(1,N+1):
    for j in range(1,N+1):
        tmp = gcd(i,j)
        for k in range(1,N+1):
            ans += gcd(tmp,k)
                
print(ans)

Measured memory_bytes: 69768
#include<stdio.h>

int main()
{
    int N;
    scanf("%d",&N);
    
    char S[N];
    scanf("%s",S);
    
    char T[N];
    scanf("%s",T);
    
    int counter = 0;
    
    char ST[N+N];
    
    for(int i=0;i<N;i++){
        ST[counter] = S[i];
        counter++;
        ST[counter] = T[i];
        counter++;
    }
    
    for(int i=0;i<N+N;i++){
        printf("%c",ST[i]);
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'
void trace(int n, int arr[]){for(int i = 0; i < n; i++){cout << arr[i] << " ";} cout << endl << endl;}
const int N = 105;
ll n, w, weight[N], value[N], dp[N][100005];
ll solve(int idx, ll val){
    if(!val)
        return 0;
    if(idx >= n)
        return 1e15;
    if(dp[idx][val] != -1)
        return dp[idx][val];
    ll mn = min(solve(idx + 1, val),
                solve(idx + 1, val - value[idx]) + weight[idx]);
    dp[idx][val] = mn;
    return dp[idx][val];
}
int main()
{
    Hello
    memset(dp, -1, sizeof dp);
    cin >> n >> w;
    for(int i = 0; i < n; i++)
        cin >> weight[i] >> value[i];
    for(int i = 1e5; i >= 1; i--)
        if(solve(0, i) <= w)
            return cout << i, 0;
    return 0;
}

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

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

  map<string, int> m;
  int N; cin >> N;
  for (int i = 0; i < N; i++) {
    string s; cin >> s;
    m[s]++;
  }
  int M; cin >> M;
  for (int i = 0; i < M; i++) {
    string t; cin >> t;
    m[t]--;
  }
  int ans = 0;
  for (pair<string, int> p : m) {
    ans = max(ans, p.second);
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int T = sc.nextInt();
        T= T + 1/2 ;
         
        System.out.println((T/A)*B );
    }
}


Measured memory_bytes: 20948
#include <iostream>

using namespace std;

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

    for (int x=0; x<=n; x++){

        for (int y=0; y<=(n-x); y++){
            int sub = Y - (10000*x + 5000*y);

            if (sub/1000 == (n-x-y)){
                cout << x << ' ' << y << ' ' << (n-x-y) << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;

}

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

namespace ConsoleApp20
{
    class Program
    {
        static void Main(string[] args)
        {

            //long[] iti = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
            /*
             * 
             * int a,b,c;
            a = int.Parse(Console.ReadLine()); //標準入力
            string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            b = int.Parse(str[0]);  //数値で受け取りたい場合は変換する
            c = int.Parse(str[1]);
　　　　　　　Console.Write("改行なし a = {0} b = {1} c = {2}", a, b, c)//改行なし出力
            Console.WriteLine("改行あり a = {0} b = {1} c = {2}", a, b, c);//改行付き出力
             * */
            string str = Console.ReadLine();

            Console.WriteLine(str.Substring(0,3));
        }
    }
}


Measured memory_bytes: 25880
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.time.chrono.MinguoChronology;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws ParseException {

		Scanner sc = new Scanner(System.in);
		String a = sc.nextLine();
		SimpleDateFormat sd = new SimpleDateFormat();
		sd.applyPattern("yyyy/MM/dd");
		Date date = sd.parse(a);
		String b = "2019/04/30";
		Date hikaku = sd.parse(b);
		int ans = date.compareTo(hikaku);
		if (ans == 0  || ans == -1) {
			System.out.println("Heisei");
		} else {
			System.out.println("TBD");
		}
    }
}

Measured memory_bytes: 22096
package main

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

var sc *bufio.Scanner

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	var s, t string
	fmt.Scan(&s, &t)

	structure := make(map[rune][]int)
	for r := 'a'; r <= 'z'; r++ {
		structure[r] = make([]int, 0)
	}

	for i, rs := range s {
		structure[rs] = append(structure[rs], i+1)
	}

	n := len(s)
	ans := 0
	for _, rt := range t {
		if len(structure[rt]) == 0 {
			ans = -1
			break
		}
		baseIndex := (ans % n) + 1
		var searchIndex int
		switch {
		case sort.SearchInts(structure[rt], baseIndex) == len(structure[rt]):
			searchIndex = n + structure[rt][0]
		default:
			searchIndex = structure[rt][sort.SearchInts(structure[rt], baseIndex)]
		}
		ans += searchIndex - baseIndex + 1
	}

	fmt.Println(ans)
}


Measured memory_bytes: 5248
n, k = [int(n) for n in input().split()]

l = {}
for i in range(n):
    a, b = [int(n) for n in input().split()]

    if a in l:
        l[a] += b
    else:
        l[a] = b

l = sorted(l.items())
c_ = 0
for a, b in l:
    c = c_ + b
    if c_ < k <= c:
        print(a)
        break
    else:
        c_ = c 

Measured memory_bytes: 14600
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<deque>
#include<iomanip>

using namespace std;
typedef long long ll;

int main(void)
{
    int N, A, B;
    cin >> N >> A >> B;

    int ans = min(A*N, B);

    cout << ans << endl;

    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - 1e8;
const ll INFLL = numeric_limits<ll>::max() - 1e17;

signed main() {
    ll N;
    cin >> N;
    ll ans = 0;
    if (N <= 100) {
        for (ll i = 1; i <= N; i++) if ((N / i) == (N % i)) ans += i;
    } else {
        for (ll i = 1; i * i < N ; i++) if (N % i == 0) ans += ((N / i) - 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
k, s  = map(int, input().split())
ans = 0
for i in range(k + 1):
    for j in range(i, k + 1):
        if j <= s - i - j <= k:
            l = s - i - j
            if i == j == l:
                ans += 1
            elif i == j or j == l:
                ans += 3
            elif i != j != l:
                ans += 6
print(ans)

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

#define ALL(a) (a).begin(), (a).end()
#define ll long long

using namespace std;

int getend(string &str, int start){
    int depth = 1;
    int i;
    for(i = start+1; depth > 0; i++){
        if(str[i] == '(')depth++;
        if(str[i] == ')')depth--;
    }
    return i;
}

ll operate(string op, ll x, ll y){
    char t = op[0];
    switch(t){
        case '*': return x*y;
        case '+': return x+y;
        case '^': return x-y;
    }
}

ll calc(string str, map<string, int> &op){
    //cerr << "inp: " << str << endl;
    for(int i = 0; i < str.size(); i++){
        if(str[i] == '('){
            int end = getend(str,i);
            ll result = calc(str.substr(i+1,end-i-2), op);
            string putin = to_string(result);
            str.replace(i, end-i,putin);
        }
    }
    list<string> arr;
    for(int i = 0; i < str.size(); i++){
        if(str[i] >= '0' && str[i] <= '9'){
            int end = i;
            while(str[end] >= '0' && str[end] <= '9' && end < str.size())end++;
            arr.push_back(str.substr(i, end-i));
            i = end-1;
        }
        else if(str[i] == '-'){
            int end = i+1;
            while(str[end] >= '0' && str[end] <= '9' && end < str.size())end++;
            arr.push_back(str.substr(i, end-i));
            i = end - 1;
        }
        else{
            arr.push_back(string{str[i]});
        }
    }
    for(int i = 0; i < 3; i++){
        for(auto itr = arr.begin(); itr != arr.end(); ++itr){
            if(op.find(*itr) != op.end() && op[*itr] == i){
                //cerr << "inp: ";
            //for(auto v : arr)cerr << v << " ";cerr << endl << endl;
                auto left = itr, right = itr;--left; ++right;
                string ins = to_string(operate(*itr, stoll(*left), stoll(*right)));
                --itr;
                for(int i = 0; i < 3; i++)itr = arr.erase(itr);
                arr.insert(itr,ins);
                itr = arr.begin();
                //cerr << "itr: " << *itr << endl;
                //cerr << "res: ";
            //for(auto v : arr)cerr << v << " ";cerr << endl << endl;
            }
        }
    }
    //cerr  << *arr.begin() << endl;
    return stoll(*arr.begin());
}

signed main(){
    string str;
    cin >> str;
    for(auto &e: str)if(e == '-')e = '^';
    map<string, int> op;
    ll ans = LLONG_MIN;
    for(int i = 0; i < 3; i++)for(int j = 0; j < 3; j++)for(int k = 0; k < 3; k++){
        op["*"] = i;op["+"]=j;op["^"]=k;
        //for(auto e : op)cerr << e << " ";
        //cerr << endl;
        ans = max(ans, calc(str, op));
        //cerr << endl;
    }
    cout << ans << endl;
    return 0;
}




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

using namespace std;

bool palindrome(string s)
{
    string t = s;
    reverse(s.begin(), s.end());
    return s == t;
}

int main()
{
    string s;
    cin>>s;
    int n = s.length();
    if (!palindrome(s))
        goto BAD;
    if (!palindrome(s.substr(0, n / 2)))
        goto BAD;
    if (!palindrome(s.substr(n / 2 + 1, n / 2)))
        goto BAD;
    printf("Yes\n");
    return 0;
BAD:;
    printf("No\n");
}


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

int main(){
  int N,X,Y; cin >> N >> X >> Y;
  int count[2002]={};
  for(int i=1; i<=N-1; i++){
    for(int j=i+1; j<=N; j++){
      count[min(j-i,abs(X-i)+1+abs(Y-j))]++;
    }
  }
  
  for(int k=1; k<=N-1; k++) cout << count[k] << endl;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    s = readline().strip()
    n = len(s) - 1

    ans = 0
    for i in range(2**n):
        d = 0
        for j in range(n+1):
            ans += int(s[-(j+1)]) * 10**d
            d += 1
            if ((i >> j) & 1):
                d = 0

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0L;i--)
#define prep(i,n) for(int64_t i=1;i <= (int64_t)(n);i++)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  fspcnt = 0;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int n;
  cin >> n;
  cout << (n*(n+1))/2 << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	ll tot, n;
	cin >> tot >> n;
	vector<ll> vc(n);
	for(auto& el: vc) cin >> el;
	cout << max(-1LL, tot - (accumulate(vc.begin(), vc.end(), 0LL))) << '\n';
}


Measured memory_bytes: 3700
#include<iostream>
#include<algorithm>

using namespace std;


int main(int argc, char const *argv[])
{
	int n;
	int maxv = -2000000000;
	int minv = 2000000000;

	cin>>n;

	int current = 0;
	for(int i=0; i<n; i++) {
		cin >> current;
		maxv = max(maxv, current - minv);
		minv = min(minv, current);
	}
	cout<< maxv << endl;
}


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

int main(){
  int n;
  int a[3];
  cin >> n;

  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++) cin >> a[j];
    sort(a,a+3); //昇順
    if(a[0]*a[0] + a[1]*a[1] == a[2]*a[2]) cout << "YES" << endl;
    else 
      cout << "NO" <<endl;
  }
  return 0;
}

Measured memory_bytes: 1168
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := 5
	array := make([]int, n)
	for i := 0; i < n; i++ {
		array[i] = nextInt()
	}
	sort.Slice(array, func(i, j int) bool { return array[i] > array[j] })
	arrayStr := fmt.Sprint(array)
	l := len(arrayStr)
	fmt.Println(arrayStr[1:(l - 1)])
}



Measured memory_bytes: 1128
#include <bits/stdc++.h>
#define MOD 1000000000
#define MAX 10000005
#define ll long long
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define ub upper_bound
#define lb lower_bound
#define clr(x) memset(x,0,sizeof(x))
#define sws ios::sync_with_stdio(false); cin.tie(0)
#define pi acos(-1)
#define rep(I, N) for (ll I = 0; I < (N); ++I)
#define repp(I, A, B) for (ll I = (A); I <= (B); ++I)
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
using namespace std;
ll pwr(ll base, ll p, ll mod = MOD)
{
    ll ans = 1;
    while(p)
    {
        if(p & 1)   ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        p /= 2;
    }
    return ans;
}
// for inverse modulo : if (1/b)%mod then ans is (b^(mod-2))%mod
ll gcd(ll a, ll b)
{
    if(b == 0)  return a;
    return gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
    return (a*b) / gcd(a, b);
}
bool isPrime[MAX];
void sieve(int n) 
{
    for(int i = 0; i <= n;++i) 
    {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= n; ++i) 
    {
         if(isPrime[i] == true) 
         {
             for(int j = i * i; j <= n ;j += i)
                 isPrime[j] = false;
        }
    }
}
bool cmp(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.first > b.first);
}
const ll N = 2e5 + 5 ;
int main()
{
    sws;
    //clock_t clk;
    //clk = clock();
    //freopen("A.in", "r", stdin); 
    //freopen("A.out", "w", stdout);

 
    string str;
    cin >> str;
    int sz = str.size();
    rep(i,sz) if(str[i] == '9') {cout << "Yes"; return 0; }
    cout << "No";


    //clk = clock() - clk;
    //cout << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        char[][] map = new char[h + 2][w + 2];
        for (int i = 0; i < h; i++) {
            String s = sc.next();
            for (int j = 0; j < w; j++) {
                map[i + 1][j + 1] = s.charAt(j);
            }
        }
        int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
        int[] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
        for (int i = 1; i < h + 1; i++) {
            for (int j = 1; j < w + 1; j++) {
                if (map[i][j] == '#') {
                    continue;
                }
                int num = 0;
                for (int k = 0; k < 8; k++) {
                    if (map[i + dy[k]][j + dx[k]] == '#') {
                        num++;
                    }
                }
                map[i][j] = (char)('0' + num);
            }
        }
        for (int i = 1; i < h + 1; i++) {
            for (int j = 1; j < w + 1; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }
}


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

int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++){cin >> a[i];}
    int m[n];
    m[0] = 0;
    m[1] = a[0] * 2;
    for(int j=2;j<n;j++){
        m[j] = 2*a[j-1] - m[j-1];
    }
    int sub = a[n-1] - m[n-1]/2;
    for(int k=0;2*k<n-1;k++){
        cout << m[2*k]+sub << " " << m[2*k+1]-sub << " ";
    }

    cout << m[n-1]+sub << endl;
    return 0;
}

Measured memory_bytes: 2048
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll q, h, s, d, n;
	cin >> q >> h >> s >> d >> n;
	ll cost_per = 1e9;
	if(cost_per > q*4){
		cost_per = q*4;
	}
	if(cost_per > h*2){
		cost_per = h*2;
	}
	if(cost_per > s){
		cost_per = s;
	}
	ll ans;
	if(cost_per > d/2){
		if(n%2 == 0) ans = d * (n/2);
		else ans = d * (n/2) + cost_per;
	}
	else{
		ans = cost_per * n;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,mmx,avx,tune=native")
#include "bits/stdc++.h"
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
const int MOD=1000000007;
#define endl "\n"
#define fst first
#define snd second
const int UNDEF = -1;
const int INF=1<<30;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;typedef vector<ll> vll;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<vi> vvi;
#ifdef ONLINE_JUDGE
#define assert(...) /* nothing */
#endif
#define DEBUG_CAT
#ifdef DEBUG_CAT
#define dbg(...)   printf( __VA_ARGS__ )
#else 
#define dbg(...)   /****nothing****/
#endif
const int mn=(1e5)+4;


int cnt[mn];
int rev[mn];
void fail() {printf("-1\n"); exit(0);}
vi va,vb;
vi g[mn];
map<pii,pii> h;
bitset<mn> seen;
bool globok=true;
void dfs(int x, int p) {
	if (seen[x]) return;
	seen[x]=true;
	for (auto &y:g[x]) {
		dfs(y,x);
	}
	if (cnt[x]&1) {
		auto it=h.find(MP(p,x));
		if (it==h.end()) globok=false;
		int e=it->second.first;
		rev[e]^=1;
		cnt[x]^=1;
		cnt[p]^=1;
	}
	return;
}


int main(){
	int m;
	int n;
	scanf("%d",&n);
	scanf("%d",&m);
	va.resize(m-1+1);
	vb.resize(m-1+1);
	srand(clock());
	for(int i = 0 ; i <= m-1 ; i++){
		scanf("%d",&va[i]);
		scanf("%d",&vb[i]);
		int a=va[i],b=vb[i];
		cnt[va[i]]^=1;
		h[MP(a,b)]=MP(i,0);
		h[MP(b,a)]=MP(i,1);
		g[a].PB(b); g[b].PB(a);
	}
	if (m&1) fail();
	//for (int x=1;x<=n;x++) printf("%d: %d\n",x,cnt[x]);
	dfs(1,-1);
	if (!globok) fail();
	for (int x=1;x<=n;x++) if (cnt[x]&1) fail();
	for (int i=0;i<m;i++) {
		int a=va[i],b=vb[i];
		if (rev[i]) swap(a,b);
		printf("%d %d\n",a,b);
	}
	return 0;
}



Measured memory_bytes: 24064
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()

    c = collections.Counter(S)
    c2 = collections.Counter()
    ans = min(c['.'], c['#'])

    for i in range(N):
        c2[S[i]] += 1
        ans = min(ans, c2['#'] + c['.'] - c2['.'])

    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

using int64 = long long;

struct WeightedEdge {
  int from, to;
  int64 weight;
};

template<class T> inline bool UpdateMin(T& a, T b) {
  if (a > b) { a = b; return 1; } return 0;
}

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

  int n, m;
  int64 p;
  cin >> n >> m >> p;

  vector<vector<WeightedEdge>> graph(n);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    graph[a].push_back(WeightedEdge{a, b, p - c});
  }

  vector<int64> distances(n, INT64_MAX);
  distances[0] = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int v = 0; v < n; v++) {
      for (const auto& e : graph[v]) {
        if (distances[e.from] == INT64_MAX) continue;
        UpdateMin(distances[e.to], distances[e.from] + e.weight);
      }
    }
  }
  int64 ans = distances[n - 1];

  for (int i = 0; i < 2 * n; i++) {
    for (int v = 0; v < n; v++) {
      for (const auto& e : graph[v]) {
        if (distances[e.from] == INT64_MAX) continue;
        if (distances[e.to] == INT64_MIN) continue;
        if (distances[e.from] == INT64_MIN) distances[e.to] = INT64_MIN;
        else if (UpdateMin(distances[e.to], distances[e.from] + e.weight)) {
          distances[e.to] = INT64_MIN;
        }
      }
    }
  }

  if (distances[n - 1] < ans) {
    cout << -1 << endl;
  } else {
    cout << max(-distances[n - 1], 0LL) << endl;
  }
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
using namespace std;
string s;
int main()
{
	int ans = 0;
	int i = 0;
	cin >> s;

	if (s[0] == 'W')
	{
			for (; s[i] != 'B'&&i<s.size(); i++);
			while (i<s.size())
			{
				for (; s[i] == s[i + 1];i++);
				ans++;
				i++;
			}
	}
	else
	{
		for (; s[i] != 'W'&&i<s.size(); i++);
		while (i<s.size())
		{
			for (; s[i] == s[i + 1]; i++);
			ans++;
			i++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<vector<int> > G(n, vector<int>(n,0));
    rep(i,n){
        int u,k;
        cin >> u >> k;
        u--;
        rep(i,k){
            int v;
            cin >> v;
            v--;
            G[u][v] = 1;
        }
    }
    queue<int> q;
    vector<int> d(n,-1);
    d[0] = 0;
    q.push(0);
    while(!q.empty()){
        int p = q.front();
        q.pop();
        rep(i,n){
            if(G[p][i] == 1 && d[i] == -1){
                //cout << G[p][i] << " " << d[i] << endl;
                q.push(i);
                d[i] = d[p]+1;
                //cout << d[i] << endl;
            }
        }
    }
    rep(i,n){
        cout << i+1 << " " << d[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
#include<tuple>
using namespace std;
#define ll long long
#define P pair<double, int>
int main(){
  int xs, ys, xt, yt;
  int n;
  int x[1002], y[1002], r[1002];
  vector< vector<P> > edge(1002);
  bool used[1002] = {};
  double dst[1002] ={};
  priority_queue<P, vector<P>, greater<P> > q;
  cin >> xs >> ys >> xt >> yt >> n;
  for(int i=1;i<=n;i++)
    cin >> x[i] >> y[i] >> r[i];
  x[0] = xs;
  y[0] = ys;
  r[0] = 0;
  x[n+1] = xt;
  y[n+1] = yt;
  r[n+1] = 0;
  for(int i=0;i<=n;i++)
    for(int j=1;j<=n+1;j++){
      if(i==j) continue;
      edge[i].push_back(P(max(sqrt(pow(x[j]-x[i], 2) + pow(y[j]-y[i], 2)) - (r[i] + r[j]), 0.0), j));
    }
  for(int i=0;i<edge[0].size();i++){
    q.push(edge[0][i]);
  }
  used[0] = true;
  int target;
  double distance;
  while(!q.empty()){
    tie(distance, target) = q.top();q.pop();
    if(used[target]) continue;
    used[target] = true;
    dst[target] = distance;
    if(target == n+1) break;
    for(int i=0;i<edge[target].size();i++){
      if(used[edge[target][i].second]) continue;
      int tar;
      double dis;
      tie(dis, tar) = edge[target][i];
      q.push(P(dis + distance, tar));
    }
  }
  cout << setprecision(12) << dst[target] << endl;
}

Measured memory_bytes: 26348
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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; }

ll pmod(ll n, ll p) {
	ll m = n % MOD;
	if (p == 0) return 1;
	ll rtn = pmod((m * m) % MOD, p / 2) % MOD;
	if (p % 2 == 1) rtn = rtn * m % MOD;
	return rtn;
}

ll modinv(ll n) {
	return pmod(n, MOD - 2);
}

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

	//0～Nまであらかじめ結果を求めておく
	vi res(N);
	rep(i, N) res[abs(i - (N - 1 - i))]++;

	vi A(N);
	rep(i, N)
	{
		int a;
		cin >> a;
		A[a]++;
	}

	rep(i, N)
	{
		if (A[i] != res[i])
		{
			cout << 0 << endl;
			return 0;
		}
	}

	cout << pmod(2, N / 2) << endl; 

	return 0;
}

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

using namespace std;



int main() {
    ios::sync_with_stdio(false);
    
    int n, W;
    cin >> n >> W;
    
    const int64_t INF = 4e18;
    
    vector<long long> D(100005, INF);
    D[0] = 0;
    
    for (int i = 0; i < n; ++i) {
        int w, v;
        cin >> w >> v;
        
        for (int j = 100000 - v; j >= 0; --j) {
            D[j + v] = min(D[j + v], D[j] + w);
        }
    }
    
    for (int i = 100000; i >= 0; --i) {
        if (D[i] <= W) {
            cout << i;
            break;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807/2;
const int MAX=10000;
const ll tMOD=(ll)1e9+7;
const ll MOD=(ll)998244353;
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;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


string s;
int n;
int main(){
	cin>>n>>s;
	if(n%2!=0){
		cout<<"No"<<endl;
		return 0;
	}
	if(s.substr(0,n/2)==s.substr(n/2,n/2)){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fori(i,a,b) for(int i=a;i<(int)(b);i++)
#define repi(i,n) fori(i,0,n)
const ll MOD = 1000000007;

void solve(){
    int h,w;
    cin>>h>>w;
    string a[h];
    repi(i,h)cin>>a[i];
    ll dp[h][w];
    repi(i,h)repi(j,w)dp[i][j]=0;
    dp[0][0]=1;
    repi(i,h)repi(j,w){
        if(a[i][j]=='#')continue;
        if(i<h-1&&a[i+1][j]=='.')dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
        if(j<w-1&&a[i][j+1]=='.')dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
    }
    cout<<dp[h-1][w-1]<<endl;
}

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


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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e5 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);



int n , m;


void solve(int testCase){

    int k; scanf("%d" , &k);
    scanf("%d %d" , &n , &m);

    for(int i = n ; i <= m ; i ++) {
            if(i % k == 0) {
                    printf("OK\n");
                    return;
            }
    }

    printf("NG\n");

}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 3652
#!/usr/bin/env python
# -*- coding: utf-8 -*-

IN = 'sample-1.in'  # sample case for local test
def local_test():
    try:
        from pcm.utils import set_stdin
        import sys
        if len(sys.argv) == 1:
            set_stdin(os.path.dirname(__file__) + '/test/' + IN)
    except:
        pass


import sys
import os
import time
import re
from pydoc import help
import string
import math
import numpy as np
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    CS = [0]*(N+1)

    for n in range(N):
        if n >= 1:
            CS[n+1] = CS[n] + A[n]
        else:
            CS[n+1] = A[n]

    res = 0
    for v in Counter(CS).values():
        if v >= 2:
            res += v*(v-1)//2

    print(res)
    sys.stdout.flush()
        

if __name__ == "__main__":
    local_test()
    solve()


Measured memory_bytes: 52864
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>>
#include <functional>
#include <string>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

ll func(ll b, ll n) {
	if (n < b)
		return n;
	return func(b, n/b) + n%b;
}

signed main() {

	string str;

	cin >> str;
	reverse(ALL(str));

	string ss[4] = {"maerd","remaerd","esare","resare"};
	int pos = 0;
	while (pos < str.length()) {
		bool f = 0;
		REP(i, 4) {
			if (ss[i] == str.substr(pos, ss[i].length())) {
				pos += ss[i].length();
				f = 1;
				break;
			}
		}
		if (!f) {
			printf("NO\n");
			return 0;
		}

	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 512
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

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

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> veci;
typedef vector<long long> vecl;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
	if (y == 0) 
		return 1; 
	ll p = power(x, y/2) % MOD; 
	p = (p * p) % MOD; 
  
	return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work
ll N;
vector<vector<ll>> ADJ;
vector<ll> subtree_size;
vector<ll> ans;

void dfs_1(ll u,ll p=-1)
{
	subtree_size[u]=1;
	for(auto v:ADJ[u])
	{
		if(v!=p)
		{
			dfs_1(v,u);
			subtree_size[u]+=subtree_size[v];
		}
	}
	ans[1]=(ans[1]*modInverse(subtree_size[u]))%MOD;
}
void dfs_2(ll u,ll p=-1)
{
	for(auto v:ADJ[u])
	{
		if(v!=p)
		{
			ans[v]=ans[u];
			ans[v]=(ans[v]*subtree_size[v])%MOD;
			ans[v]=(ans[v]*modInverse(N-subtree_size[v]))%MOD;
			dfs_2(v,u);
		}
	}
}

int main()
{
	#ifndef ONLINE_JUDGE
	if (fopen("INPUT.txt", "r"))
	{
		freopen ("INPUT.txt" , "r" , stdin);
		//freopen ("OUTPUT.txt" , "w" , stdout);
	}
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	clock_t clk;
	clk = clock();
//-----------------------------------------------------------------------------------------------------------//

	READ(N);
	ADJ.resize(N+1);
	subtree_size.resize(N+1,0);
	ans.resize(N+1,1);
	FORI(i,1,N+1)
	{
		ans[1]=(ans[1]*i)%MOD;
	}
	FORI(i,0,N-1)
	{
		READV(u);
		READV(v);
		ADJ[u].pb(v);
		ADJ[v].pb(u);
	}
	dfs_1(1);
	dfs_2(1);
	FORI(i,1,N+1)
	{
		cout<<ans[i]<<endl;
	}

//-----------------------------------------------------------------------------------------------------------//


	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

	return 0;
}

Measured memory_bytes: 17904