akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <utility>
#include <functional>
#include <queue>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>      // std::setprecision
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor_ct.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
using namespace std;
using namespace boost::math;

int main() {
	int M;string D;

	cin >> M >> D;
  
    int d10 = D[0], d1 = D[1], r = 0, d = stoi(D);
  
    for (int i = 22; i <= d; i++)
      if (i % 10 >= 2) {
      auto mul = (i / 10) * (i % 10);
        
      if (mul <= M)
        r++;
    }

	cout << r << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int fish=1e9+7;
int las[500005],N,nex[500005],cnt,Arrive[500005];
void jt(int x,int y)
{
	cnt++;
	nex[cnt]=las[x];
	las[x]=cnt;
	Arrive[cnt]=y;
}
long long dp[200005][2];
void dfs(int x,int fa)
{
    dp[x][0]=dp[x][1]=1;
	for (int i=las[x];i;i=nex[i])
	{
		if (Arrive[i]!=fa)
		{
			dfs(Arrive[i],x);
			dp[x][1]=(dp[x][1]*dp[Arrive[i]][0])%fish;
			dp[x][0]=(dp[x][0]*(dp[Arrive[i]][1]+dp[Arrive[i]][0]))%fish;
		}
	}
}
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N-1;i++)
	  {
	  	int x,y;
	  	scanf("%d%d",&x,&y);
	  	jt(x,y);
	  	jt(y,x);
	  }
	dfs(1,1);
	printf("%lld",(dp[1][0]+dp[1][1])%fish);
	return 0;
}

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

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
const int N = 200001;
const int mod = 998244353;
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(int x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

char ss[N];
int f[N][2][3][3];

int add(int x, int y) {
	x += y;
	return x >= mod ? x - mod : x;
}

int pow_mod(int a, int k) {
	int ans = 1;
	while(k) {
		if(k & 1) ans = (LL)ans * a % mod;
		a = (LL)a * a % mod, k /= 2;
	} return ans;
}

int main() {
	scanf("%s", ss + 1);
	int n = strlen(ss + 1);
	if(n == 2) {
		if(ss[1] != ss[2]) puts("2");
		else puts("1");
		return 0;
	}
	bool bk = 0;
	for(int i = 1; i <= n; i++) {
		if(ss[i] != ss[1]) {bk = 1; break;}
	} if(!bk) {printf("1\n"); return 0;}
	if(n <= 3) {
		if(ss[1] != ss[2] && ss[2] != ss[3]) {
			if(ss[1] == ss[3]) puts("7");
			else puts("3");
		} else puts("6");
		return 0;
	}
	int ans = 0, cc = 1, sum = 0;
	for(int i = 1; i < n; i++) if(ss[i] == ss[i + 1]) cc = 0;
	for(int i = 1; i <= n; i++) sum += ss[i] - 'a';
	sum %= 3;
	f[1][0][0][0] = f[1][0][1][1] = f[1][0][2][2] = 1;
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < 3; k++) if(f[i - 1][0][j][k] || f[i - 1][1][j][k]){
				for(int h = 0; h < 3; h++) {
					if(h == k) f[i][1][(j + h) % 3][h] = add(f[i][1][(j + h) % 3][h], f[i - 1][0][j][k]);
					else f[i][0][(j + h) % 3][h] = add(f[i][0][(j + h) % 3][h], f[i - 1][0][j][k]);
					f[i][1][(j + h) % 3][h] = add(f[i][1][(j + h) % 3][h], f[i - 1][1][j][k]);
				}
			}
		}
	} ans = add(add(f[n][1][sum][0], f[n][1][sum][1]), f[n][1][sum][2]);
	ans = add(ans, cc);
	printf("%d\n", ans);
	return 0;
}


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

using namespace std;
int main(){
	string s;
	cin>>s;
	int a[26]={};
	for(int i=0;i<s.size();i++){
		a[s[i]-'A']++;
	}
	for(int i=0;i<26;i++){
		if(a[i]!=0&&a[i]!=2){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] a = new int[n];
    int[] b = new int[n];
    int[] c = new int[n - 1];
    for(int i = 0; i < n;i++){
      a[i] = sc.nextInt();
    }
    for(int i = 0; i < n;i++){
      b[i] = sc.nextInt();
    }
    for(int i = 0; i < n  - 1;i++){
      c[i] = sc.nextInt();
    }

    int before = -2;
    int score = 0;
    for(int i = 0; i < n;i++){
      score += b[a[i] - 1];
      if(before + 1 == a[i]){
        score += c[before - 1];
      }
      before = a[i];
    }

    System.out.println(score);
  }
}


Measured memory_bytes: 23764
// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

use std::cmp::*;

fn main() {
    let n: u64 = read();
    let h: Vec<u64> = read_vec();
    let mut max_attempt = 0_u64;
    let mut now_attempt = 0_u64;

    if n == 0 { println!("{}", max_attempt); return; }

    for i in 1..n as usize
    {
        if h[i] <= h[i - 1] {
            now_attempt += 1;
        }
        else
        {
            max_attempt = max(now_attempt, max_attempt);
            now_attempt = 0;
        }
    }

    max_attempt = max(now_attempt, max_attempt);
    println!("{}", max_attempt);
}


