akhauriyash/Code-Regression huggingface dataset:
/*
  AtCoder Regular Contest 100
  D - Equal Cut
*/

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<limits>
using namespace std;

unsigned int N;
long long A[200001];
unsigned int l, c, r;

long long getVal() {
  long long prev_diff, curr_diff;
  long long cval = A[c], eval = A[N];

  // left side
  prev_diff = numeric_limits<long long>::max();
  while (1) {
    curr_diff = abs((cval - A[l]) - (A[l] - 0));
    if (curr_diff > prev_diff) {
      --l;
      break;
    }

    prev_diff = curr_diff;
    ++l;
    if (l >= c) {
      --l;
      break;
    }
  }

  // right side
  prev_diff = numeric_limits<long long>::max();
  while(1) {
    curr_diff = abs((eval - A[r]) - (A[r] - cval));
    if (curr_diff > prev_diff) {
      --r;
      break;
    }

    prev_diff = curr_diff;
    ++r;
    if (r >= N) {
      --r;
      break;
    }
  }

  // calc val
  long long sum[4];
  sum[0] = A[l] - 0;
  sum[1] = cval - A[l];
  sum[2] = A[r] - cval;
  sum[3] = eval - A[r];
  long long maxval = *max_element(sum, sum+4);
  long long minval = *min_element(sum, sum+4);
  return maxval - minval;
}

