akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <utility>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
#define mod 1000000007
using namespace std;

int main(){
	int H,W,K;
	cin >> H >> W >> K;
	ll dp[H+1][W+1]={};//first is location.second is numbebr
	dp[0][0]=1;
	rep(i,0,H){ //現在地(高さ)
		rep(j,0,W){ //現在地(横)
			rep(k,0,(1<<(W-1))){
				bool ok = false;
				rep(l,0,W-2){
					if((k & (1<<l)) && (k & (1<<1+l)))ok = true;//隣合ってる横線がともにtrueなら除外
				}
				if(ok) continue;
				if(j>=1 && (k & (1<<j-1))){ //もし現在地から左にいけるなら
					dp[i+1][j-1] += dp[i][j]; //一段下がって,左に移行した値
					dp[i+1][j-1] %= mod;
				}else if(j<=W-2 && (k & (1<<j))){//右版
					dp[i+1][j+1] += dp[i][j];
					dp[i+1][j+1] %= mod;
				}else{ //したにおりる版
					dp[i+1][j] += dp[i][j];
					dp[i+1][j] %= mod;
				}
			}
		}
	}
	cout << dp[H][K-1] << endl;
}

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

int main(){

	int n,k;
	cin>>n>>k;
	int aa;
	vector<int> arr(n);
	for(int i=0;i<n;i++){
		cin>>aa;
		arr[i] = aa;
	}
	vector<int> dp(k+1);
	dp[0] = false;
	for(int i=0;i<=k;i++){
		for(int j=0;j<n;j++){
			if(i>=arr[j] && dp[i-arr[j]] == false) dp[i] = true;
		}
	}
	if(dp[k]) cout<<"First";
	else cout<<"Second";
	return 0;
	
	
	
}


Measured memory_bytes: 640
#include "bits/stdc++.h"

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;


ll N;
ll score[100010][3];
ll dp[100010][3];
int main(){
	cin >> N;
	REP(i,0,N){
		cin >> score[i][0] >> score[i][1] >> score[i][2];
	}
	dp[0][0]=0;
	REP(i,0,N){
		REP(j,0,3){
			REP(k,0,3){
				if (j == k) continue;
				dp[i+1][k] = max(dp[i+1][k], dp[i][j] + score[i][k]);
			}

		}
	}
	p(max({dp[N][0], dp[N][1], dp[N][2]}));
	return 0;
}

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


void main()
{
  for(string[] inputs; (inputs = readln.split)[0] != "0";)
	writeln( solve( inputs[0].to!int, inputs[1].to!int ) );
}

int[][] G, D;
bool[][][] M;

int solve(int n, int m)
{
  G = new int[][](n, n);
  D = new int[][](n, 2);
  M = new bool[][][](n, n, 2);

  foreach(i; 0..n){
	foreach(j; 0..n){
	  G[i][j] = (i == j ? 0 : int.max / 2);
	  M[i][j][0] = M[i][j][1] = false;
	}

	D[i][0] = D[i][1] = int.max / 2;
  }
  
  foreach(_; 0..m){
	auto inputs = readln.split;

	int a = inputs[0].to!int, b = inputs[1].to!int, c = inputs[2].to!int;

	G[a - 1][b - 1] = c;
	G[b - 1][a - 1] = c;

	M[a - 1][b - 1][0] = true;
	M[b - 1][a - 1][0] = true;
  }

  foreach(i; 0..n)
	foreach(j; 0..n)
	  foreach(k; 0..n)
		if(M[i][k][0] && M[k][j][0])
		  M[i][j][1] = true;

  dfs(n, 0, 1, 0);

  return min(D[n - 1][0], D[n - 1][1]);
}

void dfs(int n, int now, int magic, int cost)
{
  if(D[now][magic] <= cost) return;

  D[now][magic] = cost;
  
  foreach(next; 0..n){
	if(M[now][next][0]) dfs(n, next, magic, cost + G[now][next]);
	if(M[now][next][1] && 0 < magic) dfs(n, next, magic - 1, cost);
  }
}

/*
現在いる場所、そこまでの費用、特別乗車券を使ったかどうかで最小値を更新するDFSをします。
特別乗車券を使えるのはi,jの間にパス2の経路が存在する場合だけなので、それをMに記録していきます。
あるkを選択する時iからk、kからjまでの経路が存在すれば特別乗車券が使えます。
*/

/*
2 1
1 2 5
3 2
1 2 5
2 3 5
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 5 9
4 6 8
0 0
*/

Measured memory_bytes: 2876
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)


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

    ll n,Q;cin>>n>>Q;
    vector<vector<ll>> e(n+1,vector<ll>(0));
    vector<ll> node(n+1,0);
    vector<ll> ans(n+1,0);
    vector<bool> f(n+1,false);

    rep(i,n-1){
        ll a,b;cin>>a>>b;
        e.at(a).pb(b);
        e.at(b).pb(a);
    }

    rep(i,Q){
        ll p,x;cin>>p>>x;
        node.at(p)+=x;
    }

    queue<ll> q;
    q.push(1);
    q.push(0);

    while(!q.empty()){
        ll v=q.front();q.pop();
        ll score=q.front();q.pop();

        score+=node.at(v);
        f.at(v)=true;
        ans.at(v)=score;

        for(int i=0;i < siz(e.at(v));i++)
        {
            if(!f[e[v][i]]){
                q.push(e[v][i]);
                q.push(score);
            }
        }
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<(i==n ? '\n':' ');
    }

}


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

namespace AtCoder
{
    class Code2
    {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();
            string s2 = Console.ReadLine();

