akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

#define endl '\n'

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;


using ll = long long;
using ull = unsigned long long;

//#define int ll


const int N = 2e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 2e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P2 = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-6;
const double PI = acos(-1.0);


template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
bool prime(int n) {
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){return 0;}
    }return 1;}
ll bp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int p[N] , sum[N] , dp[N];

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> p[i];
    }
    dp[1] = 1;
    sum[p[1]] = 1;
    for(int i = 2; i <= n; i ++) {
        dp[i] = dp[i-1];
        if(p[i] != p[i-1]) {
            dp[i] += sum[p[i]];
            if(dp[i] > mod)
                dp[i] -= mod;
            sum[p[i]] += dp[i-1];
            if(sum[p[i]] > mod)
                sum[p[i]] -= mod;
        }
    }
    cout << dp[n];
}


signed main() {
    ios;
    int tt = 1;
//    cin >> tt;
    while(tt--) {
        solve();
    }
    return 0;
}
/*

0 0 0
0 0 1
0 1 0

0 1 1
1 0 1
1 0 0
1 1 0
1 1 1

*/


Measured memory_bytes: 2560
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    ans = 0
    tmp = 0
    targ = 'ACGT'
    for c in S:
        if c in targ:
            tmp += 1
        else:
            ans = max(ans, tmp)
            tmp = 0
    ans = max(ans, tmp)
    return ans