Measured memory_bytes: 8444
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	long long l, r;
	cin >> l >> r;
	long long minmod = 2019;
	for (long long i = l; i < r; i++) {
		for (long long j = i + 1; j <= r; j++) {
			minmod = min(minmod, (i * j) % 2019);
			if (minmod == 0) {
				cout << 0 << endl;
				return 0;
			}
		}
	}
	cout << minmod << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF (int)1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
	
}

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





signed main(){
	ll n,ans = 0;
	cin >> n;

	ll b[n-1],a[n];
	rep(i,0,n-1) cin >> b[i];

	rep(i,1,n-1){
		a[i] = min(b[i],b[i-1]);
	}

	a[0] = b[0];
	a[n-1] = b[n-2];

	rep(i,0,n) ans += a[i];

	cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=998244353 ;

  

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

Measured memory_bytes: 256
H,W = list(map(int,input().split()))
c = [list(map(int,input().split())) for i in range(10)]
A = [list(map(int,input().split())) for i in range(H)]

#i:始点 j:終点 k:経由する点
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j],c[i][k]+c[k][j])

ans = 0

for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += c[A[i][j]][1]

print(ans)


Measured memory_bytes: 3444
#include<cstdio>

int getCount(int l,int r,int mod,int left){
    if(l%mod<=left) l = l-l%mod+left;
    else l = l+mod-l%mod+left;
    if(l>r) return 0;
    else return (r-l+mod)/mod;
}