            Console.WriteLine(funcMain(s1,s2));
        }

        static private string funcMain(string arg1, string arg2)
        {
            string ret = "EQUAL";
            // 長さ比較
            if (arg1.Length > arg2.Length)
                ret = "GREATER";
            else if (arg1.Length < arg2.Length)
                ret = "LESS";
            else
            {
                for (int i = 0; i < arg1.Length; i++)
                {
                    if (int.Parse(arg1[i].ToString()) > int.Parse(arg2[i].ToString()))
                    {
                        ret = "GREATER";
                        break;
                    }
                    else if (int.Parse(arg1[i].ToString()) < int.Parse(arg2[i].ToString()))
                    { 
                        ret = "LESS";
                        break;
                    }
                }
            }

            return ret;
        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>
 
 

 
int main(void){
	int i,j,k;
	int n,num[4000];
	long long int tanka,sale_num,sale_sum[4000],sale_all[4001];
	bool judge[4001];
	
	while(scanf("%d",&n),n){
		
		//初期化


		
		for(i=0;i<n;i++){
			scanf("%d %lld %lld",&num[i],&tanka,&sale_num);
			sale_sum[i]=tanka*sale_num;
		}

		k=0;
		for(j=0;j<4001;j++){
			judge[j]=0;
			sale_all[j]=0;
		}
		
		
		//idに対応したsaleに+
		for(i=0;i<n;i++){
			sale_all[num[i]] = sale_all[num[i]] + sale_sum[i];
		}
		
		for(i=0;i<n;i++){
			if((sale_all[num[i]] >= 1000000)&&(judge[num[i]]==0)){
				printf("%d\n",num[i]);
				judge[num[i]]=1;
				k=1;
			}
		}
		
		if(k!=1)printf("NA\n");
	}
	
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};


const double EPS = 1e-9;

int main(){
    int t;
    cin >> t;
    for(int test_case=0;test_case<t;test_case++){
        int n,k;
        cin >> n >> k;
        vector<ll> X(n);
        for(int i=0;i<n;i++) cin >> X[i];
        vector<ll> D(n-1);
        for(int i=0;i<n-1;i++){
            D[i] = X[i+1] - X[i];
        }
        sort(all(D));
        ll ce = min(n-1,k-1);
        ll ret = 0;
        for(int i=0;i<(n-1)-ce;i++){
            ret += D[i];
        }
        cout << ret << endl;
    }
    return 0;
}

Measured memory_bytes: 2528
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
int solve(string s){
	int cs=0,mi=0,ans=0;
	set<int> S;
	for(int i=0;i<s.size();i++){
		if(s[i]=='1')cs++;
		else cs--;
		chmin(mi,cs);
		if(ans<cs-mi){
			S.clear();
			ans=cs-mi;
		}
		if(ans==cs-mi){
			S.insert(i%2);
		}
	}
	if(S.size()==2)ans++;
	return ans;
}
int main(){
	string s;
	cin>>s;
	if(s.size()==1){
		cout<<1<<endl;
		return 0;
	}
	int a=solve(s);
	for(int i=0;i<s.size();i++){
		if(s[i]=='0')s[i]='1';
		else if(s[i]=='1')s[i]='0';
	}
	int b=solve(s);
	//cout<<a<<" "<<b<<endl;
	cout<<max(a,b)<<endl;
}


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


#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ll long long


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    vi antenas(5);
    int dist;

    for ( int i = 0; i < 5; i++ ) cin >> antenas[i];
    cin >> dist;

	for ( int i = 0; i < 4; i++ ) {
		for ( int j = i + 1; j < 5; j++ ) {
			if ( abs(antenas[i] - antenas[j]) > dist ) {
				cout << ":(\n";
				return 0;
			}
		}
	}

	cout << "Yay!\n";


    return 0;
}


Measured memory_bytes: 256
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())


def era(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    data1 = []
    for d in data:
        data1.append([d, 1])
    return data1


mod = 10 ** 9 + 7
n = ni()
lis = era(n)
for i in range(1, n + 1):
    for j in range(len(lis)):
        if i < lis[j][0]:
            break
        elif i % lis[j][0] == 0:
            count = 0
            m = i
            while(m % lis[j][0] == 0):
                m = m // lis[j][0]
                count += 1
            lis[j][1] += count
ans = 1
for i in range(len(lis)):
    ans *= lis[i][1]
    ans %= mod
print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <bitset>
#include <cmath>
#include <string>
#include <stdlib.h>

#define ll long long
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)

using namespace std;


int main() {
    int N, K; cin >> N >> K;
    string S; cin >> S;
    int ans = 0;
    repp(i,1,N) {
        if (S[i-1] == S[i]) ++ans;
    }
    cout << min(N-1, (ans+2*K)) << endl;
}


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

using std::cout;
using std::cin;
using std::endl;

/*  テンプレここから */
typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define inf (1e9)
#define infl (1e18)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outpossible(bool_val) cout << (bool_val ? "possible" : "impossible") << endl;
#define outpossible(bool_val) cout << (bool_val ? "possible" : "impossible") << endl;

template<typename a, size_t n, typename t>
void array_fill(a (&array)[n], const t &val){
    std::fill( (t*)array, (t*)(array+n), val );
}

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
/*  テンプレここまで */

