akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* na, Arg1&& arg1, Args&&... args) {
  const char* c = strchr(na + 1, ',');
  cerr.write(na, c - na) << " : " << arg1 << " , ";
  __f(c + 1, args...);
}
#define SZ(v) (int)v.size()
#define endl "\n"
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) sort(ALL(v)),v.erase(unique(ALL(v)),v.end())
typedef long long LL;
typedef pair <int,int> pii;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 1e9;
const LL INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, m;
vector <int> graph[ N ];
int cost[ N ];
int path[ N ];
set <int> st[ N ];

void bfs() {
  queue <int> q;
  memset(cost, -1, sizeof(cost));
  cost[1] = 0;
  q.push(1);
  while (!q.empty()) {
    int f = q.front(); q.pop();
    for (auto x: graph[f]) {
      if (cost[x] == -1 || cost[x] > cost[f] + 1) {
        cost[x] = cost[f] + 1;
        path[x] = f;
        q.push(x);
      }
    }
  }
}

void solve() {
  cin >> n >> m;

  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
    st[u].insert(v);
    st[v].insert(u);
  }

  bfs();
  bool f = true;
  for (int i = 2; i <= n; i++) {
    //trace(i, cost[i], path[i]);
    if (cost[i] == -1) f = false;
  }

  if (!f) {
    cout << "No" << endl;
    return;
  }

  cout << "Yes" << endl;
  for (int i = 2; i <= n; i++) {
    //trace(i, cost[i]);
    //if (st[i].find(path[i]) == st[i].end()) assert(false);
    cout << path[i] << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  int t = 1;
  for (int tc = 1; tc <= t; tc++) solve();
  return 0;
}



Measured memory_bytes: 33992
a,b,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(m)]
x,y,c = [list(i) for i in zip(*l)]
p = min(a) + min(b)

for i in range(m):
    p = min(p,a[x[i]-1] + b[y[i]-1] - c[i])

print(p)

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

using namespace std;


const int MAX_N = 100 + 5;
const int MAX_W = 1e9 + 5;
const int MAX_V = 1e5 + 5 ;

bool v[MAX_N][MAX_V];
int dp[MAX_N][MAX_V];
int N, W;
vector<pair<int, int>> ks;

int solve(int n, int va){
	if (va <= 0)
		return 0;

	if (n == N)
		return MAX_W;

	if (v[n][va]) return dp[n][va];
	
	dp[n][va] = min(solve(n+1, va - ks[n].second) + ks[n].first, solve(n+1, va));

	v[n][va] = 1;
	return dp[n][va];

	/*if (ks[n].first + w > W) { 
		 short& score = dp[n][w] = solve(n+1, w);
		 v[n][w] = 1;
		 return score;
	}
	else {
		short& score = dp[n][w] =  max(static_cast<short>(solve(n+1, w + ks[n].first) + ks[n].second), solve(n+1, w));
		v[n][w] = 1;
		return score;
	}*/
	
}

int max_weight(){

	for (int i = MAX_V;i >= 0;i--){
		if( solve(0, i) <= W)
			return i;
	}
	return 0;
}

int main(){
	cin >> N >> W;

	for(int i = 0;i < N;i++){
		int x;
		int y;
		cin >> x;
		cin >> y;
		ks.push_back({x, y});
	}

	cout << max_weight() << endl;
	return 0;
}


Measured memory_bytes: 52364
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int MAXN = 500005;

template <typename T> inline void read(T &AKNOI) {
    T x = 0, flag = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    AKNOI = flag * x;
}

char s[MAXN];
int n, l[MAXN], r[MAXN];
LL ans;

void solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) {
		if (s[i] == '<') {
			l[i] = l[i - 1] + 1;
		}
	}
	for (int i = n; i >= 0; --i) {
		if (s[i + 1] == '>') {
			r[i] = r[i + 1] + 1;
		}
		ans += max(l[i], r[i]);
	}
	printf("%lld\n", ans);
}

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


Measured memory_bytes: 4608
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE FlexibleContexts #-}

import Data.Bits
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IMS
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS
import qualified Data.Sequence as Seq
import Data.Sequence (Seq)
import qualified Data.Array.IArray as A
import qualified Data.Array.MArray.Safe as A
import qualified Data.Array.MArray as A
import Data.Array (Array)
import Data.Array.Unboxed (UArray)
import Data.Array.IArray (IArray)
import Data.Array.MArray.Safe (MArray)
import Data.Array.IO.Safe (IOArray, IOUArray)
import Data.Array.ST.Safe (STArray, STUArray, runSTArray, runSTUArray)
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Monad.ST
-- import Control.Monad.ST.Safe
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Control.Monad.State.Strict
import Data.Int
import System.IO
import Data.Function
import Control.Monad.Primitive
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Generic.Mutable as VGM
import Data.STRef
import Data.IORef

main :: IO ()
main = do
  [n,a,b] <- map read . words <$> getLine :: IO [Int]
  putStrLn $ unwords $ map show $ [min a b, max 0 $ a+b - n]


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

