akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD=1e9+7;

//const int MOD=998244353;
const double PI=3.14159265359;

vector<int> v2, vtemp;

long long getCt(int l, int r){
    if(l==r){
        return (v2[r]-(l?v2[l-1]:0)>=0?1:0);
    }
    
    long long ans=getCt(l, (l+r)/2)+ getCt((l+r)/2+1, r);
    copy(v2.begin()+(l+r)/2+1, v2.begin()+r+1, vtemp.begin());
    
    int rlen=r-(l+r)/2;
    
    sort(vtemp.begin(), vtemp.begin()+rlen);
    
    
    
    
    for(int i=l; i<=(l+r)/2; i++){
        int val=i?v2[i-1]:0;
        
        auto it=lower_bound(vtemp.begin(), vtemp.begin()+rlen, val);
        int pos=it-vtemp.begin();
        ans+=rlen-pos;
    }
    
    return ans;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    long long n;
    cin>>n;
    
    vector<int> v(n);
    for(auto &i:v) cin>>i;
    
    v2.resize(n);
    vtemp.resize(n);
    
    /*
    if(n==1){
        cout<<v[0];
        return 0;
    }
    */
    
    long long goalCt=(n*n/4) + (bool)(n*n%4);
    
    //cout<<goalCt<<endl;
    
    int l=0, r=1e9+1;
    
    while(l<r){
        int mid=(l+r)/2;
        for(int i=0; i<n; i++){
            v2[i]=v[i]>=mid+1?1:-1;
        }
        for(int i=1; i<n; i++){
            v2[i]=v2[i-1]+v2[i];
        }
        //cout<<getCt(0,n-1)<<" "<<;
        
        
        if(getCt(0,n-1)>=goalCt) l=mid+1;
        else r=mid;
    }
    
    cout<<l;
    
    
    
    return 0;
}

Measured memory_bytes: 1408
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
rev_a = list(reversed(a))
rev_b = list(reversed(b))
stock = 0
getted = 0
 
for i in range(n):
  #Be careful that rev_a size is N+1 !
  if stock > 0:
    if rev_a[i] >= stock:
      getted += stock
      rev_a[i] = rev_a[i] - stock
    else:
      getted += rev_a[i]
      rev_a[i] = 0
    stock = 0
  
  if rev_a[i] >= rev_b[i]:
    getted += rev_b[i]
  else:
    getted += rev_a[i]
    stock = rev_b[i] - rev_a[i]
  
  if i == n-1:
    if rev_a[i+1] >= stock:
      getted += stock
    else:
      getted += rev_a[i+1]
 
print(getted)

Measured memory_bytes: 19004
#include <stdio.h>
#include<math.h>
#include<stdlib.h>

int main(void){
	int a,b,c;
	scanf("%d%d", &a, &b);
	if (a%b == 0) {
		c = a / b;
	}
	else {
		c = a / b;
		c++;
	}
	printf("%d\n",c);

	return 0;
}

Measured memory_bytes: 128
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = [[INF] * N for _ in range(N)]
    for _ in range(M):
        s, t, c = il()
        graph[s][t] = c
    for n in range(N):
        graph[n][n] = 0

    # ワーシャルフロイド
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if graph[i][k] == INF or graph[k][j] == INF: continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    # 回答
    ret = []
    for n in range(N):
        if graph[n][n] < 0:
            # 自身までの距離が負の場合
            # (負の閉路が存在する場合）
            print('NEGATIVE CYCLE')
            exit()
        tmp = []
        for d in graph[n]:
            if d == INF:
                tmp.append('INF')
            else:
                tmp.append(d)
        ret.append(tmp)
    else:
        for r in ret:
            print(*r)


if __name__ == '__main__':
    main()



Measured memory_bytes: 7868
ARR = [
    [84, 97, 66],
    [79, 89, 11],
    [61, 59, 7],
]


N = 7
BRR = [
    89,
    7,
    87,
    79,
    24,
    84,
    30,
]


ARR = []

for i in range(3):
    ARR.append(list(map(int,input().split())))

N = int(input())

BRR = []

for i in range(N):
    BRR.append(int(input()))


def calculagte(arr, n, brr):
    status = [
        [False, False, False],
        [False, False, False],
        [False, False, False]
    ]

    for h in range(3):
        for w in range(3):
            for i in range(n):
                if arr[h][w] == brr[i]:
                    status[h][w] = True

    isOk = False

    if status[0][0] and status[0][1] and status[0][2]:
        isOk = True

    if status[1][0] and status[1][1] and status[1][2]:
        isOk = True

    if status[2][0] and status[2][1] and status[2][2]:
        isOk = True


    if status[0][0] and status[1][0] and status[2][0]:
        isOk = True

    if status[0][1] and status[1][1] and status[2][1]:
        isOk = True

    if status[0][2] and status[1][2] and status[2][2]:
        isOk = True

    if status[0][0] and status[1][1] and status[2][2]:
        isOk = True

    if status[2][0] and status[1][1] and status[0][2]:
        isOk  = True

    if isOk:
        print("Yes")
    else:
        print("No")

