akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<cctype>
#include<string>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define INF 2100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
int dp[17][17];
int main(void)
{
	int a,b,n,x,y;
	while(cin>>a>>b) {
		if(!a&&!b) return 0;
		rep(i,0,b+1) {
			rep(j,0,a+1) {
				dp[i][j]=0;
			}
		}	
		cin>>n;
		rep(i,0,n) {
			cin>>x>>y;
			x--,y--;
			dp[y][x]=-1;
		}
		dp[0][0]=1;
		rep(i,0,b) {
			rep(j,0,a) {
				if(dp[i][j]!=0&&dp[i][j]!=-1) {
					if(dp[i+1][j]!=-1&&i+1<=b) dp[i+1][j]+=dp[i][j];
					if(dp[i][j+1]!=-1&&j+1<=a) dp[i][j+1]+=dp[i][j];
				}
			}
		}
		/*rep(i,0,b) {
			rep(j,0,a) {
				printf("%3d",dp[i][j]);
			}
			cout<<endl;
		}*/
		cout<<dp[b-1][a-1]<<endl;
	}
}

Measured memory_bytes: 2944
x,k,d=map(int,input().split())
x=abs(x)
ans=0
if x>k*d:
    ans=x-k*d
else:
    dis_zero=x//d
    #print(dis_zero)
    n=k-dis_zero
    a=x-(d*dis_zero)
    D=abs(a-d)
    if n%2==0:
        ans=a
    elif n%2!=0:
        ans=D
print(ans)
    


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

using namespace std;

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<pair<int, int>>> edges(N, vector<pair<int, int>>());
  for (int i = 0; i < M; i++) {
    int l, r, d;
    cin >> l >> r >> d;
    l--;
    r--;
    edges[l].push_back({r, d});
    edges[r].push_back({l, -d});
  }
  const long long inf = 1e15;
  vector<long long> D(N, inf);
  bool ok = true;
  for (int i = 0; i < N; i++) {
    if (D[i] != inf) continue;
    queue<int> que;
    que.push(i);
    D[i] = 0;
    long long max_d = 0, min_d = 0;
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (auto e : edges[v]) {
        int n = e.first;
        auto d = e.second + D[v];
        if (D[n] != inf) {
          if (D[n] == d) {
            continue;
          } else {
            ok = false;
            break;
          }
        }
        D[n] = d;
        chmax(max_d, d);
        chmin(min_d, d);
        que.push(n);
      }
    }
    if (max_d - min_d > 1e9) ok = false;
  }
  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}
/* vim:set fdm=marker: */


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

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    Int x,k;
    cin>>x>>k;

    Int n = x/k;
    Int xa = abs(x-n*k);
    Int ans = min(x,min(xa,abs(xa-k))); //x < k

    cout<<ans<<endl;

    return 0;
}


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

int main()
{
	int64_t n;
	cin >> n;
	vector<int64_t> as(n);
	for (auto &a : as)
	{
		cin >> a;
	}

	vector<vector<int64_t>> dp(n, vector<int64_t>(2, -(1LL << 60)));
	dp[0][0] = 0;
	for (int64_t i = 0; i < n - 1; i++)
	{
		dp[i + 1][0] = max(dp[i][0] + as[i], dp[i][1] - as[i]);
		dp[i + 1][1] = max(dp[i][0] - as[i], dp[i][1] + as[i]);
	}

	cout << max(dp[n - 1][0] + as[n - 1], dp[n - 1][1] - as[n - 1]) << endl;

	return 0;
}

Measured memory_bytes: 6528
A, B, N=map(int, input().split())
if N<=5:
  print(max([int(A*i/B)-A*int(i/B) for i in range(N+1)]))
  exit()
  
if B==1:
  print(0)
  exit()
            