long long fact(long long n){
    if(n == 0 || n == 1) return 0;
    return n * (n-1) / 2;
}

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0;i<n;++i) cin >> arr[i];
    int min = 10000000;
    int max = -10000000;
    long long total = 0;
    for(auto &val : arr){
        if(val < min) min = val;
        if(val > max) max = val;
        total += val;
    }
    cout << min << " " << max << " " << total << "\n";
    return 0;
}



Measured memory_bytes: 3124
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<string,int> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
map<string,int> mp;
int dp[5005][5005];
int main(){
int n;
cin>>n;
string s;
cin>>s;
for(int i=n-1;i>=0;i--){
    for(int j=n-1;j>=0;j--){
        if(i==j)continue;
        if(s[i]==s[j])dp[i][j]=dp[i+1][j+1]+1;
    }
}
int ans=0;
for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
       int tmp=min(dp[i][j],j-i);//j-iまでが限界領域
       ans=max(ans,tmp);
    }
}
cout<<ans<<endl;
}


Measured memory_bytes: 98048
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int n = parseInt(line);
			if (n == 0) break;

			byte[] table = new byte[24 * 60 * 60];
			for (int i = 0; i < n; i++) {
				line = br.readLine();
				String start = line.substring(0, line.indexOf(' '));
				String arrive = line.substring(line.indexOf(' ') + 1);
				table[secondValue(start)]++;
				table[secondValue(arrive)]--;
			}
			int peak = 0, inuse = 0;
			for (int i = 0; i < table.length; i++) {
				inuse += table[i];
				if (peak < inuse) {
					peak = inuse;
				}
			}
			System.out.println(peak);
		}
	}

	static int secondValue(String time) {
		StringTokenizer st = new StringTokenizer(time, ":");
		int second = parseInt(st.nextToken()) * 3600;
		second += parseInt(st.nextToken()) * 60;
		second += parseInt(st.nextToken());
		return second;
	}
}

Measured memory_bytes: 62304
import java.util.*;
public class Main {
    public static void main(String[] args) {
        int val;
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.next());
//        String[] s = new String[n];
//        HashMap<String, LinkedList<Integer>> map = new HashMap<>();
//        String city;
//        int point;
//        int[] score = new int[n];
//        for (int i = 0; i < n; i++) {
//            city = sc.next();
//            point = sc.nextInt();
//            if (map.containsKey(city)){
//                map.getOrDefault(city).add(point)
//            }
//        }

        List<c> first = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            first.add(new c(sc.next(), i+1, sc.nextInt()));
        }

    first.sort((s1, s2) -> {
        if (s1.s.equals(s2.s)){
            return s2.p - s1.p;
        } else{
            return s1.s.compareTo(s2.s);
        }
    });
        for (c eachc:
             first) {
            System.out.println(eachc.i);
        }
    }

    static class c {
        String s;
        int i;
        int p;

        public c(String s, int i, int p){
            this.s = s;
            this.i = i;
            this.p = p;
        }
    }
}

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