calculagte(ARR, N, BRR)


Measured memory_bytes: 9296
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define REP(i,n) for(int i = 0;i < n; i++)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e18;

#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
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;}
template<typename T>vector<T>
make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}

int isPrime[111111];

signed main(){
	IOS();
	vector<int>ans;
	rep(i,2,111111)isPrime[i] = true;
	rep(i,2,111111)if(isPrime[i]){
		for(int j = i+i;j < 111111;j+=i){
			isPrime[j] = 0;
		}
	}
	vector<int>prime;
	rep(i,0,111111){
		if(isPrime[i])prime.push_back(i);
	}
	while(1){
		int N,P;
		cin>>N>>P;
		if(N==-1&&P==-1)break;
		vector<int>tmp;
		vector<int>used(111111,0);
		int s = upper_bound(all(prime),N)-prime.begin();
		rep(i,s,s+100){
			if(i>=prime.size())break;
			rep(j,s,100+s){
				if(j>=prime.size())break;
				if(i>j)continue;
				if(i==j){
					if(used[i])continue;
					used[i] = 1;
				}
				tmp.push_back(prime[i]+prime[j]);
			}
		}
		sort(all(tmp));
		ans.push_back(tmp[P-1]);
	}
	for(auto e:ans){
		cout<<e<<endl;
	}
}


Measured memory_bytes: 5096
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



struct Point{
	ll x,y;
};

ll W,H,V,T,X,Y,P,Q,R;
ll num_row,num_col,center_row,center_col;
Point center;

Point calc_loc(ll row,ll col){

	Point point;
	point.x = col*W;

	if(abs(center_col-col)%2 == 0){
		point.x += P;
	}else{
		point.x += (W-P);
	}

	point.y = (row*H);

	if(abs(center_row-row)%2 == 0){
		point.y += Q;
	}else{
		point.y += (H-Q);
	}
	return point;
}


ll calc_dist(Point a,Point b){
	return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

ll calc_left(ll row){

	ll left = 0,right = center_col,m = (left+right)/2;
	ll res = BIG_NUM;

	Point point;

	while(left <= right){
		point = calc_loc(row,m);

		if(calc_dist(point,center) <= R*R){
			res = m;
			right = m-1;
		}else{
			left = m+1;
		}
		m = (left+right)/2;
	}

	return res;
}

ll calc_right(ll row){

	ll left = center_col,right = num_col-1,m = (left+right)/2;
	ll res = num_row;

	Point point;

	while(left <= right){
		point = calc_loc(row,m);

		if(calc_dist(point,center) > R*R){
			res = m;
			right = m-1; //より左へ
		}else{
			left = m+1; //右へ
		}
		m = (left+right)/2;
	}

	return res;
}

int main(){

	scanf("%lld %lld %lld %lld %lld %lld %lld %lld",&W,&H,&V,&T,&X,&Y,&P,&Q);

	R = V*T;

	num_row = 2*(R/H+2)+1;
	num_col = 2*(R/W+2)+1;

	center.x = W*(R/W+2)+X;
	center.y = H*(R/H+2)+Y;

	center_row = (R/H+2);
	center_col = (R/W+2);

	ll ans = 0,left,right;

	for(ll row = num_row-1; row >= 0; row--){
		left = calc_left(row);
		if(left == BIG_NUM)continue;
		right = calc_right(row);
		ans += (right-left);
	}

	printf("%lld\n",ans);

	return 0;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100005
#define INF 1000000005
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 1000000007;
vector<int> to[N];
vector<int>black(N,INF);
vector<int>white(N,INF);
int main(){
    int n;
    cin>>n;
    REP(i,n-1){
        int x,y;
        cin>>x>>y;
        x--;y--;
        to[x].push_back(y);
        to[y].push_back(x);
    }
    black[0]=0;
    white[n-1]=0;
    queue<int> q;
	q.push(0);
    while(SZ(q)){
        int a=q.front();
        q.pop();
        for(auto s:to[a]){
            //fanction
            if(black[s]==INF){
                black[s]=black[a]+1;
                q.push(s);
            }
        }
    }
    q.push(n-1);
    while(SZ(q)){
        int a=q.front();
        q.pop();
        for(auto s:to[a]){
            //fanction
            if(white[s]==INF){
                white[s]=white[a]+1;
                q.push(s);
            }
        }
    }
    int tmp=0;
    REP(i,n){
        if(white[i]>=black[i])tmp++;
        else tmp--;
        //cout<<black[i]<<" "<<white[i]<<endl;
    }
    if(tmp>0)OUT("Fennec");
    else OUT("Snuke");
    return 0;
}

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;

int w, h, x, y;

void dfs(vector<vector<int>> &map, int x, int y)
{
  // 今いるところを0に置き換える
  map[x][y] = 0;

  for (int dx = -1; dx <= 1; dx++)
  {
    for (int dy = -1; dy <= 1; dy++)
    {
      // x方向にdx移動したものをnx，y方向にdy移動したものをnyとおく
      int nx = x + dx, ny = y + dy;

      // nxとnyが地図の範囲内かどうかとmap[nx][ny]が陸なのかを判定
      if (0 <= nx && nx < h && 0 <= ny && ny < w && map[nx][ny] == 1)
        dfs(map, nx, ny);
    }
  }
  return;
}

void solve(vector<vector<int>> &map)
{
  int ans = 0;
  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      if (map[i][j] == 1)
      {
        dfs(map, i, j);
        ans++;
      }
    }
  }
  cout << ans << endl;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  while (1)
  {
    cin >> w >> h;
    if (w == 0 && h == 0)
      break;
    vector<vector<int>> map(h, vector<int>(w));
    for (int i = 0; i < h; i++)
    {
      for (int j = 0; j < w; j++)
      {
        cin >> map[i][j];
      }
    }
    solve(map);
  }
  return 0;
}



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


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

