akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/python3.6
import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    if a > b:
        a, b = b, a
    ab.append((a, b))

dt = [[0] * n for _ in range(18)]
for i, item in enumerate(x):
    dt[0][i] = bisect.bisect_right(x, item + l) - 1

for i in range(1, 18):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    if a == b:
        print(days)
        continue
    for i in range(17, -1, -1):
        if dt[i][a] < b:
            a = dt[i][a]
            days += 2**i
    print(days + 1)

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

int main()
{
    int A[3][3];
    bool a_check[3][3];
    rep(i, 3)
        rep(j, 3)
    {
        a_check[i][j] = false;
    }
    rep(i, 3)
        rep(j, 3)
    {
        cin >> A[i][j];
    }
    int n;
    cin >> n;
    rep(i, n)
    {
        bool flag = false;
        int tmp;
        cin >> tmp;
        rep(j, 3)
        {
            if (flag)
                break;
            rep(k, 3)
            {
                if (A[j][k] == tmp)
                {
                    a_check[j][k] = true;
                    break;
                }
            }
        }
    }

    rep(i, 3)
        rep(j, 3)
    {
        if (!a_check[i][j])
            break;
        else if (j == 2)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    rep(i, 3)
        rep(j, 3)
    {
        if (!a_check[j][i])
            break;
        else if (j == 2)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    rep(i, 3)
    {
        if (!a_check[i][i])
            break;
        else if (i == 2)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    rep(i, 3)
    {
        if (!a_check[i][2 - i])
            break;
        else if (i == 2)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
/*
    Problem 20
    https://atcoder.jp/contests/abc077/tasks/arc084_a
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 1000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
vector<int> a, b, c;
int n;
/* function */
int bin1(int x) {
    int ok = 0;
    int ng = n+2;
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (a[mid] < x) ok = mid;
        else ng = mid;
    }
    return ok;
}
int bin2(int x) {
    int ok = n+1;
    int ng = -1;
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (x < c[mid]) ok = mid;
        else ng = mid;
    }
    return ok;
}
/* main */
int main(){
    cin >> n;
    a.resize(n);
    b.resize(n);
    c.resize(n);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]);
    for (int i = 0; i < n; i++) scanf("%d", &c[i]);

    a.push_back(-1), a.push_back(INF);
    c.push_back(-1), c.push_back(INF);
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (ll)bin1(b[i]) * (ll)(n+1 - bin2(b[i]));
    }
    cout << ans << '\n';
}

Measured memory_bytes: 4948
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long k,a,b,ans=1;
int main() {
	cin>>k>>a>>b;
	if(b<=a+1||a-1>=k) {
		cout<<1+k;
		return 0;
	}
	if(a>1) k-=(a-1),ans=a;
	while(k) {
		if(k>=2) {
			ans+=b-a;
			k-=2;
		}
		if(k==1) {
			ans++;
			k--;
		}
	}
	cout<<ans;
}

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