vector<int> v[202020];
ll ans[202020];
void dfs(int x, int p){
    for(auto to : v[x]){
        if(to==p)continue;
        ans[to]+=ans[x];
        dfs(to,x);
    }
}
int main(){
    int n;
    cin>>n;
    int q;
    cin>>q;
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        --a;--b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    while(q--){
        int p,x;
        cin>>p>>x;
        --p;
        ans[p]+=x;
    }
    dfs(0,-1);
    rep(i,n){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 24320
#include <stdio.h>

int main(void){
    char input;
    
    scanf("%c", &input);
    
    switch(input){
        case 'A': printf("T"); break;
        
        case 'T': printf("A"); break;
        
        case 'C': printf("G"); break;
        
        case 'G': printf("C"); break;
        
    }
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,v,x[N];
int dp1[(1<<19)+3],dp2[(1<<19)+3];
int tor[20][N],tol[20][N],len[20],dep;
void maxn(int &x,int y){y>x? x=y:0;}
int mxr[N];//左侧覆盖i，右侧最多覆盖多少个城市
int main(){
    scanf("%d%d",&n,&v);x[0]=-2e9,x[n+1]=2e9;
    for(len[0]=v;len[dep]!=0;dep++) len[dep+1]=len[dep]/2;
    dep++;
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    for(int d=0;d<dep;d++){
        tol[d][0]=n,tor[d][n+1]=n;
        for(int i=1;i<=n;i++) tol[d][i]=(x[i]-x[i-1]<=len[d])? tol[d][i-1]:n+1-i;
        for(int i=n;i>=1;i--) tor[d][i]=(x[i+1]-x[i]<=len[d])? tor[d][i+1]:i;
    }
    
    for(int i=0;i<(1<<dep);i+=2)
        for(int j=1;j<dep;j++)
            if((i&(1<<j))==0)
                maxn( dp1[i|(1<<j)], tor[j][dp1[i]+1] ),
                maxn( dp2[i|(1<<j)], tol[j][n-dp2[i]] );
    
    memset(mxr,0xc0,sizeof(mxr));
    for(int i=0,j=((1<<dep)-1)^1;j>=0;i+=2,j-=2)
        maxn( mxr[dp1[i]], dp2[j] );
    for(int i=n;i>=1;i--) maxn( mxr[i], mxr[i+1] );
    for(int i=1;i<=n;i++)
        if(mxr[n-tol[0][i]] + tor[0][i] >= n) puts("Possible");
        else puts("Impossible");
    return 0;
}

Measured memory_bytes: 39296
var
    nm,i,x:longint;
    n:string;
begin
    readln(n);
    x:=pos(' ',n);
    delete(n,x,1);
    val(n,nm);
    for i:=1 to trunc(sqrt(nm)) do
    if(sqr(i)=nm)then
    begin
        writeln('Yes');
        exit;
    end;
    writeln('No');
end.

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    int n,sum=0;
    int l,r;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        sum+=r-l+1;
    }
    cout<<sum;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
#define F first
#define S second
typedef pair<int,int>pii;
typedef pair<int,pii>piii;
typedef pair<pii,pii>piiii;
const int INF=1e9+7;
const int dx[]={0,-1,0,1};
const int dy[]={-1,0,1,0};
int main(){
    int w,h;
    while(cin>>w>>h,w||h){
        set<piiii>W;

        for(int i=0;i<2*h-1;i++){
            for(int j=0;j<w-1+(i&1);j++){
                int v;cin>>v;
                if(v==0)continue;
                int y1,y2,x1,x2;
                if(i&1){
                    y1=i/2;y2=y1+1;x1=x2=j;
                }
                else{
                    y1=y2=i/2;x1=j;x2=x1+1;
                }
                W.insert(piiii(pii(y1,x1),pii(y2,x2)));
                W.insert(piiii(pii(y2,x2),pii(y1,x1)));
            }
        }

        int d[64][64];fill_n(*d,64*64,INF);
        queue<piii>Q;Q.push(piii(0,pii(0,0)));
        while(Q.size()){
            piii p=Q.front();Q.pop();
            int y=p.S.F,x=p.S.S,cnt=p.F;
            if(y<0||y>=h||x<0||x>=w)continue;
            if(d[y][x]!=INF)continue;
            d[y][x]=cnt;
            for(int i=0;i<4;i++){
                if(W.find(piiii(pii(y,x),pii(y+dy[i],x+dx[i])))!=W.end())continue;
                Q.push(piii(cnt+1,pii(y+dy[i],x+dx[i])));
            }
        }
        if(d[h-1][w-1]==INF)cout<<0<<endl;
        else cout<<d[h-1][w-1]+1<<endl;
    }
    return 0;
}

Measured memory_bytes: 1328
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;
typedef pair<P,int> PP;
int h,w,n,N=1<<17;
P a[100000];

class StarrySkyTree{
public:
  int Mi[333333],A[333333];
  void init(){fill(Mi,Mi+333333,0);fill(A,A+333333,0);}
  void add(int a,int b,int x,int k=0,int l=0,int r=N) {
    if(r<=a||b<=l) return;
    if(a<=l&&r<=b){
      A[k]+=x;
      while(k){
        k=(k-1)/2;
        Mi[k]=min(Mi[k*2+1]+A[k*2+1],Mi[k*2+2]+A[k*2+2]);
      }
      return;
    }
    add(a,b,x,k*2+1,l,(l+r)/2);
    add(a,b,x,k*2+2,(l+r)/2,r);
  }
  int getMin(int a,int b,int k=0,int l=0,int r=N) {
    if(r<=a||b<=l)return 1<<29;
    if(a<=l&&r<=b)return Mi[k]+A[k];
    int left=getMin(a,b,k*2+1,l,(l+r)/2),right=getMin(a,b,k*2+2,(l+r)/2,r);
    return min(left,right)+A[k];
  }
};

StarrySkyTree t[2];
vector<PP> v[2][111111];
bool calc(int m) {
  t[0].init(),t[1].init();
  for(int i=0; i<h+w+2; i++) v[0][i].clear(),v[1][i].clear();
  for(int i=0; i<n; i++) {
    int o=(a[i].F+a[i].S)%2;
    int d1=a[i].F+a[i].S-m;
    int d2=a[i].F+a[i].S+m;
    int x=w-(a[i].S-a[i].F+o)/2-1,y=abs(d1)%2;
    d1=max(0,d1),d2=min(h+w,d2);
    x-=(m+y)/2;
    v[0][d1].push_back(PP(P(max(0,x+y),min(h+w,x+m+1)),1));
    v[0][d2+1].push_back(PP(P(max(0,x+y),min(h+w,x+m+1)),-1));
    v[1][d1].push_back(PP(P(max(0,x),min(h+w,x+m+y)),1));
    v[1][d2+1].push_back(PP(P(max(0,x),min(h+w,x+m+y)),-1));
  }
  int z=1,l=w-1,r=w;
  bool f=0,f2=0;
  for(int i=0; i<h+w; i++) {
    for(int k=0; k<2; k++) {
      for(int j=0; j<v[k][i].size(); j++) t[k].add(v[k][i][j].F.F,v[k][i][j].F.S,v[k][i][j].S);
    }
    z=min(z,t[i%2].getMin(l,r));
    if(i>=w-1) f=1;
    if(i>=h-1) f2=1;
    l+=f?(i%2?1:0):(i%2?0:-1);
    r+=f2?(i%2?0:-1):(i%2?1:0);
  }
  return z;
}

int main() {
  cin >> h >> w >> n;
  for(int i=0; i<n; i++) cin >> a[i].F >> a[i].S;
  int l=-1,r=h+w;
  while(l+1<r) {
    int m=(l+r)/2;
    if(calc(m)) r=m;
    else l=m;
  }
  cout << r << endl;
  return 0;
}


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


/* エイリアス */
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define endl '\n'

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace


/* 関数マクロ */
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n, m) for (ll i = n; i <= m; ++i)
#define rep3(i, n, m) for (ll i = n; i >= m; --i)
#define all(v) v.begin(), v.end()
#define si(v) int(v.size())
#define UNIQUE(v) sort(all(v)), v.erase(unique(all(v)),v.end())


/* 定数 */
const ll mod = 1e9 + 7;
const ll infll = (1LL << 62) - 1;
const ll inf = (1LL << 30) - 1;


/* その他 */
template<class S, class T> inline bool chmax(S &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class S, class T> inline bool chmin(S &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;


signed main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  int a, b, c, d; cin >> a >> b >> c >> d;
  cout << (d == 1) << endl;
}

Measured memory_bytes: 3656
import sys

def f(p,q):
    num=0
    for ppp,qqq in xy:
        num=max(num,(p-ppp)**2+(q-qqq)**2)
    return num

inf=float("inf")
N=int(input())
xy=[list(map(int,input().split())) for i in range(N)]
ans=inf
if N==2:
    x=(xy[0][0]+xy[1][0])/2
    y=(xy[0][1]+xy[1][1])/2
    p,q=xy[0]
    num=(x-p)**2+(y-q)**2
    print(num**0.5)
    sys.exit()
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            p,q=xy[i]
            r,s=xy[j]
            v,w=xy[k]
            a=2*v-2*r
            b=2*w-2*s
            c=v**2+w**2-r**2-s**2
            d=2*p-2*r
            e=2*q-2*s
            f=p**2+q**2-r**2-s**2
            if a*e==b*d:
                num=0
            else:
                x=(c*e-b*f)/(a*e-b*d)
                y=(c*d-a*f)/(b*d-a*e)
                num=0
                for ppp,qqq in xy:
                    num=max(num,(x-ppp)**2+(y-qqq)**2)
                ans=min(ans,num)
            x,y=(p+r)/2,(q+s)/2
            num=0
            for ppp,qqq in xy:
                num=max(num,(x-ppp)**2+(y-qqq)**2)
            ans=min(ans,num)
            x,y=(p+v)/2,(q+w)/2
            num=0
            for ppp,qqq in xy:
                num=max(num,(x-ppp)**2+(y-qqq)**2)
            ans=min(ans,num)
            x,y=(r+v)/2,(s+w)/2
            num=0
            for ppp,qqq in xy:
                num=max(num,(x-ppp)**2+(y-qqq)**2)
            ans=min(ans,num)
print(ans**0.5)

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

namespace ABC_147A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c;

            var word = Console.ReadLine().Split(' ');

            a = int.Parse(word[0]);
            b = int.Parse(word[1]);
            c = int.Parse(word[2]);

            if (a+b+c >= 22)
            {
                Console.WriteLine("bust");
            }

            else
            {
                Console.WriteLine("win");
            }

            Console.ReadKey();
        }
    }
}


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