int main() {
    int k;
    cin >> k;
    int ans = 0;
    for(int a = 1; a <= k; ++a) {
        for(int b = 1; b <= k; ++b) {
            for(int c = 1; c <= k; ++c) {
                int temp = gcd(b,c);
                temp = gcd(temp, a);
                ans += temp;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
	string s;
  	cin >> s;
  	if (s.size() == 3)
      reverse(s.begin(), s.end());
  	cout << s << endl;
    return 0;
}



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

int main(int argc, char *argv[])
{
  char c;
  cin >> c;
  if (c == 'A') {
    c = 'T';
  } else if (c == 'T') {
    c = 'A';
  } else if (c == 'C') {
    c = 'G';
  } else if (c == 'G') {
    c = 'C';
  }

  cout << c << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define MOD2 (998244353)
#define MOD3 (1000000009)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("ride.in");ofstream coutt("ride.out");
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}
int ceil(const int &a,const int &b){return (a+b-1)/b;}
////Read:
//Use __builtin_popcountll for ll;
//Check corner cases, n==1;
//
////Some function:
//__builtin_popcountll(), 

int n,m,dp[2005][2005][2][2];
vi a,b;

int f(int i,int j,bool x,bool y){
    if(i>=n || j>=m)return x&&y;
    int &ans=dp[i][j][x][y];
    if(ans!=-1)return ans;
    ans=0;
    if(a[i]==b[j])ans=(ans+f(i+1,j+1,1,1))%MOD;
    if(x && y)ans=(ans+f(i+1,j+1,1,1))%MOD;
    if(x)ans=(ans+f(i,j+1,1,0))%MOD;
    if(y)ans=(ans+f(i+1,j,0,1))%MOD;
    return ans;
}

signed main(){
    FASTER;
    memset(dp,-1,sizeof dp);
    cin>>n>>m;
    a=vi(n);
    b=vi(m);
    cin>>a>>b;
    cout<<f(0,0,1,1);    
}

Measured memory_bytes: 129508
/*
 Educational Dp Contest Atcoder
 
 */

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}

const ll MOD =998244353;
const ll hell=1000000007;
const int INF=1e16;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

const int N=100005;

int dp[N][101],pre[N][101];
int a[101];
void solve()
{
    
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[0][0]=1;
    for(int j=0;j<=k;j++)
        pre[0][j]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            // dp[i][j]=dp[i-1][j-0]+dp[i-1][j-1]....dp[i-1][j-a[i]];
            int in=max((int)0,j-a[i]);
            dp[i][j]=(pre[i-1][j]-(in>0?pre[i-1][in-1]:0)+hell)%hell;
        }
        pre[i][0]=dp[i][0];
        for(int j=1;j<=k;j++)
            pre[i][j]=(dp[i][j]+pre[i][j-1])%hell;
    }
    cout<<dp[n][k]<<endl;
}

int32_t main()
{
    
    IOS;
    //FILE *fin = freopen("in","r",stdin);
    //FILE *fout = freopen("out","w",stdout);
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3200
// atcoder/abc082/A/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int a, b;
  while (cin >> a >> b) {
    cout << (a + b + 1) / 2 << endl;
  }

  return 0;
}


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

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#define mp make_pair
#define pb push_back
#define pll pair<LL,LL>
#define pii pair<int,int>
#define y second
#define x first
#define LL long long 
#define sqr(x) ((x)*(x))
#define pi acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
LL cnt[1000005];
void solve(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        for(int j = i;j<=n;j+=i)cnt[j]++;
    }
    LL ans=0;
    for(int i = 1;i<=n-1;i++){
        ans+=cnt[n-i];
    }
    printf("%lld\n",ans);
}
int main(){
    int t=1;
    int T=1;
    while(t--){
        solve();
    }
}
/*
100
5
5 4
4 2
4 2 3
5 4 2 3 1
*/