int main(){
  int a,b,c,x;
  cin >> a>>b>>c>>x;
  int ans =0;
  for(int i=0;i<=a;i++){
    for(int j=0;j<=b;j++){
      for(int k=0;k<=c;k++){
        if(500*i+100*j+50*k == x){
          ans++;
        }
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n = int(input())
a_list = list(map(int,input().split()))
a_dic = {}
for i in range(n):
  a_dic[i] = 3

ans = 1
for a in a_list:
  if a == 0:
    ans = ans * a_dic[a]
    a_dic[a] -= 1
  else:
    ans = ans * (a_dic[a] - a_dic[a-1])
    a_dic[a] -= 1
    
print(ans % (10**9 + 7))

Measured memory_bytes: 24620
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
#include <iomanip>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fcout cout << fixed << setprecision(10)
#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
const ll inf = 1e18;
const ll mod = 1e9 + 7;

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

// mod.m での a の逆元 a^(-1) を計算する。
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while(b){
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll modpow(ll a, ll n){
    ll res = 1;
    while(n>0){
        if(n&1){
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>=1;
    }
    return res;
}


int main(){
    int x;
    cin >> x;
    int ans = 8 - (x-400)/200;
    cout << ans << endl;
}



Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(a) cout << #a << ": " << a << endl
#define sz(a) int(a.size())
#define rep(i,n) for(int i=0;i<n;i++)
#define forr(i, st, en) for(int i = st; i < en; i++)
#define all(v) (v).begin(),(v).end()
#define fast cin.tie(0); ios::sync_with_stdio(false)

int32_t main(){ fast;
	
	int n, m, x; cin>>n>>m>>x;
	vector<int> a(n + 1, 0);
	rep(i, m){
		int t; cin>>t;
		a[t] = 1;
	}
	int res = 0, res2 = 0;
	rep(i, x){
		if(a[i]){
			res++;
		}
	}
	for(int i = x; i<=n; i++){
		if(a[i]){
			res2++;
		}
	}	
	cout<<min(res, res2)<<endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>京都
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

int N;
int P[50];

signed main()
{
	cin >> N;
	REP(i, N) cin >> P[i];

	for (int i = 0; i < N; i++)
	{
		for (int j = i; j < N; j++)
		{
			int p[50];
			memcpy(p, P, sizeof(p));
			int tmp = p[i];
			p[i] = p[j];
			p[j] = tmp;

			bool ok = true;
			for (int k = 0; k < N - 1; k++)
			{
				if (p[k] > p[k + 1])
				{
					ok = false;
				}
			}
			if (ok)
			{
				cout << "YES" << endl;
				return 0;
			}
		}
	}

	cout << "NO" << endl;
}











Measured memory_bytes: 256
/*
created by sanyam singhal
*/

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long int
#define mod 1000000007
#define w(t) int t;	cin>>t while(t--)
#define triplet pair<int,pair<int,int>>
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define fastIO ios_base::sync_with_stdio(0);	cin.tie(0);	cout.tie(0);
#define loop(i, k, n) for(ll i=k; i<n; i+=1)
#define loop2(i, k, n) for(ll i=k; i>=n; i--)

const ll inf = 1e18;
const int N = 500;

ll dp[N][N];
ll sumij[N][N];

void take_fileIO(){
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
  return;
}

ll solve_by_dp(vector<ll> &a, ll i, ll j){
  if(j==i){
    return 0;
  }
  else if(dp[i][j]!=-1)
    return dp[i][j];
  else{
    ll ans = LLONG_MAX;
    for(ll k=i+1; k<=j; k++){
      ll part1 = solve_by_dp(a, i, k-1);
      ll part2 = solve_by_dp(a, k, j);
      ll curr_ans = part1 + part2 + sumij[i][k-1] + sumij[k][j];
      // cout<<curr_ans<<endl;
      if(curr_ans < ans){
        ans = curr_ans;
      }
    }
    return dp[i][j] = ans;
  }
}

void solve(){
  ll n; cin>>n;
  vector<ll>a(n);
  loop(i, 0, n) 
    cin>>a[i];

  memset(dp, -1, sizeof(dp));
  // loop(i, 0, n)
  //   cout<<a[i]<<" ";

  for(int i=0; i<n; i++){
    for(int j=i; j<n; j++){
      // for(int k=i; k<=j; k++){
      //   sumij[i][j] += a[k];
      // }
      if(i==j){
        sumij[i][j] = a[j];
        continue;
      }
      sumij[i][j] = a[j] + sumij[i][j-1];
    }
  }

  // for(int i=0; i<n; i++){
  //   for(int j=0; j<n; j++){
  //     cout<<sumij[i][j]<<" ";
  //   }
  //   cout<<endl;
  // }

  cout<<solve_by_dp(a, 0, n-1)<<endl;
  return;
}

int main(){

  fastIO;
  // take_fileIO();
  solve();
  return 0;
}

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

int fgcd (int a, int b) {
    if (a > b) {
        int d = a; a = b; b = d;
    }
    if (b%a == 0) return a;
    else return fgcd(a, b%a);
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a / fgcd(a, b) * b << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n+1];
        for (int i = 0; i < n+1; i++) {
            a[i] = sc.nextLong();
        }
        if(a[0] != 0){
            if(n == 0 && a[0] == 1) System.out.println(1);
            else System.out.println(-1);
        }else{
            long[] max = new long[n+1];
            max[n] = a[n];
            for (int i = n; i > 0; i--) {
                max[i-1] = max[i] + a[i-1];
            }
            max[0] = 1;
            long ans = 1L;
            for (int i = 0; i < n; i++) {
                max[i+1] = Math.min(max[i+1], (max[i] - a[i]) * 2);
                ans += max[i+1];
                if(max[i+1] < a[i+1]){
                    ans = -1;break;
                }
            }
            System.out.println(ans);
        }
        sc.close();

    }

}


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

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll ar[M];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,i,x = 0;
	cin >> n;
	for(i=1;i<=n;++i)
	{
		cin >> ar[i];
		x = x^ar[i];
	}
	for(i=1;i<=n;++i)
		cout << (x^ar[i]) << " ";
	cout << "\n";
}

Measured memory_bytes: 5116
#include<iostream>
#include<cstdio>
#include<cstring>
//#include<vector>
#include<algorithm>



#ifdef L_JUDGE
#pragma warning(disable:4996)
#endif

using namespace std;
const int MAXN=1005;

int N;
int A[MAXN];

int main(){
	#ifdef L_JUDGE
		freopen("in.txt","r",stdin);
//		freopen("out.txt","w",stdout);
	#endif
        while(scanf("%d",&N)!=EOF){
            int sum=0;
            for(int i=0;i<N;i++){
                scanf("%d",A+i);
                sum+=A[i];
            }
            sort(A,A+N);
            int Alice=0,Bob=0;
            for(int i=N-1;i>=0;i-=2){
                 Alice+=A[i];
            }
            cout<<2*Alice-sum<<endl;
        }

	#ifdef L_JUDGE
		fclose(stdin);
		fclose(stdout);
//		system("out.txt");
	#endif

	return 0;
}


Measured memory_bytes: 256
/*
         Md.Fagun Molla
         18ICTCSE006
         BSMRSTU(SHIICT)
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define End return 0;
int main ()
{
    string s1,s2,s3;
    cin>>s1;

    cin>>s2;
    ll a,b;
    cin>>a>>b;
    cin>>s3;
    if(s1==s3)
        a=a-1;
    else if(s2==s3)
        b=b-1;
    cout<<a<<" "<<b<<endl;
    End;
}
/* pray for me
All is well
*/




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int main() {
	int x, a, b;
	cin >> x >> a >> b;
	x -= a;
	while (x - b >= 0) {
		x -= b;
	}
	cout << x << "\n";
}

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

int main() {
  ll N,M; cin>>N>>M;
  ll ans;
  if(N>=M/2)
  {
    ans=M/2;
  }
  else
  {
    ans=N+(M/2-N)/2;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#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 H, W, K;
    cin >> H >> W >> K;
    VS s(H);
    rep(h, 0, H) cin >> s[h];
    VVL acc(H, VL(W, 0));
    ll start = -1;
    rep(h, 0, H){
        acc[h][0] = (s[h][0] == '#');
        rep(w, 1, W){
            acc[h][w] = acc[h][w-1] + (s[h][w] == '#');
        }
        if(start == -1 && acc[h][W-1] != 0) start = h;
    }
    VVL ans(H, VL(W, 0));
    // start check!
    ll id = 1;
    rep(w, 0, W){
        if(acc[start][w] == acc[start][W-1]){
            ans[start][w] = id;
        }else{
            ans[start][w] = id;
            if(acc[start][w] != acc[start][w+1] && acc[start][w] != 0){
                id++;
            }
        }
    }
    if(start != H-1 && acc[start+1][W-1] != 0) id++;
    // umeume
    rep(h, 0, start){
        rep(w, 0, W){
            ans[h][w] = ans[start][w];
        }
    }
    // remainder
    rep(h, start+1, H){
        if(acc[h][W-1] == 0){
            rep(w, 0, W) ans[h][w] = ans[h-1][w];
        }else{
            rep(w, 0, W){
                if(acc[h][w] == acc[h][W-1]){
                    ans[h][w] = id;
                }else{
                    ans[h][w] = id;
                    if(acc[h][w] != acc[h][w+1] && acc[h][w] != 0){
                        id++;
                    }
                }
            }
        }
        if(h != H-1 && acc[h+1][W-1] != 0) id++;
    }

    rep(h, 0, H){
        rep(w, 0, W){
            cout << ans[h][w];
            if(w == W-1) cout << endl;
            else cout << " ";
        }
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

int main(){
    int A, B;
    cin >> A >> B;

    int cnt = 1;
    int ans = 0;
    while(cnt < B){
        cnt--;
        cnt += A;
        ans++;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
fo_x = '0' + str(n) + 'b'
a = [None] * n
x = [None] * n
y = [None] * n
ans = 0
flag = 0
for i in range(n):
    a[i] = int(input())
    ax = [None] * a[i]
    ay = [None] * a[i]
    for j in range(a[i]):
        ax[j],ay[j] = map(int,input().split())
    x[i] = ax
    y[i] = ay

for i in range(2 ** n):
    b = format(i,fo_x)
    for j in range(len(b)):
        if b[j] == '0':
            continue
        for z in range(a[j]):
            if str(y[j][z]) != b[x[j][z]-1]:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0:
        ans = max(ans,b.count('1'))
    flag = 0
print(ans)

Measured memory_bytes: 73700
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (2e9)
#define INFL (2e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using vint=vector<int>;
using vll=vector<ll>;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    int n, m; cin >> n >> m;
    vint a(m);
    arr<int> c(m);
    rep(i, m){
        int x, y; cin >> x >> y;
        a[i] = x;
        rep(j, y){
            int k; cin >> k;
            c[i].push_back(k-1);
        }
    }

    vint b(m, 0);
    rep(i, m){
        rep(j, c[i].size()) b[i] += (1<<c[i][j]);
    }

    int dp[1<<n] = {};
    rep(i, 1<<n) dp[i] = INF;
    dp[0] = 0;

    rep(bit, 1<<n){
        rep(i, a.size()){
            chmin(dp[bit | b[i]], dp[bit] + a[i]);
        }
    }

    if(dp[(1<<n) - 1]==INF) pr(-1);
    else pr(dp[(1<<n)-1]);
    return 0;}

Measured memory_bytes: 3716
unittest
{
//	assert( [ "2 3" ].parse.expand.solve == "3 3\n##.\n..#\n#.#" );
//	assert( [ "7 8" ].parse.expand.solve == "3 5\n#.#.#\n.#.#.\n#.#.#" );
//	assert( [ "1 1" ].parse.expand.solve == "4 2\n..\n#.\n##\n##" );
//	assert( [ "3 14" ].parse.expand.solve == "8 18\n..................\n..................\n....##.......####.\n....#.#.....#.....\n...#...#....#.....\n..#.###.#...#.....\n.#.......#..#.....\n#.........#..####." );
}



import std.conv;
import std.format;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto ab = input.front.split.to!( long[] );
	return tuple( ab[ 0 ], ab[ 1 ] );
}

auto solve( long a, long b )
{
	auto ansss = new char[][]( 40, 100 );
	a--;
	b--;
	
	// 黒地に白点を打つ
	for( auto y = 0L; y < ansss.length / 2; y += 2 )
	{
		ansss[ y     ][] = '#';
		ansss[ y + 1 ][] = '#';
		for( auto x = 0L; x < ansss[ y ].length && 0 < a; x += 2 )
		{
			ansss[ y ][ x ] = '.';
			a--;
		}
	}
	
	// 白地に黒点を打つ
	for( auto y = ansss.length.signed / 2 + 1; y < ansss.length; y += 2 )
	{
		ansss[ y - 1 ][] = '.';
		ansss[ y     ][] = '.';
		for( auto x = 0L; x < ansss[ y ].length && 0 < b; x += 2 )
		{
			ansss[ y ][ x ] = '#';
			b--;
		}
	}
	return format( "%s %s\n%s", ansss.length, ansss[ 0 ].length, ansss.join( '\n' ) );
}


Measured memory_bytes: 256
import Data.Char
import Data.List

solve :: Int -> Int -> Int
solve k s = solver 0 0
    where　solver x y
            | y > k = 0
            | x > k = 0
            | x == 0 = solver 0 (y+1) + solver 1 y + if (s-y)>=0 && (s-y) <= k then 1 else 0
            | otherwise = solver (x+1) y + if (s-x-y)>=0 && (s-x-y) <= k then 1 else 0

main = do
    [k,s] <- (map read . words) <$> getLine
    print $ solve k s

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

int cmp(int a, int b) {
    if (a == b) {
        return 0;
    }
    return a < b ? -1 : 1;
}
int v[26];

void solve() {
    string s;
    read(s);
    FOR(s.size()) {
        v[s[i] - 'a']++;
    }
    FOR(26) {
        if (v[i] & 1) {
            print("No");
            return;
        }
    }
    print("Yes");
}

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

    int tt = 1;
//    read(tt);
    FOR(tt) {
//        write("Case #", i + 1, ": ");
        solve();
    }

}



Measured memory_bytes: 3656
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000
void initialize(void);
int isEmpty(void);
int isFull(void);
void push(int);
int pop(void);

int top;
int S[MAX];
int main(){
  int x,i,j;
  char s[100];
  initialize();
  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
      i = pop();
      j = pop();
      push(i+j);
    } else if ( s[0] == '-' ){
      i = pop();
      j = pop();
      push(j-i);
    } else if ( s[0] == '*' ){
      i = pop();
      j = pop();
      push(i*j);
    } else {
      x = atoi(s);
      push(x);
    }
  }
  printf("%d\n",S[top]);
  return 0;
}
void initialize(void){
  top = 0;
}

int isEmpty(void){
  if(top==0)
  return 1;

  return 0;
}
int isFull(void){
  if(top >= MAX - 1)
    return 1;

  return 0;
}
void push(int x){
  if (isFull()==1){
    printf("error(overflow)");
  }else{
  top++;
  S[top] = x;
  }
}
int pop(void){
  if(isEmpty()==1){
    printf("error(underflow)");
  }else{
    top--;
    return S[top+1];
  }
}

Measured memory_bytes: 548
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

const int N=1e6+7;
int cnt[N];
int t[220000];

int main(){
	int n,m;
	int i,j,k;
	int a,b,c;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>t[i];
		cnt[t[i]]++;
	}
	for(i=N-1;i>0;i--){
		for(j=2*i;j<N;j+=i){
			cnt[j]+=cnt[i];
		}
	}
	a=0;
	for(i=0;i<n;i++){
		if(cnt[t[i]]==1)a++;
	}
	cout<<a<<endl;
}

Measured memory_bytes: 8332
#include<bits/stdc++.h>
using namespace std;
int n,m,a[2010][2010],b[2010][2010],ans;
string s[2010];
int main(){
	cin>>n>>m;
	for (int i=0;i<n;i++) cin>>s[i];
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++){
			if (s[i][j]=='.'&&b[i][j]==0){
				for (int k=j;k<m;k++)
					if (s[i][k]=='.')
						b[i][j]++;
					else
						break;
				for (int k=j;k<m;k++)
					if (s[i][k]=='.')
						b[i][k]=b[i][j];
					else
						break;
			}
			if (s[i][j]=='.'&&a[i][j]==0){
				for (int k=i;k<n;k++)
					if (s[k][j]=='.')
						a[i][j]++;
					else
						break;
				for (int k=i;k<n;k++)
					if (s[k][j]=='.')
						a[k][j]=a[i][j];
					else
						break;
			}
		}
	for (int i=0;i<n;i++)//,cout<<endl
		for (int j=0;j<m;j++){
//			cout<<a[i][j]<<','<<b[i][j]<<'	';
			ans=max(ans,a[i][j]+b[i][j]-1);
//			cout<<ans<<' '<<i<<' '<<j<<endl;
		}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 35840
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

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

	long long n, i, j, k, ans, s, ss;
	cin >> n >> k;
	vector<long long> a(n);
	for (i = 0; i < n; i++) cin >> a[i]; 

	s = 0; ss = 0;
	for (i = 0; i < k; i++) ss += a[i];
	for (; i < n; i++) {
		if (a[i] > 0) s += a[i];
	}
	ans = max(0LL, s + ss);

	for (i = 1; i + k <= n; i++) {
		ss = ss + a[i + k - 1] - a[i - 1];
		if (a[i + k - 1] > 0) s -= a[i + k - 1];
		if (a[i - 1] > 0) s += a[i - 1];
		ans = max(ans, s + ss);
		ans = max(ans, s);
	}

	cout << ans << "\n";


	return 0;
}


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

int main(){
	int N;
	cin>>N;
	int x[N],y[N];
	long h[N];
	int Cx,Cy;
	long H;
	for(int i=0;i<N;++i){
		cin>>x[i]>>y[i]>>h[i];
	}
	for(int cx=0;cx<=100;++cx){
		for(int cy=0;cy<=100;++cy){
			int tmph=-1;
			bool tmp=true;
			for(int i=0;i<N;++i){
				if(h[i]==0)continue;
				else if(tmph==-1){
					tmph=h[i]+abs(x[i]-cx)+abs(y[i]-cy);
				}
				else if(tmph!=-1 && tmph-abs(x[i]-cx)-abs(y[i]-cy)!=h[i]){
					tmp=false;
					break;
				}
			}
			if(tmp==true){
				for(int i=0;i<N;++i){
					if(h[i]==0){
						if(max(tmph-abs(x[i]-cx)-abs(y[i]-cy),0)!=h[i]) tmp=false;
					}
				}
				if(tmp==false)continue;
				Cx=cx;
				Cy=cy;
				H=tmph;
				break;
			}
		}
	}
	cout<<Cx<<" "<<Cy<<" "<<H<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

// 約数列挙
//  (O√n)
std::vector<long long> divisor(const long long n, const bool to_sort) {
    std::vector<long long> ret;
    if (n > 1) for(long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
             ret.emplace_back(i);
             if (i != n / i && i != 1) {
                 ret.emplace_back(n / i);
             }
        }
    }

    if (to_sort) {
        std::sort(std::begin(ret), std::end(ret));
    }

    return ret;
}

const int MAX = 2e5 + 10;
int N;
int a[MAX], cnt[MAX];
int ans[MAX];

int main(void) {
    cin >> N;
    REP(i, N) {
        cin >> a[i];
    }

    RREP(i, N) {
        const int need = a[i];
        if (cnt[i] % 2 != need) {
            ans[i] = 1;
            cnt[i]++;
            auto divs = divisor(i + 1, true);
            FORE(e, divs) {
                cnt[e - 1]++;
            }
        }
    }

    VI anses;
    REP(i, N) if (ans[i]) {
        anses.EB(i + 1);
    }

    cout << anses.size() << endl;
    FORE(e, anses) cout << e << endl;
}


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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

// container util
// -----------------------------------------------------------------------------
#define ALL(c)  (c).begin(),(c).end()
#define SZ(c) ((ll)(c).size())
#define MAX(c) *max_element(ALL(c))
#define MIN(c) *min_element(ALL(c))
#define SORT(c) sort((c).begin(),(c).end())

// repetition
// -----------------------------------------------------------------------------
#define FOR(i, a, b) for(ll i= (a); i < (ll)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
// -----------------------------------------------------------------------------
const ll INF = 1e10;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    ll N, M, K; cin >> N >> M >> K;
    vector<ll> A(N + 1, 0);
    FOR(i, 1, N + 1) {
        cin >> A[i];
        A[i] += A[i - 1];
    }
    vector<ll> B(M + 1, 0);   
    FOR(i, 1, M + 1) {
        cin >> B[i];
        B[i] += B[i - 1];
    }
    // Aからi冊読むときにBから最大j冊読める
    ll j = M, ans = 0;
    REP(i, N + 1) {
        if(A[i] > K) {
            break;
        }
        while(K - A[i] < B[j]) {
            j--;
        }
        ans = max(ans, i + j);
    }
    cout << ans << "\n";
}

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

struct BIT {
    vector<ll> bit;
    int N;

    BIT(int N) : bit(vector<ll>(N + 1, 0)), N(N) {}

    // return sum in [0, `i`] in log(n)
    ll sum(int i) {
        if (!i) return 0;
        return bit[i] + sum(i - (i & -i));
    }

    // add `x` at `i`
    void add(int i, ll x) {
        if (i > N) return;
        bit[i] += x;
        add(i + (i & -i), x);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> c(n);
    rep(i, n) {
        cin >> c[i];
        c[i]--;
    }
    vector<vector<int>> rli(q, vector<int>(3, 0));
    rep(i, q) {
        cin >> rli[i][1] >> rli[i][0];
        rli[i][0]--;
        rli[i][1]--;
        rli[i][2] = i;
    }
    sort(rli.begin(), rli.end());

    vector<int> ans(q, 0);
    BIT fwt(n);
    vector<int> lastApp(n, -1);
    int r = -1;

    rep(i, q) {
        for (int nr = r + 1; nr <= rli[i][0]; nr++) {
            if (lastApp[c[nr]] >= 0) {
                fwt.add(lastApp[c[nr]] + 1, -1);
            }
            lastApp[c[nr]] = nr;
            fwt.add(nr + 1, 1);
        }
        r = rli[i][0];
        ans[rli[i][2]] = fwt.sum(r + 1) - fwt.sum(rli[i][1]);
    }
    rep(i, q) {
        cout << ans[i] << endl;
    }
}


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

int main(void)
{
    int N, M;
    cin >> N >> M;
    int a[M];
    int b[M];
    int ans[N] = {0};
    for( int i = 0; i < M; i++){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }

    for( int i = 0; i < N; i++){
        for( int j = 0; j < M; j++){
            if( a[j] == i ){
                ans[i]++;
            }
            if( b[j] == i ){
                ans[i]++;
            }
        }
    }

    for( int i = 0; i < N; i++){
        cout << ans[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
import math
line1 = list(map(int, input().split()))
line2 = list(map(int, input().split()))
line3 = list(map(int, input().split()))
lines = [line1, line2, line3]
N = int(input())
List = [int(input()) for i in range(4, N + 4)]

for num in List:
    for i in range(len(lines)):
        for j in range(len(lines)):
            if lines[i][j] == num:
                lines[i][j] = -1

if (lines[0][0] == -1 and lines[0][1] == lines[0][0] and lines[0][2] == lines[0][0]) or (lines[1][0] == -1 and lines[1][1] == lines[1][0] and lines[1][2] == lines[1][0]) or (lines[2][0] == -1 and lines[2][1] == lines[2][0] and lines[2][2] == lines[2][0]) or (lines[0][0] == -1 and lines[1][0] == lines[0][0] and lines[2][0] == lines[0][0]) or (lines[0][1] == -1 and lines[1][1] == lines[0][1] and lines[2][1] == lines[0][1]) or (lines[0][2] == -1 and lines[1][2] == lines[0][2] and lines[2][2] == lines[0][2]) or (lines[0][0] == -1 and lines[1][1] == lines[0][0] and lines[2][2] == lines[0][0]) or (lines[0][2] == -1 and lines[1][1] == lines[0][2] and lines[2][0] == lines[0][2]):
    print("Yes")
else: print("No")

Measured memory_bytes: 38384
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<complex>
#include<set>
#include<map>
#include<queue>

using namespace std;

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

const int W = 31;
const int H = 61;

class P{
	public:
	int a,b,c,d;
	int val;
	P(int a,int b,int c,int d,int val):a(a),b(b),c(c),d(d),val(val){}
	bool operator<(const P& tmp)const{
		return val>tmp.val;
	}
};

int h,w;
char masu[H][W];

void initQue(priority_queue<P>& que){
	rep(i,h)rep(j,w){
		if(masu[i][j]=='S')que.push(P(i,j,i,j,0));
	}
}

int getCost(int y,int x){
	if(y<0 || x<0 || y>=h || x>=w)return -1;
	if(masu[y][x]=='X')return -1;
	if(masu[y][x]=='T')return 0;
	if(masu[y][x]=='S')return 0;
	return masu[y][x]-'0';
}

void addQue(priority_queue<P> &que, P& u){
	int dy[]={-2,-1,-1,0,0,0,1,1,2};
	int dx[]={1,1,2,1,2,3,1,2,1};
	
	rep(p,9){
		int ny = u.a + dy[p];
		int nx = u.b + dx[p];
		int ncost = getCost(ny,nx);
		if(ncost != -1) que.push(P(u.a,u.b, ny,nx, u.val+ncost));
	}
	rep(p,9){	
		int ty = u.c + dy[p];
		int tx = u.d - dx[p];
		int tcost = getCost(ty,tx);
		if(tcost != -1) que.push(P(ty,tx, u.c,u.d, u.val+tcost));
	}
}

bool isGoal(P& u){
	return masu[u.a][u.b]=='T' || masu[u.c][u.d]=='T';
}

int visit[H][W][H][W];
int solve(){
	rep(i,h)rep(j,w)cin>>masu[i][j];
	
	priority_queue<P> que;
	initQue(que);
	
	int ans = -1;
	rep(i,h)rep(j,w)rep(k,h)rep(p,w)visit[i][j][k][p]=0;
	while(1){
		if(que.empty())break;
		
		P u = que.top();
		que.pop();
		
		if(visit[u.a][u.b][u.c][u.d]==1)continue;
		visit[u.a][u.b][u.c][u.d]=1;
		
		//printf("(%d %d) (%d %d) %d\n",u.a,u.b,u.c,u.d,u.val);
		
		if(isGoal(u)){
			ans = u.val;
			break;
		}
		addQue(que, u);
	}
	
	return ans;
}

int main(){
	while(1){
		cin>>w>>h;
		if(h==0 && w==0)break;
		
		printf("%d\n",solve());
	}
}

Measured memory_bytes: 15776
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

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

    string s, t; cin >> s >> t;
    vector<vector<ll>> dp(s.size()+1, vector<ll>(t.size()+1, 0));
    Rep (i, s.size()) {
        Rep (j, t.size()) {
            chmax(dp[i+1][j+1], dp[i+1][j]);
            chmax(dp[i+1][j+1], dp[i][j+1]);
            chmax(dp[i+1][j+1], dp[i][j] + (s[i] == t[j]));
            // cout << (s[i] == t[j]) << "\n";
        }
    }
    // cout << dp[s.size()][t.size()] << "\n";

    string ans = "";
    ll i = s.size(), j = t.size();
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i-1][j]) {
            i--;
        } else if (dp[i][j] == dp[i][j-1]) {
            j--;
        } else {
            ans = s[i-1] + ans;
            i--; j--;
        }
    }

    cout << ans << "\n";
}

Measured memory_bytes: 70784
#include <iostream>

using namespace std;

int T[101] = {0};

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

  int N, M;
  cin >> N;

  int sum = 0;
  for (int i = 0; i < N; ++i) {
    cin >> T[i];
    sum += T[i];
  }
  cin >> M;
  for (int i = 0; i < M; ++i) {
    int p, x;
    cin >> p >> x;
    --p;

    cout << sum - T[p] + x << endl;
  }

  return 0;
}