def main():
    S = read_str()
    print(slv(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5484
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	int a, b;
	cin >> a >> b;
	cout << max({ a + b,a - b,a*b }) << endl;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){//桁数
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){//最小公倍数
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){//最大公約数
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  char a,b,c,d,e,f,g,h,i;
  cin>>a>>b>>c>>d>>e>>f>>g>>h>>i;
  cout<<a<<e<<i<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <string>
#include <math.h>
#include <vector>
#include <cstdlib>
#include <queue>
#include <iomanip> //小数点以下を表示させる(setprecision())

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'

//DP法
template <class T>
inline bool chmin(T &a, T b) //change minimum
{
        if (a > b)
        {
                a = b;
                return true;
        }
        return false;
}
template <class T>
inline bool chmax(T &a, T b) //change max
{
        if (a < b)
        {
                a = b;
                return true;
        }
        return false;
}

typedef long long ll; //64bit型
using namespace std;

// const long long INF = 1LL << 60; //無限大の値
int INF = 1000000;

int N;
ll a[100010][3];
ll dp[100010][3];
int main()
{
        cin >> N;
        FOR(i, 0, N)
        {
                FOR(j, 0, 3)
                {
                        cin >> a[i][j];
                }
        }

        FOR(i, 0, N)
        {
                FOR(j, 0, 3)
                {
                        FOR(k, 0, 3)
                        {
                                if (j == k)
                                        continue;
                                chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
                        }
                }
        }
        ll res = 0;
        FOR(j, 0, 3)
        {
                chmax(res, dp[N][j]);
        }
        cout << res << endl;

        return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn=1e5+233;
int n,m;
int a[maxn];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	string s;
	cin>>s;
	int k;
	cin>>k;
	char ch=s[k-1];
	int len=s.length();
	for(int i=0;i<n;i++){
		if(s[i]!=ch)s[i]='*';
	}
	cout<<s<<endl;
    return 0;
}


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

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int k;
    cin >> k;
    int sum=0;
    for(int i=1;i<=1000000;i++){
    	sum=(sum*10+7)%k;
    	if(sum==0){
    		cout << i << '\n';
    		return 0;
    	}
    }
    cout << "-1";
}


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

int main()
{
    // 整数値の入力
    int a;
    cin >> a;

    // aが偶数のときと奇数のときで分ける
    float ans;
    if(a%2==0){
        ans = 0.5f;
    }
    else{
        int b = a / 2;
        b += 1;

        ans = (float) b / a;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
const int oo=2139063143;
const int N=1010000;
const int P=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
//char buf[1<<24],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
	if (x< 0) putchar('-'),x=-x;
	if (x>=10) print(x/10);
	putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
int a[N],b[N];
int f[(1<<16)+10],s[(1<<16)+10];
int main ()
{
	// freopen (".in","r",stdin);
	// freopen (".out","w",stdout);
	int n; sc(n);
	for (int i=1; i< n; i++)
	{
		int x,y,w; sc(x),sc(y),sc(w); ++x,++y;
		a[x]^=w,a[y]^=w;
	}
	for (int i=1; i<=n; i++)
		++b[a[i]];
	int ans=0; n=0;
	for (int i=1; i<=15; i++)
	{
		ans+=b[i]>>1;
		if (b[i]&1) a[++n]=i;
	}
	int S=(1<<n)-1;
	for (int s=1; s<=S; s++)
	{
		f[s]=f[s>>1]+(s&1);
		for (int i=1; i<=n; i++) if (s>>(i-1)&1)
			::s[s]^=a[i];
	}
	for (int i=1; i<=S; i++)
		f[i]=s[i]?1e9:f[i]-1;
	for (int s=1; s<=S; s++) if (!::s[s])
	{
		for (int s1=s; s1; s1=(s1-1)&s)
			f[s]=min (f[s],f[s1]+f[s-s1]);
	}
	pr(ans+f[S]);
	return 0;
}


Measured memory_bytes: 2432
import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main() {
  int a, b, c;
  readf (" %d %d %d", &a, &b, &c);
  swap (a, b);
  swap (a, c);
  writeln (a, ' ', b, ' ', c);
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
n,k=MI()
s=input()
s1=s[0:k-1]
s2=s[k-1]
s3=s[k:n]
if s2=="A":
    s2="a"
if s2=="B":
    s2="b"
if s2=="C":
    s2="c"
print(s1,end="")
print(s2,end="")
print(s3)

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

inline namespace atcoder {
    using i32 = int32_t; using u32 = uint32_t;
    using i64 = int64_t; using u64 = uint64_t;
    using f32 = float; using f64 = double;

    template <typename T, size_t Depth>
    struct vector_helper { using type = vector<typename vector_helper<T, Depth - 1>::type>; };
    template <typename T>
    struct vector_helper<T, 0> { using type = T; };
    template <typename T, size_t Depth>
    using vector_t = typename vector_helper<T, Depth>::type;

    template <typename T> using vec = vector_t<T, 1>;
    template <typename T> using vvec = vector_t<T, 2>;
    template <typename T> using vvvec = vector_t<T, 3>;
}

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



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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RFOR(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); --i)
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define RREP(i, n) for (int i = (int)(n - 1); i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(a) ((int)(a).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define SQ(x) ((x) * (x))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

bool G[1000000];

int main() {
    int Q;
    cin >> Q;
    REP(_i, Q) {
        fill_n(G, 1000000, false);
        int n;
        cin >> n;
        int cnt = 0;
        while (n > 10) {
            G[n] = true;
            int m = 10;
            int ma = 0;
            int a, b;
            while ((a = n / m) != 0) {
                b = n % m;
                ma = max(ma, a*b);
                m *= 10;
            }
            cnt++;
            n = ma;
            if (G[n]) {
                cout << -1 << endl;
                goto END;
            }
            if (n < 10) break;
        }
        cout << cnt << endl;
END: {}
    }
}

Measured memory_bytes: 4056
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

class SCC {
  int V;
  std::vector<std::vector<int>> G, rG;
  std::vector<int> vs;
  std::vector<bool> used;
  std::vector<int> cmp;

  void dfs(int v){
    used[v] = true;
    for(int i=0; i<G[v].size(); i++)
      if(!used[G[v][i]]) dfs(G[v][i]);
    vs.push_back(v);
  }
  
  void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;
    for(int i=0; i<rG[v].size(); i++)
      if(!used[rG[v][i]]) rdfs(rG[v][i], k);
  }
public:
  SCC(int V):V(V),G(V),rG(V),used(V),cmp(V){}

  int size(){ return V; }
  std::vector<int> get_edge(int from){ return G[from]; }

  void add_edge(int from, int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }

  // 強連結成分(2点が相互に行き来できるグループ)数
  int scc(){
    for(int i=0; i<used.size(); i++) used[i] = 0;
    vs.clear();
    for(int v=0; v<V; v++)
      if(!used[v]) dfs(v);
    for(int i=0; i<used.size(); i++) used[i] = 0;
    int k = 0;
    for(int i=vs.size()-1; i>=0; i--)
      if(!used[vs[i]]) rdfs(vs[i], k++);
    return k;
  }

  // サイクルがあるか
  bool iscyclic(){ return scc() != V; }

  // 強連結成分番号
  std::vector<int> get_cmp(){ return cmp; }
  
  // 同じ辺を2度通らない、その頂点までの最長経路
  std::vector<int> depth(){
    std::vector<pair<int,int>> order;
    std::vector<int> dp(V, 1);

    scc();

    for(int i=0; i<V; i++){
      order.push_back(make_pair(cmp[i],i));
    }
    std::sort(order.begin(), order.end());

    for(int i=0; i<V; i++){
      int node = order[i].second;
      for(int j=0; j<G[node].size(); j++){
        dp[G[node][j]] = max(dp[G[node][j]], dp[node]+1);
      }
    }
    return dp;
  }
};

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

  SCC scc(N*N);
  
  rep(i,N){
    vector<int> v;
    rep(j,N-1){
      int a;
      cin >> a;
      a--;
      v.push_back(a);
    }
    rep(j,v.size()-1){
      int x = i;
      int y = v[j];
      int z = v[j+1];
 
      int a = min(x,y) * N + max(x,y);
      int b = min(x,z) * N + max(x,z);
 
      scc.add_edge(a,b);      
    }
  }

  if(scc.iscyclic()){
    cout << -1 << endl;
    return 0;
  }

  int mx = 0;
  vector<int> ret = scc.depth();
   
  rep(i,ret.size()){
    mx = max(mx, ret[i]);
  }
  cout << mx << endl;
  return 0;
}

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

int main(int argc, char const *argv[]) {
  int n,x;
  cin>>n>>x;
  int  m[n];
  int min=1000;
  for(int i=0;i<n;i++){
    cin>>m[i];
    x-=m[i];
    if(m[i]<min)  min=m[i];
  }
  cout<<n+x/min<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
*/

ll n,a[100010],sum_all=0,sum=0,l=-1,ans[100010]={};
vector<pair<ll,ll>> v;
priority_queue<ll> Q;

void init(){
	cin>>n;
	reg(i,1,n)cin>>a[i];
	reg(i,1,n){
		Q.push(-a[i]);
		sum+=a[i];
		sum_all+=a[i];
	}
}

int main(void){
	init();
	reg(i,1,n){
		if(l<a[i]){
			while(-Q.top()<a[i]){
				sum -= -Q.top();
				Q.pop();
			}
			v.push_back({i, sum-Q.size()*a[i]});
			l=a[i];
		}
	}
	l=sum_all;
	rep(i,v.size()){
		ans[v[i].first] = l-v[i].second;
		l=v[i].second;
	}
	reg(i,1,n)cout<<ans[i]<<endl;
	return 0;
}

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine();
            var x = int.Parse(line.Split(' ')[0]);
            var y = int.Parse(line.Split(' ')[1]);
            var ans = 0;

            if(x >= y)
            {
                ans = divider(x, y);
            }
            else
            {
                ans = divider(y, x);
            }

            Console.WriteLine(ans);
        }

        static int divider(int x, int y)
        {
            var r = 0;
            while(y > 0)
            {
                r = x % y;
                x = y;
                y = r;
            }
            return x;
        }
    }
}



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

int main(){
  string S, T;
  cin >> S >> T;
  int result = 1500;
  for(int i = 0; i < S.length()+1-T.length(); i++){
    string tmp = S.substr(i, T.length());
    int tmpint = 0;
    for(int i = 0; i < T.length(); i++){
      if(tmp[i] != T[i]){
        tmpint ++;
      }
    }
    if(tmpint < result){
      result = tmpint;
    }
  }
  cout << result << endl;
}

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

int main(){
	int a, b, c;
	int tmp;
	cin >> a >> b >> c;

	if(a > b){
		tmp = a;
		a = b;
		b = tmp;
	}

	if(a > c){
		tmp = a;
		a = c;
		c = tmp;
	}

	if(b > c){
		tmp = b;
		b = c;
		c = tmp;
	}

	cout << a << " " << b << " " << c << endl;

	return 0;
}

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

int main() {
  int A, B, i, num=0;
  int d[5];
  cin >> A >> B;
  
  for(; A<=B; A++) {
    i=A;
    for(int j=0, n=10000; j<4; j++) {
      d[j] = i / n;
      i %= n;
      n /= 10;
    }
    d[4] = i % 10;
   
    if(d[0]==d[4] && d[1]==d[3])
      num++;
  }
  
  cout << num << endl;
}

Measured memory_bytes: 256
n = input()
src = list(map(int, input().split()))
count = 0
for i in range(len(src)-2):
    if src[i]<src[i+1]<src[i+2]:
        count += 1
new_li = list(reversed(src))
for n in range(len(new_li)-2):
    if new_li[n]<new_li[n+1]<new_li[n+2]:
        count += 1
print(count)

Measured memory_bytes: 3064
s=input()
N=int(s.split()[0])
M=int(s.split()[1])

a=input()
num=[]
n=a.split()
for i in(n):
  num.append(int(i))

num.sort()
sa=[]
sa_a=[]

for i in range(len(num)-1):
  n=num[i]-num[i+1]
  if(n<0): n*=-1
  sa.append(n)
  sa_a.append(n)
sa.sort()
sa.reverse()
m=0
for i in range(N-1,len(sa)):
  m+=sa[i]
print(m)

Measured memory_bytes: 14716
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n, input, flag=0;
	cin >> n;
	while(n--){
		cin >> input;
		if(input%2 == 0){
			if(input%3 != 0 && input%5 != 0) flag = 1;;
		}
	}
	if(flag) cout << "DENIED" << endl;
	else cout << "APPROVED" << endl;
	return 0;
}

