akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PDD;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dbl(k, x) fixed << setprecision(k) << (x)

template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}

#define _upgrade                \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)

// ********************** CODE ********************** //

const int N = 2e5 + 7;
const int M = 1e9 + 7;

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

LL dp[N];
LL fac[N];
LL inv_fac[N];
bool vis1[N];
bool vis2[N];
int sub_tree_size[N];

PLL extended_euclid(LL A, LL B, LL C) {
  if (B == 0) {
    return {C / A, 0};
  }
  LL x, y;
  tie(x, y) = extended_euclid(B, A % B, C);
  return {y, x - A / B * y};
}

int inv(int n) {
  int x, _;
  tie(x, _) = extended_euclid(n, M, 1);
  return (x + M) % M;
}

void dfs1(int v) {
  vis1[v] = true;
  dp[v] = 1;
  sub_tree_size[v] = 1;
  for (auto u : G[v]) {
    if (!vis1[u]) {
      dfs1(u);
      sub_tree_size[v] += sub_tree_size[u];
      dp[v] *= (dp[u] * inv_fac[sub_tree_size[u]]) % M;
      dp[v] %= M;
    }
  }
  dp[v] *= fac[sub_tree_size[v] - 1];
  dp[v] %= M;
}

void dfs2(int v) {
  vis2[v] = true;
  res[v] = dp[v];
  for (auto u : G[v]) {
    if (!vis2[u]) {
      LL old_dp_v = dp[v];
      LL old_dp_u = dp[u];
      LL old_sub_tree_size_v = sub_tree_size[v];
      LL old_sub_tree_size_u = sub_tree_size[u];

      sub_tree_size[v] -= old_sub_tree_size_u;
      sub_tree_size[u] = old_sub_tree_size_v;

      dp[v] *= inv(old_dp_u);
      dp[v] %= M;
      dp[v] *= fac[old_sub_tree_size_u];
      dp[v] %= M;
      dp[v] *= inv_fac[old_sub_tree_size_v - 1];
      dp[v] %= M;
      dp[v] *= fac[sub_tree_size[v] - 1];
      dp[v] %= M;

      dp[u] *= inv_fac[old_sub_tree_size_u - 1];
      dp[u] %= M;
      dp[u] *= fac[sub_tree_size[u] - 1];
      dp[u] %= M;
      dp[u] *= dp[v];
      dp[u] %= M;
      dp[u] *= inv_fac[sub_tree_size[v]];
      dp[u] %= M;

      dfs2(u);

      dp[v] = old_dp_v;
      dp[u] = old_dp_u;
      sub_tree_size[v] = old_sub_tree_size_v;
      sub_tree_size[u] = old_sub_tree_size_u;
    }
  }
}

int main() {
  _upgrade;
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = (fac[i - 1] * i) % M;
  }

  for (int i = 0; i <= n; i++) {
    inv_fac[i] = inv(fac[i]);
  }

  dfs1(1);

  dfs2(1);

  for (int i = 1; i < n + 1; i++) {
    cout << res[i] << "\n";
  }
  return 0;
}

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