#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9, MOD = INF + 7;
 
/////////////////////////////////////////////////////////////////////
 
const int N = 1e5 + 5;

int PS[N][2];

int main() {
 
	sync;

	string s, t; cin >> s >> t;
	for (int i = 0; i < sz(s); i++) PS[i + 1][0] = PS[i][0] + s[i] - 'A' + 1;
	for (int i = 0; i < sz(t); i++) PS[i + 1][1] = PS[i][1] + t[i] - 'A' + 1;

	int q; cin >> q;
	while (q--) {
		int a, b, c, d; cin >> a >> b >> c >> d; a--, c--;
		int x = (PS[b][0] - PS[a][0]) % 3, y = (PS[d][1] - PS[c][1]) % 3;
		cout << (x == y ? "YES" : "NO") << endl;
	}

	return 0;
}


Measured memory_bytes: 1744
n,q,*t=map(int,open(0).read().split());s=[0];d=s*n;f=s+[1]*n;e=[[]for _ in d]
for a,b in zip(*[iter(t[:-q-q])]*2):e[a-1]+=b-1,;e[b-1]+=a-1,
for p,x in zip(*[iter(t[-q-q:])]*2):d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d)

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

const int INF=1e9+5;

int main(){
	int n;
	cin>>n;
	vector<int> h(n);
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	vector<int> dp(n,INF);
	dp[0]=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=(i+2);j++){
			if(j<n){
				dp[j]=min(dp[j],(dp[i]+abs(h[i]-h[j])));
			}	
		}
	}
	cout<<dp[n-1]<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    int N;
    string S;
    cin >> N >> S;

    vector<int> R(N, 0), G(N, 0), B(N, 0);
    for (int i = N - 1; i >= 0; i--) {
        if (i < N - 1) {
            R[i] = R[i + 1];
            G[i] = G[i + 1];
            B[i] = B[i + 1];
        }
        switch (S[i]) {
            case 'R':
                R[i]++;
                break;
            case 'G':
                G[i]++;
                break;
            case 'B':
                B[i]++;
                break;
        }
    }
    long long sum = 0;
    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            if (S[i] != 'R' && S[j] != 'R' && S[i] != S[j]) {
                sum += R[j + 1] - (j + j - i <= N - 1 && S[j + j - i] == 'R' ? 1 : 0);
            }
            if (S[i] != 'G' && S[j] != 'G' && S[i] != S[j]) {
                sum += G[j + 1] - (j + j - i <= N - 1 && S[j + j - i] == 'G' ? 1 : 0);
            }
            if (S[i] != 'B' && S[j] != 'B' && S[i] != S[j]) {
                sum += B[j + 1] - (j + j - i <= N - 1 && S[j + j - i] == 'B' ? 1 : 0);
            }
        }
    }

    cout << sum << endl;
    
    return 0;
}

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