if N>=B-1:
  x=((N+1)//B)*B-1
  print(int(A*x/B)-A*int(x/B))
else:
  x=N
  print(int(A*x/B)-A*int(x/B))

Measured memory_bytes: 9148
#include<stdio.h>

int main()

{

    int s;
    scanf("%d",&s);
    int x1,x2,x3,x4,x5,x6;
    x4=s%10;
    s=s/10;
    x3=s%10;
    s=s/10;
    x2=s%10;
    s=s/10;
    x1=s%10;
    x5=x1*10+x2;
    x6=x3*10+x4;

 if (x5>0 && x5<=12 && x6>0 && x6<=12)
    printf("AMBIGUOUS\n");
 else if (x5>0 && x5<=12)
    printf("MMYY\n");
 else if (x6>0 && x6<=12)
    printf("YYMM\n");
else
    printf("NA\n");
 return 0;

}


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

int main(){
  long long int N;
  cin >> N;
  
  long long int ans = N-1;
  int a;
  for(int i=2; i < int(sqrt(float(N)))+2 ;i++){
    if(N%i==0){
      ans = min( ans , (i+N/i-2) );
    }
  }
  
  cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
using namespace std;
#define MAXSIZE 200
#define MAXL 100
typedef long long int lli;

int getDigitSum(int x);

int getAbs(int x);

int getMin(vector<int> v);

int main(){
    string s;
    cin >> s;
    //int c1 = 'a', c2 = 'z';
    //cout << c1 << endl << c2 << endl;
    int numIncluded[26] = {};
    bool flag = true;
    for(int i = 0; s[i] != '\0'; i++){
        numIncluded[s[i] - 'a']++;

        if(numIncluded[s[i] - 'a'] > 1){
            flag = false;
            break;
        }
    }
    cout << ((flag)? "yes" : "no") << endl;
    return 0;
}

int getDigitSum(int x){
    int res = 0;
    while(x > 0){
        res += x % 10;
        x /= 10;
    }
    return res;
}

int getAbs(int x){
    return (x > 0)? x : -x;
}

int getMin(vector<int> v){
    int res = 40000;
    for(int i = 0; i < v.size(); i++){
        res = min(res, v[i]);
    }
    return res;
}

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

using namespace std;

#define ll long long
#define endl "\n"

int main() {
  ll a, b;
  cin >> a >> b;
  if (abs(a - b) & 1) {
    cout << "IMPOSSIBLE\n";
    return 0;
  }
  ll ans = (1ll * abs(a - b)) >> 1;
  ans = max(a, b) - ans;
  cout << abs(ans) << endl;
  return 0;
}

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

#define debug(x) cout << #x << " = " << x << endl;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

const int maxn = 2e5 + 10;
ll fat[maxn], inv[maxn];

ll C(int n, int k)
{
  if(n < k) 
    return 0;
  if(n < 0 || k < 0) 
    return 0;
  return (((fat[n] * inv[k]) % mod) * inv[n - k]) % mod;
}


bool has[maxn];

int main()
{
  ios::sync_with_stdio(false);
  int n, k, c;
  string s;
  int cnt = 0;
  cin >> n >> k >> c >> s;
  for(int i = 0; i < n ; i++)
  {
    if(s[i] == 'o')
    {
      has[i] = true;
      i += c;
      cnt++;
    }
  }
  
  if(cnt !=  k)
    return 0;

  vector<int>ans;

  for(int i = n-1 ; i >= 0 ; i--)
  {
    if(s[i] == 'o')
    {
      if(has[i] == true)
      {
        ans.push_back(i);
      }
      i -= c;
    }
  }

  reverse(all(ans));

  for(const auto &c : ans)
    cout << c + 1 << endl;
  
  
  return 0;
}

Measured memory_bytes: 4628
function Main(input) {

    var input = input.split("\n");

    const N = Number(input[0].split(" ")[0]);
    const K = Number(input[0].split(" ")[1]);
    const H = input[1].split(" ").map(Number);

    // 必殺技(K回) > モンスター(N体) は即抜け
    if (K >= N) {
        //出力
        console.log(0);
        return;
    }

    const sortDesc = H.sort(function (a, b) {
        return b - a;
    });

    var answer = 0;
    for (var i = K; i < N; i++) {
        answer += sortDesc[i];
    }

    //出力
    console.log(answer);
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 34592
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
  cin>>n;
  int h[n+1];
  for(int i=1;i<=n;i++)
  {
cin>>h[i];}
  int dp[n+1]={0};
  dp[2]=abs(h[2]-h[1]);
  for(int i=3;i<=n;i++)
  {
dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout<<dp[n];
  return 0;
}
  
  

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
	template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
	template<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

	void solve() {
		IOS;
		int n;
		cin >> n;
		vector<vector<int>> path(n);
		REP(i, n) {
			int u, k;
			cin >> u >> k;
			u--;
			REP(j, k) {
				int v;
				cin >> v;
				v--;
				path[u].push_back(v);
			}
		}
		queue<int> q;
		vector<int> d(n, -1);
		int s = 0;
		d[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int p = q.front();
			q.pop();
			REP(i, path[p].size()) {
				int t = path[p][i];
				if (d[t] < 0) {
					d[t] = d[p] + 1;
					q.push(t);
				}
			}
		}
		REP(i, n) {
			put(i + 1, d[i]);
		}

	}
} // namespace idaten

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



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

int main() {
    int D,N;
    cin >>D>>N;
    if(D==0){
        if(N==100)cout<<N+1<<endl;
        else cout <<N<<endl;
    }
    else if(D==1){
        if(N==100)cout<<100*N+100<<endl;
        else cout <<100*N<<endl;
    }
    else{
        if(N==100)cout <<10000*N+10000<<endl;
        else cout <<10000*N<<endl;
    }

}

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

int main() {
	long N,M;
	cin >>N>>M;
	long H[N+1],V[N+1],A[M+1],B[M+1];
	for(int i=1;i<=N;i++){
		cin >>H[i];
		V[i]=1;
	}
	for(int i=1;i<=M;i++){
		cin >>A[i]>>B[i];
		if(H[A[i]]==H[B[i]]){
			V[A[i]]=0;
			V[B[i]]=0;
		}
		if(H[A[i]]<H[B[i]]){
			V[A[i]]=0;
		}
		if(H[A[i]]>H[B[i]]){
			V[B[i]]=0;
		}
	}
	long K=0;
	for(int i=1;i<=N;i++){
		K+=V[i];
	}
	cout <<K;
}

Measured memory_bytes: 6660
#include <bits/stdc++.h>
#define ps push_back
#define LL long long
using namespace std;
const int maxn=2e5+5;
int tmpa,tmpb;
LL prea[maxn],preb[maxn];

int main(){
    int N,M,K;
    cin>>N>>M>>K;
    for(int i=0;i<N;i++){
        cin >> tmpa;
        if(i)prea[i] = prea[i-1] + tmpa;
        else prea[i] = tmpa;
    }
    for(int j=0;j<M;j++){
        cin >> tmpb;
        if(j)preb[j] =preb[j-1] + tmpb;
        else preb[j] = tmpb;
    }
    int na,nb;
    int remain = 0;
    int res=0,tmpres=0;
    for(int i=-1;i<N;i++){
        if(i==-1){
            remain = K;
            na = 0;
            nb = 0;
        }
        else{
            remain = K - prea[i];
            nb = 0;
            if(remain>=0)na = i+1;
            else break;
        }
        int head = 0,tail = M-1;
        int middle = (head + tail)  / 2;

        while(head<=tail){
            if(remain>=preb[middle]){
                nb = middle + 1;
                head = middle + 1;
            }
            else{
                tail = middle - 1;
            }
            middle = (head + tail) / 2;
        }
        tmpres = na + nb;
        res = max(res,tmpres);
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 6732
n=int(input())
L=list(map(int,input().split()))
for i in range(n):
    if L[i]>i+1:
        print(-1)
        exit()
def mal(x):
    if len(x)==0:
        return []
    else:
        t=max(x)
        i=x.index(t)
        k=i-1
        while k>i-t:
            if x[k]>t-i+k:
                t=x[k]
                i=k
            k -= 1
        after=x[:i-t+1]
        before=x[i-t+1:]
        before.remove(t)
        return mal(before)+[t]+mal(after)
ans=mal(L)

for i in range(n):
    print(ans[i])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  ll cnt = n / (a + b);
  ll mod = n % (a + b);
  if (mod >= a)
    cout << cnt * a + a << endl;
  else
    cout << cnt * a + mod << endl;
}

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

Measured memory_bytes: 3568
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = Integer.parseInt(sc.next())-1;
        int B = Integer.parseInt(sc.next())-1;

        char[][] map = new char[100][100];
        for (int i=0;i<100;i++) {
            for (int j=0;j<100;j++) {
                if (i<50) {
                    map[i][j]='.';
                } else {
                    map[i][j]='#';
                }
            }
        }

        loop:while (B>0) {
            for (int i=0;i<50;i+=2) {
                for (int j=0;j<100;j+=2) {
                    map[i][j]='#';
                    B--;
                    if (B==0) {
                        break loop;
                    }
                }
            }
        }
        loop:while (A>0) {
            for (int i=51;i<100;i+=2) {
                for (int j=0;j<100;j+=2) {
                    map[i][j]='.';
                    A--;
                    if (A==0) {
                        break loop;
                    }
                }
            }
        }

        System.out.println(100 + " " + 100);
        for (int i=0;i<100;i++) {
            StringBuilder sb = new StringBuilder();
            for (int j=0;j<100;j++) {
                sb.append(map[i][j]);
            }
            System.out.println(sb);
        }
    }
}

Measured memory_bytes: 23380
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

const int MAXN = 30;
int rec[MAXN+5][MAXN+5];
void expr() {
    map< int, vector<int> > minus;
    for(int i=1; i<=MAXN; i++) {
        for(int j=1; j<=i; j++) {
            if(i == 1 and j == 1) rec[i][j] = false;
            if(i >= 1) {
                int ni = i - 1, nj = j;
                if(ni < nj) swap(ni, nj);
                if(!rec[ni][nj]) rec[i][j] = true;
            }
            if(j >= 1) {
                int ni = i, nj = j - 1;
                if(ni < nj) swap(ni, nj);
                if(!rec[ni][nj]) rec[i][j] = true;
            }
            int g = __gcd(i, j);
            if(g > 1) {
                int ni = i / g, nj = j / g;
                if(!rec[ni][nj]) rec[i][j] = true;
            }
            printf("%d ", rec[i][j]);
            minus[i-j].emplace_back(g == 1 ? rec[i][j] : -1);
        }
        printf("\n");
    }

    for(auto m : minus) {
        fprintf(stderr, "i-j = %d:", m.first);
        for(auto e : m.second) {
            if(e < 0) fprintf(stderr, " x", e);
            else fprintf(stderr, " %d", e);
        }
        fprintf(stderr, "\n");
    }
}

int main() {
    // expr();

    int N; scanf("%d", &N);
    vector<ll> A(N);
    for(int i=0; i<N; i++) {
        scanf("%lld", &A[i]);
    }

    auto dfs = [&](auto &&self) -> bool {
        ll contain_one = 0, even = 0, odd = 0;
        for(int i=0; i<N; i++) {
            (A[i] % 2 ? odd : even)++;
            contain_one |= (A[i] == 1);
        }

        if(contain_one) {
            ll sum = 0;
            for(int i=0; i<N; i++) sum += (A[i] - 1);
            return sum % 2;
        }
            
        if(even % 2 == 1) return true;
        if(odd >= 2) return false;

        for(int i=0; i<N; i++) if(A[i] % 2 == 1) A[i]--;
        ll g = 0;
        for(int i=0; i<N; i++) g = __gcd(g, A[i]);
        for(auto &e : A) e /= g;
        
        return !self(self);
        
    };
    bool ans = dfs(dfs);
    cout << (ans ? "First" : "Second") << endl;
    return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    struct Player : IComparable
    {
        internal int id;
        internal double time;

        public override string ToString()
        {
            return id + " " + time;
        }

        public int CompareTo(object obj)
        {
            Player other = (Player)obj;
            if (time < other.time) return -1;
            else if (time == other.time) return 0;
            return 1;
        }
    }

    class Competition
    {
        StringBuilder sb;
        Player[] list1, list2, list3;
        List<Player> final;

        public Competition()
        {
            sb = new StringBuilder();

            list1 = new Player[8];
            list2 = new Player[8];
            list3 = new Player[8];
            final = new List<Player>();
        }

        public void Solve()
        {
            MakeList(list1);
            MakeList(list2);
            MakeList(list3);

            final.Sort();

            for (int i = 0; i < 2; i++)
            {
                sb.AppendLine(final[i].ToString());
            }
            Console.Write(sb);
        }

        private void MakeList(Player[] list)
        {
            for (int i = 0; i < 8; i++)
            {
                string[] input = Console.ReadLine().Split(' ');

                Player temp;
                temp.id = int.Parse(input[0]);
                temp.time = double.Parse(input[1]);

                list[i] = temp;
            }

            Array.Sort(list);

            for (int i = 0; i < 2; i++)
            {
                sb.AppendLine(list[i].ToString());
                final.Add(list[i + 2]);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Competition c = new Competition();
            c.Solve();
        }
    }
}

Measured memory_bytes: 9436
#include <stdio.h>

#define MAX 200001

int main()
{
  char s[MAX];
  char t[MAX];
  int count=0, k;
  
  scanf("%s",s);
  scanf("%s",t);
  k=strlen(s);
  
  while(k!=0){
    if(s[k-1]!=t[k-1])
      count++;
    k--;
  }
  
  printf("%d\n",count);
  
  return 0;
}


Measured memory_bytes: 2092
import java.io.*;
import java.util.*;
 
class Main
{
  public static void main(String Args[])
  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int arr[] = new int[n];
    int max =0;int prevval = in.nextInt();
    int currcount=0;
    for(int i =1;i<n;i++)
    {
      int val =in.nextInt();
      if(val<=prevval)
      {
        currcount++;
      }
      else
      {
        if(max<currcount)
          max = currcount;
        currcount=0;
      }
      prevval =val;
    }
    if(max<currcount)
        max = currcount;
    System.out.println(max);
  }
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i_len=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back
#define mp make_pair

mat P;
vec buf(10);

void dperm(ll k, ll n, ll p, vec A)
{
    if(k == n) {
        vec p;
        REP(i,0,n) p.pb(buf[i]);
        P.pb(p);
    }
    else {
        REP(i,0,SZ(A)) {
            if(p <= A[i]) {
                buf[k] = A[i];
                p = A[i];
                dperm(k+1, n, p, A);
            }
        }
    }
}

int main()
{
    ll N, M, Q;
    cin >> N >> M >> Q;
    vec a(Q), b(Q), c(Q), d(Q);
    REP(i,0,Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i]; --b[i];
    }

    vec A(M);
    REP(i,0,M) A[i] = i + 1;

    dperm(0, N, A[0], A);

    ll sum, m = 0;
    FORR(A,P) {
        sum = 0;
        REP(i,0,Q) {
            if(A[b[i]] - A[a[i]] == c[i]) sum += d[i];
        }
        m = MAX(m,sum); 
    }
    PR(m);

    return 0;
}

/*



*/

Measured memory_bytes: 13928
#include<stdio.h>
int main(){
  int a,b,c,d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  int x,y;
  if(a<b){
    x=a;
  }
  else{
    x=b;
  }
  if(c<d){
    y=c;
  }
  else{
    y=d;
  }
  printf("%d",x+y);
  return 0;
}


Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dunk(n) cout << n << endl
#define all(a) (a).begin(),(a).end()
int main() {
    vector<char> alp = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    char a;
    cin >> a;
    rep(i,25){
        if(a == alp[i]) dunk(alp[i+1]);
    }
    return 0;
}

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

const int N = 200010;

int a[N], left[N], right[N];

int main(){
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
	}
	std::stack <int> s;
	for (int i = 0; i <= n + 1; ++ i){
		while (!s.empty() && a[s.top()] > a[i]){
			right[s.top()] = i;
			s.pop();
		}
		if (!s.empty()) left[i] = s.top();
		s.push(i);
	}
	long long ans = 0;
	for (int i = 1; i <= n; ++ i){
		ans += 1ll * a[i] * (right[i] - i) * (i - left[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  int ans = 0;
  for(int j=0; j<N; j++){
    for(int k=0; k<N; k++){
      ans = max(ans, abs(vec.at(j) - vec.at(k)) );
    }
  }
  
  cout << ans << endl;
}

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

const int MAX = 110000;
const int MOD = 1000000007;

long long fac[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
    }
}

long long COM(int n){
    if (n < 0) return 0;
    return fac[n] % MOD;
}

int main() {
    long long n,m,ans;cin>>n>>m;
    if(abs(n-m)>=2)ans=0;
    else{
    COMinit();
    if(n==m)ans=2*COM(n)*COM(m)%MOD;
    else ans=COM(n)*COM(m)%MOD;
    }
    cout << ans << endl;
}

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

#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define REPR(i, a, b) for (int i = (a); i >= (b); i--)
#define ALL(container) (container).begin(), (container).end()

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

const int INF = 1e9;

int main() {
  const double btc_rate = 380000;
  double sum = 0;

  int N;
  cin >> N;
  double x[N];
  string u[N];
  REP(i, 0, N) {
    cin >> x[i] >> u[i];
    if (u[i] == "BTC") {
      sum += x[i] * btc_rate;
    } else {
      sum += x[i];
    }
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
   int i,j,n,r=0;

   scanf("%d",&n);

   for(i=1;i<10;i++){                                                           
      for(j=1;j<10;j++)
         if(i*j==n) r=1;
   }

   if(r==1) printf("Yes\n");
   else printf("No\n");
   return 0;
}


Measured memory_bytes: 128
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	char C = getcha();
	int A = C - '0';
	while ((C = getcha()) >= '0') A = A * 10 + C - '0';
	return A;
}

int daishou[200002];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();
	int A[200001];
	rep1(i, N) A[getint()] = i;

	ll kotae = 0;
	for (int i = N; i > 0; i--) {
		int a = A[i];
		int l = daishou[a - 1];
		if (!l) l = a;
		int r = daishou[a + 1];
		if (!r) r = a;
		kotae += (ll)(a - l + 1) * (r - a + 1) * i;
		daishou[l] = r;
		daishou[r] = l;
	}

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 1792
fn main() {
    let (n, k) = read_tuple();
    let pn: Vec<i64> = read_vec();
    let e_pn: Vec<_> = pn.iter().map(|&p| ((p as f64+1.0)/2.0)).collect();

    let mut temp_sum: f64 = e_pn.iter().take(k).sum();
    let mut max_sum = temp_sum;
    for i in k..n {
        temp_sum += e_pn[i];
        temp_sum -= e_pn[i - k];

        if max_sum < temp_sum {
            max_sum = temp_sum;
        }
    }

    println!("{:?}", max_sum);
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}
fn read_tuple<T: std::str::FromStr + Copy>() -> (T, T) {
    let temp = read_vec();
    (temp[0], temp[1])
}



Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int gcd(int a,int b){
	return (b==0)?a:gcd(b,a%b);
}
int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	int t;
	cin>>t;
	set<string>st;
	while(t--){
		string s;
		cin>>s;
		st.insert(s);
	}
	cout<<st.size();
	return 0;
}


Measured memory_bytes: 19200
from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree[u-1].append([v-1,w])
    tree[v - 1].append([u - 1, w])
#print(tree)
dist=[-1]*N
v=0
d=deque()
d.append(v)
dist[0]=0
determined=[0]
while len(determined)<N:
    v=d.popleft()
    for i in tree[v]:
        if dist[i[0]]==-1:
            #print(dist[i[0]],dist[v],i[1])
            dist[i[0]]=dist[v]+i[1]
            d.append(i[0])
            determined.append(i[0])
    #print(dist,d,determined)
    #input()
for i in range(N):
    print(dist[i]%2)

Measured memory_bytes: 84640
#include<cmath>
#include<cstdio>
 
long s;
int a, b, c, d;
 
int main() {
    scanf("%ld", &s);
    if (s > 1e9) {
        a = 1e9;
        b = ceil((double) s / 1e9);
        c = (long) a * b - s;
        d = 1;
    } else {
        a = s;
        b = 1;
        c = 0;
        d = 0;
    }
 
    printf("0 0 %d %d %d %d\n", a, c, d, b);
    return 0;
}

Measured memory_bytes: 256
/*input
4
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

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

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

int n;

void solve(string s, char highest)
{
	if(s.size() == n) cout << s << endl;
	else for(int i = 0; i < n; i++) if(i + 'a' <= highest + 1)
	{
		if(i + 'a' <= highest) solve(s + (char) ('a' + i), highest);
		else if(i + 'a' == highest + 1) solve(s + (char) ('a' + i), highest + 1);
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    solve("a", 'a');

    return 0;
}

Measured memory_bytes: 1536
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let a=read::<String>().as_bytes().iter().map(|c|*c as char).collect::<Vec<char>>();
    let b=read::<String>().as_bytes().iter().map(|c|*c as char).collect::<Vec<char>>();
    let c=read::<String>().as_bytes().iter().map(|c|*c as char).collect::<Vec<char>>();
    println!("{}",if a[a.len()-1]==b[0]&&b[b.len()-1]==c[0]{"YES"}else{"NO"})
}

Measured memory_bytes: 4352
N=int(input())
*H,=map(int,input().split())

D=[10**4*N]*N

D[0]=0
for i in range(N):
    if 1<=i:
        #print(i,H[i],H[i-1],abs(H[i]-H[i-1]))
        D[i]=min(D[i],abs(H[i]-H[i-1])+D[i-1])
    if 2<=i:
        #print(i,H[i],H[i-2],abs(H[i]-H[i-2]))
        D[i]=min(D[i],abs(H[i]-H[i-2])+D[i-2])
print(D[-1])

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



int dfs(long s, int N){
  int ret;
  if (s>N) {
    return 0;
  }
  bool flg3 = false;
  bool flg5 = false;
  bool flg7 = false;
  // s は 753 数か?
  int tmp = s;
  while (tmp > 0) {
    int digit = tmp%10;
    tmp /= 10;
    if (digit == 3) flg3 = true;
    else if(digit == 5) flg5 = true;
    else if(digit == 7) flg7 = true;
  }
  // end while
  // s が 753 数なら +1
  if(flg3 && flg5 && flg7) ret = 1;
  else ret = 0;
  if(s <= N){
    ret += dfs(10*s + 3, N);
    ret += dfs(10*s + 5, N);
    ret += dfs(10*s + 7, N);
  }
  return ret;
}

int main()
{
  int N, ans;
  cin >> N;
  ans = dfs(0, N);
  cout << ans << endl;
  
  return 0;
}


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define endl '\n'
#define all(x) x.begin(), x.end()

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


using vvll = vector< vector<ll> >;
using vll = vector<ll> ;

const ll maxs = 1e6+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e15;

ll fast(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        y >>= 1;
    }
    return res;
}

ll inv(ll n){
    return fast(n,mod-2);
}


void pre(){


}

ll a[maxs];
ll b[maxs];

void solve(){

    ll n,m,k;
    cin >> n >> m >> k;
    for(ll i=1;i<=n;i++){
        cin >> a[i];
        a[i] += a[i-1];
    }
    for(ll i=1;i<m+1;i++){
        cin >> b[i];
        b[i] += b[i-1];
    }

    ll ans=0;
    ll j=m;
    for(ll i=0;i<=n;i++){
        if(a[i] > k)
            break;
        while(a[i] + b[j] > k)
            j--;
        ans = max(ans , i + j);
    }
    cout << ans;

}

int main(){
    // #ifndef ONLINE_JUDGE
    // freopen("input00.txt","r",stdin);
    // #endif
    IOS;
    pre();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();   
    }
    return 0;
}

Measured memory_bytes: 6740
#include <string.h>

#include <algorithm>
#include <iostream>
#include <vector>

#define rep1(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define fill(x, y) memset(x, y, sizeof(x))
#define MOD 1000000007
#define NUM 100  // 200000

using namespace std;
using ll = long long;

struct UnionFind {
  vector<int> par;  // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

  UnionFind(int N) : par(N) {  //最初は全てが根であるとして初期化
    for (int i = 0; i < N; i++) par[i] = i;
  }

  int root(int x) {  // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  // xとyの木を統合. （x,yのそれぞれの根の内、値が小さいほうに統合される）
  // 例：root(x) = 1, root(y) == 5　なら root(y) = 1　になる
  bool unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx == ry) {
      return false;
    } else {
      if (rx > ry) swap(rx, ry);
      par[ry] = rx;
    }
    return true;
  }

  bool isSame(int x, int y) {  // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }

  //根確認用
  // for (int i = 0; i < N; i++)
  // cout << "UF.par[" << i << "] = " << UF.par[i] << endl;
};

/*最も人数の多い友達グループの人数がそのまま答えとなる*/
int main(void) {
  int N, M;
  cin >> N >> M;

  UnionFind UF(N);  //友達集合を作成（最初はそれぞれの根は自分自身）
  int A, B;
  for (int i = 0; i < M; i++) {
    cin >> A >> B;
    UF.unite(A - 1, B - 1);
  }

  vector<int> cnt(N, 0);
  int max = 0;
  for (int i = 0; i < N; i++) {
    cnt[UF.root(UF.par[i])]++;
  }
  for (int i = 0; i < N; i++) {
    if (max < cnt[i]) {
      max = cnt[i];
    }
  }

  cout << max << endl;
  return 0;
}


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

int main(){
  char c;
  int n,m,s[10002]={};
  cin>>n>>m;
  for(int i=0;i<m;i++)
    for(int j=1;j<=n;j++){
      cin>>c;
      if(c=='W')s[j]++;
    }

  int ans,min=2000000;
  for(int i=1;i<=n;i++)
    s[i]+=s[i-1];
  for(int i=0;i<=n;i++){
    int t=m*i-s[i]+s[n]-s[i];
    if(t<min)min=t,ans=i;
  }
  cout<<ans<<" "<<ans+1<<endl;
  return 0;
}

Measured memory_bytes: 1212
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 100005
using namespace std;

int a[N],sg[N],n,k;
vector<int> G[N];

void dfs(int u,int fa)
{
	sg[u]=0;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa || a[v]>=a[u]) continue;
		dfs(v,u);
		if(!sg[v]) sg[u]=1;
	}
}