Measured memory_bytes: 11532
import sys
input = sys.stdin.readline

class DSU:
    __slots__ = ["_n", "parent_or_size"]
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return x
        if self.parent_or_size[x] > self.parent_or_size[y]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        stack = []
        while self.parent_or_size[a] >= 0:
            stack.append(a)
            a = self.parent_or_size[a]
        for i in stack:
            self.parent_or_size[i] = a
        return a

def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)

main()

Measured memory_bytes: 75972
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int S1 = A * B, S2 = C * D;
    cout << (S1 > S2 ? S1 : S2) << endl;
    return 0;
}


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

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n-1);i>=0;i--)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

vector<ll> a;
ll t[10];

void f(ll x, int c, int d) {
    if (d != 0) a.pb(x);
    if (c == 10) return;
    if (d != 0) f((d-1)*t[c] + x, c+1, d-1);
    f(d*t[c] + x, c+1, d);
    if (d != 9) f((d+1)*t[c] + x, c+1, d+1);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    ll v = 1;
    forsn(i, 1, 10) v *= 10, t[i] = v;
    forn(i, 10) f(i, 1, i);
    sort(all(a));
    int k; cin >> k;
    cout << a[k-1] << endl;
    return 0;
}


Measured memory_bytes: 2420
N, X, Y = map(int, input().split())
X -= 1
Y -= 1     #１のところを０にするなど一つずつずらす
 
def dist(a, b):
  return min(abs(b-a), abs(X-a) + 1 + abs(b-Y), abs(Y-a) + 1 + abs(b-X))
   #＋１は間の一つ繋がっている分
 
ANS = [0] * N    #0がN個のリストを作成。一つ目はk=0の時（同じところ）
for i in range(N):
  for j in range(i):
    ANS[dist(i, j)] += 1  #0にずらしたことで０から始まるi,jに対応できている
        
    #i,jの最小値のindexに１ずつ足していく
        
for a in ANS[1:]:  #indexが１以降（数字の差が１以上）のものを一つづつ出力
  print(a)

#コメントの前のスペースは半角で描く

Measured memory_bytes: 47580
from math import *
n,d=map(int,input().split())
k=d*d
ans=0
for i in range(n):
    x,y=map(int,input().split())
    x1=x**2
    y1=y**2
    m=x1+y1
    if m<=k:
        ans=ans+1
print(ans)

Measured memory_bytes: 9144
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef vector<int> vec;
//配列の添字ズレに注意
//=に注意

int main(){
  long n,k; cin>>n>>k;
  long a[n];
  rep(i,n)cin>>a[i];
  
  for(int i=k;i<n;i++){
    if(a[i-k]<a[i])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  
  
  }

  //string s; cin>>s;
  //cout<< <<endl;
}