long long getComb(long long n,long long m){
    if(m>n || m<0) return 0;
    else{
        long long res = 1;
        for(long long i = n; i > (n-m); i--) res *= i;
        for(int i = 2; i <= m; i++) res /= i;
        return res;
    }
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    long long ans = 0;
    long long cnt = getCount(1,n,k,0);
    ans += cnt*cnt*cnt;
    //printf("ans = %lld\n",ans);
    if(k%2==0){
        cnt = getCount(1,n,k,k/2);
        //printf("cnt = %d\n",cnt);
        ans += cnt*cnt*cnt;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;


ll dp[100010][101][2];

int main(){
    string K;
    cin >> K;
    int d;
    cin >> d;
    dp[0][0][1] = 1;

    int n = K.size();

    for(int i = 1; i <= n; i++){
        rep(j, d){
            int digit = K[i - 1] - '0';
            rep(k, 10){
                dp[i][j][0] += dp[i - 1][((j - k)%d + d) % d][0];
                if (k < digit) dp[i][j][0] += dp[i - 1][((j - k)%d + d) % d][1];
                dp[i][j][0] %= MOD;
            }
            dp[i][j][1] = dp[i - 1][((j - digit)%d + d) % d][1];
            dp[i][j][0] %= MOD;
        }
    }

    cout << (dp[n][0][0] + dp[n][0][1] - 1 + MOD) % MOD << endl;

    return 0;
}

Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i = (ll)(a); i < (ll)(b); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1LL << 60;

int dp[3010][3010];
int main(){
    int n,t; cin >> n >> t;
    vector<pair<int,int>> p(n);
    rep(i,n) cin >> p[i].first >> p[i].second;
    sort(p.begin(), p.end());

    rep(i,3010)rep(j,3010) dp[i][j]=0;
    int ans = 0;
    rep(i,t){
        rep(j,n){
            chmax(dp[i+1][j],dp[i][j]);
            chmax(dp[i][j+1],dp[i][j]);
            int ni = i+p[j].first;
            if(ni<t) chmax(dp[ni][j+1],dp[i][j]+p[j].second);
        }
    }
    rep(j,n){
        chmax(ans,dp[t-1][j]+p[j].second);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 35712
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
#define bit(n,k) ((n>>k)&1) //*n no k bit me 1 or 0*/

const int mx=100010;
//const ll mod=1e9+7;

ll dp[101010],ans[101010];
vector<int> v[101010];
ll mod;
struct LazySegmentTree{
private:
   int n;
   vector<ll> node,lazy;
public:
   LazySegmentTree(int sz,ll init=1){
      n=1;
      while(n<sz)n*=2;
      node.resize(2*n-1,init);
      lazy.resize(2*n-1,1);
   }
 
   void eval(int k,int l,int r){
      if(lazy[k]!=1)node[k]=node[k]*lazy[k]%mod;
      if(r-l>1){
          (lazy[2*k+1]*=lazy[k])%=mod;
          (lazy[2*k+2]*=lazy[k])%=mod;
      }
      lazy[k]=1;
   }
      //[a,b)にxを加算
   void add(int a,int b,ll x,int k=0,int l=0,int r=-1){
       if(r<0)r=n;
       eval(k,l,r);
       if(r<=a||b<=l)return;
       if(a<=l&&r<=b){
          (lazy[k]*=x)%=mod;
          eval(k,l,r);
       }
       else {
          add(a,b,x,2*k+1,l,(l+r)/2);
          add(a,b,x,2*k+2,(l+r)/2,r);
          node[k]=node[2*k+1]*node[2*k+2]%mod;
        }
   }
   //[a,b)での和を返す
   ll get(int a,int b,int k=0,int l=0,int r=-1){
      if(r<0)r=n;
      eval(k,l,r);
      if(r<=a||b<=l)return 1;
      if(a<=l&&r<=b)return node[k];
      ll xl=get(a,b,2*k+1,l,(l+r)/2);
      ll xr=get(a,b,2*k+2,(l+r)/2,r);
      return xl*xr%mod;
   }
};
 
 
ll dfs1(int x,int p){
    ll ret=1;
    int n=v[x].size();
    rep(i,n){
        int to=v[x][i];
        if(to==p)continue;
        ll res=dfs1(to,x);
        (ret*=(res+1))%=mod;
    }
    dp[x]=ret;
    return ret;
}
 
 
void dfs2(int x,int p){
    ll ret=ans[x]+1;
    int n=v[x].size();
    LazySegmentTree sg(n);
    rep(i,n){
        int to=v[x][i];
        if(to==p)continue;
        (ret*=(dp[to]+1))%=mod;
        sg.add(0,i,dp[to]+1);
        sg.add(i+1,n,dp[to]+1);
    }
    sg.add(0,n,ans[x]+1);
    rep(i,n){
        int to=v[x][i];
        if(to==p)continue;
        else ans[to]=sg.get(i,i+1);
    }
    for(auto to:v[x]){
        if(to==p)continue;
        dfs2(to,x);
    }
    ans[x]=ret%mod;
}



int main(){
  int n;
  cin >> n >> mod;
  rep(i,n-1){
    int x,y; cin>>x>>y; x--; y--;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  dfs1(0,-1);
  dfs2(0,-1);
  rep(i,n)cout<<ans[i]<<endl;
  return 0;
}

Measured memory_bytes: 30208
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i=0;i<(n);++i)
#define fore(i,a) for(auto &i:a)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define ALL(x) (x).begin(),(x).end()
signed _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
using P=pair<int,int>;
int gcd(int a,int b) {return __gcd(a,b);}//if you use gcc to compile, use this

signed _main(){
  int N,K; cin >> N >> K;
  v<int> A(N);
  int maxi=0;
  rep(i,N){
    cin >> A[i];
    chmax(maxi,A[i]);
  }
  if(K>maxi){
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  int num=A[0];
  rep(i,N){
    num=gcd(num,A[i]);
  }
  if(K%num==0){
    cout << "POSSIBLE" << endl;
  }
  else{
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  int w,h;
  int p[SIZE],q[SIZE];
  ll sum_p=0,sum_q=0;
  
  scanf("%d%d",&w,&h);
  
  for(int i=0;i<w;i++){
    scanf("%d",p+i);
    sum_p += p[i];
  }
  for(int i=0;i<h;i++){
    scanf("%d",q+i);
    sum_q += q[i];
  }

  sort(p,p+w);
  sort(q,q+h);

  int t=0,s=0;
  ll ans = 0;
  
  for(int i=0;i<w+h;i++){
    if(t<w && s<h){
      if(p[t] < q[s]){
        ans += (ll)p[t] * (h+1 - s);
        t++;
      }else{
        ans += (ll)q[s] * (w+1 - t);
        s++;
      }
    }else{
      if(t<w){
        ans += (ll)p[t] * (h+1 - s);
        t++;
      }else{
        ans += (ll)q[s] * (w+1 - t);
        s++;
      }
    }
  }
  
  printf("%lld\n",ans);
  
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <utility>
using namespace std;

int main() {
	int N,M;
	cin >> N >> M;
	pair<long long, long long> p[M];
	int a=0; int b=0;
	for(int i=0; i<M; i++){
		cin >> p[i].first >> p[i].second;
		if(p[i].first==1){a++;}
		if(p[i].second==N){b++;}
		
	}
	
	int A[a]={};
	int B[b]={};
	
	int pa=0;
	int pb=0;
	for(int i=0;i<M;i++){
		if(p[i].first==1){A[pa]=p[i].second; pa++;}
		if(p[i].second==N){B[pb]=p[i].first; pb++;}	
	}
	
	sort(A,A+a);
	sort(B,B+b);
	
	
	for(int i=0; i<b; i++){
		if(binary_search(A,A+a,B[i])){
			cout<<"POSSIBLE"<<endl;
			return 0;
			
		}
	}
	
	cout<<"IMPOSSIBLE"<<endl;
	return 0;
}

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

int main(){
  
  int A,B,C,D,R,L;
  
  cin >> A >> B >> C >> D;
  L = A + B;
  R = C + D;
  
  if (L > R){
    cout << "Left" << endl;
  }
  
  else if ( L == R ){
    cout << "Balanced" <<endl;
  }
  
  else {
    cout << "Right" <<endl;
  }
}
  


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  cin>>H>>W;
  vector<vector<char>> vvc;
  vvc=vector<vector<char>>(H,vector<char>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>vvc.at(i).at(j);
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<2;j++){
      for(int k=0;k<W;k++){
        cout<<vvc.at(i).at(k);
      }
      cout<<endl;
    } 
  }
}

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

#include <iostream>
using namespace std;

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

    int a, b, c;

    a = n / 100;
    c = n % 10;
    b = (n % 100) / 10;

    if (a == 7 || b == 7 || c == 7) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;


}

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

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


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
using ll = long long;



int main() {
	int n,a,b,sum=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		sum += (b - a+ 1);
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

const int mod = 1000000007;
struct mint {
    long long x;
    mint(long long 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(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    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;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int h, w;
    cin >> h >> w;
    vector<mint> dp(w);
    dp[0] = 1;
    rep(i, h) {
        string a;
        cin >> a;
        vector<mint> pre(w);
        swap(dp, pre);
        rep(j, w) {
            if (a[j] == '#') continue;
            dp[j] += pre[j];
            if (j-1 >= 0) dp[j] += dp[j-1];
        }
    }
    cout << dp[w-1] << endl;
}

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

int main(void){
  char s[27];
  scanf("%s", s);
  int a[26] = {0};
  
  for(int i = 0; i < strlen(s); i++){
    a[s[i] - 'a']++;
  }
  
  for(int i = 0; i < 26; i++){
    if(a[i] > 1){
      printf("no\n");
      return 0;
    }
  }
  
  printf("yes\n");
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define ld long double
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,a) REP(i,0,a)
#define REV(i,a,b) for(i=a-1;i>=b;i--)
#define rev(s) reverse(s.begin(),s.end())
#define pb push_back
#define mp make_pair
#define ord(v) sort(v.begin(),v.end());
const ll MAXN=1e7+5;
#define MAX 2*1e9
#define fi first
#define se second
#define pi 3.141592653589793238
#define rem 1000000007
#define eps 1e-9
bool pos[MAXN];
    ll va[MAXN];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ll n,we,i,j,W=0;
    cin>>n>>we;
    ll w[n],v[n];
    rep(i,n)
    {
        cin>>w[i]>>v[i];
        W+=w[i];

    }
    // cout<<n<<endl;
    // rep(i,n)
    // cout<<w[i]<<" ";
    // cout<<endl;
     // cout<<W<<endl;
    ll temp=0;
    rep(i,W+1)
    {
        pos[i]=0;
        va[i]=0;
    }
    pos[0]=1;
    va[0]=0;
    REP(i,1,n+1)
    {
        REV(j,W+1,0)
        {
            if(pos[j])
             {//   cout<<i<<" "<<j<<" "<<w[i-1]<<endl;
                pos[j+w[i-1]]=1;
                va[j+w[i-1]]=max(va[j+w[i-1]],va[j]+v[i-1]);
            }

        }
    }
    rep(i,we+1)
    {
        temp=max(temp,va[i]);
    }
    cout<<temp<<endl;





    return 0;
}

Measured memory_bytes: 45804
import sys
input = sys.stdin.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            px = find(par[x])
            wei[x] += wei[par[x]]
            par[x] = px
            return px

    def weight(x):
        find(x)
        return wei[x]

    def unite(x, y, w):
        w += wei[x] - wei[y]
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            # sizeの大きいほうがx
            if par[x] > par[y]:
                x, y = y, x
                w = -w
            par[x] += par[y]
            par[y] = x
            wei[y] = w
            return True

    def same(x, y):
        return find(x) == find(y)

    def size(x):
        return -par[find(x)]

    def diff(x, y):
        return weight(y) - weight(x)

    n, m = map(int, input().split())
    # 初期化
    par = [-1] * n
    wei = [0] * n
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if same(l, r):
            if diff(l, r) != d:
                print('No')
                sys.exit()
        else:
            unite(l, r, d)
    print('Yes')
    
if __name__ == '__main__':
    main()


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

int main(){
	int a,b,c,q;
	cin >> q;
	auto f=[&]{
		cin >> a >> b >> c;
		int x = max({a,b,c});
		int y = min({a,b,c});
		int z = a+b+c-x-y;
		if((x*x)==(y*y+z*z)){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	};
	while(q--){
		f();
	}
}


Measured memory_bytes: 3084
N,K = map(int, input().strip().split())
R,S,P = map(int, input().strip().split())
T = input().strip()
score = 0


for i in range(0,K):
    s = [T[k + i] for k in range(0,N,K) if k + i < len(T)]
    prev_e = ''
    for e in s:
      if prev_e != e:
        if e == 'r':
          score += P
        if e == 's':
          score += R
        if e == 'p':
          score += S
        prev_e = e
      else:
        prev_e = ''

print(score)
    
      

Measured memory_bytes: 4212
#00:33
t = int(input())
for _ in range(t):
  a,b,c,d = map(int,input().split())
  if d - b < 0:
    print('No')
    continue
  if a - b < 0:
    print('No')
    continue
  big = int(b)
  sml = int(d)
  while sml != 0:
    big,sml = sml,big%sml
  gcd = big
  r = (a-c-1) % gcd + 1
  if r + c >= b:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 3064
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  vector<vector<int>> a(3, vector<int>(3));
  rep(i, 3) rep(j, 3) cin >> a[i][j];
  int n;
  cin >> n;
  map<int, bool> b;
  rep(i, n) {
    int p;
    cin >> p;
    b[p] = true;
  }

  bool flag = true;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      if (!b[a[i][j]]) flag = false;
    }
    if (flag) {
      cout << "Yes" << endl;
      return 0;
    }
    flag = true;
  }

  flag = true;
  rep(i, 3) {
    rep(j, 3) {
      if (!b[a[j][i]]) flag = false;
    }
    if (flag) {
      cout << "Yes" << endl;
      return 0;
    }
    flag = true;
  }

  if ((b[a[0][0]] && b[a[1][1]] && b[a[2][2]]) || (b[a[0][2]] && b[a[1][1]] && b[a[2][0]])) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;
}

Measured memory_bytes: 256
import sys

inp = [int(x) for x in sys.stdin.read().split()]
ii = 0

r, c, k = inp[ii:ii+3]
ii += 3
v=[0] * (c * r)
for _ in range(k):
    ri,ci,a = inp[ii:ii+3]
    ii += 3
    v[(ri-1)*c + (ci-1)]=a
dp= [0] * (c * r * 4)
x = c * r
if v[0]>0: dp[x] = v[0]

for i in range(r):
    for j in range(c):
        idx = i*c+j
        idx2 = (i-1)*c + j
        idx3 = i*c + j-1
        val = v[idx]
        if i>0:
            a = max(dp[idx2],dp[x + idx2],dp[2*x+idx2],dp[3*x+idx2])
            dp[idx]= a
            dp[x+idx]= a + val

        if j>0:
            dp[idx]=max(dp[idx],dp[idx3])
            dp[x + idx]=max(dp[x + idx],dp[idx3]+val,dp[x + idx3])
            dp[2*x + idx]=max(dp[x+idx3]+val,dp[2*x+idx3])
            dp[3*x + idx]=max(dp[2*x+idx3]+val,dp[3*x+idx3])


ans=0
for i in range(4): ans = max(dp[i*x + (r-1)*c + (c-1)],ans)
print(ans)



Measured memory_bytes: 461624
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val a = (0 until n).map { sc.next().toLong() }
    println(problem059c(n, a))
}

fun problem059c(n: Int, aArg: List<Long>): Long {
    val count1 = compute(n, aArg)
    val a = aArg.toMutableList()
    val a0 = a[0]
    var count = 0L
    if (a0 > 0) {
        val tmp = a0 + 1
        a[0] = a0 - tmp
        count += tmp
    } else {
        val tmp = a0 - 1
        a[0] = a0 - tmp
        count -= tmp
    }
    val count2 = compute(n, a) + count
    return Math.min(count1, count2)
}

fun compute(n: Int, aArg: List<Long>): Long {
    val a = aArg.toMutableList()
    var count = 0L
    var sum = 0L
    for (i in 0 until n) {
        if (sum + a[i] == 0L) {
            count++
            if (a[i] < 0) {
                a[i] = a[i] + 1
            } else {
                a[i] = a[i] - 1
            }
        }
        sum += a[i]
        if (i >= n - 1) {
            continue
        }
        val ai2 = a[i + 1]
        val sum2 = sum + ai2
        if (sum * sum2 < 0) {
            continue
        }
        if (sum > 0) {
            val tmp = sum + 1
            a[i + 1] = tmp * -1
            count += tmp + ai2
        } else {
            val tmp = Math.abs(sum - 1)
            a[i + 1] = tmp
            count += tmp - ai2
        }
    }
    return count
}

Measured memory_bytes: 52460
#include <iostream>
#include <vector>
//#include "../cxx-prettyprint/prettyprint.hpp"

int main() {
    int N, K;
    std::cin >> N >> K;

    if ((N - 1) % (K - 1) == 0) {
        std::cout << (N - 1) / (K - 1) << std::endl;
    } else {
        std::cout << (N - 1) / (K - 1) + 1 << std::endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N,M;
  cin >> N >> M;
  v(string) A(N);
  v(string) B(M);
  rep(i,N) {
    cin >> A[i];
  }
  rep(i,M) {
    cin >> B[i];
  }
  rep(bi,N-M+1) rep(bj,N-M+1) {
    if(B[0][0] != A[bi][bj]) continue;
    bool ok=true;
    rep(i,M) rep(j,M) {
      if(B[i][j] != A[i+bi][j+bj]) {
        ok = false;
      }
    }
    if(ok) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):

    res = A + B
    if res < A - B:
        res = A - B
    if res < A * B:
        res = A * B

    print(res)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let mut buffer = read::<String>();
  let mut dist = HashMap::new();
  for c in buffer.trim().chars() {
    let count = dist.entry(c).or_insert(0);
    *count += 1;
  }
  if dist.len() == 2 && dist.values().all(|x| *x == 2) {
    println!("Yes");
  } else {
    println!("No");
  }
}



Measured memory_bytes: 4352
package main

import "fmt"

func main() {

	var a, b, c int
	fmt.Scan(&a, &b, &c)
	minResult := 0
	if a+b <= a+c && a+b <= b+c {
		minResult = a + b
	} else if a+c < a+b && a+c <= b+c {
		minResult = a + c
	} else {
		minResult = b + c
	}
	fmt.Println(minResult)

}


Measured memory_bytes: 512
#include <cstdio>

using namespace std;

int main() {
    int n;
    int ans = 0;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] % 2) {
            printf("0\n");
            return 0;
        }
    }
    while(1) {
        ans++;
        for (int i = 0; i < n; i++) {
            a[i] /= 2;
            if (a[i] % 2) {
                printf("%d\n", ans);
                return 0;
            }
        }
    }
}


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

int main() {
    int N;
    scanf("%d", &N);
    priority_queue<int> card;
    for (int i = 0; i < N; i++) {
        int score;
        scanf("%d", &score);
        card.push(score);
    }
    int a_score = 0;
    int b_score = 0;
    while(!card.empty()) {
        a_score += card.top();
        card.pop();
        if (card.empty()) break;
        b_score += card.top();
        card.pop();
    }
    printf("%d", a_score - b_score);
}

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

int main()
{
	int n;
	int i,j,k;
	int val[4][37];
	for (i = 0; i < 10; i += 1)
	{
		val[0][i] = 1;
		val[1][i] = 0;
		val[2][i] = 0;
		val[3][i] = 0;
	}
	for (; i < 37; i += 1)
	{
		val[0][i] = 0;
		val[1][i] = 0;
		val[2][i] = 0;
		val[3][i] = 0;
	}
	for(i = 0;i < 3;i++)
	{
		for(j = 0;j < 37;j++)
		{
			for(k = j;k <= ((j>27)?37:j+9);k++)
			{
				val[i+1][k] += val[i][j];
			}
		}
	}
	while(scanf("%d",&n) != EOF)
	{
		if(n > 36)
			printf("0\n");
		else
			printf("%d\n",val[3][n]);
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

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

    int count = 0;
    while (true) {
        bool can = true;
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 != 0) {
                can = false;
            }
        }
        if (!can) {
            break;
        }
        for (int i = 0; i < n; i++) {
            a[i] /= 2;
        }
        count++;
    }
    cout << count << endl;
    return 0;
}


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