void subtask1()
{
	for(int i=1;i<=n;i++) 
	{
		dfs(i,-1);
		if(sg[i]) printf("%d ",i);
	}
	puts("");
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
//	if(k==1) 
	subtask1();
	return 0;
}


Measured memory_bytes: 2688
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    int d[N];
    for(int i = 0;i < N;i++)cin >> d[i];
    
    int sum = 0;
    for(int i = 0; i < N ; i++){
        for(int j = i; j < N ; j++){
            
            if(i!=j)sum += d[i]*d[j];
        }
    }
    cout << sum << endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
  int s;
  cin >> s;
  int h = s / 3600;
  s %= 3600;
  int m = s / 60;
  s %= 60;
  cout << h << ":" << m << ":" << s << endl;  
}


Measured memory_bytes: 3088
using System;
using System.Collections.Generic;
using System.Linq;

namespace Aizu
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var data = Console.ReadLine().Split(' ').Select(d => int.Parse(d)).ToList<int>();

            int changeCount = 0;
            for(int i = 0; i < n - 1; i++)
            {
                var pos = -1;
                var minVal = 100;
                for (int j = i + 1; j < n; j++)
                {
                    if(data[j] < minVal)
                    {
                        pos = j;
                        minVal = data[j];
                    }           
                }

                if(pos != -1 && minVal < data[i])
                {
                    changeCount++;
                    var temp = data[i];
                    data[i] = data[pos];
                    data[pos] = temp;
                }
            }

            Console.WriteLine(string.Join(" ", (string[])data.Select(d => d.ToString()).ToArray()));
            Console.WriteLine(changeCount);
        }
    }

}