int main() {
	int n;
	cin>>n;
	for (int i=0; i*7<=n; i++) {
		int remain = n-i*7;
		if (remain%4 == 0) {
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
w_list = list(map(int,input().split()))

sum_w = sum(w_list)

diff = 999
t = 0
for i in range(n):
    mae = sum(w_list[:i])
    ato = sum_w-mae
    if diff > abs(mae-ato):
        diff = abs(mae-ato)
        t = i

print(diff)

Measured memory_bytes: 38512
#define _CRT_NONSTDC_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define NL << endl

using namespace std;
using ll = long long;
const int INTMAX = numeric_limits<int>::max();
const int INTMIN = numeric_limits<int>::min();
const ll LLMAX = numeric_limits<long long>::max();
const ll LLMIN = numeric_limits<long long>::min();
const int MOD = 1000000007;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

using namespace std;

signed main() {

	int N;
	cin >> N;
	if (N / 10 == 9 || N % 10 == 9)cout << "Yes" NL;
	else cout << "No" NL;


	return 0;
}



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

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> dp(n + 1);
    for (int i = 0; i < n; ++i) {
        if (i && s[i] != s[i - 1]) {
            dp[i + 1] = max(dp[i], dp[i - 1] + 1);
        }
        else {
            dp[i + 1] = dp[i];
        }
    }
    cout << dp[n] << '\n';
    return 0;
}


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

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; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

ll N,A,B;
vector<ll> h;

bool is_OK(ll x){
    ll res = 0;
    rep(i,N){
        if(h[i]-x*B<=0)continue;
        res += ceil((h[i]-x*B)/(double)(A-B));
    }
    return res<=x;
}

int main(){
    cin>>N>>A>>B;
    h.resize(N);
    rep(i,N)cin>>h[i];
    ll left = 0, right = 1e9;
    while(right-left>1){
        ll mid = left + (right - left)/2;
        if(is_OK(mid))right = mid;
        else left = mid;
    }
    cout<<right<<endl;
}


Measured memory_bytes: 3992
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m;
int a[100005],x;
int dp[100005];

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		a[x]=1;
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]==0){
			if(i<2) dp[i]=dp[i-1];
			else dp[i]=(dp[i-1]+dp[i-2])%mod;
		}
	}
	printf("%d\n",dp[n]);
	
	return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		//?????°?¨????
        int[] Mountain = new int[10];
        int i = 0;
        int first = 0, second = 0, third = 0;
		String line;

		//???????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			for (i = 0; i < 10; i++) {
				line = br.readLine();
				Mountain[i] = Integer.parseInt(line);
				//????????????
				if (Mountain[i] > first) {
					third = second;
					second = first;
					first = Mountain[i];
					continue;
				} else if (Mountain[i] > second) {
					third = second;
					second = Mountain[i];
					continue;
				} else if (Mountain[i] > third) {
					third = Mountain[i];
					continue;
				}
			}
        System.out.println(first);
        System.out.println(second);
        System.out.println(third);
	}
}

Measured memory_bytes: 24348
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B, X;
    cin >> A >> B >> X;
    if(A<=X&&(A+B)>=X) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


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

using namespace std;