Measured memory_bytes: 256
from heapq import heappush, nlargest

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]
    h = []
    for i in A:
        for j in B:
            heappush(h, i + j)
    H = []
    for i in nlargest(K, h):
        for j in C:
            heappush(H, i+j)
    for i in nlargest(K, H):
        print(i)

if __name__ == "__main__":
    main()

Measured memory_bytes: 194344
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
signed main()
{
   SPEED;
   int n,k;
   cin>>n>>k;
   int a[n+1],cnt=0,curr=1,vis[n+1]={0},dist[n+1]={0};
   for(int i=1;i<=n;i++)
   {
       cin>>a[i];
   }
   vector <int> v;
   while(vis[curr]==0)
   {
       dist[curr]=cnt;
       v.push_back(curr);
       vis[curr]=1;
       ++cnt;
       curr=a[curr];
   }
   if(k<=dist[curr])
   {
       cout<<v[k];
   }
   else
   {
       k-=dist[curr];
       cnt-=dist[curr];
       k%=cnt;
       cout<<v[dist[curr]+k];
   }
}

Measured memory_bytes: 10008
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
// const int MOD = 1e9 + 7;

int main() {
    int a, b;
    cin >> a >> b;
    int ans = a - 1;
    if (a <= b) {
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
a = []
for i in r:
    a.append((i[0]+i[1],i[0]-i[1]))
a.sort()
ans = 0
cur = a[0][1]
for i in a:
    if i[1] < cur:
        continue
    ans += 1
    cur = i[0]
print(ans)

Measured memory_bytes: 41440
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>

using namespace std;

int main(){

long long N,T;
long long t[200'010];
cin >>N >>T;
for(int i=1;i<=N;i++){
    cin >>t[i];
}
long long x=0;

for(int i=1;i<N;i++){
    x+=min(t[i+1]-t[i],T);
}
x+=T;
cout <<x <<endl;
    

 return 0;
}

Measured memory_bytes: 1792
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

// vectorの重複削除
// std::sort(test.begin(), test.end());
// test.erase(std::unique(test.begin(), test.end()), test.end());

using namespace std;
using ll = long long;
using P = pair<int, int>; // vector<P> ba(n); みたいな感じですぐ使える ba[i] = P(a, b); make_pairをしなくてもいい
// typedef vector<int> v;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back //
// const int MOD = 1000000007;
// string alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// printf("%.20f\n", ans); あれ
// const double PI = 3.141592653589793238462643383;

int main() {
  int n; cin>>n;
  //std::vector<int> v(n+1, 0);
  ll a;
  std::map<ll, ll> map;
  rep(i,n) {
    cin>>a;
    if (map.count(a)) {
      map[a] += 1;
    } else {
      map[a] = 1;
    }
  }
  int q; cin>>q;
  ll b,c;
  ll ans = 0;
  for (auto const& [k, v]: map) {
    ans += k*v;
  }
  rep(i,q) {
    cin>>b>>c;
    if (map.count(b)) {
      ans -= b*map[b];
      if (map.count(c)) {
        map[c] += map[b];
        ans += c*map[b];
        map[b] = 0;
      } else {
        map[c] = map[b];
        ans += c*map[b];
        map[b] = 0;
      }
    }


    cout << ans << endl;
  }

}


Measured memory_bytes: 8180
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int x;
  cin >> x;

  for(int i = x;x > 0 ;i--)
  {
    // i がべき乗数か調べる
    for(int j = 1;j < sqrt(i) + 1;j++)
    {
      // iを割れるやつがあったら、割りまくってみる
      if(i % j == 0)
      {
        int b = i;
        bool chk = false;
        for(int k = 1;k <= 10;k++)
        {
          // 割まくれるか？
          if(b == j)
          {
            chk = true;
            break;
          }
          else if(b % j != 0)
          {
            chk = false;
            break;
          }
          else
          {
            b /= j;
          }
        }
        if(chk)
        {
          cout << i << endl;
          return 0;
        }
      }
    }
  }


  return 0;
}
// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;


int main() {
    int n; cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(i % 2 == 0) continue;
        int cnt = 0;
        for(int j = 1; j <= i; j++){
            if(i % j == 0) cnt++;
        }
        if(cnt == 8) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3584