Measured memory_bytes: 256
import sys


def reverse_search(n, parents):
    q = [n - 1]
    visited = set()
    while q:
        v = q.pop()
        if v in visited:
            continue
        visited.add(v)
        q.extend(u for u in parents[v] if u not in visited)
    return visited


n, m, p = list(map(int, input().split()))
INF = 10 ** 12
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
costs = [[INF] * n for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)
reachable = reverse_search(n, parents)
for v in reachable:
    links[v].intersection_update(reachable)

dist = [INF] * n
dist[0] = 0
for _ in range(len(reachable)):
    updated = False
    for v in reachable:
        d = dist[v]
        if d == INF:
            continue
        cv = costs[v]
        for u in links[v]:
            if dist[u] > d + cv[u]:
                dist[u] = d + cv[u]
                updated = True
    if not updated:
        break
else:
    print(-1)
    exit()

print(max(0, -dist[n - 1]))


Measured memory_bytes: 99932
import sys
sys.setrecursionlimit(4100000)

class Uf():
    def __init__(self, n):
        self.par = [-1]*N
 
    def root(self, x):
        if self.par[x] < 0:
            return x
        
        root_x = self.root(self.par[x])
        self.par[x] = root_x
        return root_x
    
    def merge(self, a, b):
        a, b = self.root(a), self.root(b)
        
        if a == b:
            return
            
        if self.par[a] > self.par[b]:
            a, b = b, a
        
        self.par[a] += self.par[b]
        self.par[b] = a
                 
    def isSame(self, a, b):
        return self.root(a) == self.root(b)
    
    def size(self, x):
        return -self.par[self.root(x)]