int main(void) {
  int n, k;
  cin >> n >> k;

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

  vector<int> v;
  for (auto i : mp) {
    v.push_back(i.second);
  }
  sort(v.begin(), v.end());

  int ans = 0;
  for (int i = 0; i < max(0, (int)v.size() - k); i++) {
    ans += v[i];
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 10748
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define eps 1e-14
#define INF 1e9

using namespace std;

int c[30];
int dp[50001];

signed main(){
  int n, m;
  cin >> n >> m;
  rep(i, m){
    cin >> c[i];
  }
  
  rep(i, 50001){
    dp[i] = INF;
  }
  
  // dp[i] := i円払うときの最小の枚数
  dp[0] = 0;
  rep(i, m){    
    for(int j = 0 ; j + c[i] <= n ; j++){
      dp[j+c[i]] = min(dp[j + c[i]], dp[j] + 1);
    }
  }

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


Measured memory_bytes: 3296
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int ans = 0;
        for(int i = 0;i<n;i++){
            int h = Integer.parseInt(sc.next());
            if(h>=k){
                ans++;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 46852
import jdk.nashorn.internal.ir.LabelNode;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		int e = sc.nextInt();
		int f = sc.nextInt();

		double rate = 0.0;
		int[] ws = new int[]{1, 0};

		for (int i = 0; i <= 3000; i++) {
			for (int j = 0; j <= 3000; j++) {
				int water = ((a * i) + (b * j)) * 100;
				if (water == 0 || water >= f) break;
				int cap = Math.min(f - water, (water / 100) * e);
				for (int k = 0; k <= 3000; k++) {
					for (int l = 0; l <= 3000; l++) {
						int sugar = k * c + l * d;
						if (sugar > cap || water + sugar > f) break;
						if (rate * (sugar + water) <= sugar) {
							rate = (double) sugar / (water + sugar);
							ws[0] = water;
							ws[1] = sugar;
						}
					}
				}
			}
		}

		System.out.println(ws[0] + ws[1] + " " + ws[1]);
	}
}


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

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;
int niz[100005];
vector<int> graf[100005];


int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    ff(i,1,n){
        cin >> niz[i];
    }
    ff(i,1,m){
        int a,b;
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
    }
    int res = 0;
    ff(i,1,n){
        int maks = 0;
        for(auto c:graf[i])maks = max(maks, niz[c]);
        if(niz[i] > maks)res++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 9164
A,B,M = map(int,input().split())
a_li = list(map(int,input().split()))
b_li = list(map(int,input().split()))
ans = min(a_li) + min(b_li)
for i in range(M):
    x,y,c = map(int,input().split())
    ans = min(ans, a_li[x-1] + b_li[y-1] - c)
print(ans)


Measured memory_bytes: 18684
#include <stdio.h>
int main(void)
{
    int input, h, m, tmp;
    scanf("%d", &input);
    h = input/(60*60);
    input -= h*(60*60);
    m = input/60;
    input -= m*60;
    
    printf("%d:%d:%d\n", h, m, input);
    
    return 0;
    
}


Measured memory_bytes: 2052
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 

 
signed main()
{
  string S;
  cin >> S;

  char c = S[S.length() / 2];
  int ci = S.length() / 2;
  int ans = S.length() / 2;
  if (S.length() % 2 == 0) {
    for (int i=1; i<=S.length()/2; i++) {
      if (S[ci-i] == c && S[ci+i-1] == c) {
        ans++;
      } else {
        break;
      }
    }
  } else {
    for (int i=1; i<=S.length()/2+1; i++) {
      if (S[ci-i+1] == c && S[ci+i-1] == c) {
        ans++;
      } else {
        break;
      }
    }
  }

  cout << ans << endl;
}

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

int main(){
int n,a;
  cin>>n;
  a=n%10;
  if(a==3){
cout<<"bon"<<endl;
  }
  else if(a==0||a==1||a==6||a==8){
cout<<"pon"<<endl;
  }
  else{
cout<<"hon"<<endl;
  }
}
  

Measured memory_bytes: 3632
from collections import Counter

class UnionFind():
  def __init__(self,n):
    self.parents=[-1]*n
  
  def find(self,x):
    if self.parents[x]<0:
      return x
    
    self.parents[x]=self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
    
N,K,L=map(int,input().split())
uf_road=UnionFind(N+1)
uf_train=UnionFind(N+1)

for _ in range(K):
  p,q=map(int,input().split())
  uf_road.union(p,q)

for _ in range(L):
  s,t=map(int,input().split())
  uf_train.union(s,t)
  
union_sets=[(uf_road.find(i),uf_train.find(i)) for i in range(1,N+1)]
counts=Counter(union_sets)
ans=[counts[union_set] for union_set in union_sets]

print(' '.join(str(a) for a in ans))

Measured memory_bytes: 159200
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

vector<int> a;
vector<int> b;
int N;
int M;
bool f(){
  //REP(i,b.size()){cout<<b[i]<<",";} cout<<endl;
  bool ret = false;
  int first = b[0];
  int fi = 0;
  FOR(i,1,b.size()){
    if(b[i]==first&&i==b.size()-1){
      if(i-fi>=3){
        b.erase(b.begin()+fi,b.end());
        ret = true;
      }
    }else if(b[i]!=first){
      if(i-fi>=4){
        b.erase(b.begin()+fi,b.begin()+i);
        ret = true;
      }
      first = b[i];
      fi = i;
    }
  }
  M = min(M,(int)b.size());
  return ret;
}
int main(){
  while(cin>>N){
    if(N==0) break;
    a.clear();
    REP(i,N){int tmp; cin>>tmp; a.push_back(tmp);}
    M = a.size();
    REP(i,N-3){
      if(a[i+1]==a[i+2]&&a[i+1]==a[i+3]){
        b = a;
        b[i] = b[i+1];
        while(f());
      }
    }
    FOR(i,3,N){
      if(a[i-3]==a[i-2]&&a[i-3]==a[i-1]){
        b = a;
        b[i] = b[i-1];
        while(f());
      }
    }
    FOR(i,1,N-1){
      if(a[i-1]==a[i+1]){
        b = a;
        b[i] = b[i+1];
        while(f());
      }
    }
    cout<<M<<endl;
  }
  return 0;
}

Measured memory_bytes: 1048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    vector<int> a(N);
    for(int i=0;i<N;i++) {
        cin >> a.at(i);
    }

    vector<int> b(N);
    int j, sum;
    for(int i=N;i>0;i--) {
        sum = 0;
        j = 2*i;
        while(j<=N) {
            sum += b.at(j-1);
            j += i;
        }
        if(a.at(i-1)!=sum%2) b.at(i-1) = 1;
        else b.at(i-1) = 0;
    }

    int M=0;
    for(int i=0;i<N;i++) {
        M += b.at(i);
    }

    cout << M << endl;
    for(int i=0;i<N;i++) {
        if(b.at(i)) cout << i+1 << " ";
    }
    cout << endl;

    return (0);
}


Measured memory_bytes: 2432
from collections import Counter
from collections import deque
from functools import reduce
from operator import mul
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def COMBINATION(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    o = reduce(mul, range(n, n - r, -1))
    u = reduce(mul, range(1, r + 1))
    return o // u
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])  # 経路圧縮
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


n = II()
t = LI()
m = II()
drink = [LI() for _ in range(m)]
tsum = sum(t)
for p, x in drink:
    print(tsum - t[p-1] + x)


Measured memory_bytes: 66668
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using Int = long long;

class Topological_sort {
private:
	Int V;
	vector<vector<Int>> edges;
	vector<Int> used;

public:
	Topological_sort(Int n) :V(n), edges(n), used(n) {}
	Topological_sort(vector<vector<Int>>& edges) :V(edges.size()), used(edges.size()) { this->edges = edges; }

	void add_edge(Int from, Int to) { edges[from].emplace_back(to); }

	vector<Int> build() {

		vector<Int> res, in(V);
		for (Int i = 0; i < V; i++) for (const auto& e : edges[i]) in[e]++;

		res.reserve(V);
		queue<Int> que;
		for (Int i = 0; i < V; i++) {
			if (in[i] == 0 && !used[i]) {
				used[i] = 1;
				que.emplace(i);
			}
		}
		while (!que.empty()) {
			Int now = que.front();
			//DMP(now, in);
			que.pop();
			res.emplace_back(now);
			for (const auto& e : edges[now]) {
				in[e]--;
				if (in[e] == 0) {
					if (used[e]) return vector<Int>(); // unable to sort
					used[e] = used[now] + 1;
					que.emplace(e);
				}
			}
		}

		return res;
	}

	Int longest_path() {
		if (none_of(used.begin(), used.end(), [](Int u) { return u > 0; })) build();
		return *max_element(used.begin(), used.end()) - 1;
	}

};


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, M;
	cin >> N >> M;

	vector<vector<Int>> G(N);
	Int x, y;
	for (Int i = 0; i < M; i++) {
		cin >> x >> y;
		x--;
		y--;
		G[x].push_back(y);
	}

	Topological_sort f(G);
	Int ans = f.longest_path();

	cout << ans << "\n";

}


Measured memory_bytes: 13568
root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)