int main() {
  scanf("%u", &N);

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

  long long minval = numeric_limits<long long>::max();
  for (l = 1, c = 2, r = 3; c <= N - 2; ++c) {
    if (r <= c) r = c + 1;   
    long long val = getVal();
    if (val < minval) minval = val;
  }

  printf("%llu\n", minval);
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <math.h>
using namespace std;

/*
すべての要素を１にしたいので，区間全体を１に広げる操作をする．
１が含まれる範囲Kの区間を重なるように実行すれば良い．つまり区間の数が答えである．
mこの区間で覆える範囲は，[1, (K-1)m+1] = N
*/
int main() {
  double N, K;
  cin >> N >> K;
  
  int ans = ceil((N-1) / (K-1));
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
int main(){
    int n,y;
    cin >> n >> y;
    for(int a=0;a<=n;a++){
        for(int b=0;b<=n;b++){
            if(a+b>n) break;
            int c=n-(a+b);
            if(10000*a+5000*b+1000*c==y){
                printf("%d %d %d\n",a,b,c);
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
#include <utility>
//#include <set>
//#include <map>
#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll n,m,r ;
	cin >> n >> m >> r ;
	vll town(r) ;
	for(auto &i:town) cin >> i ;
	sort(all(town)) ;
	vector<vector<pll>> g(n,vector<pll>(0)) ;
	for(int i=0;i<m;i++){
		ll a,b,c ;
		cin >> a >> b >> c ;
		a-- ; b-- ;
		g.at(a).emplace_back(b,c) ;
		g.at(b).emplace_back(a,c) ;
	}
	vvll d(n,vll(n,INF)) ;
	queue<ll> q ;
	for(int i=0;i<n;i++){
		d.at(i).at(i) = 0 ;
		q.push(i) ;
		ll p ;
		while(!q.empty()){
			p = q.front() ;
			q.pop() ;
			for(int j=0;j<g.at(p).size();j++){
				if(d.at(i).at(g.at(p).at(j).first)>d.at(i).at(p)+g.at(p).at(j).second){
					d.at(i).at(g.at(p).at(j).first) = d.at(i).at(p)+g.at(p).at(j).second ;
					q.push(g.at(p).at(j).first) ;
				}
			}
		}
	}
	ll ans = INF ;
	do{
		ll sub = 0 ;
		for(int i=0;i<r-1;i++) sub += d.at(town.at(i)-1).at(town.at(i+1)-1) ;
		ans = min(ans,sub) ;
	}while(next_permutation(all(town))) ;
	cout << ans << endl ;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
//#include "atcoder/all"
typedef long long int ll;
using namespace std;
// using namespace atcoder;
//#define mod 998244353
#define MAXM 100001
ll first[MAXM];
bool used[MAXM];
ll ans[MAXM];
int main() {
    ll n, x, m;
    cin >> n >> x >> m;
    int count = 1; //周期
    memset(used, false, sizeof(used));
    ll ret = 0;
    ans[0] = 0;
    while (!used[x]) {
        used[x] = true;
        first[x] = count;
        ret += x;
        ans[count] = ret;
        x = x * x % m;
        if (n == count) {
            cout << ret << endl;
            return 0;
        }
        count++;
    }
    ll syuuki = count - first[x];
    //cout << syuuki << endl;
    //cout << count << endl << ans[count] << endl;
    ll syuukisum = ans[count - 1] - ans[first[x] - 1];
    //cout << syuukisum << endl;
    ll tempret = ans[first[x] - 1] + ((n - first[x] + 1) / syuuki) * syuukisum;
    ll rest = (n - first[x] + 1) % syuuki;
    for (int i = 1; i <= rest; i++) {
        tempret += x;
        x = x * x % m;
    }
    cout << tempret << endl;
    return 0;
}

Measured memory_bytes: 4820
#include<queue>
#include<string>
#include<iostream>
using namespace std;
int main(){
    string cmd;
    priority_queue<int> Q;
    while(cin>>cmd&&cmd!="end"){
        if(cmd=="insert"){
            int m;
            cin>>m;
            Q.push(m);
        }
        else if (cmd=="extract"){
            int n=Q.top();
            Q.pop();
            cout<<n<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 6944
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;cin >> s;
  int n=s.size()+1;
  vector<long long> a(n);
  long long m=1e6;
  if(s[0]=='<'){
    a[0]=0;
  }
  if(s[n-2]=='>'){
    a[n-1]=0;
  }
  for(int i=0;i<n-1;i++){
    if(s[i]=='>'&&s[i+1]=='<'){
      a[i+1]=0;
    }
  }
  for(int i=0;i<n-1;i++){
    if(s[i]=='<'){
      a[i+1]=max(a[i+1],a[i]+1);
    }
  }
  for(int i=n-1;i>0;i--){
    if(s[i-1]=='>'){
      a[i-1]=max(a[i-1],a[i]+1);
    }
  }
  long long sum=0;
  for(int i=0;i<n;i++){
    sum+=a[i];
  }
  cout << sum << endl;
}

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>istream &operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
//template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> &p) {os << p.first << " " << p.second;return os;}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T, class U>bool chmin(T& a, U b) { if (a > b) { a = b; return true; }return false; }
template <class T, class U>bool chmax(T& a, U b) { if (a < b) { a = b; return true; }return false; }

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int R, G, B; cin >> R >> G >> B;
	int N; cin >> N;

	int L = 3 * 1010;
	vector<int>cnt(L);
	for (int r = 0; r*R <= N; r++) {
		for (int g = 0; r*R + g * G <= N; g++) {
			cnt[r*R + g * G]++;
		}
	}
	int ans = 0;
	for (int b = 0; b*B <= N; b++) {
		if (N - b*B >= 0) {
			ans += cnt[N - B*b];
		}
	}
	cout << ans << endl;

	return 0;
}


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

#define int long long int
#define MAX 1000001

int spf[MAX];
int f[MAX];

signed main()
{
    int i,j;
    spf[1]=1;
    for(i=2;i<MAX;i++)
    {
        if(spf[i]==0)
        {
            spf[i]=i;
            for(j=2*i;j<MAX;j+=i) if(spf[j]==0) spf[j]=i;
        }
    }

    int n;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++) cin>>a[i];

    int g=0;
    for(i=0;i<n;i++) g=__gcd(g,a[i]);

    if(g!=1) cout<<"not coprime\n";
    else
    {
        for(i=0;i<n;i++)
        {
            int t=a[i];
            while(t>1)
            {
                int c=spf[t];
                f[c]++;
                if(f[c]>1) {i=n;g=0;break;}
                while(t%c==0) {t/=c;}
            }
        }
        if(g==0) cout<<"setwise coprime\n";
        else cout<<"pairwise coprime\n";
    }

}


Measured memory_bytes: 19828
A,B=map(int,input().split())
N=len(str(bin(B)))-2
    
#ある偶数と次の奇数のxorは1
def calc(b):
    cnt=b//2
    if b%2==0:
        ans=cnt%2
        ans=ans^b
    else:
        ans=(cnt+1)%2
    return ans

print(calc(B) ^ calc(max(0,A-1)))

Measured memory_bytes: 38384
n = gets.to_i
songs = {}

n.times do
  s, t = gets.split
  t = t.to_i
  songs[s] = t
end

x = gets.chomp


songs.each_key do |name|
  if name == x
    songs.delete(name)
    break
  end
  songs.delete(name)
end

total = 0
songs.each_value do |v|
  total += v
end

puts total


Measured memory_bytes: 1788
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<complex>
#include<stack>
#include<cmath>
 
using namespace std;
 
#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

int main(){
	int a;
	double b,c;
	while(scanf("%d,%lf,%lf",&a,&b,&c)!=EOF){
		if(b/(c*c)>=25.0)printf("%d\n",a);
	}
	
}

Measured memory_bytes: 1212
#include<iostream>
#include<string.h>

using namespace std;

int a[12];
int n;

bool dfs(int i, int left, int right){
    if(i == 10){
        return true;
    }

    if(a[i] > left && dfs(i + 1, a[i], right)){
        return true;
    }
    if(a[i] > right && dfs(i + 1, left, a[i])){
        return true;
    }
    return false;
}

void solve(){
    for(int i = 0; i < 10; ++i){
        cin>>a[i];
    }

    if(dfs(0, 0, 0)){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

int main(){
    cin>>n;
    while(n--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 2988
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int key;
} Node;

typedef struct {
    Node *node;
    int size;
} Heap;

int getParent(int idx) {
    return idx / 2;
}

int getLeft(int idx) {
    return idx * 2;
}

int getRight(int idx) {
    return idx * 2 + 1;
}

bool isCorrectHeapIdx(int idx, int heapSize) {
    return 1 <= idx && idx <= heapSize;
}

bool initialize(Heap *heap, int size) {
    if((heap->node = malloc((size + 1) * sizeof(Node))) == NULL) {
        return false;
    }

    heap->size = size;
    return true;
}

void printHeap(Heap *heap) {
    for(int i = 1; i <= heap->size; i++) {
        printf("node %d: ", i);
        printf("key = %d, ", heap->node[i].key);

        int parent = getParent(i);
        int left = getLeft(i);
        int right = getRight(i);
        if(isCorrectHeapIdx(parent, heap->size)) {
            printf("parent key = %d, ", heap->node[parent].key);
        } if(isCorrectHeapIdx(left, heap->size)) {
            printf("left key = %d, ", heap->node[left].key);
        } if(isCorrectHeapIdx(right, heap->size)) {
            printf("right key = %d, ", heap->node[right].key);
        }
        puts("");
    }
}

void terminate(Heap *heap) {
    free(heap->node);
    heap->node = NULL;
    heap->size = 0;
}

int main(void) {
    int n;
    Heap heap;

    scanf("%d", &n);
    initialize(&heap, n);

    for(int i = 1; i <= n; i++) {
        scanf("%d", &heap.node[i].key);
    }

    printHeap(&heap);

    terminate(&heap);
    return 0;
}


Measured memory_bytes: 2048
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

const int MAX_A = 100000;

vector<int> A;

int calc_border(const ll N, const ll M) {
    auto cond = [](const int border, const vector<int> &as, const ll n, const ll m) {
        // printf("cand: %d\n", border);
        ll cnt = 0;
        for (auto &a : as) {
            auto p = lower_bound(as.begin(), as.end(), border - a);
            // printf("%d: %lld\n", a, n - (p - as.begin()));
            cnt += n - (p - as.begin());
        }
        return cnt >= m;
    };

    ll left = 0, right = 2 * MAX_A + 1, mid;
    while (right - left > 1) {
        mid = left + (right - left) / 2;
        if (cond(mid, A, N, M)) left = mid;
        else right = mid;
    }
    return left;
}

ll solve(const int border, const ll N, const ll M) {
    vector<ll> S(N + 1, 0);
    for (int i = 0; i < N; i++) {
        S[i + 1] = S[i] + A[i];
    }

    ll ans = 0; 
    ll cnt = 0;

    for (auto &a : A) {
        auto p = lower_bound(A.begin(), A.end(), border - a + 1);
        int s = p - A.begin();
        ans += S[N] - S[s];
        ans += a * (N - s);
        cnt += N - s;
    }

    if (cnt < M) {
        ans += border * (M - cnt);
    }

    return ans;
}

int main(void) {
    ll N, M;
    cin >> N >> M;

    A.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    int border = calc_border(N, M);
    // cout << border << endl;

    cout << solve(border, N, M) << endl;

    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long int
#define pb push_back
#define mk make_pair
#define flp(i, k, n) for(int i=k; i<n; i++)
#define rev(i, k) for(int i=k; i>=0; i--)
#define F first
#define S second
#define pi pair<int, int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int32_t main(void)
{
    int t=1;
    //cin>>t;
    while(t--)
    {
       int n, k;
       cin>>n>>k;
       int a[n+1];
       for(int i=1; i<=n; i++) cin>>a[i];
       int cur=1;
       bool vis[n+1];
       memset(vis, 0, sizeof(vis));
       while(!vis[cur])
       {
           vis[cur]=true;
           cur=a[cur];
       }
       memset(vis, 0, sizeof(vis));
       int ct=0;
       while(!vis[cur])
       {
           vis[cur]=true;
           cur=a[cur];
           ct++;
       }
       
       int start_pos=cur;
       cur=1;
       while(cur!=start_pos)
       {
           k--;
           cur=a[cur];
           if(k==0) break;
       }

       k=(k%ct);
       flp(i, 0, k)
        cur=a[cur];
      
       cout<<cur<<"\n";

    }

    return 0;
}

Measured memory_bytes: 5296
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

int a[2005][2005];
int s1[2005][2005];
int s2[2005][2005];

int calc1(int i, int j, int l) {
  return s1[i + l][j + l] - s1[i][j + l] - s1[i + l][j] + s1[i][j];
}

int calc2(int i, int j, int l) {
  return s2[i + l][j + l] - s2[i][j + l] - s2[i + l][j] + s2[i][j];
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  int n, d;
  cin >> n >> d;
  vvi c(d, vi(d));
  int sz = 1;
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    x %= d;
    y %= d;
    c[x][y]++;
  }
  for (int i = 0; i < d; ++i) for (int j = 0; j < d; ++j) {
    while (sz * sz < c[i][j]) ++sz;
  }
  vvi t(d, vi(d));
  int cnt2 = 0;
  for (int i = 0; i < d; ++i) for (int j = 0; j < d; ++j) {
    if (sz * (sz - 1) < c[i][j]) {
      t[i][j] = 2;
      ++cnt2;
    }
    else if ((sz - 1) * (sz - 1) < c[i][j]) t[i][j] = 1;
  }
  for (int i = 0; i < 2 * d; ++i) for (int j = 0; j < 2 * d; ++j) {
    a[i][j] = t[i % d][j % d];
  }
  for (int i = 0; i < 2 * d; ++i) for (int j = 0; j < 2 * d; ++j) {
    s1[i + 1][j + 1] = s1[i][j + 1] + s1[i + 1][j] - s1[i][j] + (int)(a[i][j] == 1);
    s2[i + 1][j + 1] = s2[i][j + 1] + s2[i + 1][j] - s2[i][j] + (int)(a[i][j] == 2);
  }
  int l = -1, r = d;
  while (r - l > 1) {
    int x = (l + r) / 2;
    bool ok = 0;
    for (int i = 0; i < d; ++i) for (int j = 0; j < d; ++j) {
      if (calc2(i, j, x + 1) == cnt2 && calc1(i + x + 1, j + x + 1, d - x - 1) == 0) {
        ok = 1;
        break;
      }
    }
    if (ok) r = x;
    else l = x;
  }
  cout << (sz - 1) * d + r << endl;
  return 0;
}

Measured memory_bytes: 55296
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef double db;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mp make_pair
#define case_for(n) for(int i = 1 ; i <= n ; i ++) { cout<<"Case "<<i<<": "<<endl; solve();}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll power(ll a, ll b, ll p) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % p; a = a * a % p, b /= 2; }return ans; }

db pi = 3.1415926535;

void solve()
{
	int n; cin >> n;
	//db j = 180 - ((n - 2) * 180 / n);
	//j /= 2;
	n *= 2;
	db res = 0;
	db j = (n - 2) * 180 / n - 90;
	for (int i = 0; i < n / 8; i++)
	{
		if (i % 2 == 0) res += cos(j / 180.0 * pi);
		else res += sin(j / 180.0 * pi);
	}
	res *= 2;
	printf("%.9f", res + 1);
	cout << endl;
}

int main()
{
	/*std::ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(0);*/
	//cout << tan(45 * pi / 180) << endl;
	//int t; cin >> t;
	/*while (t--)
	{
		solve();
	}
	//solve();*/
	int n; cin >> n;
	int s = n % 10;
	if (s == 2 || s == 4 || s == 5 || s == 7 || s == 9) cout << "hon";
	else if (s == 3) cout << "bon";
	else cout << "pon";
	return 0;
}
/*

*/

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int di2[] = {1, 1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1};
const int dj2[] = {1, -1, 1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main(){
  string s; cin >> s;
  int ans = 0;
  for(auto c : s) {
    if(c == '+') ++ans;
    else --ans;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3548
#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define td(v) v.begin(),v.end()
#define tdr(v) v.rbegin(),v.rend()
#define endl "\n"
#define Matrix vector<vector<int> >
using namespace std;
const int MOD = 1e9+7;
const int MOD2 = 1e9 + 9;
const int INF = 5e18;
 
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
 
 
inline long long mod(long long n, long long m){
    long long ret = n%m;
    if(ret < 0) ret += m;
    return ret;
}
 
int exp(int a, int b){
    int result = 1;
    while (b > 0){
        if (b & 1)
            result = result*a;
 
        b >>= 1;
        a = a*a;
    }
    return result;
}

void solve(){
    int n,m;
    cin>>n>>m;
    int sum=0;
    while(m--){
        int x;
        cin>>x;
        sum+=x;
    }
    if(sum>n){
        cout<<-1<<endl;
    }
    else{
        cout<<n-sum<<endl;
    }
}
signed main(){
    fastio; 
    // int x=0;
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define int long long
#define fi first
#define se second

const int maxn=3010;
int a[maxn],n,f[maxn][maxn];

int calc(int l,int r)
{
    if(l>r) return 0;
    if(f[l][r]!=-1) return f[l][r];
    int ret;
    if(((r+l)%2)!=n%2) ret=max(calc(l+1,r)+a[l],calc(l,r-1)+a[r]);
    else ret=min(calc(l+1,r)-a[l],calc(l,r-1)-a[r]);
    return f[l][r]=ret;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    forinc(i,1,n) cin>>a[i];
    memset(f,-1,sizeof f);
    cout<<calc(1,n);

}


Measured memory_bytes: 71168
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <fstream>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <algorithm>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define N 100010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mp make_pair
#define inf 1000000007
#define mod 1000000007
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define FOR(i, x, y) for (int i = x; i <= y; i++)
//#define tr(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

//using namespace __gnu_pbds;

using namespace std;

//template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int a, b;

int main()
{
	cin >> a >> b;
	
	cout << 2*b-a;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7,MAX = 1e5;

vector<string> M;

int h,w;
bool ans;
void serch(int x,int y)
{
	
	if(x>=h||y>=w)return ;
	if(M[x][y]=='.')return;
	M[x][y] = '.';
	if(x+1<h&&M[x+1][y]=='#')serch(x+1,y);
	else serch(x,y+1);
}

int main()
{
	
	cin >> h >> w;
	for(int i =0;i<h;i++)
	{
		string s;
		cin >> s;
		M.push_back(s);
	}
	serch(0,0);
	for(int i = 0;i<h;i++)
	{
		for(int j = 0;j<w;j++)
		if(M[i][j]=='#')ans = true;
	}
	if(ans)
	{
		cout<<"Impossible"<<endl;
	}
	else
	{
		cout<<"Possible"<<endl;
	}
	
	

	return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

ans = 0
for n in range(B, W):
	way = C(H-A-1+n, n)*C(W-n-1+A-1, A-1)%mod
	ans = (ans+way)%mod

print(ans)


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

// バブルソートを行う関数
int bubbleSort(int A[], int N) {
    // 交換回数
    int sw = 0;
    // 交換したかどうかのフラグ
    bool flag = true;
    
    for (int i = 0; flag; i++) {
        flag = false;
        for (int j = N - 1; j >= i + 1; j--) {
            if (A[j] < A[j - 1]) {
                // 隣接要素を交換する
                swap(A[j], A[j - 1]);
                flag = true;
                sw++;
            }
        }
    }
    return sw;
}

int main() {
    int A[100], N, sw;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];

    sw = bubbleSort(A, N);

    for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << sw << endl;

    return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int inf = 1 << 20;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
using namespace std;

int main()
{
    string s;
    cin >> s;
    int a=0,b=0,c=0;
    for(int i = 0; i < s.size(); i++){
        if(s[i]=='a') a++;
        if(s[i]=='b') b++;
        if(s[i]=='c') c++;
    }
    if((a == b && abs(c-a) == 1) || (a==c && abs(b-a) == 1) || (b==c && abs(a-b)==1) || (a==b && b == c)){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
#define MOD 1000000007
using namespace std;

int main() {
	string s;
	cin >> s;
	int count = 0;
	char key;
	REP(i, s.size() - 1) {
		key = s[i];
		if (key != s[i + 1]) {
			count++;
		}
		else {
			continue;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 10000;
int G[MAX][MAX], dp[MAX][MAX];
int main()
{
	int H, W;
	cin >> H >> W;
	int maxWidth = 0;
	bool flag = true;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
		{
			cin >> G[i][j];
			dp[i][j] = (G[i][j]) ? 0 : 1;
			if (dp[i][j] && flag)
			{
				maxWidth = 1;
				flag = false;
			}
		}
	for (int i = 1; i < H; i++)
		for (int j = 1; j < W; j++)
			if (!G[i][j])
			{
				dp[i][j] = min({ dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1] }) + 1;
				maxWidth = max(maxWidth, dp[i][j]);
			}
			else
				dp[i][j] = 0;
	cout << maxWidth * maxWidth << endl;
}


Measured memory_bytes: 29492
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <iomanip>
#include <cmath>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr ll INF = 1LL << 60;
constexpr ll MOD = 1e9 + 7;

int m[100010];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int a,b;cin>>a>>b;
    int c=a+b;
    if(c<10) cout << c << endl;
    else cout << "error" << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 100100;

int k;
string s;

void read() {
  cin >> s >> k;
}

char m(char c, int &k) {
  if (c == 'a')
    return c;
  int t = 'z' - c + 1;
  if (t <= k) {
    k -= t;
    return 'a';
  }
  return c;
}

void kill() {
  int n = s.length();
  for (int i = 0; i < n; ++i) {
    s[i] = m(s[i], k);
  }
  int t = (s[n - 1] - 'a' + k) % 26;
  s[n - 1] = 'a' + t;
  cout << s << endl;
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  read();
  kill();
}


Measured memory_bytes: 592
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<cmath>
#include<stack>
#include <algorithm>
#include <functional>
//#include<stdlib.h>
using namespace std;
int main() {
	char c[4],t=NULL;
	cin >> c;
	int s=0;
	for (int a = 1; a < 4; a++)
	{
		if (c[0] == c[a]) { s++; }
		else if (t == NULL) { t = c[a]; }
		else if (t != c[a]) { t = NULL; }
	}
	if (t != NULL && s == 1) { cout << "Yes"; }
	else { cout << "No"; }
	return 0;
}

Measured memory_bytes: 256
n,m,k = map(int,input().split())
a_li = [0] + list(map(int,input().split()))
b_li = [0] + list(map(int,input().split()))

for i in range(1,n+1):
    a_li[i] += a_li[i-1]
for i in range(1,m+1):
    b_li[i] += b_li[i-1]

ans = 0
b_cnt = m
for a_cnt in range(n+1):
    if a_li[a_cnt] > k:
        continue
    while a_li[a_cnt] + b_li[b_cnt] > k:
        b_cnt -= 1
    ans = max(ans,a_cnt+b_cnt)
print(ans)

Measured memory_bytes: 40068
#include<bits/stdc++.h>
#define ll long long
#define f(i,l,r) for(int i=l;i<r;i++)
using namespace std;
ll n,dp[100001][4],a[3][100001];
ll solve(int i,int flag)
{
 //  cout<<"HI3"; 
    if(dp[i][flag]!=-1)
    {
 //       cout<<"HII";
        return dp[i][flag];
    }
  //  if(i==0)
    //    return dp[i][flag]= max(a[0][i]+solve(i+1,0),max(a[1][i]+solve(i+1,1),a[2][i]+solve(i+1,2)));
    if(i==n)
    {
   //     cout<<"HII0"<<i<<n;
        return 0;
    }

    dp[i][flag]=0;
  //  cout<<"HII";
    if(flag!=0)
    {
        dp[i][flag]=max(dp[i][flag],a[0][i]+solve(i+1,0));
 //       cout<<"A";
    }
    if(flag!=1)
    {
        dp[i][flag]=max(dp[i][flag],a[1][i]+solve(i+1,1));
 //       cout<<"B";
    }
    if(flag!=2)
    {
        dp[i][flag]=max(dp[i][flag],a[2][i]+solve(i+1,2));
 //       cout<<"C";
    }
    return dp[i][flag];
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   // int n;
    cin>>n;
    f(i,0,100001)
        f(j,0,4)
            dp[i][j]=-1;
  //  ll ans=solve(0,3);
    f(i,0,n)
    {
        cin>>a[0][i]>>a[1][i]>>a[2][i];
     //   cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<"\n";
    }
    ll ans=solve(0,3);
    // f(i,0,n)
    // {
    //     f(j,0,4)
    //     cout<<dp[i][j]<<" ";
    //     cout<<"\n";
    // }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#define int long long
#define MOD 1000000007
using namespace std;

int n,bit[300000];

void add(int i,int x){
	while(i <= n){
		bit[i] += x;
		i += i & -i;
	}
}

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

signed main(){
	int r,fact[100001] = {0,1};
	for(int i = 2;i <= 100000;i++) fact[i] = fact[i - 1] * i % MOD;
	while(cin >> n,n){
		int num[100000];
		bit[0] = 0;
		for(int i = 0;i < n;i++) {
			num[i] = i + 1;
			bit[i + 1] = 0;
		}
		for(int i = 0;i < n;i++){
			add(i + 1,1);
		}
		cin >> r;
		for(int i = 0;i < r;i++){
			int a,b;
			cin >> a >> b; a--;b--;
			swap(num[a],num[b]);
		}
		int ans = 0;
		for(int i = 0;i < n;i++){
			ans = (ans + sum(num[i] - 1) * fact[n - i - 1] % MOD) % MOD;
			add(num[i],-1);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 5392
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

int main(int argc,char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    vector<ll> a(n),multi(n);
    int multi2=0,multi4=0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(a[i]%4==0){
            multi[i]=4;
            multi4++;
            multi2++;
        }else if(a[i]%2==0){
            multi[i]=2;
            multi2++;
        }else{
            multi[i]=0;
        }
    }

    int multi0=a.size()-multi2;

    if(multi0==0){
        cout << "Yes" << endl;
    }else{
        if(multi0<=multi4){
            cout << "Yes" << endl;
        }else{
            if(n%2==1 && multi0-multi4==1){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 4744
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define BIT(n) (1LL<<(n))
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPI(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
int main(void){
    // Your code here!
    /*
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    vector<int> v;
    v.push_back(a[0]);
    v.push_back(a[1]);
    v.push_back(a[2]);
    sort(ALL(v));
    
    int count;
    int max;
    int remain = (v[2]-v[1])+(v[2]-v[0]);
    if (remain%2==1){
        max = v[2]+1;
        count = 1;
        v[0] += 1;
    }
    else{
        max = v[2];
        count =0;
    }
    count += ((max-v[1])+(max-v[0]))/2;
    */
    int N;
    cin >> N;
    
    REP(i,N){
        ll a,b;
        cin >> a >> b;
        if (a < b){
            ll c = b;
            b = a;
            a = c;
        }
        
        ll product = a*b;
        ll sqrtpro = sqrt(product);
        int adj =0;
        
        if (sqrtpro*(sqrtpro+1) < product){
            if (sqrtpro+1 == a && sqrtpro == b){
                
                //cout << "a" << endl;
            }
            else {
                adj -=1;
                //cout << "b" << endl;
            }
            
        }
        else {
            if (sqrtpro==a && sqrtpro ==b){
                adj -=2;
                
                //cout << "t" << endl;
            }
            else if (sqrtpro*sqrtpro==product){
                adj -=3;
                //cout << "c" << endl;
            }
            else{
                adj-=2;
                //cout << "d" << endl;
            
            }
            
        }
        
        
    cout << sqrtpro*2+adj << endl;
    }
}
    
    


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

int main(){
    int x, y;
    cin >> x >> y;
    if (x < y){
        int tmp = x;
        x = y;
        y = tmp;
    }
    
    while(1){
        x = x % y;
        if (x == 0){
            cout << y << endl;
            break;
        }
        int tmp = x;
        x = y;
        y = tmp;
    }
}


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

long long int mod_pow(long long int x , int n , int mod){
	long long int ret=1;
	while(n>0){
		if(!(n%2==0)) ret=ret*x % mod;
		x = x * x % mod;
		n>>=1;
	}
	return ret;
}

int main(){
	const int mod=1000000007;
	int m , n;
	cin >> m >> n;
	cout << mod_pow(m , n , mod) << endl;
	return 0; 
}

Measured memory_bytes: 1156
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Math;

class program
{
    static public int mod = 1000000007;
    static void Main()
    {
        int n = rint();
        int[] a = inta();
        int[] num = new int[n];
        for(int i = 0; i < n-1; i++)
        {
            num[a[i] - 1]++;
        }
        for(int i = 0; i < n; i++)
        {
            WriteLine(num[i]);
        }
    }

    static int pow(int a, int b) { string binary = Convert.ToString(b, 2); int bileng = binary.Length; long a_power = a; long value = 1; for (int i = bileng - 1; i >= 0; i--) { if (binary[i] == '1') { value = value * a_power % mod; } a_power = a_power * a_power % mod; } return (int)value; }
    static string rstr() { return ReadLine(); }
    static int rint() { return int.Parse(ReadLine()); }
    static long rlong() { return long.Parse(ReadLine()); }
    static string[] stra() { return ReadLine().Split(' '); }
    static char[] chara() { string[] a = stra(); string b = ""; for (int i = 0; i < a.Length; i++) { b += a[i]; } return b.ToCharArray(); }
    static int[] inta() { string[] read_str_array = ReadLine().Split(' '); int[] return_int_array = new int[read_str_array.Length]; for (int countup_i = 0; countup_i < read_str_array.Length; countup_i++) { return_int_array[countup_i] = int.Parse(read_str_array[countup_i]); } return return_int_array; }
    static long[] longa() { string[] read_str_array = ReadLine().Split(' '); long[] return_long_array = new long[read_str_array.Length]; for (long countup_i = 0; countup_i < read_str_array.Length; countup_i++) { return_long_array[countup_i] = long.Parse(read_str_array[countup_i]); } return return_long_array; }
    static double[] doublea() { string[] read_str_array = ReadLine().Split(' '); double[] return_double_array = new double[read_str_array.Length]; for (long countup_i = 0; countup_i < read_str_array.Length; countup_i++) { return_double_array[countup_i] = double.Parse(read_str_array[countup_i]); } return return_double_array; }
    static long GCD(long a, long b) { if (a < b) { long temp = a; a = b; b = temp; } if (a % b == 0) { return b; } else { long temp = b; b = a % b; a = temp; return GCD(a, b); } }
    static long LCM(long a, long b) { return a * b / GCD(a, b); }
    static void WriteArray2(int[,] a, int b, int c) { for (int i = 0; i < b; i++) { for (int j = 0; j < c; j++) { if (j != 0) Write(" "); Write(a[i, j]); } WriteLine(); } }
    static void WriteArray(int[] a, int b) { for (int i = 0; i < b; i++) { Write(" "); Write(a[i]); } WriteLine(); }
}


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

int main(){
  int n,m;
  cin >> n >> m;
  vvi a(n+1);
  vi b(n+1,-1);
  vi c(n+1);
  int next=0;
  rep(i,m){
    int x,y;
    cin >> x >> y;
    if(b[x]==-1){
      if(b[y]==-1){
        a[next].push_back(x);a[next].push_back(y);
        b[x]=next;b[y]=next;
        c[next]+=2;
        next++;
        continue;
      }
      a[b[y]].push_back(x);b[x]=b[y];
      c[b[y]]++;
      continue;
    }
    if(b[y]==-1){
      a[b[x]].push_back(y);b[y]=b[x];
      c[b[x]]++;
      continue;
    }
    if(b[x]!=b[y]){
      int p=b[x],q=b[y];
      if(c[b[x]]>c[b[y]]){p=b[y];q=b[x];}
      for(int j : a[p]){
        a[q].push_back(j);
        b[j]=q;
        c[q]+=c[p];
      }
    }
  }
  int ans=1;
  rep(i,n+1){
    int x=a[i].size();
    ans=max(ans,x);
  }
  cout << ans;
  return 0;
}

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


int main() {
	int N;
	cin >> N;
	vector<long long> A(N);
	for (int n = 0;n<N;++n) {
		cin >> A[n];
	}
	vector<vector<long long>> DP(N, vector<long long >(2, -1e18));
	// i 番目までからj個を選んだ
	// jの範囲は i/2 -1 から(i+1)/2)
	for (int i = 1; i <= N; ++i) {
		for (int j = (i + 1) / 2; j >= (i-1) / 2; --j) {
			if (j < 0) {
				continue;
			}
			DP[j][0] = max(DP[j][0] ,DP[j][1]); 
			if (j>0) {
				if (-1e18 != DP[j - 1][0]) {
					DP[j][1] = DP[j - 1][0] + A[i-1];
				}
				else {
					DP[j][1] = A[i-1];
				}
			}
		}
	}
	long long ans = 0;
	ans = max(DP[N/2][0], DP[N/2][1]);
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 15640
#include <iostream>

using namespace std;

int main()
{
    int x1, x2, x3, x4, x5;
    cin>>x1>>x2>>x3>>x4>>x5;
    if(x1==0){
        cout<<"1";
    }
    if(x2==0){
        cout<<"2";
    }
    if(x3==0){
        cout<<"3";
    }
    if(x4==0){
        cout<<"4";
    }
    if(x5==0){
        cout<<"5";
    }
    return 0;
}

Measured memory_bytes: 3564
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, S, T, U, V, W, x, y, z;
long long max_value = INF, max_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

template <std::int_fast64_t Modulus> class modint {
	using u64 = std::int_fast64_t;
public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept {
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept {
		return modint(*this) /= rhs;
	}
	constexpr modint& operator+=(const modint rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint& operator-=(const modint rhs) noexcept {
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint& operator/=(modint rhs) noexcept {
		u64 exp = Modulus - 2;
		while (exp) {
			if (exp % 2) {
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
};
#pragma endregion

ll a[200000];
int main() {
	cin >> N;
	ll num;
	rep(i, N){
		cin >> num;
		a[i] = num - (i + 1);
	}
	sort(a, a+N);
	ll ans = 0;
	if(N%2 == 1){
		rep(i, N){
			ans += abs(a[i] - a[N/2]);
		}
	}else{
		ll median = (a[N/2] + a[N/2-1])/2;
		ll sum = 0;
		rep(i, N){
			sum += abs(a[i] - (median));
		}
		ans = sum;
		sum = 0;
		rep(i, N){
			sum += abs(a[i] - (median+1));
		}
		ans = min(ans, sum);
	}
	cout << ans;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const int inf = 1e5;
//typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int main(){
  int n;  cin >> n;
  vector<ll> a(n), b(n), h(n);
  ll si=0;
  rep(i,0,n){
    cin >> a[i] >> b[i] >> h[i];
    if(h[i]>0) si = i;
  }
  ll ans = 0;
  rep(i,0,101)rep(j,0,101){
    bool ok = true;
    ll H = h[si] + abs(a[si]-i) + abs(b[si]-j);
    rep(k,0,n){
      if(h[k]>0 &&(H != h[k]+abs(a[k]-i)+abs(b[k]-j))){
        ok = false;
        break;
      }
      if(h[k]==0 &&(H>abs(a[k]-i)+abs(b[k]-j))){
        ok = false;
        break;
      }
    }
    if(ok){
      cout << i << " " << j << " " <<  H << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
# Fast IO (only use in integer input)

# TLE

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

    N = int(input())
    Resident = []
    for i in range(N):
        x,y,p = map(int,input().split())
        Resident.append((x,y,p))

    def abs(N):
        if N >= 0:
            return N
        else:
            return -N

    minCost = [float("inf")] * (N+1)

    preCalRange = 1 << N

    horizontalLineDistance = []
    verticalLineDistance = []

    for i in range(preCalRange):
        railRoad = bin(i)[2:]
        railRoad = '0' * (N - len(railRoad)) + railRoad
        horizontalLineDistance.append([])
        verticalLineDistance.append([])
        for j in range(N):
            horizontalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            verticalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            for k in range(N):
                if railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < horizontalLineDistance[i][j]:
                    horizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])
                if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:
                    verticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])

    power2 = [1]
    for i in range(N):
        power2.append(power2[-1] * 2)
    loopCount = power2[N]
    for i in range(loopCount):
        numNewRailroad = bin(i)[2:].count('1')
        j = i
        while j >= 0:
            j &= i
            goodList1 = horizontalLineDistance[j]
            goodList2 = verticalLineDistance[i - j]
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * min(goodList1[k], goodList2[k])
            if minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()

Measured memory_bytes: 91676