N, M, K  = map(int,input().split())

exep = [[] for i in range(N)]

uf = Uf(N)

for i in range(M):
    a, b  = map(int,input().split())
    a, b = a-1, b-1 
    exep[a].append(b)
    exep[b].append(a)
    uf.merge(a, b)

for i in  range(K):
    a, b  = map(int,input().split())
    a, b = a-1, b-1
    if not uf.isSame(a,b):
        continue
    exep[a].append(b)
    exep[b].append(a)

for i in range(N):
    print(uf.size(i) - 1 - len(exep[i]), end=" ")

Measured memory_bytes: 113624
using System;

namespace B
{
    class Program
    {
        static void Main (string[] args)
        {
            var input = Console.ReadLine ().Split (' ');
            var h = int.Parse (input[0]);
            for (var i = 0; i < h; i++)
            {
                var input1 = Console.ReadLine ();
                for (var j = 0; j < 2; j++)
                {
                    Console.WriteLine (input1);
                }
            }
        }
    }
}

Measured memory_bytes: 11092
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b) { return *(int *)a - *(int *)b; }                            /* 1,2,3,4.. */
int des(const void *a, const void *b) { return *(int *)b - *(int *)a; }                            /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { return *(char *)a - *(char *)b; }                     /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) { return strcmp(*(const char **)a, *(const char **)b); } /* aaa,aab.. */
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define rep(i, n) for (int i = 0; i < n; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int parent[MAX];
int root(int x)
{
  if (parent[x] == x)
    return x;
  return parent[x] = root(parent[x]);
}

int main(void)
{
  int n, m;
  scanf("%d %d", &n, &m);

  int x, y, z;
  rep(i, n + 1)
  {
    parent[i] = i;
  }
  rep(i, m)
  {
    scanf("%d %d %d", &x, &y, &z);
    int rx = root(x);
    int ry = root(y);
    if (rx == ry)
      continue;
    parent[ry] = rx;
  }

  int group[MAX] = {0};
  int ans = 0;
  rep(i, n)
  {
    int ri = root(i + 1);
    if (group[ri])
      continue;
    group[ri] = 1;
    ans++;
  }

  printf("%d\n", ans);
  return 0;
}


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

const int MAX = 1e5+5;

const int MOD = 1e9 + 7;

ll ara[MAX] , dp[MAX][20];

int n;
string str;

ll solve(int id , int rem) {

    
    if( id == n ) {
        if( rem == 5) return 1;
        return 0;
    }
    
    ll &ret = dp[id][rem];
    if( ret != -1) return ret;
    
    ret = 0;
    
    
    if( str[id] != '?') {
        int num = (str[id] - '0');
        ret = solve(id+1 , (rem *10 + num )%13 );
        return ret;
    }
    
    for(int i =0 ; i < 10 ; i++ ) {
        
        ret = ( ret + solve(id+1 , (rem *10 + i)%13 )  )%MOD;
    }
    return ret;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
    cin>>str;
    n = str.size();
    
    memset(dp , -1 , sizeof dp);
    
    cout<<solve(0 , 0 )<<'\n';
    return 0;
}

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

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

    // even + even = even
    // odd + odd = even
    // odd + even = odd
    // even + odd = odd

    cout << (N * (N-1)) / 2 + (M * (M-1)) / 2 << "\n";
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)