Measured memory_bytes: 131516
// ConsoleApplication1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;

int main()
{
	int h, w;
	while (cin >> h >> w, h|w)
	{
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++)
			{
				cout << "#";

			}
			cout << endl;
		}
		cout << endl;



	}
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します



Measured memory_bytes: 3084
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define vvll vector <vll>
#define vsi vector <si>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    double pi=acos(-1);
    double r;
    cin>>r;
    cout<<setprecision(30)<<r*pi*2;




}


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

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

template<class T> using v = std::vector<T>;
template<class T> using vv = v<v<T>>;

const int mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    set<int> st;
    rep(i,9) rep(j,9) {
        st.insert((i+1)*(j+1));
    }
    int n; cin >> n;
    if (st.count(n)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main(){
    int n; cin >> n;
    bool is_ok = true;
    vector<int> v(n);

    for(int i = 0;i < n; ++i){
        cin >> v[i];
        if(v[i] & 1) is_ok = false;
    }

    if(!is_ok){
        cout << "0\n";
    }else{
        int ans = 0;
        bool reached = false;
        while(true){
            for(auto& a : v){
                a >>= 1;
                if(a & 1) reached = true;
            }
            ans++;
            if(reached) break;
        }
        cout << ans << endl;
    }

    return EXIT_SUCCESS;
}


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const double eps = 1e-9;

/*{
  }*/
class UnionFind
{
public:
  int n;
  vector<int> par, rnk;

  UnionFind(int n_)
  {
    n = n_;
    par.resize(n);
    rnk.resize(n);
    for(int i = 0; i < n; i++){
      par[i] = i;
      rnk[i] = 0;
    }
  }

  int find(int x)
  {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rnk[x] < rnk[y]){
      par[x] = y;
    }else{
      par[y] = x; 
      if(rnk[x] == rnk[y]) rnk[x]++;
    }
  }

  bool same(int x, int y)
  {
    return find(x) == find(y);
  }
};

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

  vi a(n), b(n);
  rep(i, 0, n) cin >> a[i];
  rep(i, 0, n) cin >> b[i];

  vector<pii> v;
  rep(i, 0, n) v.emplace_back(b[i], a[i]);
  sort(all(v));
  rep(i, 0, n) a[i] = v[i].second, b[i] = v[i].first;

  auto sa = a;
  sort(all(sa));
  rep(i, 0, n){
    if(sa[i] > b[i]){
      cout << "No" << endl;
      return 0;
    }
  }

  rep(i, 0, n-1){
    if(sa[i+1] <= b[i]){
      cout << "Yes" << endl;
      return 0;
    }
  }

  map<int, int> reva;
  rep(i, 0, n) reva[sa[i]] = i;
  for(auto& i : a) i = reva[i];

  UnionFind uf(n);
  rep(i, 0, n) uf.unite(i, a[i]);

  set<int> st;
  rep(i, 0, n) st.insert(uf.find(i));

  if(sz(st) > 1) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}