using namespace std;

typedef long long  ll;

void Print(const vector<pair<string, int>> &c)
{
    for (auto it : c)
        cout << it.first << (it == c.back() ? '\n' : ' ');
}

bool isStable(int n, const vector<pair<string, int>> &c)
{
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            if (c[i].first[1] == c[j].first[1])
                if (c[i].second > c[j].second)
                    return false;
                else
                    break;
        }
    return true;
}

bool BubbleSort(int n, vector<pair<string, int>> c)
{
    for (int i = 0; i < n; ++i)
        for (int j = n - 1; i < j; --j)
            if (c[j].first[1]  < c[j - 1].first[1])
                swap(c[j], c[j - 1]);
    // Output
    Print(c);

    return isStable(n, c);
}

bool SelectionSort(int n, vector<pair<string, int>> c)
{
    for (int i = 0; i < n; ++i) {
        int min_idx = i;
        for (int j = i; j < n; ++j)
            if (c[j].first[1] < c[min_idx].first[1])
                min_idx = j;
        swap(c[i], c[min_idx]);
    }

    // Output
    Print(c);

    return isStable(n, c);
}

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

    int n;

    cin >> n;

    vector<pair<string, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }

    cout << (BubbleSort(n, a) ? "Stable\n" : "Not stable\n");
    cout << (SelectionSort(n, a) ? "Stable\n" : "Not stable\n");

    return 0;
}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
ll modpow(ll a, ll b){
 
    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b=b/2;
    }
    return ans;
}
 
 
int main(){
 
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n,m;
    cin>>n>>m;
 
    if(n == m) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
 
 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int dp[100000+9];
int main(){
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i = 0;i<n;i++)
        cin>>arr[i];
    dp[0] = 0;
    dp[1] = abs(arr[1] - arr[0]);
    for(int i =2 ; i<n;i++){
        dp[i] = min(abs(arr[i]-arr[i-1]) + dp[i-1] ,abs(arr[i] - arr[i-2]) + dp[i-2] );
    }
    printf("%d",dp[n-1]);
    return 0;
}

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

template <typename T>
void print(const T &v);