std::vector<ll> prime_common_divisors(ll num)
{
    std::vector<ll> nums(1, 1);
    ll save_num = num;
    for(ll d = 2; d*d <= save_num; ++ d) {
        if(num % d == 0) nums.emplace_back(d);
        while(num % d == 0) num /= d;
    }
    if(num != 1) nums.emplace_back(num);
    return nums;
}

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

    ll a, b;
    cin >> a >> b;

    std::vector<ll> a_list = prime_common_divisors(a);
    std::vector<ll> b_list = prime_common_divisors(b);

    std::sort(all(a_list));
    std::sort(all(b_list));

    int ans = 0;
    for(int i = 0; i < (int)a_list.size(); ++ i) {
        ans += (std::count(all(b_list), a_list[i]) == 1);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

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

int main(void) {
  int i,j;
  int n;
  while(1){
    cin>>n;
    if(n==0)break;
    vi v;
    while(n){
      v.push_back(n%8);
      n/=8;
    }
    reverse(all(v));
    rep(i,v.size()){
      if(v[i]>=4)v[i]++;
      if(v[i]>=6)v[i]++;
      cout<<v[i];
    }
    cout<<endl;
  }
}

Measured memory_bytes: 3008
x, y = map(int, input().split())
r = 0

if x == 1 or y == 1:
	r += 300000
if x == 2 or y == 2:
	r += 200000
if x == 3 or y == 3:
	r += 100000	
if x == 1 and y == 1:
	r = 1000000
if x == 2 and y == 2:
	r = 400000
if x == 3 and y == 3:
	r = 200000

print(r)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
const int A=0;
const int B=1;
const int C=2;
const int INF=45451919;
int D,N;
int temp[201],huku[201][3];
int dp[201][201];


int main(){
	cin>>D>>N;
	for(int i=1;i<=D;i++)cin>>temp[i];
	for(int i=1;i<=N;i++)cin>>huku[i][A]>>huku[i][B]>>huku[i][C];
	//for(int i=1;i<=N;i++)cout<<huku[i][A]<<huku[i][B]<<huku[i][C]<<endl;
	for(int i=0;i<201;i++)for(int j=0;j<201;j++)dp[i][j]=-1;
	for(int i=1;i<=N;i++)if(huku[i][A]<=temp[1]&&huku[i][B]>=temp[1])dp[1][i]=0;
	
	
//		for(int j=0;j<10;j++)
//	cout<<huku[j][C]<<"  ";
//	cout<<endl;
	
for(int i=1;i<=D;i++){
	for(int j=1;j<=N;j++){
		if(huku[j][A]<=temp[i]&&huku[j][B]>=temp[i]&&dp[i][j]!=-1){
			for(int k=1;k<=N;k++){
				if(huku[k][A]<=temp[i+1]&&huku[k][B]>=temp[i+1]){
					dp[i+1][k]=max(abs(huku[k][C]-huku[j][C])+dp[i][j],dp[i+1][k]);
					}
			}
		}
	}
}
	//デバッグ
		/*for(int i=1;i<=D;i++){
		for(int j=1;j<=N;j++){
			cout<<dp[i][j]<<" ";
		}*/
		int ans=0;
		for(int i=1;i<=N;i++)ans=max(ans,dp[D][i]);
			cout<<ans<<endl;
	
return 0;
}

Measured memory_bytes: 1320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

int main(){
    ll N, M;
    cin >> N >> M;
    VL a(N), acc(N+1, 0);
    rep(i, 0, N) cin >> a[i];
    sort(ALL(a));
    rep(i, 0, N) acc[i+1] = acc[i] + a[i];
    ll L = 0, R = 1e9;
    while(R - L > 1){
        ll mid = L + (R - L)/2;
        ll num = 0;
        rep(i, 0, N){
            auto itr = lower_bound(a.begin(), a.end(), mid - a[i]);
            auto pos = distance(a.begin(), itr);
            num += (N - pos);
        }
        if(num >= M) L = mid;
        else R = mid;
    }

    ll ans = 0, num = 0;
    rep(i, 0, N){
        auto itr = lower_bound(a.begin(), a.end(), L - a[i]);
        auto pos = distance(a.begin(), itr);
        num += N - pos;
        ans += a[i] * (N - pos) + (acc[N] - acc[pos]);
    }
    ans -= (num - M) * L;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>

int main(){
    char a[3][3];
    scanf("%s",a[0]);
    scanf("%s",a[1]);
    scanf("%s",a[2]);
    std::cout<<a[0][0]<<a[1][1]<<a[2][2]<<"\n";
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
const int INF=1e9+5;
const int N=200000+5;
const ll oo=1e18+5;
const ll mod=998244353;


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	unordered_map<string,int> maps;
	int ans=0;
	for(int i=0;i<n;++i){
		string s;
		cin>>s;
		if(!maps[s]) ++ans;
		++maps[s];
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 17744
#include <iostream>
#include <vector> 
#include <algorithm>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

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

  // Input
  int n;
  cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a.at(i);
  sort(a.begin(), a.end());
  int answer;
  answer = a[n-1] - a[0];
  

  // Output
	cout << answer << "\n";
	return 0;
}

Measured memory_bytes: 256
///HELLO THERE~!
///CREATED BY MD SADMAN MEHEDI SIVAN(IUT CSE-SWE^19)

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define read freopen("blue.txt","r",stdin);
#define write freopen("red.txt","w",stdout);


typedef long long ll;

using namespace std;


int main()
{
   int N,P;
   cin>>N>>P;
   cout<<N-P+1;


	return 0;

}


Measured memory_bytes: 256
S = input()

if len(S) == 1:
    print(0)
    exit(0)

n = len(S) // 2
S1 = '01' * n
S2 = '10' * n
if n % 2 == 1:
    S1 += '0'
    S2 += '1'
ret1 = 0
ret2 = 0
for idx, s in enumerate(S):
    if S1[idx] != s:
        ret1 += 1
    if S2[idx] != s:
        ret2 += 1


print(min(ret1, ret2))

Measured memory_bytes: 3316
/*
 /+==================================================+\
//+--------------------------------------------------+\\
|.|\\...>>>>>>> Hollwo_Pelw(ass) 's code <<<<<<<...//|.|
\\+--------------------------------------------------+//
 \+==================================================+/
*/
#include <bits/stdc++.h>
using namespace std;
// type
typedef long long ll;
typedef long double ld;
// loop
//#define For(i, l, r)        for (int i = l; i < r; i++)
//#define ForE(i, l, r)       for (int i = l; i <= r; i++)
//#define Ford(i, r, l)       for (int i = r; i > l; i--)
//#define FordE(i, r, l)      for (int i = r; i >= l; i--)
//#define Fora(i, a)          for (auto i : a)
// I/O
#define open(file, in, out) if (fopen(file in, "r")) {        \
                                freopen(file in, "r", stdin);  \
                                freopen(file out, "w", stdout); \
                            }
#define FAST_IO             std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define setpre(n)           fixed << setprecision(n)
// pair
#define F                   first
#define S                   second
#define pii                 pair<int, int>
#define pll                 pair<ll, ll>
#define pdd                 pair<ld, ld>
// vector & !!?(string)
#define eb                  emplace_back
#define pb                  push_back
#define all(a)              a.begin(), a.end()
#define rall(a)             a.rbegin(), a.rend()
#define sz(a)               a.size()
#define len(a)              a.length()
// geometry calculate
#define pi                  acos(-1.0)
#define g_sin(a)            sin(a*pi/180)
#define g_cos(a)            cos(a*pi/180)
#define g_tan(a)            tan(a*pi/180)
// set val
#define ms0(a)              memset(a,        0, sizeof(a));
#define ms1(a)              memset(a,        1, sizeof(a));
#define msn1(a)             memset(a,       -1, sizeof(a));
#define msinf(a)            memset(a, 0x3f3f3f, sizeof(a));
// constant
const int mod1 = 998244353, mod = 1e9+7;
const int MAXN = 100005, MAXM = 200010;
// code
#define int long long

void Solve() {
    int n; cin >> n;
    vector<pii> arr;
    vector<int> dp(n+1);
    for (int i = 0, x, y; i < n; i++){
        cin >> x >> y;
        arr.eb(x, x+y);
    }
    arr.eb(1e10, 1e10+1);
    sort(all(arr));

    dp[n] = 1;

    stack<int> st;
    st.push(n);

    for (int i = n-1; i >= 0; i--){
        while (arr[st.top()].F < arr[i].S)
            st.pop();
        int j = st.top();
        dp[i] = (dp[i + 1] + dp[j]) % mod1;
        st.push(i);
    }
    cout << dp[0];
}

signed main(){
    open("", ".inp", ".out");
    FAST_IO;
    int TC = 1;
    //cin >> TC;
    while(TC--) Solve();
    return 0;
}
/*
./-=====>>><<<-------- DEBUG -------->>><<<=====-\.
/.................................................\

+====================== INP ======================+


+====================== OUT ======================+


\................................................./
.\-=====>>><<<--------= END =-------->>><<<=====-/.
*/


Measured memory_bytes: 8996
import java.util.Scanner;

public class  Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); //台形の面積を求める
        int a = sc.nextInt(); //上辺
        int b = sc.nextInt(); //下辺
        int h = sc.nextInt(); //高さ
      
        System.out.println((a+b)*h/2);
    }
}