Measured memory_bytes: 13552
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vs = vector<string>;
#define  rep(i,n) for(ll i = 0; i < (n); ++i)
#define  red(i,n) for(ll i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
#define  yn(a)    cout << ( (a)?"Yes\n":"No\n" )
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll INF = 1e9+9, LINF = 1e18;

int main(){
    ll n,ans=0;
    string s;
    cin>>n>>s;
    ll R[n]={0},B[n]={0},G[n]={0},r=0,b=0,g=0;
    red(i,n){
        r+=(s[i]=='R');
        b+=(s[i]=='B');
        g+=(s[i]=='G');
        R[i]=r;
        B[i]=b;
        G[i]=g;
    }
    rep(i,n-2){
        if(s[i]=='R')for(int j=i+1;j<n-1;j++){
            if(s[j]=='B')ans+=G[j+1]-(j+j-i<n && s[j+j-i]=='G');
            if(s[j]=='G')ans+=B[j+1]-(j+j-i<n && s[j+j-i]=='B');
        }
        if(s[i]=='B')for(int j=i+1;j<n-1;j++){
            if(s[j]=='R')ans+=G[j+1]-(j+j-i<n && s[j+j-i]=='G');
            if(s[j]=='G')ans+=R[j+1]-(j+j-i<n && s[j+j-i]=='R');
        }
        if(s[i]=='G')for(int j=i+1;j<n-1;j++){
            if(s[j]=='R')ans+=B[j+1]-(j+j-i<n && s[j+j-i]=='B');
            if(s[j]=='B')ans+=R[j+1]-(j+j-i<n && s[j+j-i]=='R');
        }
    }
//    rep(i,n)cout<<R[i]<<" ";cout<<endl;
    cout<<ans<<endl;   
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
int main(){long long n,m,i,t=0,p=0,c=0,d=0;
cin>>n>>m;
long long a[n+1]={0},b[n+1]={0};
for(i=0;i<m;i++){long long j,k;
cin>>j>>k;
if(b[j]==0){
    a[j]=k;b[j]=1;
}else if(b[j]==1){
    if(a[j]!=k){
    t=1;break;}
}

}if(t==1)
cout<<-1;
if(n==1&&b[1]==1&&t==0)
cout<<a[1];
if(n==1&&b[1]==0&&t==0)
cout<<0;
else if(n>1&&t==0){
    if(b[1]==1){
        if(a[1]==0)
        p=1;
        
    }else{
        a[1]=1;
    }if(p==1){
        cout<<-1;
    }else{
for(c=2;c<=n;c++){
    if(b[c]==0)
    a[c]=0;
}for(i=1;i<=n;i++){
    cout<<a[i];
}
    }
}



    return 0;
  
}


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

using namespace std;
typedef long long ll;
    
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A;
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }

    int allp = accumulate(A.begin(), A.end(), 0);
    // cout << "allp:" << allp << "\n";
    float toku = (float)allp/(float)(4*M);
    // cout << "toku:" << toku << "\n";

    std::sort(A.begin(), A.end(), greater<int>());

    for (int i = 0; i < M; i++) {
        if (A[i] < toku) {
            std::cout << "No";
            return 0;
        }
    }
    std::cout << "Yes";

    return 0;
}


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

typedef long long ll;
typedef pair<int, int> ii;

const int N = 105;
int n;
ll res;
ii a[N];

inline static bool cmp(ii &a, ii &b) {
    return atan2(a.second, a.first) < atan2(b.second, b.first);
}
inline static ll D(ll x, ll y) {
    return x * x + y * y;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << setprecision(20) << fixed;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a, a + n, cmp);
    for (int i = 0; i < n; ++i) {
        ll x = a[i].first, y = a[i].second;
        res = max(res, D(x, y));
        for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
            x += a[j].first;
            y += a[j].second;
            res = max(res, D(x, y));
        }
    }
    cout << sqrt(res) << endl;

    return 0;
}