int main()
{
    char a;
    cin >> a;
    if (a - 'a' < 0)
    {
        cout << 'A' << endl;
    }
    else
    {
        cout << 'a' << endl;
    }
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

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

int main() {
    int n, x, y;
    int pmax = 0, pmin = 2e9, mmax = -2e9, mmin = 2e9;
    cin >> n;
    while (n--) {
        cin >> x >> y;
        chmax(pmax, x + y);
        chmin(pmin, x + y);
        chmax(mmax, x - y);
        chmin(mmin, x - y);
    }
    cout << max(pmax - pmin, mmax - mmin) << endl;

    return 0;
}

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

using namespace std;
using ll = long long;
int main()
{
    int n;
    cin >> n;
    
    string s;
    cin >> s;

    char prev = '\0';
    int cnt = 0;
    for (auto c: s)
    {
        if (c != prev)
        {
            cnt++;
            prev = c;
        }
    }
    
    cout << cnt;

    return 0;
}


Measured memory_bytes: 512
#include <iostream>

bool is_same_side(double x1, double x2, double y1, double y2, double px1, double py1, double px2, double py2)
{
        return ((px1 - x1)*(py1 - y2)-(px1 - x2)*(py1 - y1))*((px2 - x1)*(py2 - y2)-(px2 - x2)*(py2 - y1)) > 0;
}

int main()
{
        double x1, x2, x3, y1, y2, y3, xp, yp;
        while(std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> xp >> yp)
                if(     is_same_side(x1, x2, y1, y2, x3, y3, xp, yp) &&
                        is_same_side(x2, x3, y2, y3, x1, y1, xp, yp) &&
                        is_same_side(x3, x1, y3, y1, x2, y2, xp, yp))
                        std::cout << "YES" << std::endl;
                else
                        std::cout << "NO" << std::endl;
        return 0;
}

Measured memory_bytes: 1216
#include <stdio.h>

int main(){
	int N,i,j,k,l,f,Ans[101]={0},maxans;
	scanf("%d",&N);
	char ss[101];
	scanf("%s",ss);
	for(i=0;i<26;i++){
      f=0;
        for(j=0;j<N;j++){
			if(ss[j]=='a'+i && f==0){
              f=1;
              for(k=N-1;k>j;k--){
                if(ss[k]=='a'+i && f==1){
                  f=2;
                  for(l=j;l<=k;l++){
                    Ans[l]++;
                  }
                }
              }
            }
		}
	}

  maxans=Ans[0];
  for(i=1;i<N;i++){
    if(maxans<Ans[i])maxans=Ans[i];
  }
  printf("%d\n",maxans);
}

Measured memory_bytes: 128
n = int(input())
bb = list(map(int, input().split()))
ans = [0]*n
for k in range(n,0,-1):
  for i,num in enumerate(bb[::-1]):
    if num+i == k:
      ans[k-1] = bb.pop(-i-1)
      break
  else:
    print(-1)
    exit()
for i in ans:
  print(i)

Measured memory_bytes: 3064
package main

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

func main() {
	var m, k int
	fmt.Scan(&m)
	fmt.Scan(&k)

	n := int(math.Pow(2.0, float64(m+1)))
	max := int(math.Pow(2.0, float64(m))) - 1
	if max == 0 {
		if k == 0 {
			fmt.Println("0 0")
		} else {
			fmt.Println("-1")
		}
	} else if max == 1 {
		if k == 0 {
			fmt.Println("0 1 1 0")
		} else {
			fmt.Println("-1")
		}
	} else {
		if k <= max {
			ret := make([]string, n)
			if k == 0 {
				for i := 0; i <= max; i++ {
					ret[i*2] = strconv.Itoa(i)
					ret[i*2+1] = strconv.Itoa(i)
				}
			} else {
				ret[0] = "0"
				ret[1] = strconv.Itoa(k)
				ret[2] = "0"
				index := 3
				for i := 1; i <= max; i++ {
					if i == k {
						continue
					}
					ret[index] = strconv.Itoa(i)
					index++
				}
				ret[index] = strconv.Itoa(k)
				index++
				for i := max; i > 0; i-- {
					if i == k {
						continue
					}
					ret[index] = strconv.Itoa(i)
					index++
				}
			}
			r := strings.Join(ret, " ")
			fmt.Println(r)
		} else {
			fmt.Println("-1")
		}
	}
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;

struct vec
{
    long double x,y;
    bool operator ==(const vec &a) const{
        return x==a.x&&y==a.y;
    }
    bool operator <(const vec &a) const{
        if(a.x!=x) return x<a.x;
        return y<a.y;
    }
    vec operator +(const vec &a) const{
        return {x+a.x,y+a.y};
    }
    vec operator *(const long double &a) const{
        return {x*a,y*a};
    }
    vec operator -(const vec &a) const{
        return {x-a.x,y-a.y};
    }
    vec operator /(const long double &a) const{
        return {x/a,y/a};
    }
    long double len() const{
        return (x*x+y*y);
    }
    long double dot(const vec &a) const{
        return x*a.x+y*a.y;
    }
    long double crs(const vec &a) const{
        return x*a.y-y*a.x;
    }
    vec proj(const vec &a) const{
        return (a/a.len())*(*this).dot(a)/a.len();
    }
};


struct P
{
    int x,y;
    bool operator <(const P &a) const{
        //if(x!=a.x)
         return x>a.x;

    }
};


long long x,y,z,mod=998244353;
//vector<long long> v,v1;
vector<P> v[300110];
//vector<long long> v1;
int i,n,m,k,a,d,b,c,h,dx[10]={1,0,-1,0},dy[10]={0,1,0,-1};
int e;
int l[311111];

int o[311111];

int j[211111];
stack<int> s;
//set<int> s;
queue<int> q,q1;
P u[1],u1[3];
//char r[1],r1[3];
string r,r1;
//2147483647
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
map<int,int> p;

//v.resize(unique(v.begin(),v.end())-v.begin());

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//rng();

bool as(P a,P b)
{
    return a.y<b.y;
}


int main()
{
    scanf("%lld %lld %lld",&x,&y,&z);
    if((z-y)%2==0) printf("%lld",(z-y)/2);
        else printf("%lld",min(y+(z-y)/2,x-z+1+(z-y)/2));
}



Measured memory_bytes: 8448
from math import *
M,N=input().split(' ')
M=int(M)
N=int(N)

res=1
if M==N:
    res=factorial(M)
    res=res*res*2
elif M-N==1:
    res=factorial(N)
    res*=res*M
elif M-N==-1:
    res=factorial(M)
    res*=res*N
else:
    res=0

print(res%(10**9+7))


Measured memory_bytes: 5192
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, C, STC):
    tbl = [0] * (2*int(1e+5) + 2)
    ST = defaultdict(list)
    for s, t, c in STC:
        ST[c].append((s, t))
    for st in ST.values():
        st.sort()
        for i, (s, t) in enumerate(st):
            if i > 0 and st[i-1][1] == st[i][0]:
                tbl[2*(st[i][0])] += 1
                tbl[2*(st[i][1])] -= 1
            else:
                tbl[2*st[i][0]-1] += 1
                tbl[2*st[i][1]] -= 1

    for i in range(1, len(tbl)):
        tbl[i] += tbl[i-1]
    ans = max(tbl)
    return ans


def main():
    N, C = read_int_n()
    STC = [read_int_n() for _ in range(N)]
    print(slv(N, C, STC))


if __name__ == '__main__':
    main()


Measured memory_bytes: 39136
#include <stdio.h>

int main(void)
{
	int a, b, ans;
	scanf("%d %d", &a, &b);

	if (b != 1)
	{
		ans = 1;
		if (b - a >= 0)
		{
			if ((b - a) % (a - 1) == 0)
				ans += (b - a) / (a - 1);
			else
				ans += (b - a) / (a - 1) + 1;
		}
	}
	else
	{
		ans = 0;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
	string a;
	char map[4]={'K','U','P','C'};
	int cnt[4]={0};
	cin>>a;
	for(int i=0;i<a.size();i++)for(int j=0;j<4;j++)if(a[i]==map[j])cnt[j]++;
	int ans=10000;
	for(int i=0;i<4;i++)ans=min(ans,cnt[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;

// const
// 円周率
const double pi = M_PI;
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)

int main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n);
  priority_queue<ll> q;
  rep(i, n) {
    ll temp;
    cin >> temp;
    q.push(temp);
  }
  rep(i, m) {
    ll temp = q.top();
    q.pop();
    temp /= 2;
    if (temp > 0) q.push(temp);
    if (SIZE(q) == 0) break;
  }
  ll res=0;
  while (SIZE(q) > 0) {
    ll temp = q.top();
    q.pop();
    res += temp;
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 2168
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const int mod=1000000007;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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


// ll memo[2020][2020];
// int pascal_triangle(){
//   for(int i = 0; i < 2020; i++){
//     for(int j = 0; j < i+1; j++){
//       if(j == 0 || j == i) memo[i][j] = 1;
//       else{
// 	memo[i][j] = (memo[i-1][j-1]+memo[i-1][j]);
//       }
//     }
//   }
//   return 0;
// }


int factrial(int n){
  if(n == 0) return 1;
  return n*factrial(n-1);
}

// int comb(int n, int k){
//   return fact(n) / (fact(n-k)*fact(k));
// }


char grid[110][110];
bool h[110];
bool w[110];

int main(){
  int H,W;
  cin >> H >> W;
  rep(i,H){
    bool f = true;
    rep(j,W){
      cin >> grid[i][j]; 
      if(grid[i][j] == '#') f = false;
    }
    if(f) w[i] = true;
  }

  rep(j,W){
    bool f = true;
    rep(i,H){
      if(grid[i][j] == '#') f = false;
    }
    if(f) h[j] = true;
  }
  rep(i,H){
    if(w[i] == true) continue;
    rep(j,W){
      if(h[j] == true) continue;
      else cout << grid[i][j];
    }
    cout << endl;
  }
  
  
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i;
	int score, sum = 0;
	
	for (i = 0; i < 5; i++){
		scanf("%d", &score);
		if (score < 40) sum += 40;
		
		else sum += score;
	}
	
	printf("%d\n", sum / 5);
	
	return (0);
}

Measured memory_bytes: 600
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

using ll = long long;

int main() {
    int N;
    ll S;
    cin >> N >> S;

    ll X[N], P[N];
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> P[i];
    }

    queue<ll> neg, pos;
    // Sより前、後にある座標をそれぞれ両端から入れていく
    for (int i = 0; i < N && X[i] < S; ++i) {
        neg.push(P[i]);
    }
    for (int i = N - 1; i >= 0 && X[i] > S; --i) {
        pos.push(P[i]);
    }

    vector<ll> route;
    // 最適解における探索順を後ろから

    int l = 0, r = N - 1;
    while (true) {
        // もう一方しか残っていない場合
        if (neg.empty()) {
            for (; l <= r; --r) {
                route.push_back(r);
            }
            break;
        }
        if (pos.empty()) {
            for (; l <= r; ++l) {
                route.push_back(l);
            }
            break;
        }

        // 末端の人口を比較、少ない方が選ばれる
        if (neg.front() >= pos.front()) {
            route.push_back(r);
            --r;
            neg.front() += pos.front();
            pos.pop();
        } else {
            route.push_back(l);
            ++l;
            pos.front() += neg.front();
            neg.pop();
        }
    }

    ll ans = 0, now = S;
    while (!route.empty()) {
        ll id = route.back();
        route.pop_back();
        ans += abs(X[id] - now);
        now = X[id];
    }

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


Measured memory_bytes: 3836
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

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

#include <bits/stdc++.h>

using namespace std;

int choice[3004][3004];
int dp[3004][3004];

int main()
{
    string s,t;
    int i,j;
    cin>>s;
    cin>>t;
    int n=s.length();int m=t.length();
    dp[0][0]=0;
    if(s[0]==t[0])
    {dp[0][0]=1;choice[0][0]=2;}
    
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(i>=1)
            {
                dp[i][j]=dp[i-1][j];
                choice[i][j]=0;
            }
            if(j>=1&&dp[i][j-1]>dp[i][j])
            {
                dp[i][j]=dp[i][j-1];
                choice[i][j]=1;
            }
            if(i>=1&&j>=1&&s[i]==t[j])
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
                choice[i][j]=2;
            }
            else if(s[i]==t[j])
            {
                dp[i][j]=1;
                choice[i][j]=2;
            }
        }
    }
    
    string ans;
     i=n-1; j=m-1;
    while(i>=0&&j>=0)
    {
        if(choice[i][j]==0)
        {
            i--;
        }
        else if(choice[i][j]==1)
        {
            j--;
        }
        else if(choice[i][j]==2)
        {
            ans.push_back(s[i]);
            i--;j--;
        }
    }
    
    reverse(ans.begin(),ans.end());
    cout<<ans;
       

    return 0;
}


Measured memory_bytes: 74036
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>

using namespace std;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))