int main() {
    ll n;
    cin >> n;
    
    ll ans = 0;
    REP(i, n){
        ll a;
        cin >> a;
        
        while(!(a & 1)){
            a /= 2;
            ans++;
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int n, T; cin >> n >> T;
    int ans = 1e9;
    while(n--) {
        int c, t; cin >> c >> t;
        if(t <= T) ans = min(ans, c);
    }
    if(ans == 1e9) cout << "TLE\n";
    else cout << ans << "\n";
}


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

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

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 1000000007; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


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

  vector<pair<int, int>> A(N);
  REP(i, N){
    cin >> A[i].first;
    A[i].second = i;
  }

  sort(ALL(A));

  int ans = 0;
  REP(i, N){
    if(i%2 != A[i].second%2) ans++;
  }
  
  cout << ans/2 << endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
	while(b){ a %= b; swap(a, b); }
	return a;
}
vector<int> good;
const int maxn = 20001;
int main(){
	for(int i = 1; i <= 30000; i++) if(i % 2 == 0 || i % 3 == 0) good.push_back(i);	
	int n; cin >> n;
	if(n == 3){
		cout << 2 << " " << 5 << " " << 63 << endl;
		return 0;
	}
	int upto = n - (n % 8);
	vector<int> ans;
	for(int i = 0; i < upto; i++) ans.push_back(good[i]);
	int miss = n - upto;
	if(miss == 0);
	else if(miss == 1){
		ans.push_back(good[upto + 3]);
	} else if(miss == 2){
		ans.push_back(good[upto]);
		ans.push_back(good[upto + 2]);
	} else if(miss == 3){
		ans.push_back(good[upto]);
		ans.push_back(good[upto + 2]);
		ans.push_back(good[upto + 3]);
	} else if(miss == 4){
		ans.push_back(good[upto]);
		ans.push_back(good[upto + 1]);
		ans.push_back(good[upto + 2]);
		ans.push_back(good[upto + 5]);
	} else {
		for(int j = 0; j < 4; j++) ans.push_back(good[upto + j]);
		upto += 4;
		miss -= 4;
		if(miss == 1){
			ans.push_back(good[upto + 1]);
		} else if(miss == 2){
			ans.push_back(good[upto + 1]);
			ans.push_back(good[upto + 3]);
		} else if(miss == 3){
			for(int j = 0; j < 3; j++) ans.push_back(good[upto + j]);
		}
	}
	int s = 0;
	for(int v : ans) s += v;
	for(int v : ans) assert(gcd(s, v) > 1);
	for(int v : ans) cout << v << " ";
	cout << endl;
	return 0;
}


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

int mincost(vector<int> &dp, vector<int> &h, int i){
  if(dp[i] != INT_MAX)
    	return dp[i];
	if(i >= h.size()-1){
      return 0;
    }
  if(i == h.size() -2){
  	return dp[i] = abs(h[i]-h[i+1]);
  }
  return dp[i] = min(abs(h[i]-h[i+1])+mincost(dp, h, i+1), abs(h[i]-h[i+2])+mincost(dp, h, i+2));
}

int main(){
  int n;
  cin>>n;
  vector<int> h(n, 0);
  vector<int> dp (n, INT_MAX);
  for(int i = 0; i < n; ++i){
  	cin>>h[i];
  }
  cout<<mincost(dp, h, 0);
}


Measured memory_bytes: 8012
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    priority_queue<int> a;
    for(int i=0;i<n;i++){
        int ai;
        cin>>ai;
        a.push(ai);
    }
    while(m>0){
        int temp=a.top();a.pop();
        temp/=2;
        a.push(temp);
        m--;
    }
    ll ans=0;
    while(!a.empty()){
        ans+=a.top();
        a.pop();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 892
// URL: https://atcoder.jp/contests/abc131/tasks/abc131_c

import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.string;
import std.numeric;

version(unittest) {} else
void main()
{
  long a, b, c, d; io.getV(a, b, c, d);

  auto g = gcd(c, d), e = c/g*d;
  auto na = (a-1)/c + (a-1)/d - (a-1)/e, nb = b/c + b/d - b/e;

  io.put(b-a+1-(nb-na));
}

auto io = IO();

struct IO
{
  import std.algorithm, std.conv, std.format, std.range, std.stdio, std.traits;

  dchar[] buf;
  auto sp = (new dchar[](0)).splitter;
  int precision = 10;
  string delimiter = " ";

  void nextLine()
  {
    stdin.readln(buf);
    sp = buf.splitter;
  }

  auto get(T)(ref T v)
  {
    if (sp.empty) nextLine();
    v = sp.front.to!T;
    sp.popFront();
  }

  auto getV(T...)(ref T v)
  {
    foreach (ref w; v) get(w);
  }

  auto getA(T)(size_t n, ref T v)
  {
    v = new T(n);
    foreach (ref w; v) get(w);
  }

  auto getC(T...)(size_t n, ref T v)
  {
    foreach (ref w; v)
      w = new typeof(w)(n);
    foreach (i; 0..n)
      foreach (ref w; v) get(w[i]);
  }

  auto getM(T)(size_t r, size_t c, T v)
  {
    v = new T(r, c);
    foreach (ref w; v) getA(c, w);
  }

  auto putA(T)(T v)
  {
    static if (isInputRange!T && hasLength!T && !isSomeString!T) {
      foreach (i, w; v) {
	putA(w);
	if (i < v.length - 1) write(delimiter);
      }
    } else if (isFloatingPoint!T) {
      writef(format("%%.%df", precision), v);
    } else {
      write(v);
    }
  }

  auto put(T...)(T v)
  {
    foreach (i, w; v) {
      putA(w);
      if (i < v.length - 1) write(delimiter);
    }
    writeln;
  }

  auto putB(S, T)(bool c, S t, T f)
  {
    if (c)
      put(t);
    else
      put(f);
  }

  auto dbg(T...)(T v)
  {
    stderr.writeln(v);
  }
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

class Combination {
    private:
    vector<int> x, y;
    
    int modpow(int x, int n, int mod = (int)1e9 + 7) {
        int ret = 1;
        while (n > 0) {
            if ((n & 1)) {
                ret = ret * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return ret;
    }
    
    public:
    Combination(int n) {
        x.resize(n+1);
        y.resize(n+1);        
        x[0]=y[0]=1;
        for (int i = 1; i <= n; i++) {
            x[i]=(x[i-1]*i)%mod;
            y[i]=modpow(x[i],mod-2);
        }
    }
    
    int get(int n, int r) {
        if (n < r) return 0;
        return x[n] * y[n - r] % mod * y[r] % mod;
    }
    
};

void run(){
    int n,k;
    cin>>n>>k;
    Combination comb(n);
    REP(i,1,k){
        cout<<comb.get(n-k+1,i)*comb.get(k-1,i-1)%mod<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
#define fst first
#define snd second
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> inline int Log2(T& x) {int k; for(k=0; (T(1)<<k)<=x; ++k); return k;} // number of binary digits
template<typename T> inline int count_between(vector<T>& a, T l, T r) {
  return lower_bound(all(a), r) - lower_bound(all(a), l);
}


int main() {
  ll H, W, N; cin >> H >> W >> N;
  VV X(W);

  rep(i, N) {
    int x, y; cin >> x >> y;
    --x; --y;
    X[y].push_back(x);
  }
  rep(i, W) sort(all(X[i]));

  VV ava(W);
  rep(i, W) for (auto e : X[i]) {
    if (!ava[i].empty() && ava[i].back() == e) ava[i].pop_back();
    ava[i].push_back(e+1);
  }

  int now = 0;
  V top(W, INF);
  top[0] = 0;
  rep(i, W-1) {
    if (count_between(X[i], now+1, now+2) == 1) break;
    if (count_between(X[i+1], now+1, now+2) == 0) {
      ++now;
      top[i+1] = now;
      continue;
    }
    int can = *lower_bound(all(ava[i+1]), now+1);
    if (count_between(X[i], now, can) > 0) break;
    now = can;
    top[i+1] = can;
  }

  int ans = H;
  rep(i, W) {
    if (X[i].empty()) continue;
    if (lower_bound(all(X[i]), top[i]) == X[i].end()) continue;
    chmin(ans, *lower_bound(all(X[i]), top[i]));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 18048
#include <cstdio>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <string>
using u8t = std::uint64_t;
using i8t = std::int64_t;
#define F(I,N) for(i8t I=0,I##_N=N;I<I##_N;I++)
#define FR(I,N) for(i8t I=N;I--;)
#define R(V) i8t V;std::cin>>V;
#define RV(V,N) std::vector<i8t> V;F(_i,N){R(_x)V.push_back(_x);}
#define RL1(line) std::getline(std::cin,line);
#define RL(line) std::string line;RL1(line)
#define RM(V,L,C) std::vector<char> V;F(_i,L){RL(_l)F(_j,C)V.push_back(_l[_j]);}
#define P(X) std::cout<<(X)<<std::endl;
int main() {
  R(r);
  std::printf("%.3f\n",2.0*3.14159265*r);
  return 0;
}


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

using namespace std;

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int N;
  cin >> N;
  vector < int > a(N);
  vector < vector < long long > > dp (N, vector < long long > (N, 0));
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
    dp[i][i] = a[i];
  }
  for (int L = N - 2; L >= 0; --L)
    for (int R = L + 1; R < N; ++R)
      dp[L][R] = max (a[L] - dp[L + 1][R], a[R] - dp[L][R - 1]);
  cout << dp[0][N - 1];
}


Measured memory_bytes: 73628
#include<iostream>
#include<vector>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
int main() {
	int h, w;
	int dy[4] = { 0,1,0,-1 };
	int dx[4] = { 1,0,-1,0 };
	cin >> h >> w;
	int ny, nx;
	int k = 0;
	vector<string>field;
	vector<vector<int>>kuro(h,vector<int>(w,-1));
	field.resize(h);
	for (int i = 0; i < h; i++) {
		cin >> field.at(i);
		//cout << field.at(i) << endl;
	}
	queue<pair<int, int>>q;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (field.at(i).at(j) == '#') {
				kuro.at(i).at(j) = 0;
				q.push(make_pair(i, j));
			}
		}
	}
	while (!q.empty()) {
		pair<int, int>p = q.front();
		q.pop();
		int flag = 0;
		int count = 0;
		for (int i = 0; i < 4; i++) {
			ny = p.first+dy[i];
			nx = p.second + dx[i];
			if (ny >= 0 && nx >= 0 && ny < h&&nx < w
				&&field.at(ny).at(nx) == '.'&&kuro.at(ny).at(nx) == -1) {
				q.push(make_pair(ny, nx));
				flag++;
				if (flag == 1) {
					count++;
				}
				kuro.at(ny).at(nx) = kuro.at(p.first).at(p.second) + count;
				k = kuro.at(ny).at(nx);
				//cout << kuro.at(ny).at(nx) << endl;
			}
		}
	}
	cout << k << endl;
}

Measured memory_bytes: 13456
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int N; string s[1001001];

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

	cin >> N;
	int ab = 0;
	vector<pair<int, int> > P, Q;
	for (int i = 0; i < N; i++){
		cin >> s[i];

		int b = 0, mn = 0;
		for (char c : s[i]){
			if (c == '(') b++;
			else b--;
			mn = min(mn, b);
		}

		ab += b;
		if (b >= 0) P.push_back({ -mn, -b });
		else Q.push_back({ b - mn, b });
	}

	if (ab){
		cout << "No" << endl;
		return 0;
	}

	sort(P.begin(), P.end());
	sort(Q.begin(), Q.end());

	for (auto &t : { P, Q }){
		int b = 0;
		for (auto &p : t){
			if (b - p.first < 0){
				cout << "No" << endl;
				return 0;
			}
			b -= p.second;
		}
	}

	cout << "Yes" << endl;
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define SUM(n) ((n)+1)*(n)/2
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7;

using namespace std;
using pii = pair<int,int>;

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

  int n;
  string s;
  cin >> n >> s;
  int l = 0, r = 0;
  rep(i,n){
    if(s[i] == '('){
      l ++;
    } else {
      if( l > 0 ){
	l --;
      } else {
	r ++;
      }
    }
  }
  rep(i,r){
    cout << '(';
  }
  cout << s;
  rep(i,l){
    cout << ')';
  }
  cout << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
long long N,W;

int 
main(){
	long long X,K;
	static char s[100010][20];
	int A[30],B[30],C[30];

	scanf("%lld",&N);
	long long i,j;
	for(i=0;i<N;i++){
		scanf("%d",&A[i]);
	}
		for(i=0;i<N;i++){
		scanf("%d",&B[i]);
	}
	for(i=0;i<N-1;i++){
		scanf("%d",&C[i]);
	}

	long long sum=0;
	int prev_a =0;
	for(i=0;i<N;i++){
		sum += B[A[i]-1];
		//printf("+%d\n",B[A[i]-1]);
		if(i>=1) {
			if(A[i]-prev_a==1){
				sum += C[prev_a-1];
				//printf("tt%d,%d\n",prev_a,C[prev_a-1]);
			}
		}
		prev_a = A[i];
	}
	printf("%lld\n",sum);
 return 0;
}

Measured memory_bytes: 128
H, W = [int(item) for item in input().split()]
grid = [[item for item in input().strip()] for _ in range(H)]

# print(H, W) 
# print(grid)

dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[0][1] = 1

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            pass
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]

print(dp[H][W]%(10**9+7))

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

#define     int          long long int
#define     fast() 	     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     __gcd((a),(b))
#define     lcm(a,b)     ((a)*(b))/gcd((a),(b))
#define     pb           push_back
#define     F            first
#define     S            second

const int inf=1e18,M=1e9+7;

const int N=1e5+5;

vector<int> rt(N),siz(N);

void init()
{
 for(int i=0;i<N;++i)
 rt[i]=i,siz[i]=1;
}

int root(int x)
{
 while(x!=rt[x])
 {
  rt[x]=rt[rt[x]];
  x=rt[x];
 }
 return x;
}

void uni(int a,int b)
{
 int x=root(a);
 int y=root(b);
 
 if(x==y)
 return;
 
 if(siz[x]<siz[y])
 swap(x,y);
 
 rt[y]=x;
 siz[x]+=siz[y];
}

void solve()
{
 int n,m;
 
 init();
 
 cin>>n>>m;
 
 int a,b,w;
 
 for(;m;--m)
 {
  cin>>a>>b>>w;
  uni(a,b);
 }
 
 int ans=0;
 for(int i=1;i<=n;++i)
 {
  if(rt[i]==i)
  ++ans;
 }
 
 cout<<ans;
}

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

    return 0;
}


Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.siz=[1]*n
        
    def root(self,x):
        while self.par[x]!=x:
            self.par[x]=self.par[self.par[x]]
            x=self.par[x]
        return x
    
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.siz[x]<self.siz[y]:
            x,y=y,x
        self.siz[x]+=self.siz[y]
        self.par[y]=x
        return True
    
    def is_same(self,x,y):
        return self.root(x)==self.root(y)
    
    def size(self,x):
        return self.siz[self.root(x)]
MAX=10**5
u=UnionFind(MAX*2)
for _ in range(N):
    x,y=map(int1,input().split())
    u.unite(x,y+MAX)
lx,ly=[0]*MAX*2,[0]*MAX*2
for i in range(MAX):
    lx[u.root(i)]+=1
    ly[u.root(i+MAX)]+=1
ans=0
for i in range(MAX*2):
    ans+=lx[i]*ly[i]
print(ans-N)

Measured memory_bytes: 58480
#include <stdio.h>
#include <stdlib.h>

void selectionSort(int *, int); // N 個の要素を含む 0-オリジンの配列 A


int main() {
  int i, N, *A;
  
  scanf( "%d" , &N );
  A = (int *)malloc(N * sizeof(int));
  for( i=0; i<N; i++ ) scanf( "%d" , &A[i] );
  selectionSort(A, N);
  
  return 0;
}


void selectionSort(int *A, int N) {
  int i, j, minj, temp, count=0;
  
  for ( i=0; i<N; i++ ) {
    minj = i;
    for ( j=i; j<N; j++ ) if ( A[j] < A[minj] ) minj = j;
    temp = A[i];
    A[i] = A[minj];
    A[minj] = temp;
    if ( minj != i ) count++;
  }
  for ( j=0; j<(N-1); j++ ) printf( "%d " , A[j] );
  printf( "%d\n%d\n" , A[N-1] , count );
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

int main() {
    ll X; cin >> X;
    ll money = 100;
    ll ans = 0;
    while (money < X) {
        ans++;
        money *= 1.01;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636
// ＡＢＣの過去問を解くだけだよ

// フォント x:小文字 X:大文字

/*
問題文
ある学校には、
N人の生徒がいます。

生徒たちをいくつかのグループに分け、グループごとにあるテーマについて話し合ってもらうこととなりました。

あなたは、
2人以下のグループだと効果的な話し合いが出来ないと考えており、なるだけ多くのグループを 
3人以上にしたいです。

生徒たちを上手く分けて、
3人以上のグループの数を最大化してください。
*/

#include <bits/stdc++.h>

using namespace std;

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

    int c = n / 3;

    cout << c;

    return 0;
}

// できた


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int main() {
	int h = ri();
	int w = ri();
	std::string s[h];
	for (auto &i : s) std::cin >> i;
	int dp[h][w];
	for (auto &i : dp) for (auto &j : i) j = 1000000000;
	dp[0][0] = s[0][0] == '#';
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (i + 1 < h) dp[i + 1][j] = std::min(dp[i + 1][j], dp[i][j] + (s[i][j] == '.' && s[i + 1][j] == '#'));
			if (j + 1 < w) dp[i][j + 1] = std::min(dp[i][j + 1], dp[i][j] + (s[i][j] == '.' && s[i][j + 1] == '#'));
		}
	}
	printf("%d\n", dp[h - 1][w - 1]);
	return 0;
}




Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int i,n,p=0;
    cin>>n;
    for(i=1; i<=n/i; i++)
        if(n%i==0&&i<=9&&n/i<=9)
        {
            p=1;
            cout<<"Yes"<<endl;
            break;
        }
    if(p==0)
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<string>
#include<set>

using namespace std;

multiset<int> read(){
  multiset<int> s;
  string line;
  int x;

  while(1){
    getline(cin , line );
    if ( cin.eof() || line.find(',') == string::npos) break;
    stringstream sin(line);
    sin >> x;
    s.insert(x);
  }

  return s;
}

main(){
  multiset<int> v1, v2;
  set<int> u;
  v1 = read();
  v2 = read();
  for ( multiset<int>::iterator it = v1.begin(); it != v1.end(); it++ ){
    int t = (*it);
    if ( v2.count(t) && u.find(t) == u.end() ) {
      cout << t << " " << v1.count(t) + v2.count(t) << endl;
      u.insert(t);
    }
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int A, B;
    cin >> A >> B;
    if(A+B >= 10) cout << "error" << endl;
    else cout << A+B << endl;
    
    return 0;
}

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

int main(){
    string s,s1;
    cin>>s>>s1;
    bool ok=false;
    long long n=s.size();
    if(s==s1)cout<<"Yes";
    else{
      for(long long i=0;i<s.size();i++){
           string r;
           stringstream b;
           b<<s[n-1];
           b>>r;
           s.insert(0,r);
           s.pop_back();
           if(s==s1)ok=true;
       }
       if(ok)cout<<"Yes";
       else cout<<"No";
    }
}

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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
  int n, k;
  cin >> n >> k;
  ld sum = 0;
  int lg;
  for(int i = 1; i <= n; i ++ ){
    lg = 0;
    while(i * (1 << lg) < k){
      lg ++ ;
    }
    ld shit = 1;
    for(int i = 0 ; i < lg; i ++ ){
      shit /= 2.0;
    }
    sum += shit;
  }
  sum /= n;
  cout << fixed << setprecision(15) << sum;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
vector<ll> a;
int N;
ll ans;
int main(){
  
  cin>> N;
  for(int i = 0; i < N*3; i++){
    ll tmp;
    cin>>tmp;
    a.push_back(tmp);
  }
  sort(a.begin(), a.end(), greater<ll>());
  for(int i = 0; i < N; i++){
    ans += a[i*2+1];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 6000