Measured memory_bytes: 4088
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::fixed;
using std::pair;
using std::make_pair;
using std::string;
using std::vector;
using std::list;
using std::map;
using std::set;
using std::queue;
using std::priority_queue;
using std::stack;

typedef vector<int> VI;
typedef vector<vector<int> > VII;
typedef vector<string> VS;
typedef pair<int, int> PII;

int gcd (int p, int q) {
    int temp;
    if (q == 0) {
        return p;
    } else {
        temp = p % q;
        p = q;
        q = temp;
        return gcd(p, q);
    }
    return 0;
}

int main(void) {
    int p;
    int q;
    cin >> p >> q;
    q /= gcd(p, q);

    int ans = 1;

    for (int i = 2; i * i <= q; i++) {
        if (q == 1) {
            break;
        }
        if (q % i != 0) {
            continue; 
        }
        while (q % i == 0) {
            q /= i;
        }
        ans *= i;
    }
    cout << ans * q << endl;
    return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
constexpr int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int n,k,in,saidaikouyakusu;
    cin>>n>>k;
    bool s=false;
    vector<int> v;
    for(int i=0;i<n;i++){
        cin>>in;
        v.push_back(in);
        if(in>=k)s=true;
    }
    saidaikouyakusu=v[0];
    for(int i=1;i<n;i++){
        saidaikouyakusu=gcd(saidaikouyakusu,v[i]);
    }
    if(!s||k%saidaikouyakusu)cout<<"IM";
    cout<<"POSSIBLE";
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i < n; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define P pair<int, int>
typedef long long ll;
const ll mod = 1e9+7;

//繰り返し自乗法による累乗計算
//a**n
ll pow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = pow(a, n/2);
    return res * res;
  }
  return a * pow(a, n-1);
}
//繰り返し自乗法によるmod累乗計算
//a**n (mod)
ll modpow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = modpow(a, n/2);
    return res * res % mod;
  }
  return a * modpow(a, n-1) % mod;
}
//組み合わせ
//nCa
ll com(ll n, ll a){
  ll x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  ll res = x / y;
  return res;
}
//組み合わせ(mod)
//nCa (mod)
ll modcom(ll n, ll a){
  ll x = 1, y = 1;
  rep(i, a){
    x = x * (n-i) % mod;
    y = y * (i+1) % mod;
  }
  ll ans = x * modpow(y, mod-2) % mod;
  return ans;
}
//gcd 最大公約数
ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}
//lcm 最小公倍数
ll lcm(ll x, ll y){
  return x * y / gcd(x, y);
}
//ngcd n個の最大公約数
ll ngcd(vector<ll> a){
  ll res;
  res = a[0];
  for(ll i = 1; i < a.size() && res != 1; i++) {
    res = gcd(a[i], res);
  }
  return res;
}
//nlcm n個の最小公倍数
ll nlcm(vector<ll> a) {
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size(); i++) {
    res = lcm(res, a[i]);
  }
  return res;
}
// 素数判定
bool isprime(ll x){
  ll i;
  if(x < 2) return false;
  else if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(i = 3; i*i <= x; i += 2){
    if(x % i == 0) return false;
  }
  return true;
}
// 桁和
ll digsum(ll x){
  ll res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}

int main(){
  string s, t;
  cin >> s >> t;
  vector<char> S(s.size()), T(t.size());
  rep(i,s.size()) S[i] = s[i];
  rep(i,t.size()) T[i] = t[i];
  sort(all(S));
  sort(rall(T));
  rep(i,s.size()) s[i] = S[i];
  rep(i,t.size()) t[i] = T[i];

  if(s < t) cout << "Yes" << endl;
  else cout << "No" << endl;

}



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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t meke_tuple
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a));reverse(all(a))
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) rep(ghf,SZ(a)){rep(kjh,SZ(a[ghf])){cout<<(a[ghf][kjh]<10?" ":"")<<a[ghf][kjh]<<" ";}ENDL;}
#define out(a) cout<<(a)<<endl
#define fi first
#define se second
#define Vec vector
#define P pair
typedef long long ll;
typedef string str;
typedef vector<ll> V;
typedef pair<ll,ll> Pi;
typedef vector<Pi> VP;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int max(int a,int b){if(a>b)return a; return b;}
int min(int a,int b){if(a>b)return b; return a;}
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin>>n;
  int res=0,a,b;
  rep(i,n){
    cin>>a>>b;
    res+=b-a+1;
  }
  out(res);
  
  
  
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1e9;

int gcd(int x, int y){
    int r;
    while((r=x%y) != 0){
        x = y;
        y = r;
    }
    return y;
}