Measured memory_bytes: 5168
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
using namespace std;
int n,t,sum;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t;
		sum+=t-1;
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int a[3];
    scanf("%d %d %d",&a[0],&a[1],&a[2]);

    for(int i=0;i<2;i++){
        for(int j=2;j>i;j--){
            if(a[j-1]>a[j]){
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
    if(a[0]==5&&a[1]==5&&a[2]==7){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 1588
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string>

using namespace std;
int main() {
	vector <int>a(5);
	vector <int>b(5);
	vector <int>c(5);
	int k=0;
	cin >> a[0]>>a[1]>>a[2]>>a[3]>>a[4];
	for (int i=0;i<5;i++)
	b[i] = a[i] % 10;
	if (b[0]==0 and b[1] == 0 and b[2] == 0 and b[3] == 0 and b[4] == 0  )
		cout << a[0] + a[1] + a[2] + a[3] + a[4];

	else
	{
		k = b[0];
		if (b[1] < k and b[1]!=0)
			k = b[1];
		if (b[2] < k and b[2] != 0)
			k = b[2];

		if (b[3] < k and b[3] != 0)
			k = b[3];
		if (b[4] < k and b[4] != 0)
			k = b[4];

		for (int i = 0; i < 5; i++)
		{
			if (b[i] != 0)
				c[i] = a[i] - b[i] + 10;
			else
				c[i] = a[i];
		}
		cout << c[0] + c[1] + c[2] + c[3] + c[4] - 10 + k;
	}
	

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int id = -1;
		int max = -1;
		for(int i=0; i<n; i++)
		{
			int a = scanner.nextInt();
			int v = scanner.nextInt();
			if(v > max)
			{
				id = a;
				max = v;
			}
			else if(v == max)
			{
				if(a < id)
				{
					id = a;
				}
			}
		}
		System.out.println(id + " " + max);
	}
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    int n;
    cin >> n;
    vector<int64_t> a(n);
    rep(i,0,n) cin >> a[i];
    int64_t maxi=0,ans=0;
    rep(i,0,n){
        if(a[i]<=maxi+1){
            maxi=max(maxi,a[i]);
            continue;
        }
        //print(a[i]);
        //print(maxi);
        int64_t lb=-1,ub=inf;
        while(ub-lb>1){
            int64_t m=(lb+ub)/2;
            if(a[i]-m*(maxi+1)<=2*(maxi+1)) ub=m;
            else lb=m;
        }
        //print(ub);
        a[i]-=ub*(maxi+1);
        ans+=ub;
        //cerr << a << endl;
        if(a[i]>maxi+1){
            a[i]=1;
            ++ans;
        }
        //cerr << a << endl;
        //print(ans);
        /*
        while(a[i]>maxi+1){
            if(a[i]-maxi-1<=maxi+1) a[i]=1;
            else a[i]-=maxi+1;
            ++ans;
            //cerr << a << endl;
        }
        */
        maxi=max(maxi,a[i]);
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n) cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    int ans = 0;
    rep(i, n)
    {
        int l = 0, r = n;
        if (a[l] >= b[i])
            continue;
        while (r - l > 1)
        {
            int m = (r + l) / 2;
            if (a[m] < b[i])
                l = m;
            else
                r = m;
        }
        int x = l + 1;
        l = 0, r = n - 1;
        if (c[l] > b[i])
        {
            ans += x * n;
            continue;
        }
        if (c[r] <= b[i])
            continue;
        while (r - l > 1)
        {
            int m = (r + l) / 2;
            if (b[i] < c[m])
                r = m;
            else
                l = m;
        }
        ans += x * (n - r);
    }
    cout << ans << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;
typedef tuple<ll,ll,ll> tl;
typedef tuple<ll,ll,ll,ll> ql;

#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define ROF(i, a, b) for(ll i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define FILL(x, n, v) fill(x, x+n, v);
#define ALL(x) x.begin(), x.end()
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front

#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';

const ll MOD = 1e9+7; //998244353
const ll MAXN = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);

int main(){
    FAST
    ll n, k;
    cin >> n >> k;
    ll total=0;
    FOR(i,k,n+1){
        ll minn = (i*(i+1))/2 - i;
        ll maxx = minn + i*(n-i+1);
        total += maxx - minn + 1;
        total %= MOD;
    }
    cout << total;
}

Measured memory_bytes: 3648
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int INF = 1e9;
inline int read(){
	int X = 0,w = 0 ;
	char ch = 0;
	while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
	while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
	return w ? -X : X;
}
int nxt[1000005];
int nxt2[1000005];
int n;
char s[1000005];
void get_nxt()
{
	nxt[0]=-1;
	for(int i=0,j=-1;i<n;i++)
	{
		while(~j and s[i]!=s[j])
		{
			j=nxt[j];
		}
		nxt[i+1]=++j;
	}
}
void get_nxt2()
{
	nxt2[0]=-1;
	for(int i=0,j=-1;i<n;i++)
	{
		while(~j and s[i]!=s[j])
		{
			j=nxt2[j];
		}
		nxt2[i+1]=++j;
	}
}
int main() 
{
	scanf("%s",s);
	n=strlen(s);
	get_nxt();
	reverse(s,s+n);
	get_nxt2();
	if(n%(n-nxt[n])!=0 or nxt[n]==0)
	{
		cout<<1<<endl<<1;
		return 0;
	}
	if(n-nxt[n]==1)
	{
		cout<<n<<endl<<1<<endl;
		return 0;
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		int a=i;
		int b=n-i;
		if((a%(a-nxt[a])!=0 or nxt[a]==0) and (b%(b-nxt2[b])!=0 or nxt2[b]==0))
		{
			ans++;
		}
	}
	cout<<2<<endl;
	cout<<ans;
    return 0;
}

Measured memory_bytes: 7936
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
*/

ll n,m,ans=0;
V<ll> v[100010];

void init(){
	cin>>n>>m;
	rep(i,n){
		ll x;
		cin>>x;
		v[x%m].push_back(x);
	}
	rep(i,m)sort(v[i].begin(),v[i].end());
}

int main(void){
	init();
	reg(i,0,m/2){
		if(i==0 || i*2==m){
			ans+=v[i].size()/2;
			continue;
		}
		if(v[i].size()>v[m-i].size()){
			// v[m-i]を全てv[i]とマッチ
			ll match=0;
			for(int j=0; j<v[i].size()-1 && v[i].size()-v[m-i].size()>=match+2; j++){
				if(v[i][j]==v[i][j+1]){
					match+=2;
					j++;
				}
			}
			ans+=match/2 + v[m-i].size();
		}else{
			// v[i]を全てv[m-i]とマッチ
			ll match=0;
			for(int j=0; j<v[m-i].size()-1 && v[m-i].size()-v[i].size()>=match+2; j++){
				if(v[m-i][j]==v[m-i][j+1]){
					match+=2;
					j++;
				}
			}
			ans+=match/2 + v[i].size();
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

ll N, K;
double ans=0.0, P[200000]={0.0}, S[200001]={0.0};

signed main(){
    cin >> N >> K;
    for(int i=0;i<N;i++) {
        cin >> P[i];
        S[i+1] = S[i] + P[i];
    }
    for(int i=0;i<=N-K;i++) {
        ans = max(ans, S[i+K]-S[i]);
    }
    cout << fixed << setprecision(10) << (ans+K)/2.0 << endl;
    return 0;
}

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

using namespace std;

using ll = long long;

#define ALL(A) A.begin(),A.end()

void ALLIN1_NUMBER(vector<ll>& V)
{
    for(auto& x : V)
    {
        cin >> x;
    }
}

template<class T>
void OUT0(T N)
{
    cout << N << endl;
}

static const double pi = acos(-1.0);

double Cos(double D)
{
    return cos(pi/180 * D);
}

ll happiness_counter()
{
    string s;
    cin >> s;

    ll N = s.size();

    ll ret = 0;

    for(ll i=0;i<N;i++)
    {
        if(s[i]=='L')
        {
            if(i>0)
            {
                if(s[i-1]=='L')
                {
                    ret++;
                }
            }
        }
        else
        {
            if(i<N-1)
            {
                if(s[i+1]=='R')
                {
                    ret++;
                }
            }
        }
    }
    return ret;
}

ll Ans(ll happiness_number, ll N, ll K)
{
    return min(N-1,happiness_number + 2 * K);
}

int main()
{
    ll N,K;
    cin >> N >> K;

    OUT0(Ans(happiness_counter(),N,K));

    return 0;
}

Measured memory_bytes: 512
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n+1];
        for(int i = 0; i < k; i++){
            int d = scanner.nextInt();
            for(int j = 0; j < d; j++){
                int num = scanner.nextInt();
                a[num]++;
            }
        }
        int count = 0;
        for(int i = 1; i <= n; i++){
            if(a[i] == 0){count++;}
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 46404
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    ll xp = x % d;
    ll xm = xp - d;
    ll num = (x - xp) / d;
    if(num > k) ans = x - d * k;
    else if((num - k) % 2 == 0) ans = xp;
    else ans = abs(xm);
    cout << ans << endl; 
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

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

using namespace std;

int main(void) {
    int x;
    int d500, s500, d5;

    cin >> x;

    d500 = x / 500;
    s500 = x % 500;
    d5 = s500 / 5;

    cout << (d500 * 1000) + (d5 * 5) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
using P=pair<int,int>;

int i,j,k;

struct UnionFind {  // The range of node number is from 0 to n-1
    //'rank[x]' is a rank of the union find tree the root of which is x.
    //'parents[x]' is the parent of x
    vector<int> rank, parents;
    // constructor
    UnionFind() {}
    UnionFind(int n) {  // make n trees.
        rank.resize(n, 0);
        parents.resize(n, 0);
        for (int i = 0; i < n; i++) {
            makeTree(i);
        }
    }
    // make a union find tree
    void makeTree(int x) {
        parents[x] = x;  // the parent of x is x
        rank[x] = 0;
    }
 
    // check whether the root of x is the same as that of y
    bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }
 
    // unite two tree
    bool unite(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y) return false;
        if (rank[x] > rank[y]) {
            parents[y] = x;
        } else {
            parents[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
        return true;
    }

    // travel the parents of tree recursivily to find root
    int findRoot(int x) {
        if (x != parents[x]) {
            parents[x] = findRoot(parents[x]);  // change the x's parent to the root of tree.
        }
        return parents[x];
    }
};

int main(){
    int n,k,l;cin>>n>>k>>l;//n:都市数　k:道路数　l:鉄道数
    
    UnionFind road(n),train(n);


    for(i=0;i<k;i++){//roadについて
        int p,q;cin>>p>>q;
        p--;q--;
        road.unite(p,q);
    }

    for(i=0;i<l;i++){//trainについて
        int r,s;cin>>r>>s;
        r--;s--;
        train.unite(r,s);
    }

    map<P,int> relate;
    P p;
    for(i=0;i<n;i++){
        relate[make_pair(road.findRoot(i),train.findRoot(i))]++;
    }

    for(i=0;i<n;i++){
        cout<<relate[make_pair(road.findRoot(i),train.findRoot(i))]<<" ";
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 15104
#include"bits/stdc++.h"
using namespace std;

int main() {
    int A, B, K;
    cin >> A >> B >> K;
    for (int i = A; i < min(A + K, B + 1); i++) {
        cout << i << endl;
    }

    for (int i = max(B - K + 1, A + K); i <= B; i++) {
        cout << i << endl;
    }
}

Measured memory_bytes: 256
n,m=map(int,input().split( ))
p=list(map(int,input().split( )))
q=set()
for iddd in range(m):
    i,j=map(int,input().split( ))
    if p[i-1]>p[j-1] :
        q.add(j)
    elif p[j-1]>p[i-1] :
        q.add(i)
    elif p[j-1]==p[i-1]:
        q.add(i)
        q.add(j)
print(n-len(q))


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

int main(){
    int64_t a,b,c,k,ret=0; cin >> a >> b >> c >> k;
    if(a<=k){
        ret+=a; k-=a;
    }
    else{
        ret=k; k=0;
    }
    if(k>0){
        k = max(k-b,(int64_t)0);
    }
    if(k>0){
        ret = ret - k;
    }
    cout << ret << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s, n) for(int i = s; i < (int)(n); i++)
#define co(x) cout<<x<<endl
#define SQvec(i,j) vector<vector<int>> data(i, vector<int>(j))
#define mod 1000000000+7
typedef long long int lint;

int main() {
  lint N,K,ans;
  cin >> N >> K;
  if((N-K)%(K-1) == 0){ans = (N-K)/(K-1) + 1;}
  else{ans = (N-K)/(K-1) + 2;}
  co(ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii  pair<int,int>
#define vpii vector<pii>
#define vll  vector<ll>
#define vi  vector<int>
#define pb push_back
#define f  first
#define s  second

int main() {

  char a,b;
    cin>>a>>b;
    
    if(a>b)
      cout<<">";
    else
       if(a==b)
         cout<<"=";
         else
         cout<<"<";
   
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
const int INF_INT = 2147483647;
const long long INF_LONG = 9223372036854775807;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
     
int main() {
  int n, m;  cin >> n >> m;
  vector<int> c(m);
  rep (i, m) cin >> c[i];
  vector<vector<int>> dp(m, vector<int>(n+1));

  for (int i=1; i * c[0] < n+1; ++i) dp[0][c[0]*i] = i;
  rep (i, m-1) for (int j=0; j<n+1; ++j) {
    if (j < c[i+1]) dp[i+1][j] = dp[i][j];
    else {
      dp[i+1][j] = min({dp[i][j], dp[i][j - c[i+1]] + 1, dp[i+1][j - c[i+1]] + 1});
    }
  }

  int ans=INF_INT;
  rep (i, m) if (dp[i][n] < ans) ans = dp[i][n];

  cout << ans <<endl;
}


Measured memory_bytes: 7072
#include <iostream>
#include <cmath>
#include <climits>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>

using namespace std;
using ll = long long;

template<typename T> void print(T t) { cout << t << endl; }

int main() {
	int N, c;
	string s, t;
	cin >> N >> s >> t;

	for (c = N; c > 0; c--) {
		bool ok = true;
		for (int i = 0; i < c; i++) {
			if (s[N - c + i] != t[i]) {
				ok = false;
				break;
			}
		}
		if (ok)break;
	}

	print(2 * N - c);
}

Measured memory_bytes: 3520
#include <stdio.h>
#include <iostream>
using namespace std;

void trace(int A[], int N) {
	for (int i = 0; i < N; i++) {
		if (i > 0)
			printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
}

void insertionSort(int A[], int N) {
	int i, j, v;
	for (i = 1; i < N; i++) {
		v = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
		trace(A, N);
	}
}

int main() {
	int N, i;
	int A[100];

	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}
	trace(A, N);
	insertionSort(A, N);

	return 0;
}


Measured memory_bytes: 3192
n = int(input())
l=[]
for i in range(n):
    l.append(input())
from collections import Counter
S=Counter(l)#カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})

mn = max(S.values())
for letter, count in sorted(S.most_common()):
    if(count==mn):
        print(letter)


Measured memory_bytes: 47660
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define eps 1e-10
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

char s[maxn];
ll n,p,cnt[maxn],ans,nw,base=1;

int main()
{
	n=read(); p=read(); scanf("%s",s+1);
	if(p==2||p==5)
	{
		for(int i=1;i<=n;i++) if((s[i]-'0')%p==0) ans+=i;
		cout<<ans<<endl; return 0;
	}
	for(int i=n;i>=1;i--)
	{
		nw=((s[i]-'0')*base+nw)%p; base=(base*10)%p;
		ans+=cnt[nw]; cnt[nw]++;
	}
	cout<<ans+cnt[0]<<endl;
	return 0;
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1)
    printEoln();
  if (suc == 2)
    printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

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

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

template <class T> T Sq(const T &t) { return t * t; }

const int mod = 1e9 + 7;

signed main() {
  string a, b, c;
  std::cin >> a >> b >> c;
  if (a.back() == b[0] && b.back() == c[0])
    std::cout << "YES" << std::endl;
  else
    std::cout << "NO" << std::endl;
}


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

constexpr int MAXN = 2e5 + 5;

using namespace std;
using A = int [MAXN];


template <typename T>
inline void read(T &x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int n, m;
pair<int, int> bomb[MAXN];
vector< pair<int, int> > G[MAXN];
vector<int> res;
A diff, fa, cnt, sz, pos;

inline int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void dfs(int cur, int fa, int id) {
    sz[cur] = diff[cur];
    for (auto &e : G[cur]) {
        int to = e.first, toId = e.second;
        if (to == fa) continue;
        dfs(to, cur, toId);
        sz[cur] += sz[to];
    }
    if (sz[cur] & 1) res.emplace_back(id);
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        read(bomb[i].first), read(bomb[i].second);
    sort(bomb + 1, bomb + n + 1);
    for (int i = 1; i <= n + 1; i++) //差分
        pos[i] = bomb[i].first, diff[i] = bomb[i].second ^ bomb[i - 1].second, fa[i] = i;
    for (int i = 1, l, r; i <= m; i++) {
        read(l), read(r);
        l = lower_bound(pos + 1, pos + n + 1, l) - pos;
        r = upper_bound(pos + 1, pos + n + 1, r) - pos;
        int r1 = find(l), r2 = find(r);
        if (r1 == r2) continue;
        fa[r1] = r2;
        G[l].emplace_back(make_pair(r, i));
        G[r].emplace_back(make_pair(l, i));
    }
    for (int i = 1; i <= n + 1; i++)
        if (diff[i]) cnt[find(i)]++;
    for (int i = 1; i <= n + 1; i++) 
        if (find(i) == i && (cnt[i] & 1)) {
            cout << -1 << endl;
            return 0;
        }
    for (int i = 1; i <= n + 1; i++)
        if (find(i) == i) dfs(i, 0, 0);
    printf("%d\n", res.size());
    sort(res.begin(), res.end());
    for (auto &i : res) printf("%d ", i);
    return 0;
}

Measured memory_bytes: 12668
#include <iostream>
#include <stdio.h>

using namespace std;

int n, i, a, ans;
char s[105];

int main()
{
    cin >> n >> s;
    for (i=0; i<n; i++)
    {
        if (s[i] == 'D')
        {
            a--;
        }
        else if(s[i] == 'I')
        {
            a++;
        }
        if (a >= ans)
        {
            ans = a;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); bool s=false; if(c=='-'){s=true;c=getchar();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); int s=0; if(c=='-'){s=1;c=getchar();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar(); while(c==' '||c=='\n') c=getchar(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar(); } *s='\0'; return len; }

void rsorta_d32(void *base, const int count, const int size, int32_t (*find)(const void*)){
	char (*a)[size] = (char(*)[size])base;
	char (*b)[size] = (char(*)[size])malloc(count*size);
	int c[0x100];
	for(int k=0; k<4; k++){
		memset(c, 0, sizeof(c)); for(int i=0; i<count; i++){ c[(find(a[i])>>(k<<3))&0xFF]++; } for(int i=1; i<0x100; i++) c[i]+=c[i-1]; for(int i=count-1; i>=0; i--){ int to=--c[(find(a[i])>>(k<<3))&0xFF]; memcpy(b[to], a[i], size); }{char(*t)[size]=a; a=b; b=t;}
	}
	free(b);
}

int find(const void *a){
	return *(int*)a;
}

int n;
int a[100001];
int b[100001];
int c[100001];
int d[200001];

void inc(int i){
	i+=100000;
	while(i<=200000){
		d[i]++;
		i+=i&-i;
	}
}

int sum(int i){
	i+=100000;
	int s=0;
	while(i>0){
		s+=d[i];
		i-=i&-i;
	}
	return s;
}

long f(int x){
	for(int i=1; i<=n; i++){
		c[i]=c[i-1]+(a[i]<=x?1:-1);
	}
	memset(d, 0, sizeof(d));
	long ans=0;
	inc(c[0]);
	for(int i=1; i<=n; i++){
		ans+=sum(c[i]-1);
		inc(c[i]);
	}
	return ans;
}

int main(void){
	n=nextint();
	for(int i=1; i<=n; i++){
		a[i]=b[i]=nextint();
	}
	rsorta_d32(b+1, n, sizeof(int), find);
	int kl=1, kr=n;
	long m = (long)n*(n+1)/4+1;
	//printf("%d\n", m);
	while(kl<=kr){
		int km=(kl+kr)/2;
		//printf("%d %d %ld\n", km, b[km], f(b[km]));
		if(f(b[km])>=m) kr=km-1; else kl=km+1;
	}
	//printf("%d %d %ld\n", kl, b[kl], f(b[kl]));
	printf("%d\n", b[kl]);
}


Measured memory_bytes: 3556