akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MAX 500000
#define SEN 2000000000
void merge(int *,int,int,int,int);
void mergeSort(int *,int,int,int);



int L[MAX/2+2],R[MAX/2+2],count;

int main(){
  int H[MAX],n,i;
  count=0;

  scanf("%d",&n);
  for(i=0;i <= n-1;i++){
    scanf("%d",&H[i]);
  }
  mergeSort(H,n,0,n);
  for(i=0;i <= n-1;i++){
    if(i>0)printf(" ");
    printf("%d",H[i]);
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
}
void merge(int *H,int n,int l,int m,int r){
  int n1,n2,i,j,k;
  n1=m-l;
  n2=r-m;
  for(i=0;i<n1;i++){
L[i]=H[l+i];
  }
  for(i=0;i<n2;i++){
R[i]=H[m+i];
  }
  L[n1]=R[n2]=SEN;
  i=0;
  j=0;
  for(k=l;k<r;k++){
    count++;
    if(L[i]<=R[j]){
      H[k]=L[i++];
    }
    else{
      H[k]=R[j++];
    }}}

void mergeSort(int *H,int n,int l,int r){
  if(l+1 < r){
    int m;
    m=(l+r)/2;
    mergeSort(H,n,l,m);
    mergeSort(H,n,m,r);
    merge(H,n,l,m,r);
  }}



Measured memory_bytes: 5616
use proconio::{input, fastout};

const MAX: i64 = 1_000;

#[fastout]
fn main() {
    input! {
        x: i64,
    }

    let mut v = vec![];
    let mut index = vec![];

    for i in -MAX..MAX {
        index.push(i);
        v.push(i.pow(5));
    }

    for i in 1..v.len() {
        for j in 0..i+1 {
            if v[i] - v[j] == x {
                println!("{} {}", index[i], index[j]);
                return;
            }
        }
    }
}

Measured memory_bytes: 2244
use std::io::stdin;
use std::collections::HashMap;
use std::cmp::max;

fn main() {
    let (N, W): (usize, usize) = {
        let mut line = String::new();
        stdin().read_line(&mut line).unwrap();
        let nw = line.split_whitespace().map(|s| s.parse().unwrap()).collect::<Vec<_>>();
        (nw[0], nw[1])
    };

    let things: Vec<(usize, usize)> = (0..N)
        .map(|_| {
                 let mut line = String::new();
                 stdin().read_line(&mut line).unwrap();
                 let wv = line.split_whitespace().map(|s| s.parse().unwrap()).collect::<Vec<_>>();
                 (wv[0], wv[1])
             })
        .collect();

    let mut dp = HashMap::new();
    dp.insert(0, 0);

    for (w, v) in things {
        for (dp_w, dp_v) in dp.clone() {
            let new_w = w + dp_w;
            if new_w <= W {
                let new_v = max(*dp.get(&new_w).unwrap_or(&0), dp_v + v);
                dp.insert(new_w, new_v);
            }
        }
    }

    println!("{}", dp.values().max().unwrap());
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <numeric>
#include <type_traits>

using namespace std;

int gcd(int a, int b){
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return b ? gcd(b, a % b) : a;
}

int main(){
    int N,X;
    int tmp,tmp_abs;
    int gcd_num;
    int ans;
    vector<int> x;
    bool flag = true;

    cin >> N >> X;
    for(int i = 0; i < N; i++){
        cin >> tmp;
        tmp_abs = abs(X - tmp);
        x.push_back(tmp_abs);
    }
    gcd_num = x.front();
    for(int i : x){
        gcd_num = gcd(i,gcd_num); 
    }

    cout << gcd_num << endl;
}

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

map<int,int>vis;
vector<int>v,vt,vk,r;
int n;
bool check()
{
  int i;
  for(i=0; i<n; i++)
  {
    if(vk[i]!=r[i])return false;
  }
  return true;
}

int fact(int n)
{
  int f=1,i;
  for(i=1; i<=n; i++)
  {
    f=f*i;
  }
  return f;
}

int main()
{
  int m, a, ok=0, res=0, flag=0,pos1=1,pos2=1, i;
  cin>>n;

  for(i=0; i<n; i++)
  {
    cin>>m;
    v.push_back(m);
  }
  for(i=0; i<n; i++)
  {
    cin>>m;
    vt.push_back(m);
  }
  for(i=1; i<=n; i++)
  {
    vk.push_back(i);
  }
 int f=fact(n);
  for(i=1;i<f;i++)
  {
    next_permutation(vk.begin(),vk.end());
    r=v;
    if(check()){
      pos1=i+1;
      flag++;
      r.clear();
    }
    r=vt;

    if(check()){
      pos2=i+1;
      flag++;
      r.clear();
    }
    if(flag==2)break;
  }
  cout<<abs(pos1-pos2)<<endl;

}


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

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

template<class T, class U> void chmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> void chmin(T &a, U b) { if (b < a) a = b; }

using ll = long long;
using ld = long double;
using namespace std;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int a, b, c, d; cin >> a >> b >> c >> d;

  cout << min(a, b) + min(c, d) << endl;
  
  return (0);
}

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

int main() {

	char a[3];
	int i;

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

	for (i = 0; i < 3; i++) {
		if (a[i] == '1') {
			a[i] = '9';
		}
		else if (a[i] == '9') {
			a[i] = '1';
		}
		cout << a[i];
	}

	return 0;
}

Measured memory_bytes: 760
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

ll modpow(ll a, ll n, ll m){
    if(n == 0) return 1;
    ll half = modpow(a,n/2,m);
    ll res = half * half % m;
    if(n & 1) res = res * (a%m) % m;
    return res;
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


int N;
vector<vector<int>> G;
int dp[200020];
ll ans = 0;

int dfs(int u, int p){
    if(dp[u] != -1) return dp[u];
    int res = 0;
    ll nowans = 1;
    for(int v : G[u]){
        if(v == p) continue;
        int now = dfs(v,u)+1;
        nowans += (modpow(2,now,MOD)-1+MOD)%MOD;
        nowans %= MOD;
        res += now;
    }
    if(res == 0) return dp[u] = 0;
    nowans += (modpow(2,N-res-1,MOD)-1)%MOD;
    nowans %= MOD;
   // cout << nowans << endl;
    ans += (modpow(2,N-1,MOD)-nowans+MOD)%MOD;
    ans %= MOD;
    return dp[u] = res;
}


int main(){
    cin >> N;
    G.resize(N);
    rep(i,N-1){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(i,200020) dp[i] = -1;
    dfs(0,-1);
   // cout << ans << endl;
    //rep(i,N) cout << dp[i] << endl;
    ans *= modinv(modpow(2,N,MOD),MOD);
    ans %= MOD;
    cout << ans << endl;
}
    



Measured memory_bytes: 23040
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rapido ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define pra(a) fl(i,0,a.size()) cout<<a[i]<<endl;

int32_t main()
{
  	rapido;
    int n; cin>>n;
    int x,y; cin>>x>>y;
    vector<int> cnt(n-1);
    for(int i = 1  ; i <=n; i++)
    {
        for(int j = i+1; j <= n; j++)
            cnt[min(j-i,min(abs(i-x) + abs(j-y), abs(j-x)+ abs(i-y))+1)-1]++;
    }
  	for(int i=0;i<cnt.size();i++)
      cout<<cnt[i]<<endl;
    return 0;
}

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

using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define popb pop_back
#define popf pop_front
#define ll long long int
#define vi         vector<int>
#define vll        vector<ll>
#define vpii       vector<pair<int,int>>
#define vpll       vector<pair<ll,ll>>
#define rep(i,a,b) for(i=a;i<b;i++)
#define hell 1000000007
#define mod 998244353
#define fs first
#define sc second
#define all(v) v.begin(),v.end()

int main()
{
  fastio
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  int n,i,j,sum=0;
  cin>>n;
  int a[n];
  rep(i,0,n)
  cin>>a[i];
  rep(i,0,n)
  {
    rep(j,i+1,n)
    {
      sum+=a[i]*a[j];
    }
  }
  cout<<sum;
  return 0;
}

Measured memory_bytes: 256
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())

V = sum(v)
dp = [[10**100]* (V + 1) for _ in range(N+1)]
#dp[i][j]: i番目までの品物から価値が j以上になるように
#選んだときの持ち帰る品物の重さの総和の最小値
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j-v[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(V + 1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Measured memory_bytes: 131208
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<sstream>
#include<iomanip>
#pragma GCC optimize ("Ofast")
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    long double a,b,ans;
    cin >>a;
    a=a*1.0000000;
    ans=a*a*a*1.000000/27;
    cout<<fixed;
    cout <<ans;
    
}

Measured memory_bytes: 384
fn main() {
	let mut s = String::new();
	std::io::stdin().read_line(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let a: u64 = s.next().unwrap().parse().unwrap();
	let b: u64 = s.next().unwrap().replace(".", "").parse().unwrap();
	println!("{}", a * b / 100);
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int MOD=1000000007;

int main() {
  int n;
  cin >> n;
  char s[n];
  char t[n];
  rep(i,n) cin >> s[i];
  rep(i,n) cin >> t[i];
  rep(i,n) cout << s[i] << t[i];
  cout << endl;
}


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

long long i,j,n,a,b,c,d;
string str;

int main(){
  cin >> n >> a >> b >> c >> d;
long long dis = b-a;
long long near=c*(n-1),far=d*(n-1);
for(i = 0;i < n;i++){
if(near<=dis && dis <= far){
cout << "YES" << endl;
return 0;
}
near-=c+d;
far-=c+d;
}
  cout << "NO" << endl;
return 0;
}


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

int main(){
    int N; cin >> N;
    vector<int> L(N);
    for(int i = 0; i < N; i++){
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    int ans = 0;
    for(int i = 0; i < N - 1; i++){
        for(int j = i + 1; j < N; j++){
            auto it = lower_bound(L.begin(), L.end(), L[i] + L[j]);
            ans += it - (L.begin() + j + 1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <cmath>
#include <stdio.h>
#include <functional>

using namespace std;
using ll = long long;
using ld = double;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
const ll INF = 1e17;
const ld eps = 1e-10;
const ll MOD = 1e9 + 7;

const double pi = acos(-1.0);
vector<vector<ll>> es;
vector<ll> dim;
vector<bool> visited;
map<P, bool> rev;

void dfs(ll now) {
	visited[now] = true;
	for (auto e : es[now]) {
		if (!visited[e]) {
			dfs(e);
			if (dim[e] % 2) {
				rev[P(min(now, e), max(now, e))] ^= true;
				dim[e]++;
				dim[now]++;
			}
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N, M;
	cin >> N >> M;
	es.resize(N);
	dim.resize(N);
	for (int i = 0;i < M;i++) {
		ll a, b;
		cin >> a >> b;
		a--; b--;
		es[a].push_back(b);
		es[b].push_back(a);
		rev[P(min(a, b), max(a, b))] = b < a;
		if(!(b < a))
			dim[min(a, b)]++;
		else
			dim[max(a, b)]++;
	}
	if (M % 2) {
		cout << -1 << endl;
		return 0;
	}
	visited.assign(N, false);
	dfs(0);
	bool ok = true;
	for (int i = 0;i < N;i++)
		ok &= dim[i] % 2 == 0;
	if (!ok)
		cout << -1 << endl;
	else {
		for (auto i : rev) {
			ll a, b;
			tie(a, b) = i.first;
			if (i.second)
				cout << b+1 << " " << a+1 << endl;
			else
				cout << a+1 << " " << b+1 << endl;
		}
	}
	return 0;
}



/*
7 6
2 1
2 4
5 2
1 3
3 6
7 3
*/


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


int main() {
	long long int N;
	string S;
	cin >> N >> S;
	long long int count1 = 0, count2 = 0, count3 = 0;
	vector<long long int>D(N + 1), E(N + 1);
	for(int i = 0; i < N; i++) {
		auto c = S[i];
		D[i + 1] = D[i];
		if(c == '#') {
			D[i + 1]++;
		}
	}

	for(int i = N - 1; i >= 0; i--) {
		auto c = S[i];
		E[i] = E[i + 1];
		if(c == '.') {
			E[i]++;
		}
	}

	long long int ans = 1LL << 60;
	for(size_t i = 0; i < N + 1; i++) {
		ans = min(ans, D[i] + E[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3716
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <ctime>
#include <map>
#include <stack>
#include <sstream>

using namespace std;

int main(void)
{
	queue <char> s1, s2, s3;
	char temp;
	while (1)
	{
		scanf("%c", &temp);
		if (temp == '\n')
		{
			break;
		}
		s1.push(temp);
	}

	while (1)
	{
		scanf("%c", &temp);
		if (temp == '\n')
		{
			break;
		}
		s2.push(temp);
	}

	while (1)
	{
		scanf("%c", &temp);
		if (temp == '\n')
		{
			break;
		}
		s3.push(temp);
	}

	char card = 'a';
	while (1)
	{
		if (card == 'a')
		{
			if (s1.empty())
			{
				cout << 'A' << endl;
				break;
			}
			card = s1.front();
			s1.pop();
		}

		else if (card == 'b')
		{
			if (s2.empty())
			{
				cout << 'B' << endl;
				break;
			}
			card = s2.front();
			s2.pop();
		}

		else if (card == 'c')
		{
			if (s3.empty())
			{
				cout << 'C' << endl;
				break;
			}
			card = s3.front();
			s3.pop();
		}
	}
	return 0;
}

Measured memory_bytes: 256
class UnionFind
  def initialize(n)
    @root = Array.new(n)
    @rank = Array.new(n)
    @size = Array.new(n)
    (0...n).each do |i|
      @root[i] = i
      @rank[i] = 0
      @size[i] = 1
    end
  end

  def find(x)
    if @root[x] == x
      x
    else
      @root[x] = find(@root[x])
    end
  end

  def unite(x, y)
    x_root = find(x)
    y_root = find(y)
    return if x_root == y_root

    if @rank[x_root] < @rank[y_root]
      @root[x_root] = y_root
      @size[y_root] += @size[x_root]
    else
      @root[y_root] = x_root
      @size[x_root] += @size[y_root]
      if @rank[x_root] == @rank[y_root]
        @rank[x_root] += 1
      end
    end
    nil
  end

  def size(x)
    x_root = find(x)
    @size[x_root]
  end

  def same?(x, y)
    find(x) == find(y)
  end
end

N = gets.to_i
points = N.times.map do |i|
  x, y = gets.split.map(&:to_i)
  [i, x, y]
end

edges = Array.new((N - 1) * 2)
x_sorted = points.sort_by { |_, x, _| x }
y_sorted = points.sort_by { |_, _, y| y }
(N - 1).times do |n|
  i, x, _ = x_sorted[n]
  j, x2, _ = x_sorted[n + 1]
  yen = (x - x2).abs
  edges[n] = [i, j, yen]
end
(N - 1).times do |n|
  i, _, y = y_sorted[n]
  j, _, y2 = y_sorted[n + 1]
  yen = (y - y2).abs
  edges[(N - 1) + n] = [i, j, yen]
end

def kruskal(n, edges)
  edges.sort_by! { |_, _, c| c }
  uf = UnionFind.new(n)
  ret = 0
  edges.size.times do |i|
    u, v, c = edges[i]
    if !uf.same?(u, v)
      uf.unite(u, v)
      ret += c
    end
  end
  ret
end

puts kruskal(N, edges)

Measured memory_bytes: 26320
#include <iostream>
int i,j,n,P[9999];int main(){for(i=2;i*i<9999;i++)for(j=i;j<9999;P[j+=i]=1);for(;std::cin>>n,n;printf("%d %d\n",i-2,i))for(i=n;P[i]||P[i-2];i--);}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = int;
using i64 = long long;
using f64 = double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf64 = vector<f64>;
using vstr = vector<string>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

void solve(int n, int m) {
  i64 v = 2 << (m - 1);
  cout << (1900 * m + 100 * (n - m)) * v << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  int n, m;
  cin >> n >> m;
  solve(n, m);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sys/resource.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 2*(int)1e5 + 10;

int n, k, c;
char a[N];
int dp[N], dp2[N];
vector<int> tt, tt2;

int solve(int idx){
   if(idx > n){
      return 0;
   }

   int &ans = dp[idx];
   if(ans != -1)
      return ans;
   ans = 0;

   smax(ans, solve(idx+1));
   if(a[idx] == 'x'){
      return ans;
   }

   smax(ans, 1 + solve(idx+c+1));
   return ans;
}

int solve2(int idx){
   if(idx <= 0){
      return 0;
   }

   int &ans = dp2[idx];
   if(ans != -1)
      return ans;
   ans = 0;

   smax(ans, solve2(idx-1));
   if(a[idx] == 'x'){
      return ans;
   }

   smax(ans, 1 + solve2(idx-c-1));
   return ans;
}

int32_t main(){_
   

   cin>>n>>k>>c;
   for (int i = 1; i <= n; ++i)
   {
      cin>>a[i];
   }
   
   memset(dp, -1, sizeof dp);
   memset(dp2, -1, sizeof dp2);

   for (int i = 1; i <= n; ++i)
   {
      if (solve2(i-1) + solve(i+1) < k){
         cout<<i<<endl;
      }
   }

   return 0;
}


Measured memory_bytes: 7936
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}
	public Main() {
		new RitProA().doIt();
	}
	class RitProA{
		void doIt(){
			int N = in.nextInt();
			int a[] = new int [N]; 
			long sum[] = new long[1000002];
			for(int i = 0;i < N;i++){
				a[i] = in.nextInt();
			}
			Arrays.sort(a);
			long cnt = 0;
			for(int i = 0;i < N;i++){
				cnt = cnt + a[i];
				sum[a[i]] = cnt;
			}
			for(int i = 0;i < 1000000;i++){
				if(sum[i+1] == 0){
					sum[i+1] = sum[i];
				}
			}
			int M = in.nextInt();
			int b[] = new int [M];
			long c[] = new long [M];
			for(int i = 0;i < M;i++){
				b[i] = in.nextInt();
			}
			for(int i = 0;i < M;i++){
				c[i] = in.nextLong();
			}
			for(int i = 0;i < M;i++){
				if(sum[b[i]] >=c[i]){
					System.out.println("Yes");
				}else{
					System.out.println("No");
				}
			}
		}
	}
}

Measured memory_bytes: 279240
#include<cstdio>
#include<utility>
#include<queue>
using namespace std;
const static int MAX_H = 1010, MAX_W = 1010;
static char maze[MAX_H][MAX_W];
static int state[MAX_H][MAX_W];
static int H, W;
static int dx[4] = { 0,1,0,-1 };
static int dy[4] = { -1,0,1,0 };
typedef pair<int, int > point;
int bfs(point start,point end) {
	for (int i = 0; i < H; ++i)
		for (int j = 0; j < W; ++j)
			state[i][j] = -1;
	queue<point> que;
	que.push(start);
	state[start.first][start.second] == 0;
	while (que.size()) {
		point now = que.front();
		que.pop();
		if (now.first == end.first&&now.second == end.second) {
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx = now.first + dx[i];
			int ny = now.second + dy[i];
			if (nx >= 0 && nx < H&&ny >= 0 && ny < W&&state[nx][ny] == -1 && maze[nx][ny] != 'X') {
				que.push(point(nx, ny));
				state[nx][ny] = state[now.first][now.second] + 1;
			}
		}
	}
	return state[end.first][end.second];
}
int main() {
	int n;
	scanf("%d %d %d", &H, &W, &n);
	getchar();
	int k = 0;
	point cheese[12];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			scanf("%c", &maze[i][j]);
		}
		getchar();
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (maze[i][j] != 'X'&&maze[i][j] != '.') {
				if (maze[i][j] == 'S')
					cheese[0] = point(i, j);
				else
					cheese[maze[i][j] - '0'] = point(i, j);
			}
		}
	}
	int ret = 0;
	for (int i = 0; i < n; i++) {
		ret += bfs(cheese[i], cheese[i + 1]);
		ret++;
	}
	printf("%d\n", ret);
}

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

int main() {
  string s1, s2;
  cin >> s1 >> s2;

  if (s1[0] == s2[2] && s1[1] == s2[1] && s1[2] == s2[0]) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 10000000000000001
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define vc vector
#define vll vector<long long>
#define pll pair<long long,long long> 
#define pb push_back
#define all(v) v.begin(),v.end()
#define T ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define MAX 100005
typedef long long ll;
typedef long double ld;
using namespace std;
void dfs(int src,vector<int>adj[],int vis[],int dp[])
{
	vis[src]=1;
	for(auto j:adj[src]){
		if(vis[j]==0)
		{
			dfs(j,adj,vis,dp);
		}
		dp[src]=max(dp[src],1+dp[j]);
	}
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    char mat[n][m];
	int dp[n][m];
    memset(dp,0,sizeof(dp));
    rep(i,0,n)
    {
    	rep(j,0,m)
    	cin>>mat[i][j];
	}
	dp[0][0]=1;
	rep(i,0,n)
    {
    	rep(j,0,m)
    	{
    		if(mat[i][j]!='#')
    		{
    		if(i+1<n &&mat[i+1][j]!='#')
    		{
    			dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
			}
			if(j+1<m &&mat[i][j+1]!='#')
    		{
    			dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
			}
		}
		}
	}
	cout<<dp[n-1][m-1]<<endl;
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n>=400 &&n<=599)
    {
        cout<<8<<endl;
    }
    else if(n>=600&&n<=799)
    {
        cout<<7<<endl;
    }
     else if(n>=800&&n<=999)
    {
        cout<<6<<endl;
    }
     else if(n>=1000&&n<=1199)
    {
        cout<<5<<endl;
    }
     else if(n>=1200&&n<=1399)
    {
        cout<<4<<endl;
    }
     else if(n>=1400&&n<=1599)
    {
        cout<<3<<endl;
    }
     else if(n>=1600&&n<=1799)
    {
        cout<<2<<endl;
    }
     else if(n>=1800&&n<=1999)
    {
        cout<<1<<endl;
    }

}


Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>

using namespace std;

void solve(int A, int B, int T);

void solve(int A, int B, int T) {
  int ans = 0;
  int t = A;
  for (;;) {
    if (t <= T) {
      ans += B;
    } else {
      break;
    }
    t += A;
  }
  cout << ans << endl;
}

int main() {
  int A, B, T;
  cin >> A >> B >> T;
  solve(A, B, T);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int N;
	cin >> N;
	llong MIN = 1000000001;
	llong MAX = 0;
	for(int i=0; i<N; ++i){
		llong hoge;
		cin >> hoge;
		MIN = min(MIN, hoge);
		MAX = max(MAX, hoge);
	}
	cout << MAX - MIN << endl;
}

Measured memory_bytes: 3512
#include <algorithm>
#include <iostream>
#include <vector>
using ll = long long;

struct Node {
	Node* c[26];
	int cnt;
	Node() : c{}, cnt(0) {}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin >> n;
	std::vector<std::string> g(n);
	for (auto& x : g)
		std::cin >> x;
	std::sort(g.begin(), g.end(), [&](auto a, auto b) { return a.size() < b.size(); });
	ll ans = 0;
	Node* root = new Node();
	for (int i = 0; i < n; ++i) {
		std::vector<int> m{0};
		for (auto c : g[i])
			m.push_back(m.back() | (1 << (c - 'a')));
		Node* ptr = root;
		for (auto c : std::string(g[i].rbegin(), g[i].rend())) {
			for (int k = 0; k < 26; ++k)
				if (((1 << k) & m.back()) && k != c - 'a' && ptr->c[k] != nullptr)
					ans += ptr->c[k]->cnt;
			if (!ptr->c[c - 'a'])
				ptr->c[c - 'a'] = new Node();
			ptr = ptr->c[c - 'a'];
			ans += ptr->cnt;
			m.pop_back();
		}
		ptr->cnt++;
	}
	std::cout << ans << '\n';
}


Measured memory_bytes: 225088
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define FastRead        ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl            "\n"
#define pi              acos(-1)
#define ordered_set     tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define MAX             100005
#define MOD             1000000007

typedef long long ll;

vector<ll>graph[MAX],dp(MAX);
bool vis[MAX];

void dfs(ll node)
{
    vis[node] = true;

    for(ll i=0; i<graph[node].size(); i++)
    {
        if(!vis[graph[node][i]])
            dfs(graph[node][i]);

        dp[node] = max(dp[node],1+dp[graph[node][i]]);
    }
}

int main()
{
    ll n,m,ans=INT_MIN;

    cin>>n>>m;

    for(ll i=0; i<m; i++)
    {
        ll u,v;

        cin>>u>>v;

        graph[u].push_back(v);
    }

    for(ll i=1; i<=n; i++)
        if(!vis[i])
            dfs(i);

    for(ll i=1; i<=n; i++)
        ans = max(ans,dp[i]);

    cout<<ans<<endl;
}


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

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

int main(){
  int n, ret;
  cin >> n >> ret;
  for(int i=1; i<n; i++){
    int a;
    cin >> a;
    ret=gcd(ret, a);
  }
  cout << ret;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=10001;
int n,m,ans,k;
int main(){
	scanf("%d%d",&n,&k);
	for (int i=n; i; i/=k)	ans++;
	printf("%d\n",ans);
	return 0;	
}

Measured memory_bytes: 128
ans = 20
def divisor_length(n,ans):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n // i:
                ans = min(ans,max(len(str(i)),len(str(n//i))))
            else:
                ans = min(ans,len(str(i)))
 
    return ans

n = int(input())
answer = divisor_length(n,ans)

print(answer)


Measured memory_bytes: 3188
n, m = map(int,input().split())
li = [0] * n
wa = 0
ac = 0

for i in range(m):
    p, s = map(str, input().split())
    p = int(p)

    if s == "WA" and li[p-1] >= 0: #WAかつ正解前
        li[p-1] += 1 #その問題をWAした数+1
    
    elif s == "AC" and li[p-1] >= 0: #ACかつ正解前
        wa += li[p-1] #それまでにWAした数をカウントに追加
        li[p-1] = -1 #ステータスを正解済に変更
        ac += 1 #AC+1

print(ac, wa)


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

using namespace std;

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

using ll = long long;
using pint = pair<int, int>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
    s << '[';
	for (int i = 0; i < len; ++i) {
		s << v[i]; if (i < len-1) s << ", ";
	}
    s << ']';
	return s;
}

int main(){

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

    ll h, w, n;
	cin >> h >> w >> n;

	int d[3] = {-1, 0, 1};
	map<pint, int> mp;
	rep(i, n){
	    int y, x;
		cin >> y >> x;
		--x; --y;
		rep(j, 3){
			int ny = y+d[j];
			if(ny < 1 or h-1 <= ny) continue;
		    rep(k, 3){
				int nx = x+d[k];
		        if(nx < 1 or w-1 <= nx) continue;
				++mp[{ny, nx}];
		    }
		}
	}

	vector<ll> ans(10, 0);
	ans[0] = (h-2)*(w-2);
	for(auto x : mp){
		++ans[x.second];
	}
	for(int i = 1; i < 10; ++i){
		ans[0] -= ans[i];
	}
	rep(i, 10){
	    ppp(ans[i]);
	}

    return 0;
}


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

using namespace std;
#define ll long long
#define r(i, n) for(int i=0;i<n;i++)

int main() {
    map<string, int> MAP;
    map<string, int>::iterator b, e;
    int num_query;
    cin >> num_query;
    int command, x;
    for (int loop = 0; loop < num_query; loop++) {
        string tmp;
        cin >> command;
        if (command == 0) {
            cin >> tmp >> x;
            MAP[tmp] = x;
        } else if (command == 1) {
            cin >> tmp;
            if(MAP.find(tmp)!=MAP.end()) {
                cout << MAP[tmp] << endl;
            } else cout << 0 << endl;
        } else if (command == 2) {
            cin >> tmp;
            MAP.erase(tmp);
        } else {
            string l, r;
            cin >> l >> r;
            b=MAP.lower_bound(l);
            e=MAP.upper_bound(r);
            for(;b!=e;b++) {
                cout << b->first << " " << b->second << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 27712
var
classes = {
  'light fly'   : [-Infinity, 48.00],
  'fly'         : [48.00, 51.00],
  'bantam'      : [51.00, 54.00],
  'feather'     : [54.00, 57.00],
  'light'       : [57.00, 60.00],
  'light welter': [60.00, 64.00],
  'welter'      : [64.00, 69.00],
  'light middle': [69.00, 75.00],
  'middle'      : [75.00, 81.00],
  'light heavy' : [81.00, 91.00],
  'heavy'       : [91.00, Infinity],
};

function main() {
  input.forEach(function(line) {
    var
    className;
    if(line.trim() === '') return;
    line = parseFloat(line);
    Object.keys(classes).forEach(function(name) {
      var
      range = classes[name];
      if(range[0] < line && line <= range[1]) {
        className = name;
      }
    });
    console.log(className);
  });
}

var
input = '';

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split('\n');
  main();
});

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


int main() {
  int N;
  cin >> N;
  string s;
  // C++のマップはordered。keyが最初から昇順ソートされている
  map<string, int> mymap;
  rep(i, N) {
    cin >> s;
    mymap[s]++;
  }
  
  int maxcount = 0;
  for (auto p : mymap) {
    maxcount = max(maxcount, p.second);
  }
  for (auto p : mymap) {
    if (p.second == maxcount) cout << p.first << endl;
  }
  return 0;
}


Measured memory_bytes: 25216
#include"iostream"
#include"vector"
#include"algorithm"
using namespace std;
 
int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> x(n);
	for (int i = 0; i < n; i++)
	{
		cin >> x[i];
	}
 
	int ans = 2*x[n-1]-2*x[0];
	for (int i = 0; i < n - k + 1; i++)
	{
		if (x[i] < 0 && x[i + k - 1] < 0)
		{
			ans = min({ ans,abs(x[i]) });
		}
		else if (x[i] > 0 && x[i + k - 1] > 0)
		{
			ans = min({ ans,abs(x[i + k - 1]) });
		}
		else
		{
			ans = min({ ans,2 * x[i + k - 1] - x[i],x[i + k - 1] - 2*x[i] });
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 768
# -*- coding: utf-8 -*-


def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()


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

struct p {
    int a;
    int b;
    bool isPaird = false;

    bool operator<(const p &another) const {
        if (a == another.a)
            return b < another.b;
        else
            return a < another.a;
    };
};

int main() {
    int N;
    cin >> N;
    vector<p> A(N);
    vector<p> B(N);
    rep(i, N) cin >> A[i].a >> A[i].b;
    rep(i, N) cin >> B[i].a >> B[i].b;
    sort(all(B));

    int ans = 0;
    rep(i, N) {
        int ymax  = -1;
        int ymaxi = -1;
        rep(j, N) {
            if (A[j].isPaird) continue;
            if (A[j].a < B[i].a && A[j].b < B[i].b) {
                if (A[j].b > ymax) {
                    ymax  = A[j].b;
                    ymaxi = j;
                }
            }
        }
        if (ymax >= 0) {
            B[i].isPaird     = true;
            A[ymaxi].isPaird = true;
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/rope"
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
#define lambdify(x) [&](auto &&...args){ return x(forward<decltype(args)>(args)...); }
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	long long a;
	string bb;
	cin >> a >> bb;
	int b = bb[3] - '0' + 10 * (bb[2] - '0') + 100 * (bb[0] - '0');
	cout << a * b / 100;
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define pi 3.14159265
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int> 
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
#define MAXN 10000005
int spf[MAXN];
void pf() 
{ 
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++) 
        spf[i] = i; 
    for (int i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
    for (int i=3; i*i<MAXN; i++) 
    { 
        if (spf[i] == i) 
        {
            for (int j=i*i; j<MAXN; j+=i)
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
}
void shikhar7s(int cas)
{
    pf();
    int n,i,a;
    cin>>n;
    int ans=0,c,l,p;
    rep(i,2,n+1)
    {
        a=i;
        l=-1;
        c=0;
        p=1;
        while(a!=1)
        {
            if(spf[a]!=l)
            {
                p*=(c+1);
                c=1;
                l=spf[a];
            }
            else
            {
                c++;
            }
            a/=spf[a];
        }
        p*=(c+1);
        ans+=(p*i);
    }
    cout<<ans+1;
}
signed main()
{
    fast;
    int t=1;
    //cin>>t;
    int cas=1;
    while(cas<=t)
    {
    shikhar7s(cas);
    cas++;
    }
    return 0;
}

Measured memory_bytes: 81772
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int main(void){
    int m,f,b;
    cin>>m>>f>>b;
    if(m+f<b)cout<<"NA"<<endl;
    else{
        if(m>=b)cout<<0<<endl;
        else cout<<b-m<<endl;
    }
}



Measured memory_bytes: 3108
from bisect import bisect_left


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


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        # ２分探索
        index = bisect_left(color_list, a)
        # print(index)
        color_list[index - 1] = a
        if n - index == color_num:
            color_num = color_num + 1
        # print(color_list)
    # print()
    # print(color_list)
    print(color_num)

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する


Measured memory_bytes: 52696
#include<bits/stdc++.h>
using namespace std;
struct Union_find{
  vector<int>par;
  vector<int>size;
  Union_find(int n):par(n),size(n){
    for(int i=0;i<n;i++){
      par[i]=i;
      size[i]=1;
    }
  }
  int root(int x){
    return par[x]==x?x:par[x]=root(par[x]);
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
  void unit(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y)return;
    if(size[x]<size[y]){
      par[x]=y;
      size[y]+=size[x];
    }else{
      par[y]=x;
      size[x]+=size[y];
    }
  }
  int treesize(int x){
    return size[root(x)];
  }
};
int main(){
  int N,K,M;
  cin>>N>>M>>K;
  Union_find uf(N);
  vector<vector<int>>G(N);
  vector<int>block(N,0);
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    uf.unit(a,b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for(int i=0;i<K;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    if(uf.same(a,b)){
      block[a]++;
      block[b]++;
    }
  }
  vector<int>ans(N);
  for(int i=0;i<N;i++){
    //cout<<i<<" "<<block[i]<<endl;
    ans[i]=uf.treesize(i)-G[i].size()-block[i];
    cout<<ans[i]-1<<" ";
  }
}


Measured memory_bytes: 10640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main(){
  int a[2],sum;
  for (int i = 0; i < 2; i++){
    cin >> a[i];
  }
  sort (a,a+2,greater<int>());
  sum = a[0];
  a[0] -= 1;
  sort (a,a+2,greater<int>());
  sum += a[0];
  cout << sum << '\n';
  return 0; 
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAXN = 2020;
const int MAX = MAXN * MAXN;
const int mod = 1e9 + 7;

inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }

inline int sub(int a, int b) { return a >= b ? a - b : a - b + mod; }

inline int mul(int a, int b) { return llint(a) * b % mod; }

int f[MAXN][MAXN];

int fact[MAX];
int inv[MAX];
int invfact[MAX];

int choose(int n, int k) {
  return mul(fact[n], mul(invfact[k], invfact[n - k]));
}

int main(void) {
  inv[1] = 1;
  FOR(i, 2, MAX) inv[i] = sub(0, mul(mod / i, inv[mod % i]));

  fact[0] = invfact[0] = 1;
  FOR(i, 1, MAX) {
    fact[i] = mul(fact[i - 1], i);
    invfact[i] = mul(invfact[i - 1], inv[i]);
  }

  int N, K;
  scanf("%d %d", &N, &K);

  if (K == 1) {
    printf("%d\n", 1);
    return 0;
  }

  f[0][0] = 1;
  REP(i, N + 1) REP(j, N + 1) {
    if (j < i) continue;

    if (j + 1 <= N) {
      f[i][j + 1] = add(f[i][j + 1], f[i][j]);
    }

    if (i + 1 <= j) {
      int rem_spots = N * K - i * (K - 1) - j - 1;
      int need_spots = K - 2;

      int ways = choose(rem_spots, need_spots);
      ways = mul(ways, N - i);
      f[i + 1][j] = add(f[i + 1][j], mul(ways, f[i][j]));
    }
  }

  printf("%d\n", f[N][N]);
  return 0;
}


Measured memory_bytes: 63744
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	int a,b;
	cin>>a>>b;
	if((a+b)%3==0 || a%3==0 || b%3==0) cout<<"Possible";
	else cout<<"Impossible";
	return 0;
}


Measured memory_bytes: 3628
#include<iostream>
#include<vector>
using namespace std;
int n, S[1000000];

int binarySearch(int val)
{
	int left = 0, right = n;
	while (left < right) {
		int mid = (left + right) / 2;
		if (S[mid] == val) {
			//cout << val;
			return mid;
		}
		else if (val < S[mid]) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	return -1;
}

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

	int q, val, sum = 0;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> val;
		if (binarySearch(val) >= 0) {
			sum++;
		}
	}

	cout << sum << endl;
}

Measured memory_bytes: 3420
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    string a[50],b[50],ans="No";
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n-m+1;i++){
        for(int j=0;j<n-m+1;j++){
            bool f=true;
            for(int k=0;k<m;k++){
                if(a[k+i].substr(j,m)!=b[k]){
                    f=false;
                }
            }
            if(f){
                ans="Yes";
                i=50;
                j=50;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
n = len(str(N))
s = ['3', '5', '7']
ans = 0
for d in range(3, n+1):
    for i in range(3 ** d):
        x = ''
        for j in range(d):
            x += s[(i//(3**j))%3]
        if '3' in x and '5' in x and '7' in x and int(x) <= N:
            ans += 1
print(ans)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> V;
const long long MOD=1000000007LL;
const long long INFL=1LL << 60;
const int INF=1<<29;


int main() {
    int N,K;
    cin >>N>>K;
    cout<<N-K+1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n, k; cin >> n >> k;
    VI a(n); cin >> a;
    SORT(a);

    function<bool(int)> check = [&](int x) {
        auto dp = vec<bool>(2, k + 1);
        dp[0][0] = true;
        FOR(i, 0, n){
            eFOR(j, 0, k)dp[(i + 1) & 1][j] = false;
            eFOR(j, 0, k) {
                if (!dp[i & 1][j])continue;
                dp[(i + 1) & 1][j] = true;
                if (i != x && j + a[i] <= k) {
                    dp[(i + 1) & 1][j + a[i]] = true;
                }
            }
        }

        FOR(j, max(k - a[x], 0), k)if (dp[n & 1][j])return true;
        return false;
    };

    int ok = n, ng = -1;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        if (check(mid))ok = mid;
        else ng = mid;
    }

    cout << ok << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) (vec).begin(),(vec).end()
#define int long long

signed main(){
    int n;cin>>n;
    int b=(1<<30);
    int m=0;
    rep(i,n){
        int a;cin>>a;
        if(a<=b)m++;
        b=a;
    }
    cout<<m<<endl<<n<<endl;
}


Measured memory_bytes: 3108
use std::io;
use std::str::FromStr;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn input_vec() -> Vec<u64> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn main() {
    let n: usize = input();
    let a_vec = input_vec();
    let mut money = 1000;
    let mut stock = 0;
    for i in 0..n-1 {
        if a_vec[i] >= a_vec[i+1] {
            // 売り
            money += stock * a_vec[i];
            stock = 0;
        }
        if a_vec[i] <= a_vec[i+1] {
            // 買い
            stock += money / a_vec[i];
            money -= (money / a_vec[i]) * a_vec[i];
        }
    }
    money += stock * a_vec[n-1];
    println!("{}", money);
}


Measured memory_bytes: 2116
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <utility>

int main(){
  int X, Y, Z, K;
  scanf("%d", &X);
  scanf("%d", &Y);
  scanf("%d", &Z);
  scanf("%d", &K);
  std::vector<long long > A(X), B(Y), C(Z);
  for (int i=0; i<X; i++){
    scanf("%lld", &A[i]);
  }
  for (int i=0; i<Y; i++){
    scanf("%lld", &B[i]);
  }
  for (int i=0; i<Z; i++){
    scanf("%lld", &C[i]);
  }
  std::vector<long long > BC;
  for (int i=0; i<Y; i++){
    for (int j=0; j<Z; j++){
      BC.push_back(B[i]+C[j]);
    }
  }
  std::sort(BC.begin(), BC.end(), std::greater<long long>());
  std::vector<long long >ABC;
  for (int i=0; i<X; i++){
    for (int j=0; j<std::min((int)K, (int)BC.size()); j++){
      ABC.push_back(A[i]+BC[j]);
    }
  }
  std::sort(ABC.begin(), ABC.end(), std::greater<long long>());
  for (int i=0; i<K; i++){
    printf("%lld\n", ABC[i]);
  }
  return 0;
}
 

Measured memory_bytes: 43664
N = int(input())
B = [0] + list(map(int,input().split()))
A = [0,B[1]]
for i in range(2,N):
    A.append(B[i-1])
    if A[i] > B[i]:
        A[i] = B[i]
A.append(B[N-1])
print(sum(A))

Measured memory_bytes: 9040