Measured memory_bytes: 21844
c = [list(map(int, input().split())) for _ in range(3)]
m = 0
for a1 in range(101):
    b1 = c[0][0] - a1
    if b1 >= 0:
        if a1 + b1 == c[0][0]:
            a2 = c[1][0] - b1
            a3 = c[2][0] - b1
            b2 = c[0][1] - a1
            b3 = c[0][2] - a1
            if a2 >= 0 and a3 >= 0 and b2 >= 0 and b3 >= 0:
                if a2 + b2 == c[1][1] and a3 + b2 == c[2][1]:
                    if a2 + b3 == c[1][2] and a3 + b3 == c[2][2]:
                        m = 1
if m == 1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
using System;
class Program
{
    public static void Main()
    {
        string[] str = Console.ReadLine().Split(' ');
        int area = int.Parse(str[0]) * int.Parse(str[1]);
        int rect = 2 * (int.Parse(str[0]) + int.Parse(str[1]));
        Console.WriteLine(area + " " + rect);
    }   
}


Measured memory_bytes: 15868
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n,div,flag=0;
    cin>>n;
    while(n!=0)
    {
        div=n%10;
        if(div==7)
        {
            flag=1;
            break;
        }
        n=n/10;
    }
    (flag==1)?
        cout<<"Yes"<<endl:
            cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
    long long int x, y;
    cin >> x >> y;

    int ans = 0;

    while(x <= y){
        x *= 2;
        ans++;
    }

    cout << ans << endl;

    /*
    double x, y;
    cin >> x >> y;
    long long int ans = 0;
    ans = (long long int)log2(y/x) + 1;

    cout << ans << endl;
    */
}

Measured memory_bytes: 888
n,k=map(int,input().split())
a=list(map(int,input().split()))
kk=a[0]
import fractions
for i in range(n-1):
	kk=fractions.gcd(kk,a[i+1])
if kk==1 and max(a)>=k:
	print("POSSIBLE")
