akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

# dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1 = [[0] * (S + 1) for _ in range(N + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[t][r] += dp1[t - 1][r] * 2
        dp1[t][r] += dp1[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp1[t][r] %= MOD

dp2 = [[0] * (S + 1) for _ in range(N + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[t][r] += dp2[t - 1][r]
        dp2[t][r] += dp2[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp2[t][r] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[N][r]

ans = 3 ** N - 3 * cnt + (3 * (dp2[N][S // 2]) if S % 2 == 0 else 0)
ans %= MOD

print(ans)


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

#define err(A) cout << #A << " = " << (A) << endl

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

int main()
{
    int n;
    cin >> n;
    if (n % 2 == 0)
        cout << n / 2 - 1;
    else
        cout << n / 2;
}

Measured memory_bytes: 256
<?php
while(true){
  $line = trim(fgets(STDIN));
  if($line === ""){
    break;
  }
  $words = explode(" ",$line);
  $wordsInfo = [];
  foreach($words as $word){
    if(array_key_exists($word,$wordsInfo)){
      $wordsInfo[$word]++;
    }else{
      $wordsInfo[$word] = 1;
    }
  }

  $maxCount = 0;
  $maxCountWord = "";
  $maxLengthWord = "";

  foreach($words as $word){
    if(strlen($maxLengthWord) < strlen($word)){
      $maxLengthWord = $word;
    }

    if($maxCount < $wordsInfo[$word]){
      $maxCount = $wordsInfo[$word];
      $maxCountWord = $word;
    }
  }

  echo $maxCountWord . " " . $maxLengthWord . PHP_EOL;
}

Measured memory_bytes: 15496
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    vector<vector<int>> path(4);
    rep(i,3){
        int a,b; cin>>a>>b;
        a--; b--;
        path[a].push_back(b);
        path[b].push_back(a);
    }
    rep(i,4){
        if(path[i].size()>=3){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
}


Measured memory_bytes: 3564
#include <stdio.h>
#include <math.h>

int main(){
    long n;
    scanf("%ld", &n);
    long j = (long) sqrt(n); 
    long a = 0;
    long i;
    for (i = 0; i < j; i++){
        if (n % (j - i) == 0){
            a = n / (j - i);
            break;
        }
    }

    printf("%ld", j-i+a-2);

    return 0;
}

Measured memory_bytes: 128
def merge(a, left, mid, right)
	n1 = mid - left
	n2 = right - mid
	
	l = a[left..left+n1-1]
	r = a[mid..mid+n2-1]
	l[n1] = 10 ** 9
	r[n2] = 10 ** 9

	i = 0
	j = 0
	
	for k in left..right-1
		if l[i] < r[j]
			a[k] = l[i]
			i += 1
		else
			a[k] = r[j]
			j += 1
			
			$cnt += l.length - i - 1
		end
	end
end

def merge_sort(a, left, right)
	if left + 1 < right
		mid = (left + right) / 2
		merge_sort(a, left, mid)
		merge_sort(a, mid, right)
		merge(a, left, mid, right)
	end
end

n = gets.to_i
a = gets.split(" ").map(&:to_i)
$cnt = 0

merge_sort(a, 0, n)

puts $cnt

Measured memory_bytes: 33212
using System;

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

            Calc c = new Calc();
            int sum = c.Sum(N);
            if ((sum >= 1 && sum <= Math.Pow(10, 8)) && N % sum == 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {

                Console.WriteLine("No");
            }
        }
    }
    class Calc
    {
        public int Sum(int n)
        {
            int sum = 0;
            while (n > 0)
            {
                sum += n % 10;
                n /= 10;
            }
            return sum;
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,temp;
	list<int> l;
	while(~scanf("%d",&n)){
		l.clear();
		for(int i=0;i<n;++i){
			scanf("%d",&temp);
			if(i&1){
				l.push_front(temp);
			}else{
				l.push_back(temp);
			}
		}
		if(n&1){
			list<int>::reverse_iterator a,b;
			a=l.rbegin(),b=l.rend();
			printf("%d",*a);
			++a;
			for(;a!=b;++a){
				printf(" %d",*a);
			}
		}else{
			list<int>::iterator a,b;
			a=l.begin(),b=l.end();
			printf("%d",*a);
			++a;
			for(;a!=b;++a){
				printf(" %d",*a);
			}
		}
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 8448
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


int n,m;
int* edge[100001];
int edlen[100001]={};
int ans[100001]={};

int que[100001];
int qmax = 100001;
int qs=0,ql=0;

void allc(int a,int b){
  edge[a] = realloc(edge[a],sizeof(int)*(edlen[a]+1));
  if(edge[a]==NULL) exit(2);
  edge[a][edlen[a]++] = b;
}

void enq(int a){
  que[ql]=a;
  ql = (ql+1)%qmax;
}

int deq(void){
  int tmp = que[qs];
  que[qs] = 0;
  qs = (qs+1)%qmax;
  return tmp;
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    allc(a,b);
    allc(b,a);}

  enq(1);
  while(1){
    int tmp = deq();
    if(tmp==0) break;
    for(int i=0;i<edlen[tmp];i++){
      int nexte = edge[tmp][i];
      if(ans[nexte]==0){
	enq(nexte);
	ans[nexte] = tmp;}
    }
  }
  int flag=1;
  for(int i=2;i<=n;i++){
    if(ans[i]==0){
      flag=0; break;}}
  if(flag){
    printf("Yes\n");
    for(int i=2;i<=n;i++){
      printf("%d\n",ans[i]);}}
  else{
    printf("No\n");}
  
  return 0;
}


Measured memory_bytes: 8436
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int INF = 2e6;
ll MOD = 1e9 + 7;
 
int main(){
    string s; int k;
    cin >> k >> s;
    int sz = s.size();
    if(sz <= k) cout << s << endl;
    else {
        for(int i = 0;i < k;i++){
            cout << s[i];
        }cout << "..." << endl;
    }
}

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

/***typededfs***/
typedef long long ll;
typedef long double ldb;

/***defines***/
#define M1 1000000007
#define M2 998244353
#define F first
#define S second
#define pb push_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forz(i,n) for(int i=0;i<(n);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define rforz(i,n) for(int i=(n-1);i>=0;i--)
#define rfore(i,a,b) for(int i=(a);i>=(b);i--)
#define test int T; cin>>T; while(T--)


int main(){ 
      FASTIO;
      int n;
      cin>>n;
      int a[n][3];
      forz(i,n){
            forz(j,3){
                  cin>>a[i][j];
            }
      }
      int dp[n][3]{};
      dp[0][0] = a[0][0]; dp[0][1] = a[0][1] ; dp[0][2] = a[0][2];
      fore(i,1,n-1){
            dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i][0];
            dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + a[i][1];
            dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + a[i][2];
      }
      cout<<max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
      
}

Measured memory_bytes: 6008
sN = input()
K = int(input())
N = int(sN)


def run():
    dp = [[[0] * 4 for _ in range(2)] for _ in range(len(sN) + 1)]
    dp[0][0][0] = 1

    for i in range(len(sN)):
        for j in range(2):
            # j=0 : 現在の桁まで数字が同じ
            # j=1 : すでに小さい数値とわかっている

            # limには次の桁の数字の最大値を代入する
            lim = 9 if j == 1 else (ord(sN[i]) - ord('0'))
            for k in range(lim + 1):
                for l in range(4):
                    nl = l + int(k > 0)
                    if nl >= 4: continue
                    dp[i + 1][k < lim or j == 1][nl] += dp[i][j][l]

        # print(dp)

    print(dp[len(sN)][0][K] + dp[len(sN)][1][K])


if __name__ == '__main__':
    run()


Measured memory_bytes: 9112
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=998244353;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
vector<ll> pw2(51,1);vector<ll> pw10(19,1);
ll fac[500001],finv[500001],inv[500001];
 
void table() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(ll i=2;i<500001;i++){
        fac[i]= fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

ll dev(long long a,long long b){
    return (a*inv[b])%MOD;
}

ll comb(ll n, ll k){
    if(n<k) return 0;
    if(n<0 || k<0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
ll mod_pow(ll x,ll n,ll mod){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main(){
    table();
    {rep1(i,50) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N,M,K; cin>>N>>M>>K;
    ll ans=0;
    rep(i,K+1){
        ans+=(((M*comb(N-1,i))%MOD)*mod_pow(M-1,N-i-1,MOD))%MOD;
        ans%=MOD;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 15332
package main

import (
	"fmt"
)

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {
	var s string
	var red, blue, ans int
	fmt.Scan(&s)
	for _, num := range s {
		if num == '0' {
			red++
		} else {
			blue++
		}
	}
	ans = min(red, blue) * 2
	fmt.Println(ans)
}

Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<string>
#define MAX 200
using namespace std;
class stack{
  public:
    stack();
    void push(int v);
    bool isFull();
    bool isEmpty();
    int pop();

  private:
    vector<int> values=vector<int>(MAX);
    int top=0;
};

stack::stack(){
}

void stack::push(int v){
  if (isFull()!=true){
    values[top+1]=v;
    top++;
  }
}

bool stack::isFull(){
  return top>=MAX-1;
}

bool stack::isEmpty(){
  return top==0;
}

int stack::pop(){
  if(isEmpty()!=true){
    top--;
    return values[top+1];
  }
}

int main(int argc,char* argv[]){
  int temp;
  string s;
  stack data;
  while(cin >> s){
    if(s=="*") data.push(data.pop()*data.pop());
    else if(s=="+") data.push(data.pop()+data.pop());
    else if(s=="-"){
      temp = -data.pop();
      data.push(temp+data.pop());
    }
    else data.push(stoi(s));
    
  }
  cout << data.pop() << endl;
}

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

using ll = long long;
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

#define INF 1e9

int main(){
  ll H, W;
  cin >> H >> W;
  if(H == 1 || W == 1){
    cout << 1 << endl;
    return 0;
  }
  ll odd = ((W+1)/2)*((H+1)/2);
  ll even = (W/2)*(H/2);

  cout << odd + even << endl;

  return 0;
}


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

using namespace std;

struct RollingHash
{
  typedef long long int_type;
  typedef pair<int_type, int_type> hash_type;

  int_type base, mod[2];

  vector<int_type> hashed[2], power[2];

  RollingHash(){ base = 9973LL, mod[0] = 999999937LL, mod[1] = 1000000007LL; }

  void init(const string& s)
  {
    int sz = s.size();
    
    for(int i = 0; i < 2; i++){
      hashed[i].assign(sz + 1, 0); 
      power[i].assign(sz + 1, 0);
      
      hashed[i][0] = 0;
      power[i][0] = 1;
      for(int j = 0; j < sz; j++){
	power[i][j+1] = power[i][j] * base % mod[i];
	hashed[i][j+1] = (hashed[i][j]+s[j])*base % mod[i];
      }
    }
  }

  hash_type get(int l, int r)
  {
    int_type hash1 = ((hashed[0][r] - hashed[0][l]*power[0][r-l]) % mod[0] + mod[0]) % mod[0];
    int_type hash2 = ((hashed[1][r] - hashed[1][l]*power[1][r-l]) % mod[1] + mod[1]) % mod[1];
    return hash_type(hash1, hash2);
  }
  
  hash_type concat(hash_type hash1, hash_type hash2, int hash2_len)
  {
    return hash_type((hash1.first*power[0][hash2_len] + hash2.first) % mod[0], 
		     (hash1.second*power[1][hash2_len] + hash2.second) % mod[1]);
  }
};

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

  RollingHash rollhash[2];
  rollhash[0].init(T);
  rollhash[1].init(P);

  for(int i = 0; i <= (int)(T.size()-P.size()); i++){
    if(rollhash[0].get(i, i+P.size()) == rollhash[1].get(0, P.size())) cout << i << endl;
  }

  return 0;
}

Measured memory_bytes: 1228
'use strict'

function main(s) {

  s = s.split('\n');
  const n = Number(s[0].split(' ')[0]);
  const x = Number(s[0].split(' ')[1]);
  const donuts = s.slice(1, -1).map(el => Number(el));

  donuts.sort((a, b) => a - b);
  const sum = donuts.reduce((a, b) => a + b);
  const ans = Math.floor((x - sum) / donuts[0]) + donuts.length;

  console.log(ans);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7628
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a;
int b, c;
int main() {
	cin >> a;
	b=a/100;
	c=a%10;
	if(b==c) cout << "Yes";
	else cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <iomanip>
#include <bitset>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

const int N = 1000 + 7;

vector <int> g[N];
vector <int> rg[N];
int comp[N];
bool u[N];

vector <int> t;

void zhfs(int v)
{
    u[v] = true;
    for (int to : g[v])
    {
        if (!u[to])
        {
            zhfs(to);
        }
    }
    t.push_back(v);
}

int sz = 0;

void rzhfs(int v)
{
    comp[v] = sz;
    u[v] = true;
    for (int to : rg[v])
    {
        if (!u[to])
        {
            rzhfs(to);
        }
    }
}

void dfs(int v)
{
    u[v] = true;
    for (int to : g[v])
    {
        if (!u[to])
        {
            dfs(to);
        }
    }
}

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    int n, m;
    scanf("%d%d", &n, &m);
    vector <pair <int, int> > e;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        e.push_back({a, b});
        g[a].push_back(b);
        rg[b].push_back(a);
    }
    for (int i = 0; i < n; i++)
    {
        if (!u[i])
        {
            zhfs(i);
        }
    }
    reverse(t.begin(), t.end());
    for (int v : t) u[v] = 0;
    for (int v : t)
    {
        if (!u[v])
        {
            sz++;
            rzhfs(v);
        }
    }
    map <pair <int, int>, int> ans;
    for (int v = 0; v < n; v++)
    {
        for (int j = 0; j < n; j++)
        {
            u[j] = 0;
        }
        u[v] = true;
        for (int to : g[v])
        {
            if (u[to])
            {
                ans[{v, to}] = 1;
            }
            dfs(to);
        }
        reverse(g[v].begin(), g[v].end());
        for (int j = 0; j < n; j++)
        {
            u[j] = 0;
        }
        u[v] = true;
        for (int to : g[v])
        {
            if (u[to])
            {
                ans[{v, to}] = 1;
            }
            dfs(to);
        }
    }
    for (auto c : e)
    {
        if (comp[c.first] != comp[c.second]) ans[c] ^= 1;
        if (ans[c])
        {
            cout << "same\n";
        }
        else
        {
            cout << "diff\n";
        }
    }
}


Measured memory_bytes: 19184
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(void)
{
	int N = 0;
	int counter = 0;

	std::cin >> N;

	string str = std::to_string(N);
	for (int i = 0; i < 3; i++)
	{
		
		if(str[i] != str[i + 1] && counter < 2)
		{
			counter = 0;
		}
		else
		{
			counter++;
		}
		
	}


	if (counter >= 2)
	{
		std::cout << "Yes";
	}


	else {
		std::cout << "No";
	}

}



Measured memory_bytes: 256
from bisect import bisect_left, bisect_right

n = int(input())
stick = list(map(int, input().split()))
stick.sort()

count = 0
for i in range(n - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        l = bisect_right(stick, stick[i] - stick[j])
        r = bisect_left(stick, stick[i] + stick[j]) # [l, r) が範囲
        if j <= l:
            break
        count += min(r, j) - l
print(count)



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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, k, a, cnt[31] = {}, ans = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> a;
            // cout << a[i][k[i]];
            ++cnt[a];
            // cout << cnt[a] << endl;
        }
    }
    for (int i = 0; i <= m; i++) {
        // cout << cnt[i] << endl;
        if (cnt[i] == n) {
            ans++;
        }
    }
    cout << ans << 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++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll t1,t2;cin >>t1 >> t2;
  ll a1, a2,b1,b2;cin >> a1 >> a2 >> b1 >> b2;
  ll adis =a1*t1+a2*t2; 
  ll bdis =b1*t1+b2*t2;
  if(adis==bdis){
      cout << "infinity" << endl;
      return 0;
  }
  if(adis<bdis){
      swap(a1,b1);
      swap(a2,b2);
      swap(adis,bdis);
  }
  if(a1>b1){
      cout << 0 << endl;
      return 0;
  }
  ll disdif1 = b1*t1-a1*t1;
  ll disdif2 = adis-bdis;
  ll ans = disdif1/disdif2  * 2+ 1 ;
  if(disdif1%disdif2==0)ans--;
  cout << ans << endl;
}

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

int main()
{
	int n, l;

	scanf("%d%d", &n, &l);

	int mi = 1000000;
	int sum = 0;

	for(int i = 0; i < n; i++) {
		int x = i + 1 + l - 1;
		sum += x;
		if(abs(mi) > abs(x)) {
			mi = x;
		}
	}

	printf("%d\n", sum - mi);

	return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
 int x,y,z,a=0;
 cin>>x>>y>>z;
 for(int i=0;i<z;i++)
 {
     if(y-x>=0){

      a=a+1;
     y=y-x;}
 }
 cout<<a;
 return 0;
}


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

typedef long long ll;
const ll MOD = (1e+9) + 7;

int n;
int t[100000], a[100000];

int main()
{

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

  ll ans = 1;
  if(t[n-1] != a[0]) ans = 0;
  for(int i = 1; i < n-1; i++){
    if(t[i] == t[i-1] && a[i] == a[i+1]){
      ans *= min(t[i], a[i]);
      ans %= MOD;
    }
    else if(t[i] > t[i-1] && a[i] == a[i+1] && t[i] > a[i]) ans = 0;
    else if(t[i] == t[i-1] && a[i] == a[i+1] && t[i] < a[i]) ans = 0;
    else if(t[i] > t[i-1] && a[i] > a[i+1] && a[i] != t[i]) ans = 0;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

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

    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> X(N);
    REP(i, N) cin >> X[i];
    vector<ll> dp(N);
    REP(i, N-1) {
        dp[i+1] = dp[i] + min(B, A*(X[i+1] - X[i]));
    }
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1792
package main 

import (
  "fmt"
//  "sort"
)

func main() {
  var s []byte
  fmt.Scan(&s)
  
  n := len(s)
  k, k2, k3 := true, true, true
  for i := 0; i < n; i++{
    if s[i] != s[n-1-i] {
      k = false
    }
  }
  
  for i := 0; i < (n-1)/2; i++ {
    if s[i] != s[(n-1)/2-1-i] {
      k2 = false
    }
  }
  
  for i := (n+3)/2; i < n; i++ {
    if s[i] != s[n-1-i] {
      k3 = false
    }
  }

  if k && k2 && k3 {
    fmt.Print("Yes")
  } else {
    fmt.Print("No")
  }
}

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

 int main()
 {
     int a,b,i;

     cin>>a>>b;

     if(a>b){
        for(i=1;i<=a;i++){
            cout<<b;
        }
        cout<<endl;
     }
     else if(a<b){
        for(i=1;i<=b;i++){
            cout<<a;
        }
        cout<<endl;
     }
     else if(a==b){
        for(i=1;i<=b;i++){
            cout<<b;
        }
        cout<<endl;
     }

     return 0;
 }


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)
const ll INF = 10010001010;
const int inf = 1000034000;
typedef vector<ll> vecl;
typedef vector<int> veci;
typedef tuple<string, int, int> TUP;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed << setprecision(15);
    int N,M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M;i++)
    {
        int a,b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    queue<ll> que;
    vector<ll> seen(N, -1);
    que.push(0);
    seen[0] = 0;
    while (!que.empty())
    {
        int now = que.front();
        que.pop();
        for(int next : G[now]){
            if(seen[next] == -1){
                //cout << now << ": " << next << endl;
                seen[next] = now;
                que.push(next);
            }
        }
    }
    cout << "Yes" << endl;
    for (int i = 1; i < N; i++)
    {
        cout << seen[i]+1 << endl;
    }
}


Measured memory_bytes: 10944
#include <iostream>

using namespace std;

const int MAX = 500000;
const int INF = 2147483647;

int L[MAX/2+2];
int R[MAX/2+2];
int c = 0;

void merge(int A[], int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  for (int i = 0; i < n1; ++i)
    L[i] = A[left + i];
  for (int i = 0; i < n2; ++i)
    R[i] = A[mid + i];
  L[n1] = R[n2] = INF;
  int i = 0, j = 0;
  for (int k = left; k < right; ++k) {
    if (L[i] <= R[j]) {
      A[k] = L[i];
      ++i;
    }
    else {
      A[k] = R[j];
      ++j;
    }
    ++c;
  }
}

void mergeSort(int A[], int left, int right) {
  if (left + 1 < right) {
    int mid = left + (right - left) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);
  int n;
  int S[MAX] = {};

  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> S[i];

  mergeSort(S, 0, n);

  for (int i = 0; i < n; ++i) {
    cout << S[i];
    if (i == n - 1) cout << "\n";
    else cout << " ";
  }
  cout << c << "\n";
}



Measured memory_bytes: 7008
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
from queue import Queue
def bfs(field, sy, sx, wall, dir):
    h = len(field)
    w = len(field[0])
    dp = [[-1 for _j in range(w)] for _i in range(h)]
    q = Queue()

    dp[sy][sx] = 0
    q.put((sy, sx))
    
    dy = [1, -1, 0, 0, 1, 1, -1, -1]
    dx = [0, 0, 1, -1, 1, -1, 1, -1]
    def isin(x,y): return 0 <= y and y < h and 0 <= x and x < w
    
    while not q.empty():
        y, x = q.get()
        for k in range(dir):
            ny,nx = y+dy[k],x+dx[k]
            if not isin(nx, ny) or field[ny][nx] == wall:
                continue
            elif dp[ny][nx] != -1:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.put((ny,nx))
        
    return dp
    
# END CUT HERE

def ABC088_D():
    h, w = mi()
    s = [['' for _j in range(w)] for _i in range(h)]
    for i in range(h):
        s[i] = li()
    dp = bfs(s, 0, 0, '#', 4)
    if dp[h - 1][w - 1] < 0:
        print(-1)
    else:
        cnt = 0
        for i in range(h):
            for j in range(w):
                cnt += s[i][j] == '.'
        print(cnt - (dp[h - 1][w - 1] + 1))
# verified on 2019/06/13
# Pypy3:233ms https://atcoder.jp/contests/abc088/submissions/5898207
# https://atcoder.jp/contests/abc088/tasks/abc088_d

if __name__ == '__main__':
    ABC088_D()

Measured memory_bytes: 4052
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
using namespace std;
int main(){
	
	int l[10];
	int v1,v2;
	int sum;
	char comma;
	double h,d;
	int ans;
	
	while(cin>>l[0]){
		
		sum=l[0];
		
		for(int i=1;i<10;i++){
			cin>>comma>>l[i];
			sum+=l[i];
		}
		cin>>comma>>v1>>comma>>v2;
		
		h=double(sum)/(v1+v2);
		d=double(v1)*h;
		
		for(int i=0;i<10;i++){
			d-=l[i];
			if(d<=0){
				ans=i+1;
				break;
			}
		}
		cout<<ans<<endl;
		
	}
	
}

Measured memory_bytes: 1160
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def lcm(a, b):
    return a * b / fractions.gcd(a, b)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret


class UnionFind:
    def __init__(self, n):
        self.sz = [-1 for i in range(n)]

    # 検索
    def find(self, x):
        if self.sz[x] < 0:
            return x
        else:
            self.sz[x] = self.find(self.sz[x])
            return self.sz[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x, y = y, x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれている集合のサイズを求める
    def size(self, x):
        return -self.sz[self.find(x)]


def main():
    h, n = map(int, input().split())
    a = list(map(int, input().split()))
    if sum(a) >= h:
        print("Yes")
    else:
        print("No")



            


    




    


if __name__ == '__main__':
    main()


Measured memory_bytes: 15992
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
// using Graph = vector<vector<int>>;
const ll mod = 1e9 + 7;
const ll INF = 1e9;
const ll LINF = 1LL << 60;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ///////////////////////////////////////
  int n;
  cin >> n;
  n %= 10;
  if (n == 3)
    cout << "bon" << endl;
  else if (n == 0 || n == 1 || n == 6 || n == 8)
    cout << "pon" << endl;
  else
    cout << "hon" << endl;
  return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define repr(i, n) for(int i = n;i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define MOD 1000000007

typedef long long ll;

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

    int n,a,b = 0;
    cin >> n;

    int c = n;

    rep(i,9){
        a = c % 10;
        b += a;
        c = c / 10;
    }

    if(n % b == 0){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
    
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  int k;
  cin >> k;
  ll ans = 0;
  for (int a = 1; a <= k; a++) {
    for (int b = 1; b <= k; b++) {
      for (int c = 1; c <= k; c++) {
        ans += gcd(a, gcd(b, c));
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3644
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    N=int(input())
    S=str(input())
    R=[]
    G=[]
    B=[]
    for i in range(N):
        if S[i]=='R':
            R.append(i)
        if S[i]=='G':
            G.append(i)
        if S[i]=='B':
            B.append(i)
    lr=len(R)
    lg=len(G)
    ans=lr*lg*(N-lr-lg)

    cnt=0
    for i in range(N):
        for j in range(i+1,N):
            k=2*j-i
            if k>=N:
                continue
            else:
                if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                    cnt+=1
    print(ans-cnt)




resolve()

Measured memory_bytes: 68400
"use strict";

const main = arg => {
    const inputList = arg.trim().split("\n");
    const N = parseInt(inputList[0].split(" ")[0]);
    const K = parseInt(inputList[0].split(" ")[1]);
    let ALightList = inputList[1].split(" ").map(ele => parseInt(ele));

    for (let i = 0; i < K; i++) {
        const imos = Array(ALightList.length).fill(0);

        for (let j = 0; j < ALightList.length; j++) {
            let minus = j - ALightList[j];
            let plus = j + ALightList[j] + 1;
            if (minus < 0) {
                minus = 0;
            }
            imos[minus]++;
            imos[plus]--;
        }
        imos.length = ALightList.length;

        for (let k = 1; k < imos.length; k++) {
            imos[k] += imos[k - 1]
        }

        if (ALightList.every((ele, idx) => ele == imos[idx])) {
            break;
        }

        ALightList = imos;
    }
    console.log(ALightList.join(" "))
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 117592
//
// Created by Hideaki Imamura on 2020-03-28.
//
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

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

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
const ll mod = 1000000007;

ll fact[400000];
ll invfact[400000];

inline ll take_mod(ll a) {
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b) {
    return take_mod(a + b);
}

inline ll sub(ll a, ll b) {
    return take_mod(a - b);
}

inline ll mul(ll a, ll b) {
    return take_mod(a * b);
}

inline ll mod_pow(ll x, ll n) {
    ll res = 1LL;
    while (n > 0) {
        if (n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x) {
    return mod_pow(x, mod - 2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}


ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}

ll N;
vector<vector<ll>> G;
vector<ll> p, q, ret;
// p: value of the vertex
// q: the number of offsprings

void dfs1(int v, int par) {
    ll val = 1;
    for (auto u : G[v]) {
        if (u == par) continue;
        dfs1(u, v);
        q[v] = add(q[v], q[u]);
        val = mul(val, mul(comb(q[v], q[u]), p[u]));
    }
    q[v]++;
    p[v] = val;
}

void dfs2(int v, int par, ll par_pattern) {
    ret[v] = mul(p[v], mul(par_pattern, comb(N - 1, q[v] - 1)));
    for (auto u : G[v]) {
        if (u == par) continue;
        dfs2(u, v, mul(ret[v], mod_inv(mul(comb(N - 1, q[u]), p[u]))));
    }
}

int main() {
    make_fact(300000);
    make_invfact(300000);
    cin >> N;
    G.assign(N + 1, vector<ll>());
    for (int i = 0; i < N - 1; ++i) {
        ll a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    p.assign(N + 1, 0);
    q.assign(N + 1, 0);
    ret.assign(N + 1, 0);

    dfs1(1, 0);
    dfs2(1, 0, 1);
    for (int i = 1; i <= N; ++i) cout << ret[i] << endl;
    return 0;
}

Measured memory_bytes: 25584
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　redcoderになるためAtCoderを巡る旅をしてます。

　　　 　 ＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　 ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣/ヽ
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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

    int n;
    string s, t; cin >> n >> s >> t;
    int ans = n + n;
    for(int i = n - 1; i >= 0; i--) {
        if(s[i] == t[0]) {
            int flg = 1;
            for(int k = 1; i + k < n; k++) {
                if(s[i + k] != t[k]) flg = 0;
            }
            if(flg) ans = min(ans, n + i);
        }
    }
    cout << ans << endl;
}


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

int main(){
    int S;
    cin >> S;
    int a[4];
    a[0]=S/1000;
    a[1]=S/100-10*a[0];
    a[2]=S/10-100*a[0]-10*a[1];
    a[3]=S-1000*a[0]-100*a[1]-10*a[2];
    for(int i=0; i<3; i++){
        if( a[i]==a[i+1] ){
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;

    return 0;
}

Measured memory_bytes: 256
using System;

class Program {

    private static int Main() {
        var input = Console.ReadLine();
        var chars = input.ToCharArray();

        for( int i = 0; i < chars.Length; ++i ) {
            var c = chars[ i ];
            if( char.IsLower( c ) ) {
                chars[ i ] = char.ToUpper( c );
            } else if( char.IsUpper( c ) ) {
                chars[ i ] = char.ToLower( c );
            }
        }

        Console.WriteLine( chars );

        return 0;
    }

}

Measured memory_bytes: 5548
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    aa = LI()

    c = collections.defaultdict(int)
    c[0] = 1
    t = [0]
    r = 0
    for i in range(n):
        a = aa[i]
        tt = (t[-1] + a - 1) % k
        t.append(tt)
        if i >= k-1:
            # print("k", t[i-k+2],i-k+2)
            c[t[i-k+1]] -= 1
        r += c[tt]
        c[tt] += 1
        # print("ar", a,tt,r,sorted(c.items()), t)

    return r

print(main())





Measured memory_bytes: 40760
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long int lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(lo i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

lo n,m,b[li],a[li],k,flag,t,x,y,dizi[li];
lo cev=1;
string s;
vector<lo> v[li];

inline lo mul(lo xx,lo yy){
	return (xx%mod)*(yy%mod)%mod;
}

void dfs(lo node,lo ata,lo der){
	//~ cout<<cev<<endl;
	if(der==0)cev=mul(m,cev);
	else if(der==1){dizi[ata]++;cev=mul(m-dizi[ata],cev);}
	else{dizi[ata]++;cev=mul(cev,(m-dizi[ata]-1));}
	for(lo i=0;i<(lo)v[node].size();i++){
		lo go=v[node][i];
		if(go==ata)continue;
		dfs(go,node,der+1);
	}
}

int main(void){
	scanf("%lld %lld",&n,&m);
	for(lo i=1;i<n;i++){
		scanf("%lld %lld",&x,&y);
		v[x].pb(y);
		v[y].pb(x);
	}
	//~ for(lo i=2;i<=300000;i++)dizi[i]=1;
	dfs(1,0,0);
	printf("%lld\n",cev);
	return 0;
}


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

void solve(){
    int64_t n, ans = 0;
    cin >> n;
    for(int64_t i = 1; i <= n; i++){
        if(i % 3 != 0 && i % 5 != 0){
            ans += i;
        }
    }
    cout << ans << endl;
}

int main(){
    solve();
}


Measured memory_bytes: 3580
N = int(input())
S = input()


dp1 = [False]*10
dp2 = [[False]*10 for _ in range(10)]
dp3 = [[[False]*10 for _ in range(10)] for _ in range(10)]


for i in range(N):
    num = int(S[i])
    for j in range(10):
        for k in range(10):
            if dp1[j] == True and dp2[j][k] == True and dp3[j][k][num] == False:
                dp3[j][k][num] = True
        if dp1[j] == True and dp2[j][num] == False:
            dp2[j][num] = True
    if dp1[num] == False:
        dp1[num] = True

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            res += dp3[i][j][k] 
print(res)
                 



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

using namespace std;

typedef long long ll;
typedef vector<int> vi; 
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ini(a, i) memset(a, i, sizeof(a))
#define present(i, c) ((c).find(i) != (c).end())

#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define fora(i, a, b) for(int i = (a); i < (b); i++)
#define ford(i, n) for(int i = (n)-1; i >= 0; i--)

#define TRACE(x...) x
#define watch(x) TRACE(cerr << #x" = " << x << endl)
#define watch_all(x) TRACE(cerr << #x" = "; for(auto __i : x) cerr << __i << " "; cerr << endl)
	
#define INF 0x3F3F3F3F

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

// ============================
// Codigo Original
// ============================
/*int N, _W;
int W[101], V[101];
ll dp[101][100001];

void run_test() {
	cin >> N >> _W;
    for1(i, N) cin >> W[i] >> V[i];

    ini(dp, 0);
    for1(i, N) 
        for(int w = 1; w <= _W; w++)
			if(W[i] > w) dp[i][w] = dp[i-1][w];
			else dp[i][w] = max(dp[i-1][w], dp[i-1][w - W[i]] + V[i]);

    cout << dp[N][_W] << endl;
}*/

// ============================
// Otimizando Memoria
// Removendo uma dimensao da DP
// ============================
int N, _W;
int W[101], V[101];
ll dp[100001];

void run_test() {
	cin >> N >> _W;
    for1(i, N) cin >> W[i] >> V[i];

    ini(dp, 0);
    for1(i, N) 
        for(int w = _W; w >= W[i]; w--) 
            dp[w] = max(dp[w], dp[w - W[i]] + V[i]);

    cout << dp[_W] << endl;
}

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

ifstream infile;
clock_t start__;
void open_func();
void close_func();

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	open_func();
	//int t; cin >> t; while(t--) run_test();
	run_test();
	close_func();
	return 0;	
}

void open_func() {
	//infile = ifstream("input.in"); if(infile.good()) cin.rdbuf(infile.rdbuf());
	start__ = clock();
	cerr << "---" << endl;
}

void close_func() {
	clock_t elapsed = clock()-start__;
	cerr << "---" << endl << "(time " << fixed << setprecision(2) << elapsed * (1.0/CLOCKS_PER_SEC) << "s)" << endl;	
	//if(infile.good()) infile.close();
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
pair<string, string> func(const string &s, int x)
{
    pair<string, string> P;
    for (int i = 0; i < s.size(); i++) {
        if (x & 1) {
            P.first += s[i];
        } else {
            P.second += s[i];
        }
        x >>= 1;
    }
    return P;
}
int main()
{
    int N; cin >> N;
    string S; cin >> S;
    string s1 = S.substr(0, N), s2 = S.substr(N, N);
    reverse(begin(s2), end(s2));
    map<pair<string, string>, int> M;
    Int ans = 0;
    for (int i = 0; i < (1 << N); i++) {
        M[func(s1, i)]++;
    }
    for (int i = 0; i < (1 << N); i++) {
        ans += M[func(s2, i)];
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 91904
a_price, b_price, c_price, X, Y = list(map(int, input().split()))

total_price_1 = 0
total_price_2 = 0
diff = 0

# A, B <= 2 * C ならAとBそれぞれ買ったほうが安い
# それ以外だとCを可能な限り買った方が安い
# Cがすごく安いと, 過剰な枚数買っても安くなる場合とそうでない場合がある

if a_price + b_price < c_price * 2:
    total_price_1 = a_price * X + b_price * Y
    print(total_price_1)
else:
    if X > Y:
        total_price_1 = (c_price * 2) * X
        total_price_2 = (c_price * 2) * Y + a_price * (X - Y)
    else:
        total_price_1 = (c_price * 2) * Y
        total_price_2 = (c_price * 2) * X + b_price * (Y - X)

    print(min([total_price_1, total_price_2]))


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long ll;

int main(){
  ll n,c,k;
  cin >> n >> c >> k;

  vector<ll> t(n);
  rep(i,n) cin >> t.at(i);
  sort(t.begin(), t.end());

  ll time=t.at(0)+k,pass=0,bus=0;
  rep(i,n){
    if(time>=t.at(i)) pass++;
    else {bus++; pass=1; time=t.at(i)+k;}

    if(pass==c&&i<n-1){bus++; pass=0; time=t.at(i+1)+k;}
    if(i==n-1) bus++;
  }

  cout << bus;
}

Measured memory_bytes: 4032
/**
*       Author: K.R.Surrya  26/04/2020 17:32:48 
*
**/
#include<bits/stdc++.h>
#define vi vector<int>
#define vii vector<vector<int> >
#define vpi vector<pair<int,int> >
#define fo(i,a,b)             for(int i=a;i<b;++i)
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define pb push_back
using namespace std; 

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it)  { return ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a,Args... args)
{
    cerr << *it << " = " << a <<endl;
    err(++it,args...);   //args is going to end.
}

void solve() {
    int S,W;
    cin >> S >> W;
    if(W>=S) {
        cout << "unsafe" << endl;
    } else {
        cout << "safe" << endl;
    }
}
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);


     auto start = chrono::high_resolution_clock::now();

     solve();

     auto end = chrono::high_resolution_clock::now();

     cerr << " Execution time : " << chrono::duration_cast<chrono::milliseconds>(end-start).count()<<"ms"<<endl;

   
    return 0;
}


Measured memory_bytes: 3644
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int x, y;
    cin >> x >> y;
    rep(i, x + 1) {
        if (i * 2 + (x - i) * 4 == y) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3636