int main()
{
    char arr[5];
    scanf("%s",&arr);
    
    strcmp(arr, "SUN") == 0?printf("7"):0;
	strcmp(arr, "MON") == 0?printf("6"):0;
	strcmp(arr, "TUE") == 0?printf("5"):0;
	strcmp(arr, "WED") == 0?printf("4"):0;
	strcmp(arr, "THU") == 0?printf("3"):0;
	strcmp(arr, "FRI") == 0?printf("2"):0;
	strcmp(arr, "SAT") == 0?printf("1"):0;	
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
using namespace std;

int main(){
	int h, w;

	while(1){
		cin >> h >> w;
		if(h == 0 && w == 0) break;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				putchar('#');
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3100
#include <stdlib.h>
#include <stdio.h>
#define REP(i, n) for(i = 0; i < n; ++i)
#define FOR(i, a, b) for(i = a; i < b; ++i)

typedef unsigned long long ull;

void yes_or_no(char boolean){
    if(boolean){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
}

ull gcd(ull a, ull b){
    if(a < b){
        return gcd(b, a);
    }
    ull r = a % b;

    while(r > 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main(){
    int i, N;
    scanf("%d", &N);

    ull T[N], temp, ans;

    scanf("%lld", &T[0]);
    ans = T[0];

    FOR(i, 1, N){
        scanf("%lld", &T[i]);
        temp = gcd(T[i], ans);
        ans *= T[i] / temp;
    }

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

Measured memory_bytes: 128
/******************************************************************************

                         بسم الله الرحمن الرحيم
                     Author: Mst: Mhamuda Khatun
                               RUCSE27

*******************************************************************************/

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pi 2*acos(0.0)
#define f first
#define s second
#define pb push_back
#define gap ' '
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mod 1000000007
#define MAX 1000000000000
#define N 305

int main()
{
    fastio;
    int a,b,c,d,x,y;
    cin>>a>>b>>c>>d;

    x= (a+d-1)/d;
    y=(c+b-1)/b;

    cout<<(y<=x?"Yes":"No");
    cout<<"\n";
    return 0;   //:D
}




Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
char a[10][10];
int u;
int n,m;
void dfs(int x,int y){
	a[x][y]='.';
	if(x==n&&y==m) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(a[i][j]=='#')
					return;
			}
		}
		u=1;
		return;
	}
	int o=0;
	if(a[x][y+1]=='#') {
		dfs(x,y+1);
		a[x][y+1]='#';
		o=1;
	}
	if(a[x+1][y]=='#') {
		dfs(x+1,y);
		a[x][y+1]='#';
		o=1;
	}
	if(o==0)
	return;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	dfs(1,1);
	if(u==1) {
		cout<<"Possible"<<'\n';
		return 0;
	}
	else {
		cout<<"Impossible"<<'\n';
		return 0;
	}
	return 0;
}


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

#define mod 1000000007

int main()
{
	long long m, n;
	long long power2[40]{};
	scanf("%lld%lld", &m, &n);
	power2[0] = 1;
	power2[1] = m;
	for (int i = 2; i < 40; i++)
	{
		power2[i] = power2[i - 1] * power2[i - 1] % mod;
	}
	long long ans{1};
	for (int i = 1; i < 40 && n; i++)
	{
		if (n & 1)
		{
			ans = ans * power2[i] % mod;
		}
		n >>= 1;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
int a[100020];
int f[100020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		f[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		f[F(x)] = F(y);
	}
	for (int i = 1; i <= n; i++) {
		if (F(i) == F(a[i])) {
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
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(int i=0;i<n;i++)
#define all(a)  (a).begin(),(a).end()
#define P pair<int, int>
#define ll long long
const int MOD = 1000000007;
//bitset<64>(x).count()
//fixed << setprecision(15) << 

int main (){
  int d, n;
  cin >> n >> d;
  int x[n][d];
  rep(i, n){
    rep(j,d){
      cin >> x[i][j];
    }
  }
  int ans = 0;
  rep(i, n){
    for(int j=i+1;j<n;j++){
      int tmp = 0;
      rep(k, d)
        tmp += pow((double)(x[i][k]-x[j][k]),2);
      bool check = false;
      for(int k=1;k<=tmp;k++){
        if(pow((double)(k),2)==tmp)
          check = true;
      }
      if(check) ans++;
    }
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <cfloat>
#include <cmath>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define INF INT_MAX
#define BINF DBL_MAX

int main(){
	string s;
	while (cin >> s){
		int x[11][11] = {};
		rep(i, 10) x[0][i] = s[i] - '0';
		for (int i = 1; i < 10; i++){
			for (int j = 0; j < 10 - i; j++){
				x[i][j] = (x[i - 1][j] + x[i - 1][j + 1]) % 10;
			}
		}
		cout << x[9][0] << endl;
	}
	return 0;
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
#define rep(n) for (int I = 0; (I) < (n); ++(I) )
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define dump(x) cout << " " << #x << "=" << x
#define vdump(v) for(size_t T=0; T<v.size(); ++T){cout << " " << #v << "[" << T << "]=" << v[T];} cout << endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    string a, b;
    cin >> a >> b;
    repeat(i, (int)b.length()) {
        cout << a[i] << b[i];
    }
    if (a.length() > b.length())
        cout << a.back();
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
#define endl "\n"
struct dsu{
    int g[N];
    void init(){for(int i=0;i<=N;i++)g[i]=i;}
    int find(int x){return x==g[x]?x:g[x]=find(g[x]);}
    void uni(int u,int v){
        int pu=find(u),pv=find(v);
        if(pu!=pv)g[pu]=pv;
    }
}dis;
int main(){
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n,q;cin>>n>>q;
    dis.init();
    while(q--){
        int mode;cin>>mode;
        int u,v;cin>>u>>v;
        if(mode==0){
            dis.uni(u,v);
        }
        else{
            if(dis.find(u)==dis.find(v))cout<<1<<endl;
            else cout<<0<<endl;
        }
    }
}


Measured memory_bytes: 4360
void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
#include <limits.h>
#include <iomanip>
#include <stack>

using namespace std;
using namespace boost::multiprecision;

int dp[51][51][101];
int N, K;
int V[50];

void solve() {
	cin >> N >> K;
	for (int n = 0; n < N; n++)cin >> V[n];
	for (int l = 0; l < N; l++) {
		for (int r = l + 1; r <= N; r++) {
			dp[l][r][0] = 0;
		}
	}
	for (int k = 1; k <= K; k++) {
		for (int l = 0; l < N; l++) {
			dp[l][l + 1][k] = V[l] * (k%2);
			for (int r = l + 2; r <= N; r++) {
				dp[l][r][k] = max(V[l]+dp[l+1][r][k-1],
								  V[r-1]+dp[l][r-1][k-1]);
				if (k - 2 >= 0) {
					dp[l][r][k] = max(dp[l][r][k],
						dp[l + 1][r][k - 2]);
					dp[l][r][k] = max(dp[l][r][k],
						dp[l][r-1][k - 2]);
				}
			}
		}
	}
	int m = 0;
	for (int k = 0; k <= K; k++)m = max(m, dp[0][N][k]);
	cout << m << endl;
	return;
}

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

lo n,m,b[li],a[li],k,flag,t;
lo cev;
string s;
vector<int> v;

int main(void){
	scanf("%lld %lld %lld",&n,&m,&k);
	cev=m*n;
	printf("%lld\n",min(cev,k));
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    ll k, n;
    cin >> k >> n;
    vector<ll> v(n+2);
    rep(i, 1, n+1)
        cin >> v[i];
    if (v[1] == 0)
    {
        v[n+1] = k;
        ll maxi = 0;
        ll sum = 0;
        ll x = 0;
        rep(i, 1, n+1)
        {
            x = abs(v[i+1] - v[i]);
            maxi = max(maxi, x);
            sum += x;
        }
        cout << sum - maxi;
    }
    else 
    {
        v[0] = 0;
        v[n+1] = k;
        ll maxi = 0;
        ll sum = 0;
        ll x = 0;
        rep(i, 0, n+1)
        {
            x = abs(v[i+1] - v[i]);
            maxi = max(maxi, x);
            sum += x;
        }
        maxi = max(k - v[n] + v[1], maxi);
        cout << sum - maxi;
    }
    return 0;
}

Measured memory_bytes: 1792
N, *m=map(int, open(0).read().split())

im = iter(m)
UVW = list(zip(im, im, im))

# set default color to -1

colors = {i:-1 for i in range(1,N+1)}
u,v,w = UVW[0]
colors[u] = 0

def opposite(u, v):
    if v == -1:
        return u
    if v == 0:
        return 1
    if v == 1:
        return 0

def same(u, v):
    if v == -1:
        return u
    else:
        return v

while -1 in colors.values():
    next_UVW = []
    for u, v, w in UVW:
        if colors[u] == -1 and colors[v] == -1:
            next_UVW.append((u, v, w))
            continue

        if w % 2 == 0:
            colors[u] = same(colors[u], colors[v])
            colors[v] = same(colors[v], colors[u])

        if w % 2 == 1:
            colors[u] = opposite(colors[u], colors[v])
            colors[v] = opposite(colors[v], colors[u])

        if colors[u] == -1 or colors[v] == -1:
            next_UVW.append((u,v,w))

    UVW = next_UVW



for i in range(1, N+1):
    print(colors[i])

Measured memory_bytes: 136304
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int n, t[400005];

void inc(int x, int v) {
    t[x += n] = v;
    for (x >>= 1; x; x >>= 1) t[x] = max(t[x << 1], t[x << 1 | 1]);
}

int que(int l, int r) {
    int z = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) z = max(z, t[l++]);
        if (r & 1) z = max(z, t[--r]);
    }
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    int d[200005] = {}, z[200005] = {};
    pii a[200005] = {};
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    sort(a, a + n);
    a[n].first = mod + mod;
    inc(n - 1, n);
    z[n] = 1;
    z[n - 1] = 2;
    for (int i = n - 2; i >= 0; i--) {
        int c = (int)(lower_bound(a, a + n, make_pair(a[i].first + a[i].second, 0)) - a);
        d[i] = max(i + 1, que(i, c));
        z[i] = z[i + 1] + z[d[i]];
        if (z[i] >= 998244353) z[i] -= 998244353;
        inc(i, d[i]);
    }
    cout << z[0];
}


Measured memory_bytes: 7560
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(), (x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int n;
  cin >> n;

  int digit = log10(n);
  int ans = 0;
  REP(i, digit)
  {
    if (i % 2 == 0)
    {
      int num = pow(10, i + 1) - pow(10, i);
      ans += num;
    }
  }
  // cout << ans << endl;
  if (digit % 2 == 0)
  {
    ans += n - pow(10, digit) + 1;
  }
  cout << ans << endl;
}


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

ll gcd(ll a, ll b){
	if (a == 0) return b;
	return gcd(b  %a, a);
}

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

ll grid[1004][1004] , dp[1004][1004];
ll h,w;

bool is_valid(ll a, ll b)
{
	return (a > -1 && b > -1 && a < h && b < w && grid[a][b] == 0);
}

ll solve()
{
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;

	ll mod = 1e9 + 7;
	for(ll i=0;i<h;i++)
	{
		for(ll j=0;j<w;j++)
		{
			if(grid[i][j] == 0)
			{
				if(is_valid(i,j-1))
				{
					dp[i][j] += dp[i][j-1];
					dp[i][j] %= mod;
				}

				if(is_valid(i-1,j))
				{
					dp[i][j] += dp[i-1][j];
					dp[i][j] %= mod;
				}
			}
		}
	}

	return dp[h-1][w-1];
}

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

	cin >> h >> w;

	ll i,j;

	for(i=0;i<h;i++)
	{
		string s;
		cin >> s;
		for(j=0;j<w;j++)
		{
			if(s[j] == '.')
				grid[i][j] = 0;
			else
				grid[i][j] = 1;
		}
	}

	cout << solve() << endl;	

}

Measured memory_bytes: 16000
from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
s = [n-1]

for i in range(1, n-1):
    s.append(s[0] - i - (a[i] - a[0]))

s.sort()
ans = 0
t = [a[0] + a[i] for i in range(1, n)]
for i, x in enumerate(t[::-1]):
    v = x + i
    ans += bisect_right(s, v) - bisect_left(s, v)

print(ans)


Measured memory_bytes: 111104