Measured memory_bytes: 9672
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		char[] s = in.next().toCharArray();

		String result = "Yes";
		for ( int i = 0; i < s.length; i += 2 ) {
			if ( s[i] == 'L' ) result = "No";
		}
		
		for ( int i = 1; i < s.length; i += 2 ) {
			if ( s[i] == 'R' ) result = "No";
		}

		System.out.println(result);
		in.close();
	}
}


Measured memory_bytes: 23760
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
  ll n,m;
  cin>>n>>m;
  ll dp[n][m];
  memset(dp,0,sizeof(dp));
  ll i=0;
  char a[n][m];
  ll j=0;
  for(i=0;i<n;i++)
  {
    for(j=0;j<m;j++)
    {
      cin>>a[i][j];
    }
  }
  for(i=0;i<n;i++)
  {
    if(a[i][0]!='#')
      dp[i][0]=1;
    else
      break;
  }
  for(i=0;i<m;i++)
  {
    if(a[0][i]!='#')
    { 
      dp[0][i]=1;
    }
    else
      break;
  }
  dp[0][0]=0;
  for(i=1;i<n;i++)
  {
    for(j=1;j<m;j++)
    {
      if(a[i][j]!='#')
      dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
      else
      dp[i][j]=0;
    }
  }
  /*for(i=0;i<n;i++)
  {
    for(j=0;j<m;j++)
      cout<<dp[i][j]<<" ";
     cout<<"\n";
  }*/
  cout<<dp[n-1][m-1]%mod<<"\n";
}

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