elif k%kk!=0 or max(a)<k:
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")


Measured memory_bytes: 14224
#include <stdio.h>

/* 配列の要素を順番に出力 */
void trace(int A[],int N) {
    int i;
    for(i=0;i<N;i++) {
        /* 隣接する要素の間に1つの空白を出力 */
        if(i>0) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
}

/* 挿入ソート(0オリジン配列) */
void insertionSort(int A[], int N) {
    int i,j,v;
    for(i=1;i<N;i++) {
        v=A[i];
        j=i-1;
        while(j>=0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1]=v;
        trace(A,N);
    }
}

int main(void)
{
    int N, i;
    int A[100];
    scanf("%d",&N);
    for(i=0;i<N;i++) scanf("%d",&A[i]);
    
    trace(A,N);
    insertionSort(A,N);
    return 0;
}


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

int main(){
  int a,b,B[5001];
  vector <int> A[1001];
  cin>>a>>b;
  for(int i=0,t;i<a;i++) cin>>t,A[t].push_back(i);
  for(int i=0;i<b;i++) cin>>B[i];
  
  int ans=0;
  for(int i=0;i<b;i++){
    int cnt=0;
    for(int j=i,pre=-1;j<b;j++){
      int nx;
      for(nx=0;nx<A[B[j]].size();nx++)if(A[B[j]][nx]>pre)break;
      if(nx==A[B[j]].size())break;
      pre=A[B[j]][nx];
      cnt++;
    }
    ans=max(ans,cnt);
  }
  cout <<ans<<endl;
  return 0;
}

Measured memory_bytes: 1308
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//






int main(void) {

    int n; cin >> n;
    vector <int> p(n), q(n);
    rep(i,n) cin >> p[i];
    rep(i,n) cin >> q[i];

    vector <int> order(n);
    rep(i,n) order[i] = i + 1;
    int num = 0;
    int a, b;
    do {
        bool same = true;
        rep(i,n) {
            if (p[i] != order[i]) {
                same = false;
            }
        }
        if (same) {
            a = num;
        }
        same = true;
        rep(i,n) {
            if (q[i] != order[i]) {
                same = false;
            }
        }
        if (same) {
            b = num;
        }
        ++num;
    } while (next_permutation(order.begin(), order.end()));

    cout << abs(a - b) << endl;

    return 0;
}









Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k,i,j;
	cin >> n >> k;
	int h[n];
	for(i=0;i<n;i++)
	{
		cin >> h[i];
	}
	int dp[n];
	dp[0]=0;
	for(i=1;i<n;i++)
	{
		dp[i] = INT_MAX;
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<=i+k;j++)
		{
			if(j<n)
				dp[j] = min(dp[j], dp[i] + abs(h[i]-h[j]));
		}
	}
	cout << dp[n-1]<< endl;
}

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

int main()
{
    int A, B;
    cin >> A >> B;
    if((A+B) % 3 == 0) cout << "Possible" << "\n";
    else if(A % 3 == 0 || B % 3 == 0) cout << "Possible" << "\n";
    else cout << "Impossible" << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    string S  = in<string>();
    int number = 0;
    if(S[0] == '+')number++;
    if(S[1] == '+')number++;
    if(S[2] == '+')number++;
    if(S[3] == '+')number++;
    if(S[0] == '-')number--;
    if(S[1] == '-')number--;
    if(S[2] == '-')number--;
    if(S[3] == '-')number--;
    cout << number << "\n";
}

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

class Program
{
    static void Main(string[] args)
    {
        long[] av = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
        long[] bw = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
        long a = av[0];
        long v = av[1];
        long b = bw[0];
        long w = bw[1];
        long t = long.Parse(Console.ReadLine());
        long ab = Math.Abs(a - b);
        long vw = v - w;
        if (ab <= vw * t) Console.WriteLine("YES");
        else Console.WriteLine("NO");
    }
}

Measured memory_bytes: 28252
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

#define LL long long
using namespace std;