int main()
{
	int n, counter = 1;
	cin >> n;
	vector<int> h(n);
	rep(i, 0, n - 1)
	{
		cin >> h[i];
	}
	rep(i, 1, n - 1)
	{
		bool isAble = true;
		rep(j, 0, i - 1)
		{
			if (h[i] < h[j]) isAble = false;
		}
		if (isAble) ++counter;
	}
	cout << counter << endl;
}

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

int main() {
  int n, d[110], num[110] = {0}, res = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> d[i];
  }
  for (int i = 0; i < n; i++) {
    num[d[i]]++;
  }
  for (int i = 1; i <= 100; i++) {
    if (num[i]) {
      res++;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
(defun app ()
    (let ((n (read))
        (ans 0))

    (loop for i from 1 to n
        do (if (not (or (zerop (rem i 3)) (zerop (rem i 5))))
            (incf ans i)
            )
        
    )
       (format t "~D~%" ans)
    )
)

(app)

Measured memory_bytes: 24244
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int y,m,d;
  char a,b;
  cin >> y >> a >> m >> b >> d;
  if(m>4)
    cout << "TBD" << endl;
  else
    cout << "Heisei" << endl;
}

Measured memory_bytes: 3564
#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    ll ans = 0;
    repeat (i,n) {
        ans += a[i] / 2;
        a[i] %= 2;
        if (i+1 < n) {
            int d = min(a[i], a[i+1]);
            a[i  ] -= d;
            a[i+1] -= d;
            ans    += d;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

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

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
ll A,C,B,D;
ll gcd(ll a, ll b)
{
if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
return a * b / gcd(a, b);
}
void solve(){
    ll x = (A-1)/C;
    ll y = (A-1)/D;
    ll z = (A-1)/(lcm(C,D));
    ll ans1 = (A-1)-(x+y-z);
    ll X = B/C;
    ll Y = B/D;
    ll Z = B/(lcm(C,D));
    ll ans2 = B-(X+Y-Z);
    cout << ans2 - ans1 << endl;
}

int main(){
    cin >> A >> B >> C >> D;
    solve();
    return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.p, self.d = [-1] * n, [0] * n

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        if self.isSame(x, y):
            return
        x, y = self.find(x), self.find(y)

        if self.d[x] > self.d[y]:
            self.p[x] += self.p[y]
            self.p[y] = x
        else:
            self.p[y] += self.p[x]
            self.p[x] = y
            if self.d[x] == self.d[y]:
                self.d[y] += 1

    def size(self, x):
        return - self.p[self.find(x)]

    def numTree(self):
        return sum([1 for p in self.p if p < 0])


N, M = map(int, input().split())
F = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    F.unite(A - 1, B - 1)
print(max([abs(F.p[i]) for i in range(N) if F.p[i] < 0]))


Measured memory_bytes: 89368
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b)
  tree_index[b].append(a)

ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x

def dfs(cur, par):
  for child in tree_index[cur]:
    if child == par:
      continue
    ans[child] += ans[cur]
    dfs(child, cur)
dfs(0, -1)
print(*ans)

Measured memory_bytes: 230960
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n, w;
    cin>>n>>w;
    vector<LP> wv(n);
    cin>>wv;

    ll w0 = wv[0].fi;
    vector<vvl> dp(n + 1, vvl(n + 1, vl(300)));
    rep(i, n) rep(j, i + 1) rep(k, 300) {
        ll wr = wv[i].fi - w0;
        chmax(dp[i + 1][j][k], dp[i][j][k]);
        if (k + wr < 300) chmax(dp[i + 1][j + 1][k + wr], dp[i][j][k] + wv[i].se);
    }

    ll ans = 0;
    rep(i, n + 1) rep(j, 300) {
        if (w0 * i + j > w) continue;

        chmax(ans, dp[n][i][j]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 24832