def square(h, w, ans):
    for i in range(1, w):
        a = h * i
        b1 = ((w - i) // 2) * h
        b2 = (w - i) * (h // 2)
        c1 = ((w - i) - ((w - i) // 2)) * h
        c2 = (w - i) * (h - (h // 2))
        ans = min(ans, max([a, b1, c1]) - min([a, b1, c1]), max([a, b2, c2]) - min([a, b2, c2]))
    return ans

def main():
    h, w = map(int, input().split())
    ans = 10 ** 10
    ans = square(h, w, ans)
    ans = square(w, h, ans)
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
s = input()
t = input()

t_len = len(t)
s_len = len(s)

dp = [[0]*(t_len+1) for _ in range(s_len+1)]

for i in range(1,s_len+1):
    for j in range(1,t_len+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

#print(dp[s_len][t_len])

s_len_tmp = s_len
t_len_tmp = t_len
ans = ''

while s_len_tmp > 0 and t_len_tmp > 0:
    if dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp-1][t_len_tmp]:
        s_len_tmp -= 1
    elif dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp][t_len_tmp-1]:
        t_len_tmp -= 1
    else:
        ans += s[s_len_tmp-1]
        s_len_tmp -= 1
        t_len_tmp -= 1
   
print(ans[::-1])

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

int main(int argc, char const *argv[])
{
	long long n,p;
	cin>>n>>p;
	if (n==1LL)
	{
		cout<<p<<endl;
		return 0;
	}
	long long ans=1LL,now=2LL;
	while (p>1LL&&now*now<=p)
	{
		long long cnt=0LL;
		while (p%now==0LL)
		{
			p/=now;
			++cnt;
		}
		for (int i = 0; i < (int)cnt/n; ++i)
		{
			ans*=now;
		}
		++now;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class D
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var h = read();
		var p = read();
		var uf = new UF(h[0] + 1);
		foreach (var r in new int[h[1]].Select(_ => read())) uf.Unite(r[0], r[1]);
		Console.WriteLine(p.Select((x, i) => uf.AreUnited(x, i + 1)).Count(x => x));
	}
}

class UF
{
	int[] p;
	public UF(int n) { p = Enumerable.Range(0, n).ToArray(); }

	public void Unite(int a, int b) { if (!AreUnited(a, b)) p[p[b]] = p[a]; }
	public bool AreUnited(int a, int b) => GetRoot(a) == GetRoot(b);
	int GetRoot(int a) => p[a] == a ? a : p[a] = GetRoot(p[a]);
}


Measured memory_bytes: 27320
s, t = Array.new(2) { gets.chomp }

answers = []
(s.size - t.size + 1).times do |i|
  tmp = s.dup
  if tmp[i...i+t.size].chars.map.with_index { |char, j| [??, t[j]].include? char }.all?
    t.size.times { |j| tmp[i + j] = t[j] }
    answers << tmp.gsub("?", "a")
  end
end

if answers.empty?
  puts "UNRESTORABLE"
else
  puts answers.sort.first
end


Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

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

ll n,m;

bool G[1000][1000];
bool Gc[1000][1000];

int color[1000];

P cou;
vector<P> p;

bool dfs(ll i) {
    bool ret = true;
    rep(j,n) {
        if(Gc[i][j]) {
            if(color[j] == 0) {
                color[j] = -1 * color[i];
                if(color[j] == 1)cou.first++;
                else cou.second++;
                ret &= dfs(j);
            }else {
                if(color[i] == color[j])return false;
            }
        }
    }
    return ret;
}

ll dp[1000][10000];

ll c2(ll n) {
    if(n < 2)return 0;
    return n * (n - 1) / 2;
}

int main() {
    cin >> n >> m;
    rep(i,m) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a][b] = G[b][a] = 1;
    }

    rep(i,n) {
        rep(j,n) {
            if(i == j)continue;

            Gc[i][j] = !G[i][j];
        }
    }

    rep(i,n) {
        if(color[i] == 0) {
            color[i] = 1;
            cou.first = 1;
            cou.second = 0;
            if(!dfs(i)) {
                cout << -1 << endl;
                return 0;
            }
            p.push_back(cou);

        }
    }

    dp[0][0] = 1;

    for(int i = 0;i < p.size();i++) {
        auto a = p[i];
        for(int j = 0;j <= n;j++) {
            dp[i + 1][j + a.first] |= dp[i][j];
            dp[i + 1][j + a.second] |= dp[i][j];
        }
    }

    ll ans = 1e18;

    for(int i = 0;i <= n;i++) {
        if(dp[p.size()][i]) {
            ans = min(ans,c2(i) + c2(n - i));
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 56960
private fun readIntArray(): List<Int> {
    return readLine()!!.split(" ").map{ it.toInt() }
}
private fun readInt(): Int {
    return readLine()!!.toInt()
}

fun main(args: Array<String>) {
    val A = readInt()
    val B = readInt()
    val C = readInt()
    val X = readInt()

    var ans = 0
    for(i in 0..A) {
        val a = X - 500 * i
        if(a < 0) {
            break
        }

        for(j in 0..B) {
            val b = a - 100 * j
            if (b < 0) {
                break
            }
            for(k in 0..C) {
                val c = b - 50 * k
                if(c < 0) {
                    break
                }
                if(c == 0) {
                    ans += 1
                }
            }
        }
    }

    println(ans)
}


Measured memory_bytes: 31752
/*
方針として、
x軸かy軸が同じ点の集まりに対して、全(x,y)の格子点が作成される
ので、その点の集まりを作成すればよい

集まりはUnionFindで確認する。
要素は、x軸およびy軸
点(x,y)があると、そのx軸とy軸を統合する。
*/

#include <iostream>
#include <unordered_map>

using namespace std;

const char X = 'x';
const char Y = 'y';

// 軸オブジェクト
struct Axis {
  char name; // x軸かy軸か
  long long value; // 軸の座標
  // unordered_map のキーにするため実装(hashも下で実装している)
  bool operator==(const Axis& other) const { // 2個めのconstの意味は、constメンバ関数。内部でthisが変化しないので、constオブジェクトからも呼び出せるようになる
    return name == other.name && value == other.value;
  }
  bool operator!=(const Axis& other) const {
    return !(*this == other);
  }
  string to_s() const { //TODO: << に渡す型は本当は何か？
    return to_string(name) + ":" + to_string(value);
  }
};
namespace std{ //TODO: この書き方面倒くさい… hash()定義するのにstruct外って変じゃない？
    template<>
    class hash<Axis>{
        public:
        size_t operator () ( const Axis &p ) const{ return p.value << 2 + (p.name == X ? 1 : 0);}
        //TODO:どうhash作る？ ひとまずnameは2個しかないので、最終ビットに追加
        //別に一意になる必要はないが、衝突が少ない程良いmapになるはず
    };
}
// 領域
struct Area {
  int x; // x軸の数
  int y; // y軸の数
};
// union find実装
struct UnionFind {
  unordered_map<Axis, Axis> parents;
  unordered_map<Axis, Area> areas; // 領域はrootのみに持たせる。あとで領域ごとに計算するため。

  void add(const Axis& axis) { // Axisはintみたいな値型とみなして、ポインタ渡しはしない。他の関数も同じ
    if (parents.find(axis) != parents.end()) { //containsがc++17までないので、その代わり
      return;
    }

    parents[axis] = axis;
    areas[axis] = { // 初回はルートになるので、領域を持たせる
      axis.name == X ? 1 : 0,
      axis.name == Y ? 1 : 0};
  }

  void unite(const Axis& a, const Axis& b) {
    const Axis& ra = root(a);
    const Axis& rb = root(b);

    if (ra == rb) {
      return;
    }

    parents[rb] = ra;

    // 親になるほうに領域を統合して、他方は削除する
    areas[ra].x += areas[rb].x;
    areas[ra].y += areas[rb].y;
    areas.erase(rb);
  }

  Axis root(const Axis& a) {
    if (parents[a] != a) {
      parents[a] = root(parents[a]);
    }

    return parents[a];
  }
};

int main() {
  UnionFind uf;
  long long n;
  int x,y;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x;
    cin >> y;
    Axis ax = {X, x};
    Axis ay = {Y, y};
    uf.add(ax); // x軸追加
    uf.add(ay); // y軸追加
    uf.unite(ax, ay); // x,y を統合
  }

  long long all_points = 0; // 全操作完了後の点の数
  for (const pair<const Axis, Area>& p : uf.areas) {
    //TODO:debug cout << "axis:" << p.first.to_s() << " area:" << p.second.x << ", " << p.second.y << endl;
    all_points += 1LL * p.second.x * p.second.y; //x*yがintをオーバーフローする可能性があるので、long long型にしておく
  }

  long long result = all_points - n; // もともとあったn個を引いたのが、作成された数

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 8868
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

unordered_map<long, unordered_set<long>> naibors;
unordered_map<long, bool> searched;
map<long, long> result;

long score = 0;

void rec(long current, priority_queue<long, vector<long>, greater<long>> &pq) {
  searched[current] = true;
  for (auto it: naibors[current]) {
    if (searched[it]) continue;
    rec(it, pq);
  }
  long tmp = pq.top();
  pq.pop();
  result[current] = tmp;
  score += tmp;
  return;
}

int main(void) {
  cout.precision(12);

  long N;
  cin >> N;

  for (long i = 1; i <= N-1; i++) {
    long a, b;
    cin >> a >> b;
    naibors[a].insert(b);
    naibors[b].insert(a);
  }

  long max_c = 0;
  priority_queue<long, vector<long>, greater<long>> pq;
  rep(i, N) {
    long c;
    cin >> c;
    pq.push(c);
    max_c = max(max_c, c);
  }

  rec(1, pq);

  cout << score - max_c << endl;
  bool flag = false;
  for (auto it: result) {
    cout << (flag ? " " : "") << it.second;
    flag = true;
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 4096