int main(void){

    int a, b;
    string s;

    cin >> a >> b;
    cin >> s;

    s[b - 1] = s[b - 1] - 0x41 + 0x61;

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>
using namespace std;



int main(){
	
	int a,b;
	while(1){
		cin>>a>>b;
		if(!a&&!b)return 0;
		int p[105][105][5]={};
		for(int i=0;i<=b;i++){
			p[i][1][0]=1;
		}
		for(int i=0;i<=a;i++){
			p[1][i][2]=1;
		}
		for(int i=2;i<=b;i++){
			for(int j=2;j<=a;j++){
				p[i][j][0]+=(p[i-1][j][0]+p[i-1][j][1])%100000;
				p[i][j][1]+=(p[i-1][j][2])%100000;
				p[i][j][2]+=(p[i][j-1][2]+p[i][j-1][3])%100000;
				p[i][j][3]+=(p[i][j-1][0])%100000;
				

			}
		}
		cout<<(p[b][a][1]+p[b][a][2]+p[b][a][3]+p[b][a][0])%100000<<endl;

	}
	return 0;
}

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

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

using namespace std;

int x,y;
char c[10];
vector<string> vec;

inline bool fin(int xp,int yp){
  return ( min(xp,yp) <= 3 && max(xp,yp) == 5 ) ||
    ( xp == yp && yp == 5 ) || 
    ( min(xp,yp) == 4 && max(xp,yp) == 6 );
}

void dfs(int cur,int xp,int yp){
  if( xp == x && yp == y ) {
    string s = "";
    rep(i,xp+yp) s += string(1,c[i]);
    vec.push_back(s);
  }
  if( fin(xp,yp) ) return;
  c[cur] = 'A';
  dfs(cur+1,xp+1,yp);
  c[cur] = 'B';
  dfs(cur+1,xp,yp+1);
}

int main(){
  cin >> x >> y;
  dfs(0,0,0);
  rep(i,vec.size()) cout << vec[i] << endl;
  return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n, m;
string s;
int dp[200009];
int seg[400009];
void upd(int v, int tl, int tr, int idx, int val){
    //cout << idx << " " << v << "\n";
    if(idx < tl || idx > tr)
        return;
    if(tl == idx && tr == idx){
        seg[v] = val;
        return;
    }
    else{
        int tm = (tl+tr)/2;
        upd(2*v, tl ,tm, idx, val);
        upd(2*v+1, tm+1 ,tr, idx, val);
        seg[v] = min(seg[2*v], seg[2*v+1]);
    }
}
int get(int v, int tl, int tr, int l, int r){
    //cout << l << " " << r << " " << v << "\n";
    if(r < tl || l > tr)
        return 1e9;
    if(l <= tl && tr <= r)
        return seg[v];
    else{
        int tm = (tl+tr)/2;
        return min(
            get(2*v, tl, tm, l, r),
            get(2*v+1, tm+1, tr, l, r)
        );
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> m;
    ++n;
    cin >> s;
    
    for(int i = 0; i <= 4*n; ++i)
        seg[i] = 1e9;
    
    for(int i = n-1; i >= 0; --i){
        if(s[i] == '0'){
            if(i == n-1)
                dp[i] = 0;
            else
                dp[i] = 1+get(1, 0, n-1, i+1, min(i+m, n-1));
        }
        else
            dp[i] = 1e9;
        upd(1, 0, n-1, i, dp[i]);
        //cout << dp[i] << "\n";
    }
    if(dp[0] >= 1e9){
        cout << "-1\n";
        return 0;
    }
    int i = 0;
    while(i < n-1){
        for(int j = i+1; j <= i+m; ++j){
            if(dp[j] == dp[i]-1){
                cout << j-i << " ";
                i = j;
                break;
            }
        }
    }
}

Measured memory_bytes: 2640
while True:
 m,f,r = list(map(int, input().split() ))
 if m==-1 and f==-1 and r==-1:
  break
 if m==-1 or f==-1:
  print("F")
 elif m+f>=80:
  print("A")
 elif 65<=m+f<80:
  print("B")
 elif 50<=m+f<65:
  print("C")
 elif 30<=m+f<50:
  if 50<=r:
   print("C")
  else:
   print("D")
 else:
  print("F")



Measured memory_bytes: 5596
private class D {
    fun solve() {
        val n = nextInt()
        val s = nextToken()
        var ans = 0
        var l = 0
        var r = n - 1
        while (l < r) {
            while (l < r && s[l] != 'W') l++
            while (l < r && s[r] != 'R') r--;
            if (l != r) {
                ans++
            }
            l++
            r--
        }
        println(ans)
    }

    var tokenBuffer = listOf<String>()
    var bufferPosition = 0

    private fun checkBuffer() {
        if (bufferPosition == tokenBuffer.size) {
            tokenBuffer = nextLine().split(" ")
            bufferPosition = 0
        }
    }

    fun nextLine() = readLine()!!
    fun nextInt(): Int {
        checkBuffer()
        return tokenBuffer[bufferPosition++].toInt()
    }

    fun nextLong(): Long {
        checkBuffer()
        return tokenBuffer[bufferPosition++].toLong()
    }

    fun nextDouble(): Double {
        checkBuffer()
        return tokenBuffer[bufferPosition++].toDouble()
    }

    fun nextToken(): String {
        checkBuffer()
        return tokenBuffer[bufferPosition++]
    }
}

fun main() {
    val reader = D().solve()

}


Measured memory_bytes: 40724
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

struct UnionFind{
    // 頂点数(1-indexed)
    const int V;
    // par[x]:=xのroot
    vector<int> par;
    // sz[x]:=xを含む集合のサイズ
    vector<int> sz;
    UnionFind(const int V):V(V){
        par.resize(V+1);
        for(int i=0;i<=V;i++) par[i]=i;
        sz.resize(V+1,1);
    }
    bool unite(int x,int y){
        x=root(x),y=root(y);
        if(same(x,y)) return false;
        if(y<x) swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
        return true;
    }
    int root(int x){
    	if(par[x]==x) return x; // xはroot
    	return (par[x]=root(par[x])); // xの親のroot
    }
    bool same(int x,int y){
    	return (root(x)==root(y));
    }
    int size(int x){
        return sz[root(x)];
    }
};

int main(){
    int n,m; cin>>n>>m;
    UnionFind uf(n);
    while(m--){
        int x,y,z; cin>>x>>y>>z;
        uf.unite(x,y);
    }
    set<int> s;
    for(int i=1;i<=n;i++){
        s.insert(uf.root(i));
    }
    cout<<s.size()<<endl;
    return 0;
}


Measured memory_bytes: 5760
def debug(*args):
    if 1 == 1:
        print(*args)

def solve(N, S):
    R = [0]*N
    L = [0]*N
    c = 0
    for i in range(N):
        if S[i] == 'R':
            c += 1
        else: # 'L'
            if c > 0:
                q, r = divmod(c, 2)
                R[i-1] = q + r
                R[i] =  q
                c = 0
    c = 0
    for i in range(N)[::-1]:
        if S[i] == 'L':
            c += 1
        else: # 'R'
            if c > 0:
                q, r = divmod(c, 2)
                L[i] = q 
                L[i+1] =  q + r
                c = 0
    #debug("S:", *S)
    #debug("R:", *R, "R=",sum(R), sum(c == "R" for c in S))
    #debug("L:", *L, "L=",sum(L), sum(c == "L" for c in S))
    #debug("A:", *[x+y for x, y in zip(R, L)])
    #debug("S", sum(x+y for x, y in zip(R, L)), N)
    print(*[x+y for x, y in zip(R, L)])



def main():
    S = input()
    solve(len(S), S)

main()






Measured memory_bytes: 7148
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<ll,ll> prl;
typedef vector<ll> vcl;
typedef map<ll,ll> mapl;
typedef unordered_map<ll,ll> umap;
#define pb push_back
#define all(v) v.begin(), v.end()
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repi(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
const ll mod = 1e9+7;

int main() {
    // your code goes here
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    rep(i,1,k){
    	if(b<=a){
    		b*=2;
    	} else {
    		c*=2;
    	}
    }
    if(a<b&&b<c) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
N = int(input())
A = [0]*N
B = [0]*N
hoge = int(1e18)
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    if a > b:
        hoge = min(hoge, b)

if hoge == int(1e18):
    print(0)
else:
    print(sum(B) - hoge)


Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
    ll N;
    cin >> N;
    ll temp = N; 
    vector<char> ans;
    ll judge_26 = 0;
    
    //以下26進数判定
    while (1) {
        temp --;
        judge_26 = temp % 26;
        char x = 'a' + judge_26; //数値を文字に
        ans.push_back(x);
        temp /= 26;
        if( temp == 0 ) {
            break;
        }
    }
    
    //配列の中身を逆にする
    reverse ( begin(ans), end(ans) );
    
    //配列の中身を出力する範囲ベースfor文
    for ( auto a: ans ) {
        cout << a;
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, a, out;

    cin >> n >> a;

    out = n / 500;
    out = n - out * 500;
    if(a >= out)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
int32_t ARR[300000];
int64_t MAX[112345];//[N-1,2N][0,N+1]
int64_t MIN[112345];//[N-1,2N]
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);

	in >> N;
	for (size_t i = 0; i < 3 * N; i++)
	{
		in >> ARR[i];
	}
	if (std::any_of(ARR, ARR + 3 * N, [](int32_t v) {return !(1 <= v && v <= 1'000'000'000); })) {
		throw 0;
	}
	//std::sort(ARR, ARR + N);
	//std::sort(ARR+2*N-1, ARR + 3*N);

	//前を最大化
	{
		int64_t sum = 0;
		std::priority_queue<int32_t> que;
		for (int32_t i = 0; i < N; i++)
		{
			que.push(-ARR[i]);
			sum += ARR[i];
		}
		MAX[0] = sum;
		//[N,2N]を処理
		for (int32_t i = 0; i <= N; i++)
		{
			que.push(-ARR[N + i]);
			sum += ARR[N + i];
			sum += que.top(); que.pop();
			MAX[i + 1] = sum;
		}
	}
	//後ろを最小化
	{
		int64_t sum = 0;
		std::priority_queue<int32_t> que;
		for (int32_t i = 0; i < N; i++)
		{
			que.push(ARR[3 * N - 1 - i]);
			sum += ARR[3 * N - 1 - i];
		}
		MIN[N + 1] = sum;
		//[N,2N]を処理
		for (int32_t i = 0; i <= N; i++)
		{
			que.push(ARR[2 * N - 1 - i]);
			sum += ARR[2 * N - 1 - i];
			sum -= que.top(); que.pop();
			MIN[N - i] = sum;
		}
	}
	//[N-1,2N]を処理
	int64_t max_value = (-9223372036854775807);
	for (int32_t i = 0; i <= N; i++)
	{
		max_value = std::max(max_value, MAX[i] - MIN[i + 1]);
	}
	std::cout << max_value << std::endl;
	return 0;
}
#endif

Measured memory_bytes: 3952
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

get_chars(Xs) :-
    get_string(S),
    string_chars(S, Xs).

get_numbers(0, []).
get_numbers(N, [X|Xs]) :- 
    get_number(X), 
    N2 is N - 1, 
    get_numbers(N2, Xs).

put_numbers([]).
put_numbers([X|Xs]) :-
    writeln(X),
    put_numbers(Xs).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)
    length(S, L),
    sub_string

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==

    between(L,U,X): L <= X <= U
    nth0(I, Xs, Y), nth1(I, Xs, Y): (Xs,Y) -> I, (I, Xs) -> Y 

    sort(Key, Order, List, Sorted): Keyは通常0?, Orderは=なしが重複削除，=は重複保持
    \+ P(X) : not P(X)
*/

take(0, _, []) :- !.
take(N, [X|Xs], [Y|Ys]) :- Y = X, N2 is N - 1, take(N2, Xs, Ys).

f(K, S) :- 
    length(S, SL),
    SL =< K,    
    string_chars(T, S),
    writeln(T), !.

f(K, S) :-
    take(K, S, S2),
    string_chars(T, S2),
    write(T),
    writeln("...").

main :-
    get_number(K),
    get_chars(S),
    f(K, S).


Measured memory_bytes: 8084
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define ANS cout << ans << endl
#define RETURN(x)    \
  cout << x << endl; \
  return 0
clock_t CLOCK;
#define START_TIMER CLOCK = clock()
#define SHOW_TIMER cerr << "time: " << (ld)(clock() - CLOCK) / 1000000 << endl
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using mll = map<ll, ll>;
using qll = queue<ll>;
using P = pair<ll, ll>;

constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

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

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

struct UnionFind {
  vector<ll> d;
  UnionFind(ll n = 0) : d(n, -1) {
  }
  ll find(ll x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(ll x, ll y) {
    return find(x) == find(y);
  }
  ll size(ll x) {
    return -d[find(x)];
  }
};

signed main() {
  init();
  ll N, M;
  cin >> N >> M;
  vll A(M);
  vll B(M);
  rep(i, M) {
    cin >> A[M - i - 1] >> B[M - i - 1];
    A[M - i - 1]--;
    B[M - i - 1]--;
  }

  UnionFind uf(N);
  vll ans(M);

  ll count = 0;
  rep2(i, 1, N) count += i;

  rep(i, M) {
    ans[M - i - 1] = count;
    if (uf.same(A[i], B[i])) continue;
    ll before = (N - uf.size(A[i])) * uf.size(A[i]) +
                (N - uf.size(B[i])) * uf.size(B[i]);
    uf.unite(A[i], B[i]);
    ll after = (N - uf.size(A[i])) * uf.size(A[i]);
    count -= (before - after) / 2;
  }

  rep(i, M) {
    COUT(ans[i]);
  }

  return 0;
}

Measured memory_bytes: 6372
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint int
using namespace std;
     
typedef long long lo;
     
template<typename tp> inline void read(tp &x) {
	x = 0; char c = getchar(); int f = 0;
	for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
	for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
	if (f) x = -x;
}
const int N = 2333;
vector <int> G[N];
char str[N];
int n, dp[N], size[N], num[N], root;

inline void dfs(int u, int fat) {
	int sum = 0, mx = 0;
	dp[u] = 0; size[u] = str[u]; num[u] = 0;
	for (int v : G[u])
		if (v != fat) {
			dfs(v, u);
			size[u] += size[v];
			sum += dp[v];
			num[u] += num[v];
			mx = max(mx, dp[v]);
		}
	dp[u] = max(sum & 1, 2 * mx - sum);
	if (fat) {
		num[u] += size[u], dp[u] += size[u];
	}
}

inline int work(int u) {
	root = u;
	memset(dp, 0, sizeof dp);
	memset(size, 0, sizeof size);
	memset(num, 0, sizeof num);
	dfs(u, 0);
	int v = -1;
	for (int to : G[u])
		if (v == -1 || num[to] > num[v]) v = to;
	if (dp[v] > num[u] - num[v] || num[u] & 1) return 1e9;
	// cout << u << "\n";
	return num[u] / 2;
}

int main(void) {
	read(n);
	scanf("%s", str + 1);
	rep (i, n) str[i] -= '0';
	rep (i, n - 1) {
		int x, y; read(x); read(y);
		G[x].push_back(y); G[y].push_back(x);
	}
	int ans = 1e9;
	rep (i, n) ans = min(ans, work(i));
	cout << (ans > 9E8 ? -1 : ans) << "\n";
}


Measured memory_bytes: 640
// Template
#include <bits/stdc++.h>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, r) for (int i = (l); i < (r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003;
template <typename T> inline bool chmin(T& x, const T& y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T& x, const T& y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Main
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v); g[v].push_back(u);
    }
    
    if (n == 2) {
        cout << (a[0] == a[1] ? "YES\n" : "NO\n");
        return 0;
    }
    int root = -1;
    rep(i, n) {
        if (sz(g[i]) >= 2) root = i;
    }
    auto dfs = [&](auto f, int v, int p) -> ll {
        if (sz(g[v]) == 1) return a[v];
        ll sum = 0;
        for (int u: g[v]) {
            if (u == p) continue;
            ll x = f(f, u, v);
            if (x > a[v]) {
                cout << "NO\n";
                exit(0);
            }
            sum += x;
        }
        ll one = a[v] * 2 - sum;
        ll two = a[v] - one;
        if (one < 0 || two < 0 || one > a[v] || two > a[v]) {
            cout << "NO\n";
            exit(0);
        }
        return one;
    };
    cout << (dfs(dfs, root, -1) == 0 ? "YES\n" : "NO\n");
    return 0;
}


Measured memory_bytes: 19408
#include <bits/extc++.h>
using namespace std;
using i64 = int64_t;
#define mod 1000000007
i64 power(i64 a, i64 b) {
  i64 ret{1};
  while (b) {
    if (b & 1) ret *= a, ret %= mod;
    a *= a;
    a %= mod;
    b /= 2;
  }
  return ret;
}

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

  vector<int> a(n), b(n);
  for (int &e : a) cin >> e;
  for (int &e : b) cin >> e;
  reverse(begin(b), end(b));
  int samv = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) samv = a[i];
  }
  if (~samv) {
    auto la = find(begin(a), end(a), samv);
    auto ua = la;
    while (ua != end(a) && *ua == samv) {
      ua++;
    }
    auto lb = find(begin(b), end(b), samv);
    auto ub = lb;
    while (ub != end(b) && *ub == samv) {
      ub++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
      if (a[i] != samv and b[i] != samv) {
        q.push(i);
      }
    }
    for (int i = 0; i < n; i++) {
      if (a[i] == samv) {
        if (b[i] == samv) {
          if (q.empty()) {
            cout << "No\n";
            return 0;
          }
          swap(b[i], b[q.front()]);
          q.pop();
        }
      }
    }
  }
  cout << "Yes\n";
  for (int e : b) cout << e << " ";
  cout << endl;
}


Measured memory_bytes: 5584