int dfs(int n, int flow, vector<vector<int> >& adj, vector<bool>& used){
	if(n == (int)adj.size()-1){
		return flow;
	}
	for(int i=0; i<(int)adj.size(); i++){
		if(!used[i] && adj[n][i] > 0){
			used[i] = true;
			int ret = dfs(i, min(flow, adj[n][i]), adj, used);
			if(ret > 0){
				adj[n][i] -= ret;
				adj[i][n] += ret;
				return ret;
			}
		}
	}
	return -1;
}

int main(){
	while(1){
		int m,n;
		cin >> m >> n;
		if(m==0) break;
		
		vector<int> cards(m+n+1);
		for(int i=1; i<=m+n; i++) cin >> cards[i];
		
		vector<vector<int> > g(m+n+2, vector<int>(m+n+2, 0));
		for(int i=1; i<=m; i++){
			for(int j=1; j<=n; j++){
				if(gcd(cards[i], cards[m+j]) != 1){
					g[i][m+j] = 1;
				}
			}
		}
		for(int i=1; i<=m; i++) g[0][i] = 1;
		for(int i=m+1; i<=m+n; i++) g[i][m+n+1] = 1;
		
		int ans = 0;
		while(1){
			vector<bool> used(m+n+2, false);
			used[0] = true;
			int ret = dfs(0, inf, g, used);
			if(ret==-1) break;
			ans += ret;
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

int N,K;
int A[110000];
int B[110000];
bool check(int x){
    for(int i=0;i<N;i++)B[i]=A[i]%x;
    sort(B,B+N);
    int s=0,t=N-1;
    int a=0;
    while(s<t){
        a+=B[s];
        while(B[s]>0){
            if(B[s]>=x-B[t]){
                B[s]-=x-B[t];
                B[t]=x;
                t--;
            }else{
                B[t]+=B[s];
                B[s]=0;
            }
        }
        s++;
    }
    return a<=K;
}
signed main() {
    cin>>N>>K;
    for(int i=0;i<N;i++)cin>>A[i];
    int As=0;
    for(int i=0;i<N;i++)As+=A[i];
    int ans=1;
    for(int i=1;i<=sqrt(As)+1;i++){
        if(As%i!=0)continue;
        if(check(i))ans=max(ans,i);
        if(check(As/i))ans=max(ans,As/i);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
// Ivan Carvalho
// Problem H - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
const int MOD = 1e9 + 7;

char entrada[MAXN][MAXN];
int dp[MAXN][MAXN],vis[MAXN][MAXN];
int N,M;

int solve(int x,int y){

	if(x >= N || y >= M) return 0;
	if(entrada[x][y] == '#') return 0;

	if(vis[x][y]) return dp[x][y];
	if(x == N - 1 && y == M - 1) return dp[x][y] = 1;

	vis[x][y] = 1;
	return dp[x][y] = (solve(x+1,y) + solve(x,y+1)) % MOD;

}

int main(){

	scanf("%d %d",&N,&M);
	for(int i = 0;i<N;i++){
		scanf("%s",entrada[i]);
	}

	printf("%d\n",solve(0,0));

	return 0;

}

Measured memory_bytes: 9344
/*
      author  : nishi5451
      created : 14.08.2020 20:36:51
*/

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


int main(){
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int vecx=x2-x1;
    int vecy=y2-y1;
    complex<int> vec(vecx,vecy);
    complex<int> z(0,1),r;
    r = vec*z;
    cout << x2+r.real() << " " << y2+r.imag() << " " << x1+r.real() << " " << y1+r.imag() << endl;



    return 0;
}

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

lst = [-1 for i in range(n)]
print(0)
sex0 = input()
if sex0 == 'Male':
    lst[0] = 1
    leftsex = 1
elif sex0 == 'Female':
    lst[0] = 0
    leftsex = 0
else:
    exit()

print(n-1)
sexn_1 = input()
if sexn_1 == 'Male':
    lst[n-1] = 1
    rightsex = 1
elif sexn_1 == 'Female':
    lst[n-1] = 0
    rightsex = 0
else:
    exit()

left = 0
right = n-1
while left+1 < right:
    mid = (left+right)//2
    print(mid)
    sexmid = input()
    if sexmid == 'Male':
        lst[mid] = 1
        midsex = 1
    elif sexmid == 'Female':
        lst[mid] = 0
        midsex = 0
    else:
        exit()
    
    if (mid-left) % 2 == abs(midsex-leftsex):
        left = mid
        leftsex = midsex
    else:
        right = mid
        rightsex = midsex

Measured memory_bytes: 4588
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;
typedef tuple<int, int, int> T;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
ll digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
ll countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}


int main() {
	IOS;
	string x, y ,z;
	cin >> x >> y >> z;
	char def = 'A' - 'a';
	char a = x[0] + def;
	char b = y[0] + def;
	char c = z[0] + def;
	printf("%c%c%c\n", a,b, c);
}



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

int main(){
  double x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  double dis;
  dis=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
  printf("%.5f\n",dis);
  return 0;
}


Measured memory_bytes: 3288
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

const int N = 2002;

int X[N][N];
int T[N][N];
int MX[N];
vi g[N];
int trn;

int dfs(int c, int p, int d, int id) {
  if(T[id][d] != trn) {
    T[id][d] = trn;
    X[id][d] = 0;
  }
  int res = d;
  X[id][d]++;
  rep(i,0,g[c].size()) {
    int u = g[c][i];
    if(u != p) {
      res = max(dfs(u, c, d+1, id), res);
    }
  }
  return res;
}

int main() {
  int n,K;
  S2(n,K);
  rep(i,0,n-1) {
    int u,v;
    S2(u,v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  if(K == 1) {
    P(n-2);
    return 0;
  }

  int ans = n;
  int half = K / 2;
  vi v;
  if(K & 1) {
    rep(i,1,n+1) {
      trn++;
      int sm = 0;
      int mx = 0;
      rep(j,0,g[i].size()) {
        MX[j] = dfs(g[i][j], i, 1, j);
        for(int k = MX[j] - 1; k > half; k--) {
          X[j][k] += X[j][k+1];
        }
        if(MX[j] >= half + 1) {
          sm += X[j][half + 1];
        }
        if(MX[j] >= half + 2) {
          mx = max(X[j][half + 1] - X[j][half + 2], mx);
        } else if(MX[j] == half + 1) {
          mx = max(X[j][half + 1], mx);
        }
      }
      ans = min(ans, sm - mx);
    }
  } else {
    rep(i,1,n+1) {
      trn++;
      int sm = 0;
      rep(j,0,g[i].size()) {
        MX[j] = dfs(g[i][j], i, 1, j);
        for(int k = MX[j] - 1; k > half; k--) {
          X[j][k] += X[j][k+1];
        }
        if(MX[j] >= half + 1) {
          sm += X[j][half + 1];
        }
      }
      ans = min(ans, sm);
    }
  }
  P(ans);

  return 0;
}

Measured memory_bytes: 16384
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define All(arr) arr.begin(), arr.end()

using namespace std;
typedef long long ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

void Main() {
  Cin(int, n);

  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (sz(to_string(i)) % 2 == 1) ans++;
  }

  cout << ans << endl;
}

int main() {
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, string> pds;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

bool cmp(pds a, pds b) {
	return (a.first == b.first) ? (a.second < b.second) : (a.first > b.first);
}

int main() {
	for (int N; cin >> N&&N;) {
		vector<pds> p;
		for (int i = 0; i < N; i++) {
			string L; int P, A, B, C, D, E, F, S, M;
			cin >> L >> P >> A >> B >> C >> D >> E >> F >> S >> M;
			int Q = (S*F)*M;
			double cp = (double)(Q - P) / (A + B + C + (D + E)*M);
			p.push_back(pds(cp, L));
		}
		sort(p.begin(), p.end(), cmp);
		for (int i = 0; i < p.size(); i++) {
			cout << p[i].second /*<< " " << p[i].first*/ << endl;
		}
		cout << "#" << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

#define ARRAY_MAX 101
#define MOD 1000000007

int main(){

    string s;
    cin >> s;
    //cout << s << endl;
    string ans;
    for(int i = 0;i < (1<<3);i++){

        int tmp = s[0]-'0';
        for(int j = 0;j < 3;j++){
            if((i>>j)&1){
                //足し算
                tmp += (s[j+1]-'0');
            }else{
                tmp -= (s[j+1]-'0');
            }
        }
        //cout << tmp << endl;
        if(tmp == 7){

            ans.push_back(s[0]);
            for(int j = 0;j < 3;j++){

                if((i>>j)&1){
                //足し算
                    ans.push_back('+');
                    ans.push_back(s[j+1]);
                }else{
                    ans.push_back('-');
                    ans.push_back(s[j+1]);
                }
            }
            ans+="=7";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256